Nell'algebra relazionale, un join (spesso tradotto come congiunzione) è un'operazione binaria, indicata con dove e rappresentano delle relazioni, che combina i loro dati laddove presentano un attributo comune.

Natural join Il natural join (o join naturale), indicato col simbolo ⨝, è un operatore binario dell'algebra relazionale scritto come , dove ed sono relazioni.In Unicode, il simbolo del join è ⨝ (U+2A1D), mentre il simbolo del farfallino (bowtie), usato occasionalmente al suo posto, è ⋈ (U+22C8).

Il risultato del natural join è l'insieme di tutte le combinazioni di tuple in ed che presentano valori uguali per i nomi dei loro attributi in comune. A titolo esemplificativo, si considerino le relazioni Dipendente e Dipartimento e il loro relativo natural join:

+ Dipendente Nome IDDip NomeDip Harry 3415 Finanza Sally 2241 Vendite George 3401 Finanza Harriet 2202 Vendite Mary 1257 Risorse Umane

+ Dipartimento NomeDip Manager Finanza George Vendite Harriet Produzione Charles

+ Dipendente Dipartimento Nome IDDip NomeDip Manager Harry 3415 Finanza George Sally 2241 Vendite Harriet George 3401 Finanza George Harriet 2202 Vendite Harriet

Come si evince dall'esempio, né la dipendente di nome Mary né il dipartimento di Produzione compaiono nel risultato. Mary viene esclusa poiché il suo dipartimento (Risorse Umane) non è presente nella relazione Dipartimento; analogamente, il dipartimento di Produzione non compare poiché non esistono tuple nella relazione Dipendente che assumano il valore "Produzione" per l'attributo NomeDip.

Questo operatore può essere utilizzato anche per definire la composizione di relazioni. Ad esempio, la composizione di Dipendente e Dipartimento corrisponde al loro join (mostrato sopra) proiettato su tutti gli attributi tranne quello comune (NomeDip). Nella teoria delle categorie, il join coincide esattamente con il prodotto fibrato.

Proprietà e utilizzo Il natural join è considerato tra gli operatori relazionali più rilevanti in quanto rappresenta la controparte dell'operatore logico AND. Se una medesima variabile appare in due predicati connessi da un operatore AND, tale variabile rappresenta la stessa entità e in entrambe le occorrenze deve essere sostituita dallo stesso valore (conseguenza dell'idempotenza dell'AND logico).

In ambito di progettazione di basi di dati, il natural join è impiegato tipicamente per combinare relazioni associate tramite una chiave esterna. Nell'esempio precedente, sussiste presumibilmente una chiave esterna da Dipendente.NomeDip a Dipartimento.NomeDip, e il natural join combina tutti i dipendenti con i rispettivi manager di dipartimento. Questa operazione risulta immediata poiché la chiave esterna insiste su attributi con lo stesso nome; qualora i nomi differissero (es. una chiave esterna da Dipartimento.Manager a Dipendente.Nome), le colonne dovrebbero essere opportunamente rinominate prima di eseguire il join. Essendo basato sull'uguaglianza degli attributi, il natural join è formalmente un caso particolare di equi-join.

Definizione formale Più formalmente, la semantica del natural join è definita come segue:

dove è un predicato che risulta vero per una relazione (in senso matematico) se e solo se è una funzione (ovvero non mappa alcun attributo a valori multipli). Di norma si richiede che ed abbiano almeno un attributo in comune; tuttavia, se questo vincolo viene omesso e le due relazioni sono disgiunte rispetto agli attributi, il natural join degenera in un prodotto cartesiano.

Simulazione tramite le primitive di Codd Il natural join non è un operatore primitivo, in quanto può essere espresso tramite gli operatori fondamentali definiti da Codd (prodotto cartesiano, selezione, proiezione e ridenominazione).

Siano i nomi degli attributi comuni a ed , gli attributi esclusivi di e gli attributi esclusivi di . Si introduca inoltre un set di attributi non presenti né in né in . L'equivalenza si articola in tre passaggi:

1. Ridenominazione: si rinominano gli attributi comuni in per evitare collisioni di nomi durante il prodotto cartesiano:

