Operatori derivati

Premessa

Portale di appartenenza: Basi di dati.

Cosa troverai in questa nota:

• Come effettuare la composizione di operatori relazionali.
• Glu operatori derivati dell’algebra relazionale.

Prerequisiti: per comprendere pienamente il contenuto di questa nota, oltre le conoscenze minime che do per scontato che tu sappia già, ti consiglio di aver letto in precedenza queste altre note:

• Operatori di base.

Buona lettura! ☝️🤓

---

L’algebra relazionale è composizionale, ovvero si possono costruire espressioni di algebra relazionale componendo insieme gli operatori relazionali.

Definizione: composizione di operatori relazionali

Dati due operatori relazionali $\star$ e $\diamond$, la loro composizione consiste nel dare come argomento dell’operatore $\diamond$ il risultato dell’operazione di $\star$:

$$\diamond (\star )$$

Esempio di composizione di due operatori

Supponiamo di avere una relazione $\text{STUDENTI(Nome, Matricola, Corso, Etaˋ)}$ e vogliamo estrarre i nomi degli studenti di $\text{Informatica}$ con meno di $25$ anni. Possiamo comporre due operatori:

1. Selezione per scegliere solo gli studenti di $\text{Informatica}$ con meno di $25$ anni:

$${\sigma }_{\text{Corso = "Informatica"}\wedge \text{Etaˋ < 25}}(\text{STUDENTI})$$

2. Proiezione per estrarre i nomi dal risultato della selezione:

$${\pi }_{\text{Nome}}$$

La composizione dei due operatori è la seguente:

$${\pi }_{\text{Nome}}({\sigma }_{\text{Corso = "Informatica"}\wedge \text{Etaˋ < 25}}(\text{STUDENTI}))$$

1 - Notazione ad albero sintattico

Per visualizzare comodamente un’interrogazione composta da una composizione di operatori si usa la notazione ad albero sintattico.

Notazione ad albero sintattico di una composizione

Una composizione di operatori relazionali si può rappresentare attraverso un albero sintattico, ossia un albero utile a visualizzare la sequenza di esecuzione delle operazioni. In particolare:

• Sul nodo radice viene posto l’operatore eseguito per ultimo nella composizione.
• Sui nodi foglia vengono poste le relazioni di partenza su cui vengono eseguite le operazioni.
• Ogni nodo interno rappresenta uno degli operatori della composizione applicato al risultato del nodo figlio.

Esempio di notazione ad albero sintattico di una composizione

Supponiamo di avere una relazione $\text{STUDENTI}(\underline{\text{Matricola}}\text{, Nome, Corso, Etaˋ)}$ e $\text{CORSI}(\underline{\text{CodiceCorso}},\text{NomeCorso},\text{Durata})$ e vogliamo estrarre le matricole degli studenti che sono iscritti a un corso con una durata superiore a $50$ ore. Possiamo comporre gli operatori così:

1. Selezione per scegliere i corsi con durata maggiore di $50$ ore:

$${\sigma }_{\text{CORSI.Durata < 50}}$$

2. Theta-join tra $\text{STUDENTI}$ e il risultato della selezione dei corsi, utilizzando l’attributo $\text{Corso}$ in $\text{STUDENTI}$ e il campo $\underline{\text{CodiceCorso}}$ in $\text{CORSI}$:

$${\bowtie }_{\text{STUDENTI.Corso = CORSI.}\underline{\text{CodiceCorso}}}$$

3. Proiezione per estrarre le matricole dal risultato del theta-join:

$${\pi }_{\text{STUDENTI.}\underline{\text{Matricola}}}$$

La composizione degli operatori è quindi la seguente:

$${\pi }_{\text{STUDENTI.}\underline{\text{Matricola}}}(\text{STUDENTI}{\bowtie }_{\text{STUDENTI.Corso = CORSI.}\underline{\text{CodiceCorso}}}({\sigma }_{\text{CORSI.Durata < 50}}(\text{CORSI})))$$

Questa interrogazione si può tradurre nel seguente albero sintattico:

1: |latex
  \text{CORSI}
|

1 -> 2
2: |latex
  \sigma_{\text{CORSI.Durata} < 50}
|

3: |latex
  \text{STUDENTI}
|

