Algebra relazionale

Accesso ai dati di un DBAggiornamento di DB: funzione che, data istanza di DB, produce altra istanza di DB, sullo stesso schema Modifica, aggiunta, rimozione tupleInterrogazione a DB: funzione che, dato un DB, produce una relazione su un dato schema (non necessariamente uno degli schemi definiti nel DB)

Accesso ai dati di un DBAggiornamento e interrogazione vengono effettuati usando specifici linguaggi Per esempio: algebra relazionale

Algebra relazionaleLinguaggio procedurale di accesso a DB Si specificano operazioni complesse

descrivendo procedimento da usare per ottenere soluzione

Interrogazioni: espressioni complesse

Algebra relazionaleAlgebra relazionale: basata su insieme di operatori Definiti su relazioni Producono relazioni come risultati

Operatori Insiemistici: unione, intersezione, differenza Specifici: ridenominazione, selezione,

proiezione, join

Operatori insiemisticiRelazioni: insiemi di tuple omogenee, cioè definite sigli stessi attributiInsiemi: ha senso usare operatori insiemisticiInsiemi di tuple omogenee: usare operatori insiemistici solo su relazioni definite sugli stessi attributi Altrimenti, si ottengono insiemi di tuple

disomogenee, che non rappresentano relazioni

Unione di relazioniDate due relazioni r1(X) e r2(X) definite sullo stesso insieme di attributi Xr1r2: relazione su X che contiene tuple appartenenti a r1 oppure a r2 oppure a entrambe

Unione di relazioniMatricola

Cognome

Età

9297 Neri 567432 Neri 399824 Verdi 38

Matricola

Cognome

Età

7274 Rossi 377432 Neri 399824 Verdi 38

Matricola

Cognome

Età

7274 Rossi 377432 Neri 399297 Neri 569824 Verdi 38

Laureati Dirigenti

Laureati Dirigenti

Differenza di relazioniDate due relazioni r1(X) e r2(X) definite sullo stesso insieme di attributi Xr1-r2: relazione su X che contiene tuple appartenenti a r1 ma non a r2

Differenza di relazioniMatricola

Cognome

Età

9297 Neri 567432 Neri 399824 Verdi 38

Matricola

Cognome

Età

7274 Rossi 377432 Neri 399824 Verdi 38

Matricola

Cognome

Età

7274 Rossi 37

Laureati Dirigenti

Laureati - Dirigenti

Intersezione di relazioniDate due relazioni r1(X) e r2(X) definite sullo stesso insieme di attributi Xr1r2: relazione su X che contiene tuple appartenenti sia a r1 che a r2

Intersezione di relazioniMatricola

Cognome

Età

9297 Neri 567432 Neri 399824 Verdi 38

Matricola

Cognome

Età

7274 Rossi 377432 Neri 399824 Verdi 38

Matricola

Cognome

Età

7432 Neri 399824 Verdi 38

Laureati Dirigenti

Laureati Dirigenti

Operatori di manipolazione di relazioni

Specifici dell’algebra relazionale (non derivano dalle teoria degli insiemi)Permettono di manipolare relazioni per creare nuove relazione Ridenominazione Selezione Proiezione Join

Operatori di manipolazione di relazioni

Specifici dell’algebra relazionale (non derivano dalle teoria degli insiemi)Permettono di manipolare relazioni per creare nuove relazione Ridenominazione Selezione Proiezione Join

Ridenominazione di relazioni

Cambia il nome di un attributo di relazione lasciandone inalterata l’istanza (modifica solo intestazione di relazione)Utile per applicare operatori insiemistici a relazioni con attributi di nome diverso

Ridenominazione di relazioni

Per esempio:

Padre FiglioAdamo CainoAdamo AbeleAbramo IsaccoAbramo Ismaele

Madre FiglioEva CainoEva SetSara IsaccoAgar Ismaele

Paternità Maternità

Paternità Maternità ?

Ridenominazione di relazioni

Una ridenominazione:

Padre FiglioAdamo CainoAdamo AbeleAbramo IsaccoAbramo Ismaele

Genitore FiglioAdamo CainoAdamo AbeleAbramo IsaccoAbramo Ismaele

Paternità GenitorePadre(Paternità)

Ridenominazione di relazioni

Una ridenominazione:

Padre FiglioAdamo CainoAdamo AbeleAbramo IsaccoAbramo Ismaele