2. Prodotto cartesiano e selezione: si calcola il prodotto cartesiano tra e la nuova relazione , filtrando (tramite operatore di selezione ) le sole tuple in cui i valori degli attributi comuni coincidono:

3. Proiezione: si esegue infine una proiezione () per preservare solo gli attributi originali, eliminando le colonne rinominate:

θ-join ed equijoin Si considerino le tabelle Auto e Barca che elencano i modelli e i rispettivi prezzi. Si supponga che un cliente voglia acquistare un'auto e una barca, ma non voglia spendere per la barca più di quanto spenda per l'auto. Il θ-join (⋈θ) sul predicato PrezzoAuto ≥ PrezzoBarca produce le coppie di righe che soddisfano tale predicato. Quando si utilizza una condizione basata sull'uguaglianza degli attributi (ad esempio Prezzo = Prezzo), la condizione può essere abbreviata.

+ Auto ModelloAuto PrezzoAuto AutoA 20.000 AutoB 30.000 AutoC 50.000 + Barca ModelloBarca PrezzoBarca Barca1 10.000 Barca2 40.000 Barca3 60.000 + ModelloAuto PrezzoAuto ModelloBarca PrezzoBarca AutoA 20.000 Barca1 10.000 AutoB 30.000 Barca1 10.000 AutoC 50.000 Barca1 10.000 AutoC 50.000 Barca2 40.000

Per combinare le tuple di due relazioni quando la condizione di unione non è semplicemente l'uguaglianza di attributi condivisi, è conveniente avere un operatore di join più generale: il θ-join (o theta-join). Il θ-join è un operatore binario scritto come o dove a e b sono nomi di attributi, θ è un operatore relazionale binario appartenente all'insieme {<, ≤, =, ≠, >, ≥}, υ è una costante di valore, e R e S sono relazioni. L'operazione restituisce tutte le combinazioni di tuple in R e S che soddisfano θ. Il risultato del θ-join è definito solo se le intestazioni di S e R sono disgiunte, cioè non contengono un attributo in comune.

La simulazione di questa operazione con le operazioni fondamentali è la seguente: R ⋈θ S = σθ(R × S)

Nel caso in cui l'operatore θ sia l'operatore di uguaglianza (=), questo join è chiamato anche equijoin.

Si noti che un linguaggio informatico che supporta il natural join e gli operatori di selezione non ha strettamente bisogno del θ-join, poiché questo può essere ottenuto effettuando una selezione sul risultato di un natural join (che degenera in un prodotto cartesiano se non vi sono attributi condivisi).

Nelle implementazioni SQL, l'unione su un predicato è solitamente chiamata inner join, e la parola chiave on permette di specificare il predicato usato per filtrare le righe. Concettualmente si crea il prodotto cartesiano e poi si filtrano le righe, ma i moderni RDBMS utilizzano strutture dati e algoritmi ottimizzati per velocizzare l'esecuzione delle query senza materializzare il prodotto cartesiano.

Semijoin Il semijoin sinistro (⋉ e ⋊) è un'unione simile al natural join, indicata come dove e sono relazioni.In Unicode, il simbolo ltimes è ⋉ (U+22C9). Il simbolo rtimes è ⋊ (U+22CA). Il risultato è l'insieme di tutte le tuple in per le quali esiste una tupla in uguale sui nomi degli attributi comuni. La differenza rispetto a un natural join è che le altre colonne di non compaiono nel risultato finale. Per esempio:

+ Dipendente Nome IDDip NomeDip Harry 3415 Finanza Sally 2241 Vendite George 3401 Finanza Harriet 2202 Produzione + Dipartimento NomeDip Manager Vendite Sally Produzione Harriet + Dipendente ⋉ Dipartimento Nome IDDip NomeDip Sally 2241 Vendite Harriet 2202 Produzione

Più formalmente, la semantica del semijoin è:

dove è come definito nel natural join.

Il semijoin può essere simulato usando il natural join e la proiezione. Se sono i nomi degli attributi di , allora:

Poiché possiamo simulare il natural join con gli operatori di base, lo stesso vale per il semijoin. Nel celebre saggio di Codd del 1970, il semijoin era chiamato restrizione.