2 -> 4
3 -> 4
4: |latex
  \pi_{\text{STUDENTI.Corso}} = \text{CORSI.}\underline{\text{CodiceCorso}}
|

4 -> 5
5: |latex
  \pi_{\text{STUDENTI.}\underline{\text{Matricola}}}
|

2 - Definizione di operatore derivato

Definizione: operatore derivato

Nell’algebra relazionale, un operatore derivato è un operatore relazionale ottenuto dalla composizione di altri operatori di base o anch’essi derivati.

Gli operatori derivati più comuni sono:

• Theta-join ${\bowtie }_{\Theta }$: per mettere in correlazione dati estratti da due o più relazioni diverse.
• Equi-join ${\bowtie }_{{\Theta }_e}$: un caso particolare del theta-join in cui i confronti del predicato è composto solo da uguaglianze
• Natural-join $\bowtie$: per generalizzare il concetto di equi-join operando una proiezione sull’unione degli attributi di entrambe le relazioni coinvolte.
• Semi-join ${⋉}_{\Theta }$: per limitare il theta-join allo schema di una delle due relazioni.
• Outer-join: effettuano un natural-join su cui però non vengono perse tutte le tuple dangling di una delle due relazioni o di entrambe e sono distinti in tre tipi:
  • Left-join $⊐\bowtie$: mantiene le tuple dangling della relazione a sinistra dell’operatore.
  • Right-join $\bowtie ⊏$: mantiene le tuple dangling della relazione a destra dell’operatore.
  • Full-join $⊐\bowtie ⊏$: mantiene le tuple dangling di entrambe le relazioni.
• Quoziente $÷$: per cercare i valori di un attributo che sono associati a ogni valore di altri attributi.

3 - Theta-join ${\bowtie }_{\Theta }$

Definizione: theta-join

Date due relazioni $R(A)$ ed $S(B)$ (con $A\cap B=\varnothing$) e un predicato $\Theta$ tra due attributi $A_i\in A$ e $B_j\in B$, il theta-join $R{\bowtie }_{\Theta }S$ è un operatore relazionale definito come la selezione di alcuni record secondo il predicato $\Theta$ nel prodotto cartesiano $R\times S$:

$$R{\bowtie }_{\Theta }S={\sigma }_{\Theta }(R\times S)$$

Viene usato per mettere in correlazione dati estratti da due o più relazioni diverse.

Esempio di theta-join

Sia $R$ la seguente relazione.

$\text{Matricola}$	$\text{Studente}$
$1203842$	$\text{Rossi Mario}$
$1298314$	$\text{Verdi Luigi}$
$3209239$	$\text{Neri Marco}$

Sia $S$ la seguente relazione.

$\text{Codice}$	$\text{Altezza}$
$1298314$	$\text{170cm}$
$1902359$	$\text{165cm}$
$1203842$	$\text{185cm}$

La relazione ottenuta dall’operazione $R{\bowtie }_{Matricola=\text{Codice}}S$ è la seguente.

$\text{Matricola}$	$\text{Studente}$	$\text{Codice}$	$\text{Altezza}$
$1203842$	$\text{Rossi Mario}$	$1203842$	$\text{185cm}$
$1298314$	$\text{Verdi Luigi}$	$1298314$	$\text{170cm}$

Osservazione: cardinalità del risultato del theta-join

Date due relazioni $R(A)$ ed $S(B)$ (con $A\cap B=\varnothing$) e un predicato $\Theta$ tra un attributo $A_i\in A$ e un attributo $B_j\in B$, la cardinalità della relazione prodotta dall’operazione di theta-join $R{\bowtie }_{\Theta }S$ è:

$$0\le |R{\bowtie }_{\Theta }S|\le |R\times S|$$

Sappiamo però che $|R\times S|\le |R|\cdot |S|$, quindi:

$$0\le |R{\bowtie }_{\Theta }S|\le |R|\cdot |S|$$

Osservazione: theta-join con schemi non disgiunti

Nel caso in cui ci sia bisogno di effettuare un’operazione di theta-join tra due relazioni $R$ ed $S$ con schemi $A$ e $B$ non disgiunti (cioè $A\cap B\ne \varnothing$), si può usare l’operazione di ridenominazione per cambiare il nome degli attributi in conflitto (a patto però che siano dello stesso tipo).