Genitore FiglioAdamo CainoAdamo AbeleAbramo IsaccoAbramo Ismaele

Paternità GenitorePadre(Paternità)GenitorePadre(Paternità)

Ridenominazione di relazioni

Una ridenominazione:

Padre FiglioAdamo CainoAdamo AbeleAbramo IsaccoAbramo Ismaele

Genitore FiglioAdamo CainoAdamo AbeleAbramo IsaccoAbramo Ismaele

Paternità GenitorePadre(Paternità)GenitorePadre(Paternità)

Ridenominazione di relazioni

Un’altra ridenominazione:

Madre FiglioEva CainoEva SetSara IsaccoAgar Ismaele

Genitore FiglioEva CainoEva SetSara IsaccoAgar Ismaele

Maternità GenitoreMadre(Maternità)

Ridenominazione di relazioni

Genitore FiglioAdamo CainoAdamo AbeleAbramo IsaccoAbramo IsmaeleEva CainoEva SetSara IsaccoAgar Ismaele

GenitorePadre(Paternità) GenitoreMadre(Maternità)

Corretta applicazionedi unionerelazioni

Ridenominazione di relazioniCognome

Agenzia

Stipendio

Rossi Roma 45Neri Milano 53

Imp

Ridenominazione di relazioniCognome

Agenzia

Stipendio

Rossi Roma 45Neri Milano 53

Cognome

Fabbrica

Salario

Verdi Latina 33Bruni Monza 32

Imp Op

Ridenominazione di relazioni

Cognome

Sede Retribuzione

Rossi Roma

45

Neri Milano

53

Verdi Latina

33

Bruni Monza

32

Cognome

Agenzia

Stipendio

Rossi Roma 45Neri Milano 53

Cognome

Fabbrica

Salario

Verdi Latina 33Bruni Monza 32

Imp Op

Sede,RetribuzioneAgenzia,Stipendio(Imp)

Sede,RetribuzioneFabbrica,Salario(Op)

Ridenominazione di relazioni

Sia r(X) è la schema di una relazione r definita su insieme X={A1,…,Ak}… e sia Y un insieme di attributi Y={B1,…,Bk}

La ridenominazione B1,..,BkA1,…,Ak(r) contiene una tupla t’ per ogni tupla t in r, così definita: t’ è una tupla su Y, e t’[Bi]=t[Ai] per 1ik

Ridenominazione di relazioni

Di solito, si indicano nelle ridenominazione solo attributi ridenominati (quelli per cui Ai Bi)

GenitorePadre(Paternità): omesso Figlio

Operatori di manipolazione di relazioni

Specifici dell’algebra relazionale (non derivano dalle teoria degli insiemi)Permettono di manipolare relazioni per creare nuove relazione Ridenominazione Selezione Proiezione Join

SelezioneData relazione r su insieme di attributi X, selezione F(r) produce relazione su attributi X che contiene tuple di r che soddisfano la condizione di selezione F

A B C

Selezione secondo FF(r)

A B C

SelezioneF formula proposizionale: condizione di selezione formata da Operatori booleani:

(AND), (OR), (NOT)

SelezioneF formula proposizionale: condizione di selezione formata da Operatori booleani Condizione atomiche: termine che

possono contenere Confronti fra attributi (per esempio,

Stipendio>Tasse, dove Stipendio e Tasse sono attributi)

Confronti fra attributi e constanti (per esempio, Età 60, dove Età è un attributo)

SelezioneCognome

Nome

Età

Stipendio

Rossi Mario 25 1.000,00Neri Luca 40 1.500,00Verdi Nico 36 2.250,00Rossi Marc

o40 1.900,00

Impiegati

Cognome

Nome

Età

Stipendio

Verdi Nico 36 2.250,00

Età>30Stipendio>2.000,00(Impiegati)

SelezioneCognome

Nome

Età

Stipendio

Rossi Mario 25 1.000,00Neri Luca 40 1.500,00Verdi Nico 36 2.250,00Rossi Marc

o40 1.900,00

Impiegati

Cognome

Nome

Età

Stipendio

Verdi Nico 36 2.250,00

Età>30Stipendio>2.000,00(Impiegati)Età>30Stipendio>2.000,00(Impiegati)

Operatori di manipolazione di relazioni

Specifici dell’algebra relazionale (non derivano dalle teoria degli insiemi)Permettono di manipolare relazioni per creare nuove relazione Ridenominazione Selezione Proiezione Join

