Join in algebra relazionale
L'operatore join in algebra relazionale correla i dati contenuti in relazioni diverse confrontando i valori. Esistono due tipi di join: il join naturale e il join condizionale (theta join).
Si tratta di un operatore che ha per operandi una o due relazioni (tabelle) in ingresso e fornisce in uscita un'altra relazione (tabella).
Nota. Oltre al join naturale e al theta join c'è anche un terzo tipo di join detto join estrerno (outer join) introdotto nel linguaggio SQL
Join naturale
Il join naturale correla i dati in due relazioni diverse sulla base dei valori uguali negli attributi con lo stesso nome. Il simbolo del join naturale è una farfalla. $$ r_1 \Join r_2 = \{ t \in X_1 ∪ X_2 \: | \: t[X_1] \in r_1 ∧ t[X_2] \in r_2 \} $$
Il presupposto è che ci siano due relazioni contenenti alcuni attributi con lo stesso nome.
Esempio
L'operatore individua individua le tuple che hanno lo stesso valore nell'attributo in comune e le unisce in una tabella.
L'attributo in comune delle due relazioni è presente una sola volta nella tabella join in uscita.
Nota. Il join naturale è una relazione definita sull'unione degli insiemi degli attributi delle due relazioni r1(X1) e r2(X2) ossia X1 ∪ X2
Generalmente l'attributo in comune è una chiave di una delle due relazioni anche se non è necessario.
Possono anche esserci più attributi in comune.
Esempio
Ho due relazioni R(X1) e T(X2).
Dove X1={a,b,c} e X2={b,d}
Le due relazioni hanno un attributo in comune. E' l'attributo b.
Calcolo il join naturale delle due relazioni.
$$ r_1 \Join r_2 $$
Il join naturale legge ogni riga (tupla o ennupla) della prima tabella R e verifica se esiste lo stesso valore dell'attributo b anche nella seconda tabella T.
Se esiste, seleziona le tuple di R e T e le dispone in un'unica riga nella tabella join.
Il risultato finale è una tabella con lo schema composto dagli attributi delle due relazioni e le tuple (righe) che hanno lo stesso valore nell'attributo in comune.
La colonna dell'attributo in comune (b) è presente una sola volta nella tabella del join naturale.
La cardinalità del join naturale
In base al numero delle tuple il join è detto
- Join completo. Il join si dice completo se ogni tupla di ciascuna relazione degli operandi contribuisce almeno a una tupla del risultato.
Nota. Il massimo risultato di tuple possibile tra i join completi è il prodotto cartesiano |r1|·|r2|. Il minimo è pari alla cardinalità massima tra le due relazioni max(|r1|,|r2|).
- Join incompleto. Il join si dice incompleto se almeno una tupla delle relazioni degli operandi non contribuisce al risultato.
- Join vuoto. Il join si dice vuoto se nessuna tupla delle relazioni degli operandi contribuisce al risultato finale.
Nota. In questo caso la tabella finale del join è senza tuple.
Pertanto la cardinalità del join è un numero compreso tra zero (join vuoto) e il prodotto cartesiano delle relazioni |r1|x|r2|.
Il caso del join naturale senza attributi in comune
Se nel join naturale non ci sono attributi in comune, il risultato è il prodotto cartesiano delle relazioni r1 x r2.
Gli insiemi degli attributi X1 e X2 sono disgiunti.
Non avendo attributi in comune, le tuple non devono rispettare nessuna condizione di join naturale.
Non essendoci condizioni da rispettare, sono ammesse alla join tutte le tuple di entrambe le relazioni r1 e r2.
Pertanto, la join naturale degenera in un prodotto cartesiano r1 x r2.
Il caso del join naturale con tutti gli attributi in comune
Se nel join naturale tutti gli attributi in comune, il risultato è l'intersezione delle relazioni r1 x r2. $$ r_1(X_1) \Join r_2(X_2) = r_1(X_1) ⋂ r_2(X_2) $$
Dove X1=X2 perché gli insiemi degli attributi sono congiunti e identici tra loro.
Join condizionale (o theta join)
Il join condizionale (theta join) correla i dati in due relazioni diverse sulla base di una condizione booleana. E' anche detto theta join. Il simbolo del join condizionale è una farfalla seguita da una C. $$ r_1 \Join _C r_2 $$
L'operatore theta join legge le tuple della prima relazione e verifica quali tuple della seconda relazione soddisfano la condizione di join.
Se la condizione è soddisfatta le tuple sono combinate e aggiunte nella tabella di join.
Viceversa, le tuple che non la soddisfano sono escluse.
Nota. Il join condizionale tra due relazioni r1 e r2 equivale a una selezione sul prodotto cartesiano delle relazioni r1 X r2. $$ r_1 \Join _C r_2 = \sigma_c (r_1 x r_2) $$ Per questa ragione il theta join è considerato un operatore derivato, in quanto si realizza usando due operatori primitivi dell'algebra relazionale (prodotto cartesiano+selezione).
Il caso particolare dell'equi join
Se la condizione è composta da operatori di uguaglianza (=), eventualmente in congiunzione (and) tra loro, il join condizionale è detto equi join.
Di fatto l'equi join è simile a un join naturale in cui nella condizione di join sono ammessi gli attributi con nomi diversi e le costanti.
Un esempio pratico
Ho due tabelle Azienda e Edificio.
Utilizzo l'equi-join per associare l'ufficio al piano dell'edificio in cui si trova.
La condizione di join è l'uguaglianza direzione=servizio
$$ Azienda \: \Join_{(direzione=servizio)} \: Edificio $$
Il risultato finale è la seguente tabella
Esempio 2
Questo join mostra il piano degli uffici con più di 10 dipendenti.
La condizione di join è (direzione=servizio) and (dipendenti>10).
$$ Azienda \: \Join_{(direzione=servizio \: ∧ \: dipendenti>10)} \: Edificio $$
Non essendo la condizione composta da una congiunzione di uguaglianze, si tratta di un theta join.
Il risultato finale è la seguente tabella
E così via.
