Date post: | 02-May-2015 |
Category: |
Documents |
Upload: | vanda-pandolfi |
View: | 218 times |
Download: | 0 times |
Algebra relazionale
Accesso ai dati di un DB
Aggiornamento di DB: funzione che, data istanza di DB, produce altra istanza di DB, sullo stesso schema Modifica, aggiunta, rimozione tuple
Interrogazione 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 DB
Aggiornamento e interrogazione vengono effettuati usando specifici linguaggi Per esempio: algebra relazionale
Algebra relazionale
Linguaggio procedurale di accesso a DB Si specificano operazioni complesse
descrivendo procedimento da usare per ottenere soluzione
Interrogazioni: espressioni complesse
Algebra relazionale
Algebra relazionale: basata su insieme di operatori Definiti su relazioni Producono relazioni come risultati
Operatori Insiemistici: unione, intersezione, differenza Specifici: ridenominazione, selezione,
proiezione, join
Operatori insiemistici
Relazioni: 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 relazioni
Date 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 relazioni
Matricola
Cognome
Età
9297 Neri 56
7432 Neri 39
9824 Verdi 38
Matricola
Cognome
Età
7274 Rossi 37
7432 Neri 39
9824 Verdi 38
Matricola
Cognome
Età
7274 Rossi 37
7432 Neri 39
9297 Neri 56
9824 Verdi 38
Laureati Dirigenti
Laureati Dirigenti
Differenza di relazioni
Date 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 relazioni
Matricola
Cognome
Età
9297 Neri 56
7432 Neri 39
9824 Verdi 38
Matricola
Cognome
Età
7274 Rossi 37
7432 Neri 39
9824 Verdi 38
Matricola
Cognome
Età
7274 Rossi 37
Laureati Dirigenti
Laureati - Dirigenti
Intersezione di relazioni
Date 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 relazioni
Matricola
Cognome
Età
9297 Neri 56
7432 Neri 39
9824 Verdi 38
Matricola
Cognome
Età
7274 Rossi 37
7432 Neri 39
9824 Verdi 38
Matricola
Cognome
Età
7432 Neri 39
9824 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 Figlio
Adamo Caino
Adamo Abele
Abramo Isacco
Abramo Ismaele
Madre Figlio
Eva Caino
Eva Set
Sara Isacco
Agar Ismaele
Paternità Maternità
Paternità Maternità ?
Ridenominazione di relazioni
Una ridenominazione:
Padre Figlio
Adamo Caino
Adamo Abele
Abramo Isacco
Abramo Ismaele
Genitore Figlio
Adamo Caino
Adamo Abele
Abramo Isacco
Abramo Ismaele
Paternità GenitorePadre(Paternità)
Ridenominazione di relazioni
Una ridenominazione:
Padre Figlio
Adamo Caino
Adamo Abele
Abramo Isacco
Abramo Ismaele
Genitore Figlio
Adamo Caino
Adamo Abele
Abramo Isacco
Abramo Ismaele
Paternità GenitorePadre(Paternità)GenitorePadre(Paternità)
Ridenominazione di relazioni
Una ridenominazione:
Padre Figlio
Adamo Caino
Adamo Abele
Abramo Isacco
Abramo Ismaele
Genitore Figlio
Adamo Caino
Adamo Abele
Abramo Isacco
Abramo Ismaele
Paternità GenitorePadre(Paternità)GenitorePadre(Paternità)
Ridenominazione di relazioni
Un’altra ridenominazione:
Madre Figlio
Eva Caino
Eva Set
Sara Isacco
Agar Ismaele
Genitore Figlio
Eva Caino
Eva Set
Sara Isacco
Agar Ismaele
Maternità GenitoreMadre(Maternità)
Ridenominazione di relazioni
Genitore Figlio
Adamo Caino
Adamo Abele
Abramo Isacco
Abramo Ismaele
Eva Caino
Eva Set
Sara Isacco
Agar Ismaele
GenitorePadre(Paternità) GenitoreMadre(Maternità)
Corretta applicazionedi unionerelazioni
Ridenominazione di relazioni
Cognome
Agenzia
Stipendio
Rossi Roma 45
Neri Milano 53
Imp
Ridenominazione di relazioni
Cognome
Agenzia
Stipendio
Rossi Roma 45
Neri Milano 53
Cognome
Fabbrica
Salario
Verdi Latina 33
Bruni 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 45
Neri Milano 53
Cognome
Fabbrica
Salario
Verdi Latina 33
Bruni 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
Selezione
Data 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
Selezione
F formula proposizionale: condizione di selezione formata da Operatori booleani:
(AND), (OR), (NOT)
Selezione
F 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,00
Neri Luca 40 1.500,00
Verdi Nico 36 2.250,00
Rossi Marco
40 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,00
Neri Luca 40 1.500,00
Verdi Nico 36 2.250,00
Rossi Marco
40 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
Proiezione
Data 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
Proiezione
Per esempio: Impiegati(Cognome,Nome,Reparto,Capo) Cognome,Nome(Impiegati) ha attributi Cognome,
Nome
Relazioni non devono contenere tuple ripetute Tuple uguali collassano in una sola
ProiezioneCognome
Nome
Reparto
Capo
Rossi Mario Vendite De Rossi
Neri Luca Vendite De Rossi
Verdi Nico Personale
Baldi
Rossi Marco
Personale
BaldiReparto
Capo
Vendite De Rossi
Personale
Baldi
Impiegati
Reparto,Capo(Impiegati)
Tuple di una proiezione
Una 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
Join
Operatore che permette di correlare dati contenuti in relazioni diverse confrontando i valori delle tuple (modello relazionale basato su valori)
Join NaturaleTheta-Join
Join Naturale
Permette 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 Naturale
Date r1(X) e r2(Y), r1r2 è relazione su XY:
r1r2={t su XY | t[X]r1 e t[Y]r2}
Join Naturale
Impiegato
Reparto
Rossi Vendite
Neri Produzione
Bianchi Produzione
Reparto Capo
Produzione
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 Vendite
Neri Produzione
Bianchi Produzione
Reparto Capo
Produzione
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 Vendite
Neri Produzione
Bianchi Produzione
Reparto Capo
Produzione
Mori
Vendite De Rossi
Rel1 Rel2
Rel1 Rel2
Join Naturale
Se 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 Capo
Vendite De Rossi
Produzione
Mori
Reparto Capo
Acquisti Baldi
Produzione
Mori
Vendite Rossi
Reparto Capo
Contabilità
Tilli
Produzione
Mori
Vendite De Rossi
Rel1 Rel2
Rel1 Rel2
Join Naturale
Reparto Capo
Vendite De Rossi
Produzione
Mori
Reparto Capo
Acquisti Baldi
Produzione
Mori
Vendite Rossi
Reparto Capo
Contabilità
Tilli
Produzione
Mori
Vendite De Rossi
Rel1 Rel2
Rel1 Rel2
Join Naturale
Se 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 P123
Acquisti Baldi Baldi P124
Produzione
Mori Mori P123
Produzione
Mori Bianchi P124
Reparto Capo
Acquisti Baldi
Produzione
Mori
Impiegato
Progetto
Mori P123
Baldi R124
Rel1 Rel2
Rel1 Rel2
Join Naturale
Numero 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. Tigli
RM 1A2396 Verdi Piero v. Tigli
RM 4E5432 Bini Luca v. Aceri
MI 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. Tigli
RM 1A2396 Verdi Piero v. Tigli
RM 4E5432 Bini Luca v. Aceri
MI 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
Codice
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 completi
Date 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 completi
Cardinalità di un insieme: il numero di elementi che appartengono al insieme Cardinalità di A: scritto |A|
Per esempio: |{a,b,d}|=3, ||=0
Join completi
Cardinalità di join: Se r1r2 è completo:max(|r1|,|r2|) |r1r2| |r1|x|r2|
Join completi
Impiegato
Progetto
Capo
Rossi P124 Mori
Neri P124 Mori
Bianchi P124 Mori
Rossi P124 Bruni
Neri P124 Bruni
Bianchi P124 Bruni
Impiegato
Progetto
Rossi P124
Neri P124
Bianchi P124
Progetto
Capo
P124 Mori
P124 Bruni
Rel1 Rel2
Rel1 Rel2
Un esempio di join con |r1|x|r2| tuple
Join incompleti
Join incompleti hanno tuple senza corrispondenza, dette dangling tuples
Impiegato
Reparto
Rossi Vendite
Neri Produzione
Bianchi Produzione
Reparto Capo
Produzione
Mori
Acquisti Bruni
Rel1 Rel2
Impiegato
Reparto Capo
Rossi Vendite Mori
Neri Produzione
Mori
Rel1 Rel2
Join incompleti
Caso limite: se non ci sono tuple combinabili, risultato del join è relazione vuota (senza tuple)
Cardinalità di join
Date 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 join
Se XY contiene chiave per r2|r1r2| |r1|
Ogni tuple di r1 combinata con al più 1 tupla di r2
Cardinalità di join
Se 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 esterni
Per 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 esterni
Join esterno sinistro: estende solo le tuple del primo operando Aggiunge tuple di r1 senza corrispettivo in
r2
Join esterno destro:estende solo le tuple del primo operando Aggiunge tuple di r2
Join esterno completo: estende tuple di entrambi gli operandi Bilaterale
Join esterni
Impiegato
Reparto
Rossi Vendite
Neri Produzione
Bianchi Produzione
Reparto Capo
Produzione
Mori
Acquisti Bruni
Rel1 Rel2
Impiegato
Reparto Capo
Rossi Vendite NULL
Neri Produzione
Mori
Bianchi Produzione
Mori
Rel1 LEFT Rel2
Join esterni
Impiegato
Reparto
Rossi Vendite
Neri Produzione
Bianchi Produzione
Reparto Capo
Produzione
Mori
Acquisti Bruni
Rel1 Rel2
Impiegato
Reparto Capo
Neri Produzione
Mori
Bianchi Produzione
Mori
NULL Acquisti Baldi
Rel1 RIGHT Rel2
Join esterni
Impiegato
Reparto
Rossi Vendite
Neri Produzione
Bianchi Produzione
Reparto Capo
Produzione
Mori
Acquisti Bruni
Rel1 Rel2
Impiegato
Reparto Capo
Rossi Vendite NULL
Neri Produzione
Mori
Bianchi Produzione
Mori
NULL Acquisti Baldi
Rel1 FULL Rel2
Theta-Join
Serve 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-Join
Impiegato
Reparto
Rossi Vendite
Neri Produzione
Bianchi Produzione
Divisione
Capo
Vendite Bruni
Produzione
Mori
Acquisti Baldi
Rel1 Rel2
Impiegato
Reparto Divisione Capo
Rossi Vendite Vendite NULL
Neri Produzione
Produzione
Mori
Bianchi Produzione
Produzione
Mori
Reparto=Divisione(Rel1 Rel2)
Theta-Join ed Equi-Join
Theta-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-Join
Per 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-Join
Theta-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-Join
Per 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-Join
Per 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-Join
Per 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