Algebra relazionale. Accesso ai dati di un DB Aggiornamento di DB: funzione che, data istanza di DB,...

transcript

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

9297 Neri 56

7432 Neri 39

9824 Verdi 38

Matricola

Cognome

7274 Rossi 37

7432 Neri 39

9824 Verdi 38

Matricola

Cognome

7274 Rossi 37

7432 Neri 39

9297 Neri 56

9824 Verdi 38

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

9297 Neri 56

7432 Neri 39

9824 Verdi 38

Matricola

Cognome

7274 Rossi 37

7432 Neri 39

9824 Verdi 38

Matricola

Cognome

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

9297 Neri 56

7432 Neri 39

9824 Verdi 38

Matricola

Cognome

7274 Rossi 37

7432 Neri 39

9824 Verdi 38

Matricola

Cognome

7432 Neri 39

9824 Verdi 38

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

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

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à ?

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

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

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

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

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

Cognome

Agenzia

Stipendio

Rossi Roma 45

Neri Milano 53

Cognome

Agenzia

Stipendio

Rossi Roma 45

Neri Milano 53

Cognome

Fabbrica

Salario

Verdi Latina 33

Bruni Monza 32

Imp Op

Cognome

Sede Retribuzione

Rossi Roma

Neri Milano

Verdi Latina

Bruni Monza

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)

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

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

GenitorePadre(Paternità): omesso Figlio

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

Selezione secondo FF(r)

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

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

Stipendio

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

SelezioneCognome

Stipendio

Rossi Mario 25 1.000,00

Neri Luca 40 1.500,00

Rossi Marco

40 1.900,00

Impiegati

Cognome

Stipendio

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

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}

Proiezione su YY(r)

Proiezione

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

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

ProiezioneCognome

Reparto

Rossi Mario Vendite De Rossi

Neri Luca Vendite De Rossi

Verdi Nico Personale

Rossi Marco

Personale

BaldiReparto

Vendite De Rossi

Personale

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)

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

Vendite De Rossi

Rel1 Rel2

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

Join Naturale

Impiegato

Reparto Capo

Rossi Vendite De Rossi

Neri Produzione

Bianchi Produzione

Impiegato

Reparto

Rossi Vendite

Neri Produzione

Bianchi Produzione

Reparto Capo

Produzione

Vendite De Rossi

Rel1 Rel2

Join Naturale

Impiegato

Reparto Capo

Rossi Vendite De Rossi

Neri Produzione

Bianchi Produzione

Impiegato

Reparto

Rossi Vendite

Neri Produzione

Bianchi Produzione

Reparto Capo

Produzione

Vendite De Rossi

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

Reparto Capo

Acquisti Baldi

Produzione

Vendite Rossi

Reparto Capo

Contabilità

Produzione

Vendite De Rossi

Rel1 Rel2

Join Naturale

Reparto Capo

Vendite De Rossi

Produzione

Reparto Capo

Acquisti Baldi

Produzione

Vendite Rossi

Reparto Capo

Contabilità

Produzione

Vendite De Rossi

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

Impiegato

Progetto

Mori P123

Baldi R124

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

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

Codice

Data Agente

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

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

Codice

Data Agente

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

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

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

P124 Mori

P124 Bruni

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

Acquisti Bruni

Rel1 Rel2

Impiegato

Reparto Capo

Rossi Vendite Mori

Neri Produzione

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

Se XY contiene chiave per r2|r1r2| |r1|

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

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

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

Acquisti Bruni

Rel1 Rel2

Impiegato

Reparto Capo

Rossi Vendite NULL

Neri Produzione

Bianchi Produzione

Rel1 LEFT Rel2

Join esterni

Impiegato

Reparto

Rossi Vendite

Neri Produzione

Bianchi Produzione

Reparto Capo

Produzione

Acquisti Bruni

Rel1 Rel2

Impiegato

Reparto Capo

Neri Produzione

Bianchi Produzione

NULL Acquisti Baldi

Rel1 RIGHT Rel2

Join esterni

Impiegato

Reparto

Rossi Vendite

Neri Produzione

Bianchi Produzione

Reparto Capo

Produzione

Acquisti Bruni

Rel1 Rel2

Impiegato

Reparto Capo

Rossi Vendite NULL

Neri Produzione

Bianchi Produzione

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

Vendite Bruni

Produzione

Acquisti Baldi

Rel1 Rel2

Impiegato

Reparto Divisione Capo

Rossi Vendite Vendite NULL

Neri Produzione

Produzione

Bianchi Produzione

Produzione

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

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

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

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

Algebra relazionale. Accesso ai dati di un DB Aggiornamento di DB: funzione che, data istanza di DB,...

Documents