Esempio di theta-join con schemi non disgiunti

Sia $R(A)$ la seguente relazione.

$\text{Matricola}$	$\text{Studente}$
$1203842$	$\text{Rossi Mario}$
$1298314$	$\text{Verdi Luigi}$
$3209239$	$\text{Neri Marco}$

Sia $S(B)$ la seguente relazione.

$\text{Matricola}$	$\text{Altezza}$
$1298314$	$\text{170cm}$
$1902359$	$\text{165cm}$
$1203842$	$\text{185cm}$

Normalmente non potremmo effettuare l’operazione di theta-join tra $R(A)$ ed $S(B)$ perché entrambi hanno un attributo $\text{Matricola}$, però possiamo rinominare uno dei due (in questo caso quello della relazione $S$) tramite l’operazione di ridenominazione ${\rho }_{\text{Codice}\leftarrow \text{Matricola}}(S)$ per ottenere la relazione $S^{\prime }(B^{\prime })$:

$\text{Codice}$	$\text{Altezza}$
$1298314$	$\text{170cm}$
$1902359$	$\text{165cm}$
$1203842$	$\text{185cm}$

Ora, avendo gli schemi $A$ ed $B^{\prime }$ distinti, possiamo effettuare l’operazione di theta-join $R{\bowtie }_{Matricola=\text{Codice}}{S}^{\prime }$ per ottenere la seguente relazione:

$\text{Matricola}$	$\text{Studente}$	$\text{Codice}$	$\text{Altezza}$
$1203842$	$\text{Rossi Mario}$	$1203842$	$\text{185cm}$
$1298314$	$\text{Verdi Luigi}$	$1298314$	$\text{170cm}$

4 - Equi-join ${\bowtie }_{{\Theta }_e}$

Definizione: equi-join

Date due relazioni $R(A)$ ed $S(B)$ (con $A\cap B=\varnothing$) e un predicato ${\Theta }_e$ tra due attributi $A_i\in A$ e $B_j\in B$ che confronta solamente le loro uguaglianze, l’equi-join $R{\bowtie }_{{\Theta }_e}S$ è un operatore relazionale definito come la selezione di alcuni record secondo il predicato ${\Theta }_e$ nel prodotto cartesiano $R\times S$:

$$R{\bowtie }_{{\Theta }_e}S={\sigma }_{{\Theta }_e}(R\times S)$$

Rappresenta un caso particolare del theta-join in cui i confronti del predicato è composto solo da uguaglianze.

Osservazione: partecipazione completa di una delle due relazioni nell'equi-join

Se si prova a effettuare un equi-join tra due relazioni $R(A)$ ed $S(B)$ (con $A\cap B=\varnothing$), in cui $R$ ha partecipazione completa (ossia ogni record di $R$ ha almeno una corrispondenza in $S$), otteniamo che la cardinalità sarà:

$$|R|\le |R{\bowtie }_{{\Theta }_e}S|\le |R|\cdot |S|$$

Osservazione: equi-join in corrispondenza di una chiave primaria

Siano due relazioni $R(A=\{\dots ,A^{\prime },\dots \})$ ed $S(B=\{\underline{PK},\dots \})$ (dove $A^{\prime }$ è un sottoinsieme di attributi $A^{\prime }\subseteq A$ qualsiasi e $\underline{PK}$ è la chiave primaria di $S$) tali che $A\cap B=\varnothing$.

Se si prova a effettuare un equi-join con un predicato del tipo $A_i=\underline{P{K}_i}$ (dove $B_i\in B$ e $\underline{P{K}_i}\in \underline{PK}$), per ogni record di $R$ si troverà al più una ($\le 1$) corrispondenza con $S$ (altrimenti si violerebbe il vincolo di chiave primaria non essendoci più unicità nei valori), quindi otteniamo che la cardinalità sarà:

$$|R{\bowtie }_{{\Theta }_e}S|\le |R|$$

Se proviamo a fare però la stessa cosa ma aggiungendo il vincolo di integrità referenziale, otteniamo una corrispondenza 1 a 1 tra i record delle due relazioni.

Osservazione: equi-join in corrispondenza di una chiave primaria con vincolo di integrità referenziale