ProiezioneData relazione r su insieme di attributi X e un sottoinsieme Y di X, la proiezione Y(r) è l’insieme di tuple su Y ottenute dalle tuple di r considerando solo i valori su YY(r) = {t[Y] | t r}

A B C

Proiezione su YY(r)

A B

ProiezionePer esempio: Impiegati(Cognome,Nome,Reparto,Capo) Cognome,Nome(Impiegati) ha attributi Cognome,

NomeRelazioni non devono contenere tuple ripetute Tuple uguali collassano in una sola

ProiezioneCognome

Nome

Reparto

Capo

Rossi Mario Vendite De RossiNeri Luca Vendite De RossiVerdi Nico Persona

leBaldi

Rossi Marco

Personale

BaldiReparto

Capo

Vendite De Rossi

Personale

Baldi

Impiegati

Reparto,Capo(Impiegati)

Tuple di una proiezioneUna proiezione Y(r) contiene al più tante tuple quante rSe Y è una superchiave di r, allora Y(r) contiene tante tuple quante rQuesto può accadere comunque anche se Y non è superchiave (basta che le tuple su Y siano casualmente tutte diverse tra loro)

Operatori di manipolazione di relazioni

Specifici dell’algebra relazionale (non derivano dalle teoria degli insiemi)Permettono di manipolare relazioni per creare nuove relazione Ridenominazione Selezione Proiezione Join

JoinOperatore che permette di correlare dati contenuti in relazioni diverse confrontando i valori delle tuple (modello relazionale basato su valori)

Join NaturaleTheta-Join

Join NaturalePermette di correlare dati contenuti in relazioni diverse confrontando attributi con stesso nomeProduce una relazione definita su unione di insiemi di attributi delle due relazioni su cui operaTuple del risultato: ottenute combinando le tuple dei due operandi con valore uguale su attributi comuni

Join NaturaleDate r1(X) e r2(Y), r1r2 è relazione su XY:

r1r2={t su XY | t[X]r1 e t[Y]r2}

Join NaturaleImpiegato

Reparto

Rossi VenditeNeri Produzio

neBianchi Produzio

ne

Reparto CapoProduzione

Mori

Vendite De Rossi

Rel1 Rel2

Rel1(Impiegato,Reparto) Rel2(Reparto,Capo)

X Y

Join Naturale

Impiegato

Reparto Capo

Rossi Vendite De Rossi

Neri Produzione

Mori

Bianchi Produzione

Mori

Impiegato

Reparto

Rossi VenditeNeri Produzio

neBianchi Produzio

ne

Reparto CapoProduzione

Mori

Vendite De Rossi

Rel1 Rel2

Rel1 Rel2

Join Naturale

Impiegato

Reparto Capo

Rossi Vendite De Rossi

Neri Produzione

Mori

Bianchi Produzione

Mori

Impiegato

Reparto

Rossi VenditeNeri Produzio

neBianchi Produzio

ne

Reparto CapoProduzione

Mori

Vendite De Rossi

Rel1 Rel2

Rel1 Rel2

Join NaturaleSe relazioni da combinare definite su stesso insieme di attributi, r1(X), r2(X)… r1r2 = r1r2 Cioè il join coincide con intersezione:

combina tuple con stessi valori di attributi su r1 e r2

Join Naturale

Reparto CapoVendite De

RossiProduzione

Mori

Reparto CapoAcquisti BaldiProduzione

Mori

Vendite Rossi

Reparto CapoContabilità

Tilli

Produzione

Mori

Vendite De Rossi

Rel1 Rel2

Rel1 Rel2

Join Naturale

Reparto CapoVendite De

RossiProduzione

Mori

Reparto CapoAcquisti BaldiProduzione

Mori

Vendite Rossi

Reparto CapoContabilità

Tilli

Produzione

Mori

Vendite De Rossi

Rel1 Rel2

Rel1 Rel2

Join NaturaleSe relazioni da combinare definite su insiemi di attributi disgiunti, r1(X), r2(Y) con XY=… condizione di corrispondenza tra tuple è sempre vera… r1r2=r1xr2 (prodotto cartesiano)Combina tutte le tuple di r1 con tutte quelle di r2

Join Naturale

Reparto Capo Impiegato

Progetto

Acquisti Baldi Mori P123Acquisti Baldi Baldi P124Produzione

Mori Mori P123

Produzione

Mori Bianchi P124