Antijoin L'antijoin (▷), scritto come R ▷ S dove R e S sono relazioni,In Unicode, il simbolo dell'Antijoin è ▷ (U+25B7). è simile al semijoin, ma il risultato restituisce solo quelle tuple in R per le quali non esiste una tupla in S uguale sui loro attributi comuni.

Ad esempio:

+ Dipendente Nome IDDip NomeDip Harry 3415 Finanza Sally 2241 Vendite George 3401 Finanza Harriet 2202 Produzione + Dipartimento NomeDip Manager Vendite Sally Produzione Harriet + Dipendente ▷ Dipartimento Nome IDDip NomeDip Harry 3415 Finanza George 3401 Finanza

Formalmente è definito come:

R ▷ S = { t : t ∈ R ∧ ¬∃s ∈ S(Fun (t ∪ s)) }

L'antijoin può essere definito anche come il complemento del semijoin, nel seguente modo:

A causa di questa proprietà, l'antijoin è talvolta chiamato anti-semijoin, e scritto con il simbolo del semijoin con una barra orizzontale sopra (invece di ▷). Nel caso in cui le relazioni abbiano gli stessi attributi (siano cioè compatibili all'unione), l'antijoin equivale alla sottrazione insiemistica.

Divisione La divisione (÷) è un'operazione binaria scritta come R ÷ S. La divisione non è implementata direttamente nel linguaggio SQL standard. Il risultato è costituito dalle restrizioni delle tuple in R sugli attributi esclusivi di R (presenti cioè in R ma non in S), a condizione che in R esistano tutte le loro combinazioni con le tuple presenti in S.

Esempio

+ Completati (R) Studente Compito Fred Database1 Fred Database2 Fred Compilatore1 Eugene Database1 Eugene Compilatore1 Sarah Database1 Sarah Database2 + ProgettoDB (S) Compito Database1 Database2 + Completati ÷ ProgettoDB Studente Fred Sarah

Se ProgettoDB contiene tutti i compiti del progetto Database, allora il risultato della divisione contiene esattamente gli studenti che hanno completato entrambi i compiti del progetto (Fred e Sarah, ma non Eugene).

Più formalmente la semantica della divisione è definita come segue:

dove {a1,...,an} è l'insieme degli attributi univoci di R e t[a1,...,an] è la restrizione di t a tale insieme. Di solito si richiede che gli attributi di S siano un sottoinsieme di quelli di R, altrimenti il risultato dell'operazione sarà sempre vuoto.

La simulazione della divisione con le operazioni di base procede in questo modo: assumiamo che a1,...,an siano gli attributi unici di R e b1,...,bm siano gli attributi di S. Nel primo passo proiettiamo R sui suoi attributi esclusivi e costruiamo tutte le combinazioni (prodotto cartesiano) con le tuple di S: T := πa1,...,an(R) × S

Nell'esempio precedente, T rappresenterebbe una tabella in cui ogni studente viene combinato con ogni compito richiesto. Es: T := πStudente(R) × S

+ T Studente Compito Fred Database1 Fred Database2 Eugene Database1 Eugene Database2 Sarah Database1 Sarah Database2

Nel passaggio successivo sottraiamo la relazione originale R da T: U := T − R In U si ottengono le possibili combinazioni che "avrebbero potuto" trovarsi in R, ma che di fatto sono assenti (i compiti mancanti). Es: U := T − πStudente,Compito(R)

+ U (T − R, i mancanti) Studente Compito Eugene Database2

Ora eseguiamo una proiezione sugli attributi unici di R. Si ottengono così le restrizioni delle tuple in R per le quali **non** tutte le combinazioni con S erano presenti in R (quindi gli studenti che *non* hanno finito tutti i compiti): V := πa1,...,an(U) Es: V := πStudente(U)

+ V Studente Eugene

Infine, basta proiettare l'originale R sui suoi attributi univoci e sottrarre i risultati trovati in V: W := πa1,...,an(R) − V Es: W := πStudente(R) − V.

+ πStudente(R) Studente Fred Eugene Sarah + V Studente Eugene + W (Il risultato desiderato) Studente Fred Sarah

Note Annotazioni

Fonti

Categoria:Algebra relazionale