Siano due relazioni $R(A=\{\dots ,A^{\prime },\dots \})$ ed $S(B=\{\underline{PK},\dots \})$ (dove $A^{\prime }$ è un sottoinsieme di attributi $A^{\prime }\subseteq A$ qualsiasi e $\underline{PK}$ è la chiave primaria di $S$) tali che $A\cap B=\varnothing$. Vale inoltre il vincolo di integrità referenziale seguente:

$$\forall t_i\in R,\exists t_j\in S(t_i[A^{\prime }]=t_j[\underline{PK}])$$

Se si prova a effettuare un equi-join con un predicato del tipo $A_i=\underline{P{K}_i}$ (dove $A_i\in A$ e $\underline{P{K}_i}\in \underline{PK}$), per ogni record di $R$ si troverà esattamente una ($=1$) corrispondenza con $S$, quindi otteniamo che la cardinalità sarà:

$$|R{\bowtie }_{{\Theta }_e}S|=|R|$$

5 - Natural-join $\bowtie$

Definizione: natural-join

Date due relazioni $R(X,Y)$ ed $S(X,Z)$ tali che gli sottoinsiemi di attributi $X$, $Y$ e $Z$ sono disgiunti due a due e un predicato ${\Theta }_e$ che verifica l’uguaglianza tra ogni attributo $X_i\in X$ in $R$ col corrispondente $X_i\in X$ in $S$, il natural-join (anche detto inner-join) $R\bowtie S$ è un operatore relazionale definito come la proiezione rispetto a $X$, $Y$ e $Z$ dell’equi-join tra $R$ ed $S$:

$$R\bowtie S={\pi }_{X,Y,Z}(R{\bowtie }_{{\Theta }_e}S)$$

Viene usato per generalizzare il concetto di equi-join operando una proiezione sull’unione degli attributi di entrambe le relazioni coinvolte.

Le tuple che non hanno corrispondenze in entrambe le relazioni sono dette dangling e vengono scartate durante l’operazione.

Esempio di natural-join

Sia $\text{FERMATE}$ la seguente relazione.

$\text{Numero}$	$\text{Localitaˋ}$	$\text{Orario}$
$738$	$\text{Messina Centrale}$	$\text{20:35}$
$738$	$\text{Villa San Giovanni}$	$\text{22:35}$
$738$	$\text{Roma Tiburtina}$	$\text{06:21}$
$1992$	$\text{Messina Centrale}$	$\text{15:27}$
$54321$	$\text{Acireale}$	$\text{10:44}$
$54321$	$\text{Giarre-Riposto}$	$\text{11:30}$
$\text{1420}$	$\text{Torino Porta Susa}$	$\text{16:19}$

Sia $\text{TRENI}$ la seguente relazione.

$\text{Numero}$	$\text{OrarioPartenza}$	$\text{Destinazione}$
$738$	$\text{18:35}$	$\text{Milano Centrale}$
$1992$	$\text{20:27}$	$\text{Roma Termini}$
$54321$	$\text{10:34}$	$\text{Messina Centrale}$
$\text{1238}$	$\text{22:57}$	$\text{Bari Centrale}$

La relazione ottenuta dall’operazione $\text{FERMATE}\bowtie \text{TRENI}$ è la seguente.

$\text{Numero}$	$\text{Localitaˋ}$	$\text{Orario}$	$\text{OrarioPartenza}$	$\text{Destinazione}$
$738$	$\text{Messina Centrale}$	$\text{20:35}$	$\text{18:35}$	$\text{Milano Centrale}$
$738$	$\text{Villa San Giovanni}$	$\text{22:35}$	$\text{18:35}$	$\text{Milano Centrale}$
$738$	$\text{Roma Tiburtina}$	$\text{06:21}$	$\text{18:35}$	$\text{Milano Centrale}$
$1992$	$\text{Messina Centrale}$	$\text{15:27}$	$\text{20:27}$	$\text{Roma Termini}$
$54321$	$\text{Acireale}$	$\text{10:44}$	$\text{10:34}$	$\text{Messina Centrale}$
$54321$	$\text{Giarre-Riposto}$	$\text{11:30}$	$\text{10:34}$	$\text{Messina Centrale}$