Reparto CapoAcquisti BaldiProduzione

Mori

Impiegato

Progetto

Mori P123Baldi R124

Rel1 Rel2

Rel1 Rel2

Join NaturaleNumero attributi di r1r2 somma numeri attributi di r1 e r2Spesso join fatto su chiave di relazione Per esempio:

Infrazioni(Codice,Data,Agent,Art,Prov,Numero) Auto(Prov,Numero,Proprietario,Indirizzo)

Spesso imposto vincolo di integrità referenziale tra attributi di join (per evitare che r1 faccia riferimento a valori inesistenti in r2)

Join Naturale

Prov

Numero

Proprietario

Indirizzo

RM 2F7643 Verdi Piero v. TigliRM 1A2396 Verdi Piero v. TigliRM 4E5432 Bini Luca v. AceriMI 2F7643 Luci Gino v. Aceri

Auto

Codice

Data Agente

Art

Prov

Numero

143256

25/10/03

567 44 RM 4E5432

987554

26/10/03

456 34 RM 4E5432

987557

26/10/03

456 34 RM 2F7643

630876

15/10/03

456 53 MI 2F7643

539856

12/10/03

567 44 MI 2F7643

Infrazioni

Join Naturale

Prov

Numero

Proprietario

Indirizzo

RM 2F7643 Verdi Piero v. TigliRM 1A2396 Verdi Piero v. TigliRM 4E5432 Bini Luca v. AceriMI 2F7643 Luci Gino v. Aceri

Auto

Codice

Data Agente

Art

Prov

Numero

143256

25/10/03

567 44 RM 4E5432

987554

26/10/03

456 34 RM 4E5432

987557

26/10/03

456 34 RM 2F7643

630876

15/10/03

456 53 MI 2F7643

539856

12/10/03

567 44 MI 2F7643

Infrazioni

Join NaturaleCodice

Data Agente

Art

Prov

Numero

Proprietario

Indirizzo

143256

25/10/03

567 44 RM 4E5432 Bini Luca v. Aceri

987554

26/10/03

456 34 RM 4E5432 Bini Luca v. Aceri

987557

26/10/03

456 34 RM 2F7643 Verdi Piero v. Tigli

630876

15/10/03

456 53 MI 2F7643 Luci Gino v. Aceri

539856

12/10/03

567 44 MI 2F7643 Luci Gino v. Aceri

Infrazioni Auto

•Tra Infrazioni e Auto esiste vincolo integrità referenziale•{Prov,Numero} è chiave di Auto•Quindi, ogni tupla di Infrazioni è combinata esattamente conuna tupla di Auto

Join completiDate r1(X) e r2(Y), r1r2 è completo se e solo se, per ogni tupla t1 di r1 esiste tupla t in r1r2 tale che t[X]=t1 e analogamente per r2

Join completiCardinalità di un insieme: il numero di elementi che appartengono al insieme Cardinalità di A: scritto |A|

Per esempio: |{a,b,d}|=3, ||=0

Join completiCardinalità di join: Se r1r2 è completo:max(|r1|,|r2|) |r1r2| |r1|x|r2|

Join completi

Impiegato

Progetto

Capo

Rossi P124 MoriNeri P124 MoriBianchi P124 MoriRossi P124 BruniNeri P124 BruniBianchi P124 Bruni

Impiegato

Progetto

Rossi P124Neri P124Bianchi P124

Progetto

Capo

P124 MoriP124 Bruni

Rel1 Rel2

Rel1 Rel2

Un esempio di join con |r1|x|r2| tuple

Join incompletiJoin incompleti hanno tuple senza corrispondenza, dette dangling tuples

Impiegato

Reparto

Rossi VenditeNeri Produzion

eBianchi Produzion

e

Reparto CapoProduzione

Mori

Acquisti Bruni

Rel1 Rel2

Impiegato

Reparto Capo

Rossi Vendite MoriNeri Produzion

eMori

Rel1 Rel2

Join incompletiCaso limite: se non ci sono tuple combinabili, risultato del join è relazione vuota (senza tuple)

Cardinalità di joinDate r1(X) e r2(Y):

0 |r1r2| |r1|x|r2|

Se r1 r2 completo:|r1r2| max(|r1|,|r2|)

Ogni tuple di r1 combinata con almeno 1 tupla di r2 e viceversa

Cardinalità di joinSe XY contiene chiave per r2

