Operatori derivati

Premessa

Portale di appartenenza: Basi di dati.

Cosa troverai in questa nota:

• La definizione degli operatori derivati dell’algebra relazionale e delle loro proprietà.

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! ☝️🤓

Definizione: operatore derivato

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

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

Per mettere in correlazione dati estratti da due o più relazioni diverse, si usa il theta join.

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)$$

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$ 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{Matricola}$	$\text{Altezza}$
$1298314$	$\text{170cm}$
$1902359$	$\text{165cm}$
$1203842$	$\text{185cm}$

Normalmente non potremmo effettuare l’operazione di theta-join tra $R$ ed $S$ 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 $R_3$:

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

Ora, avendo gli schemi $A$ ed $A_3$ distinti, possiamo effettuare l’operazione di theta-join $R{\bowtie }_{Matricola=\text{Codice}}{R}_3$ 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}$

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

Un caso particolare del theta-join in cui i confronti del predicato è composto solo da uguaglianze è l’equi-join.

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)$$

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|$$

3 - Natural-join $\bowtie$

Si può generalizzare il concetto di equi-join operando una proiezione sull’unione degli attributi di entrambe le relazioni coinvolte.

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)$$

I record 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.

4 - 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)$$

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.

5 - 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))$$

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 $3210985$ non è abbinata al corso $\text{Matematica Discreta}$).

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})))$$

6 - Outer-join

Nel caso in cui volessimo effettuare dei natural-join su cui però non vogliamo perdere le tuple dangling di una delle due relazioni o di entrambe, possiamo usare gli outer-join, 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.

6.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 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 definito un natural-join in cui i record dangling della relazione $R$ vengono mantenuti e rispetto agli attributi $Z$ assumono valore nullo, mentre i record dangling della relazione $S$ vengono scartati:

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

6.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 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 definito un natural-join in cui i record dangling della relazione $S$ vengono mantenuti e rispetto agli attributi $Y$ assumono valore nullo, mentre i record dangling della relazione $R$ vengono scartati:

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

6.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 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 definito un natural-join in cui sia i record dangling della relazione $R$ che quelli della relazione $S$ vengono mantenuti e rispetto agli attributi $Y$ e $Z$ assumono valore nullo:

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

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 Collettivo Studentesco Informatica).