Possiamo notare come i record $⟨\text{1420},\text{Torino Porta Susa},\text{16:19}⟩$ in $\text{FERMATE}$ e $⟨\text{1238},\text{22:57},\text{Bari Centrale}⟩$ in $\text{TRENI}$ siano dangling perché non hanno una corrispondenza nella relazione opposta.

Osservazione: natural-join su schemi disgiunti equivalente al prodotto cartesiano

Date due relazioni $R(A)$ ed $S(B)$ (con $A\cap B=\varnothing$), il loro natural-join diventa equivalente al loro prodotto cartesiano:

$$R\bowtie S=R\times S$$

Osservazione: natural-join su schemi corrispondenti equivalente all'intersezione

Date due relazioni $R(A=\{A_1,A_2,\dots ,A_n\})$ ed $S(A=\{A_1,A_2,\dots ,A_n\})$, il loro natural-join diventa equivalente alla loro intersezione:

$$R\bowtie S=R\cap S$$

Ciò accade perché il natural-join, per definizione, viene effettuato su tutti gli attributi $A_1,A_2,\dots ,A_n\in A$ (essendoci sempre una corrispondenza in entrambi gli schemi) e include solo i record che appaiono in entrambe, cosa che coincide proprio con la definizione di intersezione.

6 - Semi-join ${⋉}_{\Theta }$

Definizione: semi-join

Date due relazioni $R(A)$ ed $S(B)$ (con $A\cap B=\varnothing$) e un predicato $\Theta$, il semi-join $R{⋉}_{\Theta }S$ è un operatore relazionale definito come la proiezione rispetto allo schema $A$ del theta-join tra $R$ ed $S$:

$$R{⋉}_{\Theta }S={\pi }_A(R{\bowtie }_{\Theta }S)$$

Viene usato per limitare il theta-join allo schema di una delle due relazioni.

Esempio di semi-join

Sia $\text{FERMATE}$ la seguente relazione.

$\text{Numero}$	$\text{Localitaˋ}$	$\text{Orario}$
$738$	$\text{Messina Centrale}$	$\text{20:35}$
$738$	$\text{Villa San Giovanni}$	$\text{22:35}$
$738$	$\text{Roma Tiburtina}$	$\text{06:21}$
$1992$	$\text{Messina Centrale}$	$\text{15:27}$
$54321$	$\text{Acireale}$	$\text{10:44}$
$54321$	$\text{Giarre-Riposto}$	$\text{11:30}$
$\text{1420}$	$\text{Torino Porta Susa}$	$\text{16:19}$

Sia $\text{TRENI}$ la seguente relazione.

$\text{Numero}$	$\text{OrarioPartenza}$	$\text{Destinazione}$
$738$	$\text{18:35}$	$\text{Milano Centrale}$
$1992$	$\text{20:27}$	$\text{Roma Termini}$
$54321$	$\text{10:34}$	$\text{Messina Centrale}$
$\text{1238}$	$\text{22:57}$	$\text{Bari Centrale}$

Sia $\Theta$ il seguente predicato:

$$\text{FERMATE.Orario > TRENI.OrarioPartenza}$$

La relazione ottenuta dall’operazione $\text{FERMATE}{⋉}_{\Theta }\text{TRENI}$ è la seguente.

$\text{Numero}$	$\text{Localitaˋ}$	$\text{Orario}$
$738$	$\text{Messina Centrale}$	$\text{20:35}$
$738$	$\text{Villa San Giovanni}$	$\text{22:35}$
$54321$	$\text{Acireale}$	$\text{10:44}$
$54321$	$\text{Giarre-Riposto}$	$\text{11:30}$

Ciò che abbiamo fatto è stato effettuare essenzialmente una selezione sulla relazione $\text{FERMATE}$ scegliendo di visualizzare solo quelle fermate che saranno visitate successivamente all’orario di partenza di ogni treno nella relazione $\text{TRENI}$.

Osservazione: cardinalità del risultato del semi-join

Date due relazioni $R(A)$ ed $S(B)$ (con $A\cap B=\varnothing$) e un predicato $\Theta$, la cardinalità della relazione prodotta dall’operazione di semi-join $R{⋉}_{\Theta }S$ è:

$$0\le |R{⋉}_{\Theta }S|\le |R|$$

Ciò accade perché il semi-join è composto da una proiezione e la cardinalità di una proiezione è al massimo uguale a quella dell’istanza a cui si riferisce.