|r1r2| |r1|Ogni tuple di r1 combinata con al più 1 tupla di r2

Cardinalità di joinSe XY contiene chiave per r2 e c’è vincolo di integrità referenziale fra XY in r1 e la chiave di r2

|r1r2| = |r1|Ogni tuple di r1 combinata esattamente con 1 tupla di r2

Join esterniPer combinare sempre le tuple di due relazioni, anche quando non ci sono corrispondenze tra i valori degli attributi comuni, inserendo valori NULL in assenza di contropartiNon tralasciano tuple di operandi nel risultato

Join esterniJoin esterno sinistro: estende solo le tuple del primo operando Aggiunge tuple di r1 senza corrispettivo in

r2Join esterno destro:estende solo le tuple del primo operando Aggiunge tuple di r2

Join esterno completo: estende tuple di entrambi gli operandi Bilaterale

Join esterniImpiegato

Reparto

Rossi VenditeNeri Produzion

eBianchi Produzion

e

Reparto CapoProduzione

Mori

Acquisti Bruni

Rel1 Rel2

Impiegato

Reparto Capo

Rossi Vendite NULLNeri Produzion

eMori

Bianchi Produzione

Mori

Rel1 LEFT Rel2

Join esterniImpiegato

Reparto

Rossi VenditeNeri Produzion

eBianchi Produzion

e

Reparto CapoProduzione

Mori

Acquisti Bruni

Rel1 Rel2

Impiegato

Reparto Capo

Neri Produzione

Mori

Bianchi Produzione

Mori

NULL Acquisti Baldi

Rel1 RIGHT Rel2

Join esterniImpiegato

Reparto

Rossi VenditeNeri Produzion

eBianchi Produzion

e

Reparto CapoProduzione

Mori

Acquisti Bruni

Rel1 Rel2

Impiegato

Reparto Capo

Rossi Vendite NULLNeri Produzion

eMori

Bianchi Produzione

Mori

NULL Acquisti Baldi

Rel1 FULL Rel2

Theta-JoinServe per fare Join su relazioni senza attributi omonimiOperatore derivato: si ottiene come prodotto cartesiano seguito da selezione di tuple che verificano condizione di uguaglianza tra valori di attributi

r1 F r2 = F(r1 r2)

Theta-JoinImpiegato

Reparto

Rossi VenditeNeri Produzion

eBianchi Produzion

e

Divisione

Capo

Vendite BruniProduzione

Mori

Acquisti Baldi

Rel1 Rel2

Impiegato

Reparto Divisione Capo

Rossi Vendite Vendite NULLNeri Produzion

eProduzione

Mori

Bianchi Produzione

Produzione

Mori

Reparto=Divisione(Rel1 Rel2)

Theta-Join ed Equi-JoinTheta-Join: r1 F r2 = F(r1 r2)Condizione di selezione F è formula proposizionale come descritto per operatore di selezioneSe F è congiunzione di uguaglianze tra attributi di r1 e attributi di r2: theta-join detto equi-join

Theta-Join ed Equi-JoinPer esempio: Rel1(Impiegato,Reparto),

Rel2(Divisione,Capo)Reparto=Divisione(Rel1 Rel2)

Infrazioni(Codice,Data,Ag,Art,Prov,Num), Auto(Provincia,Targa,Prop,Indirizzo)

Prov=Provincia Num=Targa(Infrazioni Auto)

Theta-Join ed Equi-JoinTheta-join e equi-join più utili di join naturale Permettono di operare su relazioni

senza attributi in comune Join naturale simulabile mediante

ridenominazione, equi-join e proiezione

Theta-Join ed Equi-JoinPer esempio: R1(A,B,C), R2(B,C,D)R1R2 =

A,B,C,D(R1B=B’C=C’(B’,C’B,C(R2)))

Theta-Join ed Equi-JoinPer esempio: R1(A,B,C), R2(B,C,D)R1R2 =

A,B,C,D(R1B=B’C=C’(B’,C’B,C(R2)))

Join naturale Equi-join

Theta-Join ed Equi-JoinPer esempio: R1(A,B,C), R2(B,C,D)R1R2 =

A,B,C,D(R1B=B’C=C’(B’,C’B,C(R2)))

Si ridenomina R2 affinchè abbia attributi diversi da quelli di R1Equi-join tra R1 e R2 per selezionare tuple in corrispondenzaProiezione del risultato per eliminare attributi ridondanti