7 - Outer-join

Definizione: outer-join

Gli outer-join sono operatori relazionali che effettuano un natural-join su cui però non vengono perse tutte le tuple dangling di una delle due relazioni o di entrambe e sono distinti in tre tipi:

• Left-join $⊐\bowtie$: mantiene le tuple dangling della relazione a sinistra dell’operatore.
• Right-join $\bowtie ⊏$: mantiene le tuple dangling della relazione a destra dell’operatore.
• Full-join $⊐\bowtie ⊏$: mantiene le tuple dangling di entrambe le relazioni.

7.1 - Left-join $⊐\bowtie$

Definizione: left-join

Date due relazioni $R(X,Y)$ ed $S(X,Z)$ tali che gli sottoinsiemi di attributi $X$, $Y$ e $Z$ sono disgiunti a due a due e un predicato ${\Theta }_e$ che verifica l’uguaglianza tra ogni attributo $X_i\in X$ in $R$ col corrispondente $X_i\in X$ in $S$, il left-join $R⊐\bowtie S$ è un operatore relazionale (in particolare un outer-join) definito come un natural-join in cui le tuple dangling della relazione $R$ vengono mantenute e rispetto agli attributi $Z$ assumono valore nullo, mentre le tuple dangling della relazione $S$ vengono scartate:

$$R⊐\bowtie S=(R\bowtie S)\cup R-{\pi }_{X,Y}(R\bowtie S)$$

7.2 - Right-join $\bowtie ⊏$

Definizione: right-join

Date due relazioni $R(X,Y)$ ed $S(X,Z)$ tali che gli sottoinsiemi di attributi $X$, $Y$ e $Z$ sono disgiunti a due a due e un predicato ${\Theta }_e$ che verifica l’uguaglianza tra ogni attributo $X_i\in X$ in $R$ col corrispondente $X_i\in X$ in $S$, il right-join $R\bowtie ⊏S$ è un operatore relazionale (in particolare un outer-join) definito come un natural-join in cui le tuple dangling della relazione $S$ vengono mantenute e rispetto agli attributi $Y$ assumono valore nullo, mentre le tuple dangling della relazione $R$ vengono scartate:

$$R\bowtie ⊏S=(R\bowtie S)\cup S-{\pi }_{X,Z}(R\bowtie S)$$

7.3 - Full-join $⊐\bowtie ⊏$

Definizione: full-join

Date due relazioni $R(X,Y)$ ed $S(X,Z)$ tali che gli sottoinsiemi di attributi $X$, $Y$ e $Z$ sono disgiunti a due a due e un predicato ${\Theta }_e$ che verifica l’uguaglianza tra ogni attributo $X_i\in X$ in $R$ col corrispondente $X_i\in X$ in $S$, il right-join $R⊐\bowtie ⊏S$ è un operatore relazionale (in particolare un outer-join) definito come un natural-join in cui sia le tuple dangling della relazione $R$ che quelle della relazione $S$ vengono mantenute e rispetto agli attributi $Y$ e $Z$ assumono valore nullo:

$$R⊐\bowtie ⊏S=(R\bowtie S)\cup (R⊐\bowtie S)\cup (R\bowtie ⊏S)$$

8 - Quoziente $÷$

Definizione: quoziente

Date due relazioni $R(A,B)$ ed $S(B)$ (con $A\cap B=\varnothing$), il quoziente $R÷S$ è un operatore relazionale definito nel seguente modo:

$$R÷S=({\pi }_A(R))-({\pi }_A((({\pi }_A(R))\times S)-R))$$

Viene usato per cercare i valori di un attributo che sono associati a ogni valore di altri attributi.

Esempio di quoziente

Sia $\text{ESAMI}(\underline{\text{Matricola}},\text{Corso})$ la seguente relazione che rappresenta quali esami ha completato ogni matricola.

$\underline{\text{Matricola}}$	$\text{Corso}$
$5837292$	$\text{Algebra Lineare}$
$3210985$	$\text{Programmazione I}$
$3210985$	$\text{Algebra Lineare}$
$5837292$	$\text{Matematica Discreta}$
$5837292$	$\text{Programmazione I}$

Sia $\text{PIANO\_DI\_STUDI}(\underline{\text{Corso}})$ la seguente relazione che rappresenta quali esami deve completare ogni matricola.

$\underline{\text{Corso}}$
$\text{Programmazione I}$
$\text{Matematica Discreta}$
$\text{Algebra Lineare}$

Dalla definizione di quoziente, associamo così i valori al nostro esempio:

• Relazioni: $R={\pi }_{\text{Matricola, Corso}}(\text{ESAMI}),S={\pi }_{\text{Corso}}(\text{PIANO\_DI\_STUDI})$.
• Attributi: $A=\{\text{Matricola}\},B=\{\text{Corso}\}$.

Otteniamo quindi l’operazione:

$${\pi }_{\text{Matricola, Corso}}(\text{ESAMI})÷{\pi }_{\text{Corso}}(\text{PIANO\_DI\_STUDI})=({\pi }_{\text{Matricola}}({\pi }_{\text{Matricola, Corso}}(\text{ESAMI})))-({\pi }_{\text{Matricola}}((({\pi }_{\text{Matricola}}({\pi }_{\text{Matricola, Corso}}(\text{ESAMI})))\times {\pi }_{\text{Corso}}(\text{PIANO\_DI\_STUDI}))-{\pi }_{\text{Matricola, Corso}}(\text{ESAMI})))$$

Otteniamo “il quoziente” della divisione, cioè quelle matricole che sono abbinate a tutti i corsi della seconda tabella (in questo caso, la matricola $5837292$ è abbinata a tutti i corsi).

Osservazione: cardinalità del risultato del quoziente

Date due relazioni $R(A,B)$ ed $S(B)$ (con $A\cap B=\varnothing$), la cardinalità della relazione prodotta dall’operazione di quoziente $R÷S$ è:

$$|R÷S|\le |{\pi }_A(R)|\le |R|$$

Ciò accade perché il semi-join è composto da una proiezione e la cardinalità di una proiezione è al massimo uguale a quella dell’istanza a cui si riferisce.

Osservazione: risoluzione delle interrogazioni con quantificatori universali tramite quoziente

Le interrogazioni con una quantificazione universale, ossia quelle interrogazioni in cui sono presenti parole chiave come “tutti”, “ogni” e “sempre”, possono essere risolte tramite l’operatore quoziente.

Esempio: risoluzione di un'interrogazione con quantificatore universale tramite quoziente

Operiamo sulla base di dati ospedaliera l’interrogazione “elencare i codici dei pazienti che sono stati ricoverati in ogni reparto”.

Dalla definizione di quoziente, associamo così i valori al nostro esempio:

• Relazioni: $R={\pi }_{\text{CodPaz, Reparto}}(\text{RICOVERI}),S={\pi }_{\text{Reparto}}(\text{RICOVERI})$.
• Attributi: $A=\{\text{CodPaz}\},B=\{\text{Reparto}\}$.

Otteniamo quindi l’operazione:

$${\pi }_{\text{CodPaz, Reparto}}(\text{RICOVERI})÷{\pi }_{\text{Reparto}}(\text{RICOVERI})=({\pi }_{\text{CodPaz}}({\pi }_{\text{CodPaz, Reparto}}(\text{RICOVERI})))-({\pi }_{\text{CodPaz}}((({\pi }_{\text{CodPaz}}({\pi }_{\text{CodPaz, Reparto}}(\text{RICOVERI})))\times {\pi }_{\text{Reparto}}(\text{RICOVERI}))-{\pi }_{\text{CodPaz, Reparto}}(\text{RICOVERI})))$$

---

Approfondimento

Se vuoi saperne di più:

• Proprietà degli operatori relazionali.
• Risoluzione delle interrogazioni con negazione.
• Uso creativo dell’algebra relazionale.

Fonti:

• 🏫 Lezioni e slide del Prof. Pensa Ruggero Gaetano del corso di Basi di Dati (canale B), Corso di Laurea in Informatica presso l’Università di Torino, A.A. 2024-25:
  • 3. L’algebra relazionale.
  • 4. L’algebra relazionale, seconda parte.
• 🏫 Appunti di Luca Barra del corso di Basi di Dati, Corso di Laurea in Informatica presso l’Università di Torino, A.A. 2022-23 (caricati sul repository GitHub del Team Studentesco Informatica).