ALGEBRA RELAZIONALEALGEBRA RELAZIONALE
Algebra Relazionale 2
Le basi di dati rappresentano le informazioni di interesse per applicazioni che gestiscono i dati
E’ importante considerare linguaggi per la specifica di operazioni sui dati stessi, che siano legati al modello dei dati scelto (modello relazionale)
Algebra Relazionale 3
Linguaggi per basi di dati
operazioni sullo schema DDL: data definition language per definire lo
schema VDL: view definition language per definire le
viste d’utente operazioni sui dati
DML: data manipulation language interrogazione ("query") inserimento, cancellazione e aggiornamento dei dati
Algebra Relazionale 4
Linguaggi per l’interrogazione
Una base di dati richiede un insieme di operazioni che consentano all’utente di specificare le richieste di recupero fondamentali
Le operazioni di questo tipo producono nuove relazioni, sulle quali è ulteriormente possibile applicare operazioni
Algebra Relazionale 5
Linguaggi di interrogazioneper basi di dati relazionali
Dichiarativi (di alto livello) le espressioni specificano le proprietà del
risultato ("che cosa")
Procedurali (di basso livello) specificano le modalità di generazione del
risultato ("come")
Algebra Relazionale 6
Linguaggi di interrogazione
Algebra relazionale: procedurale (teorico) Calcolo relazionale: dichiarativo (teorico) SQL (Structured Query Language): combina
gli aspetti dichiarativi del calcolo e quelli procedurali dell’algebra (linguaggio reale)
Algebra Relazionale 7
Algebra relazionale
Insieme di operatori, definiti su relazioni, che producono ancora relazioni come risultati insiemistici: unione, intersezione, differenza specifici: ridenominazione, selezione, proiezione join: join naturale, prodotto cartesiano, theta-join raggruppamento: divisione
Algebra Relazionale 8
Operatori insiemistici
le relazioni sono insiemi i risultati debbono essere relazioni
- è sensato applicare le operazioni insiemistiche classiche di unione,intersezione, differenza
- è possibile applicare solo a relazioni definite sugli stessi attributi
Algebra Relazionale 9
Laureati
Matricola
74329824
Età
5445
Nome
NeriVerdi
7274 42Rossi
Quadri
Matricola
74329824
9297Età
5445
33Nome
NeriVerdi
Neri
Laureati Quadri
Matricola EtàNome
7432 54Neri9824 45Verdi9297 33Neri
7274 42Rossi7432 54Neri9824 45Verdi
7274 42Rossi7432 54Neri9824 45Verdi9297 33Neri
7432 54Neri9824 45Verdi9297 33Neri
7274 42Rossi
Unione
Algebra Relazionale 10
Laureati
Matricola
74329824
Età
5445
Nome
NeriVerdi
7274 42Rossi
Quadri
Matricola
74329824
9297Età
5445
33Nome
NeriVerdi
Neri
Laureati Quadri
Matricola EtàNome7432 54Neri9824 45Verdi
7432 54Neri9824 45Verdi
7432 54Neri9824 45Verdi
7432 54Neri9824 45Verdi
Intersezione
Algebra Relazionale 11
Laureati
Matricola EtàNome
7432 54Neri9824 45Verdi
7274 42Rossi
Quadri
Matricola
74329824
9297Età
5445
33Nome
NeriVerdi
Neri
Laureati – QuadriMatricola EtàNome
7432 54Neri9824 45Verdi
7274 42Rossi7432 54Neri9824 45Verdi
7274 42Rossi
Differenza
Algebra Relazionale 12
Paternità
Padre Figlio
Adamo CainoAbramo Isacco
Adamo Abele
Maternità
Madre Figlio
Eva SetSara Isacco
Eva Abele
Paternità Maternità
??
Una unione sensata ma impossibile
Algebra Relazionale 13
Ridenominazione
operatore unario "modifica lo schema" lasciando inalterata
l'istanza dell'operando, cambia solo il nome degli attributi
Algebra Relazionale 14
Ridenominazione: definizione formale
Siano R una relazione su X, e Y un altro insieme di attributi con la stessa cardinalità
X = {A1,……. Ak}
Y = {B1,……. Bk}La ridenominazione
A1,……. Ak B1,……. Bk (R)contiene una ennupla t’ per ogni ennupla t in R tale che:
t’ è una ennupla su Y t’[Bi]=t[Ai], per ogni i=1,…,k
Algebra Relazionale 15
Paternità
Padre Figlio
Adamo CainoAbramo Isacco
Adamo Abele
Genitore Padre (Paternità)
Padre Figlio
Adamo CainoAbramo Isacco
Adamo AbeleGenitore
Algebra Relazionale 16
Paternità
Padre Figlio
Adamo CainoAbramo Isacco
Adamo Abele
Maternità
Madre Figlio
Eva SetSara Isacco
Eva Abele
Genitore Padre (Paternità)
Genitore Madre (Maternità)
Genitore Figlio
Adamo CainoAbramo Isacco
Adamo Abele
Genitore Figlio
Eva SetSara Isacco
Eva Abele
Algebra Relazionale 17
Genitore Padre (Paternità)
Genitore Madre (Maternità)
Genitore Figlio
Adamo CainoAbramo Isacco
Adamo Abele
Genitore Figlio
Eva SetSara Isacco
Eva Abele
Genitore Figlio
Adamo CainoAbramo Isacco
Adamo Abele
Eva SetSara Isacco
Eva Abele
Genitore Padre (Paternità)
Genitore Madre (Maternità)
Sede, Retribuzione Ufficio, Stipendio (Impiegati)
Sede, Retribuzione Fabbrica, Salario (Operai)
Impiegati Cognome
NeriRossi
Ufficio
MilanoRoma
Stipendio
6455
Operai Cognome
VerdiBruni
Fabbrica
LatinaMonza
Salario
5545
Cognome RetribuzioneSede
NeriRossi
6455
MilanoRoma
VerdiBruni
LatinaMonza
5545
Algebra Relazionale 19
Selezione
operatore unario su una tabella produce un risultato che
ha lo stesso schema della relazione di partenza (colonne della tabella)
contiene un sottoinsieme delle ennuple dell'operando (righe della tabella),
quelle che soddisfano una condizione
Algebra Relazionale 20
Selezione
A B C A B C
Algebra Relazionale 21
Impiegati Cognome Filiale StipendioMatricola
Neri Milano 645998Rossi Roma 557309
Neri Napoli 645698Milano Milano 449553
impiegati che: guadagnano più di 50 guadagnano più di 50 e lavorano a Milano hanno lo stesso nome della filiale presso cui
lavorano
Algebra Relazionale 22
Selezione, sintassi e semantica
sintassi
Condizione (Operando) Condizione: espressione booleana Operando: una espressione dell’algebra relazionale
semantica il risultato è una relazione sugli stessi attributi che
contiene le ennuple dell'operando che soddisfano la condizione
Algebra Relazionale 23
Condizione di selezione
F formula proposizionale formata da• operatori booleani: (AND), (OR), ¬ (NOT)• condizioni atomiche: termini che possono contenere
confronti fra attributi, o fra attributi e costanti. Hannoforma: AB oppure Ac dove
– operatore di confronto (=, , >, <, , )– A, B attributi in X– c costante compatibile con dominio di
attributo (A) con cui c viene confrontata
Algebra Relazionale 24
Condizioni di selezione, esempi
Esempi: (Stipendio > 50)
Filiale='Milano'
Cognome = Filiale
(Stipendio > 50) AND (Filiale='Milano')
NOT (Cognome='Neri')
Algebra Relazionale 25
Cognome Filiale StipendioMatricola
Neri Milano 645998Rossi Roma 557309
Neri Napoli 645698Milano Milano 449553
Impiegati
Milano Milano 449553 Neri Napoli 645698
impiegati che guadagnano più di 50
Stipendio > 50 (Impiegati)
Algebra Relazionale 26
Impiegati Cognome Filiale StipendioMatricola
Neri Milano 645998Rossi Roma 557309
Neri Napoli 645698Milano Milano 449553
impiegati che guadagnano più di 50 e lavorano a Milano
Stipendio > 50 AND Filiale = 'Milano' (Impiegati)
Rossi Roma 557309
Neri Napoli 645698Milano Milano 449553
Neri Milano 645998
Algebra Relazionale 27
Impiegati Cognome Filiale StipendioMatricola
Neri Milano 645998Rossi Roma 557309
Neri Napoli 645698Milano Milano 449553
impiegati che hanno lo stesso nome della filiale presso cui lavorano
Cognome = Filiale(Impiegati)
Neri Milano 645998Rossi Roma 557309
Neri Napoli 645698
Milano Milano 449553
Algebra Relazionale 28
Osservazioni
l’operazione di selezione è commutativa
<Cond1> ( <Cond2> (R)) =
<Cond2> ( <Cond1> (R)) =
<Cond1> AND <Cond2> (R) il numero delle t-uple della relazione R dopo
l’applicazione di una selezione è minore o uguale al numero delle t-uple di R
| <Cond> (R) | | R |
Algebra Relazionale 29
Selezione con valori nulli
Cognome Filiale EtàMatricola
Neri Milano 455998
Rossi Roma 327309Bruni Milano NULL9553
Impiegati
Età > 40 (Impiegati)
• la condizione atomica è vera solo per valori non nulli
Algebra Relazionale 30
Un risultato non desiderabile
Età>30 (Persone) Età30 (Persone) Persone Perché? Perché le selezioni vengono valutate
separatamente! Ma anche
Età>30 Età30 (Persone) Persone Perché? Perché anche le condizioni atomiche
vengono valutate separatamente!
Algebra Relazionale 31
Età > 40 (Impiegati)
la condizione atomica è vera solo per valori non nulli
per riferirsi ai valori nulli esiste la apposita di condizione:
IS NULL
Algebra Relazionale 32
A questo punto:
Età>30 (Persone) Età30 (Persone) Età IS NULL
(Persone) =
Età>30 Età30 (Età IS NULL) (Persone) =
Persone
Algebra Relazionale 33
Logica con il valore NULL
Oltre ai valori di verità Vero (V) e Falso (F), si introduce NULL (?)
NOT ( A IS NULL) si scrive anche A IS NOT NULL
Algebra Relazionale 35
Cognome Filiale EtàMatricola
Neri Milano 455998Rossi Roma 327309
Bruni Milano NULL9553
Impiegati
Neri Milano 455998Bruni Milano NULL9553
(Età > 40) OR (Età IS NULL) (Impiegati)
Neri Milano 455998Bruni Milano NULL9553
Algebra Relazionale 36
Selezione e proiezione
operatori "ortogonali" selezione:
decomposizione orizzontale
proiezione: decomposizione verticale
selezione
proiezione
Algebra Relazionale 38
Proiezione
operatore unario su una tabella produce un risultato che
ha parte degli attributi della tabella contiene ennuple (righe) cui contribuiscono tutte
le ennuple della tabella iniziale
Algebra Relazionale 39
Impiegati Cognome Filiale StipendioMatricola
Neri Milano 645998Neri Napoli 557309
Rossi Roma 645698Rossi Roma 449553
per tutti gli impiegati:matricola e cognomecognome e filiale
Algebra Relazionale 40
Proiezione, sintassi e semantica
sintassi
<ListaAttributi> (Operando)
<ListaAttributi> è un elenco di attributi di Operando
Operando è una espressione nell’algebra relazionale
semantica il risultato contiene le ennuple ottenute da tutte le
ennuple dell'operando ristrette agli attributi nella lista
Algebra Relazionale 41
Cognome Filiale StipendioMatricola
Neri Milano 645998Neri Napoli 557309
Rossi Roma 645698Rossi Roma 449553
matricola e cognome di tutti gli impiegati
Matricola, Cognome (Impiegati)
Algebra Relazionale 42
Cognome Filiale StipendioMatricola
Neri Milano 645998Neri Napoli 557309
Rossi Roma 645698Rossi Roma 449553
cognome e filiale di tutti gli impiegati
Cognome, Filiale (Impiegati)
Algebra Relazionale 43
Cardinalità delle proiezioni
una proiezione contiene al più tante ennuple quante l'operando può contenerne di meno
se X è una superchiave di R, allora X(R) contiene esattamente tante ennuple quante R
Algebra Relazionale 44
Selezione e proiezione
Combinando selezione e proiezione, possiamo estrarre interessanti informazioni da una relazione
Cond ( A,B,C (R) ) = ( A,B,C Cond (R) ) ?
Sono commutative a certe condizioni !
Algebra Relazionale 45
Cognome Filiale StipendioMatricola
Neri Milano 645998Rossi Roma 557309
Neri Napoli 645698Milano Milano 449553 Milano Milano 449553 Neri Napoli 645698
matricola e cognome degli impiegati che guadagnano più di 50
Stipendio > 50 (Impiegati) Matricola,Cognome ( )
Algebra Relazionale 46
combinando selezione e proiezione, possiamo estrarre informazioni da una relazione
non possiamo però correlare informazioni presenti in relazioni diverse
Algebra Relazionale 47
Join
il join è l'operatore più interessante dell'algebra relazionale
permette di correlare dati in relazioni diverse sfrutta la caratteristica fondamentale del
modello relazionale, che è quella di essere basato su valori
Idea del join naturalematricola cognome data_nasc
2021 Rossi 1-3-1975
2424 Bianchi 23-3-1974
3445 Neri 2-2-1975
matricola corso voto
2021 Basi dati 28
2021 Calcolo 25
3445 Algebra 30
matricola cognome data_nasc corso voto
2021 Rossi 1-3-1975 Basi dati 28
2021 Rossi 1-3-1975 Calcolo 25
3545 Neri 2-2-1975 Algebra 30
2021 Rossi 1-3-1975 Basi dati 28
2021 Rossi 1-3-1975 2021 Basi dati 28
2021 Rossi 1-3-1975 Calcolo 25
2021 Rossi 1-3-1975
2021 Calcolo 25
3445 Neri 2-2-1975 3445 Algebra 30
3445 Neri 2-2-1975 Algebra 30
Algebra Relazionale 49
Join naturale
operatore binario (generalizzabile a più relazioni)
produce un risultato sull'unione degli attributi degli operandi
(schema) con ennuple costruite ciascuna a partire da una
ennupla di ognuno degli operandi (istanza)
Algebra Relazionale 50
Join, sintassi e semantica
R1(X1), R2(X2)
R1 R2 è una relazione su X1X2
{ t su X1 X2 : esistono t1R1e t2R2
con t[X1] =t1 [X1] e t[X2] =t2 [X2] }
Algebra Relazionale 51
Join, proprietà
Il join naturale è commutativo:
R1 R2 = R2 R1
Il join naturale è associativo:
( R1 R2 ) R3 = R1 ( R2 R3 )
Matricola Cognome Nome6554 Rossi Mario8765 Neri Paolo
3456 Rossi Maria9283 Verdi Luisa
studenti
Corso Titolo Docente01 Analisi Mario02 Chimica Bruni04 Chimica Verdi
corsi
Matricola Voto Corso3456 30 043456 24 029283 28 01
esami
6554 26 01
(studenti esami) ((studenti esami) corsi )
A MoriB Bruni
Reparto CapoRossi ANeri B
Bianchi B
Impiegato Reparto
Rossi A MoriNeri B Bruni
Impiegato Reparto Capo
Bianchi B Bruni
Rossi ANeri B
Bianchi B
Rossi ANeri B
Bianchi B
A MoriB BruniA MoriB BruniB BruniB Bruni
ogni ennupla contribuisce al risultato:join completo
Algebra Relazionale 54
Neri B MoriImpiegato Reparto Capo
Bianchi B Mori
Impiegato RepartoRossi ANeri B
Bianchi B
Reparto CapoB MoriC Bruni
AC
Un join non completo
Algebra Relazionale 55
Impiegato RepartoRossi ANeri B
Bianchi B
Reparto CapoD MoriC Bruni
Impiegato Reparto Capo
Un join vuoto
Algebra Relazionale 56
Rossi B Mori
Neri B Mori
Impiegato Reparto Capo
Bianchi B Bruni
Rossi ANeri B
Impiegato RepartoRossi ANeri B
Rossi BNeri B
A MoriB Bruni
Reparto CapoA MoriB BruniB MoriB BruniB BruniB Bruni
Rossi B Bruni
Un join completo, con n x m ennuple
Ogni n-upla di ciascuna tabella è combinabile con tutte le n-uple dell’altro
Algebra Relazionale 57
Cardinalità del join
Il join di R1(A) e R2(B) contiene un numero di ennuple compreso fra zero e il prodotto di |R1| e |R2|
Algebra Relazionale 58
Impiegato RepartoRossi ANeri B
Bianchi B
Rossi A MoriImpiegato Reparto Capo
Neri B Bruni
Impiegato CapoRossi MoriNeri BruniNeri Bianchi
se il join coinvolge una chiave di R1 allora il numero di ennuple è compreso tra zero e |R2|
Neri B Bianchi
Verdi Bianchi
Algebra Relazionale 59
Impiegato RepartoRossi ANeri B
Bianchi B
Rossi A MoriImpiegato Reparto Capo
Neri B Bruni
Impiegato CapoRossi MoriNeri BruniNeri Bianchi
se il join coinvolge una chiave di R1 e c’è un vincolo di integrità allora il numero di ennuple è compreso uguale a |R2|
Neri B Bianchi
Algebra Relazionale 60
Cardinalità del join, riepilogo
R1(A,B) , R2 (B,C) in generale:
0 |R1 R2| |R1| · |R2| se B è chiave in R1
0 |R1 R2| |R2| se B è chiave in R1 ed esiste vincolo di
integrità referenziale fra B (in R2) e R1
|R1 R2| = |R2|
Algebra Relazionale 61
Join naturale e valori nulli
Algebra Relazionale 62
Impiegato RepartoRossi ANeri B
Bianchi B
Reparto CapoB MoriC Bruni
Neri B MoriImpiegato Reparto Capo
Bianchi B Mori
AC
Join, una difficoltà
alcune ennuple non contribuiscono al risultato: vengono "tagliate fuori'': si possono omettere informazioni importanti
Algebra Relazionale 63
Join esterno
Il join esterno estende, con valori nulli, le ennuple che verrebbero tagliate fuori da un join (naturale)
esiste in tre versioni: sinistro, destro, completo
Algebra Relazionale 64
Join esterno
sinistro: prevede che tutte le ennuple del primo operando, estendendole con valori nulli, se necessario, diano un contributo al join
destro: ... del secondo operando ... completo: … di entrambi gli operandi … OSSERVAZIONE: il Join esterno non è commutativo
Impiegato RepartoRossi ANeri B
Bianchi B
ImpiegatiReparto Capo
B MoriC Bruni
Reparti
Neri B MoriImpiegato Reparto Capo
Bianchi B Mori
Impiegati LEFT Reparti
C
Rossi A NULL
ARossi
Impiegato RepartoRossi ANeri B
Bianchi B
ImpiegatiReparto Capo
B MoriC Bruni
Reparti
Neri B MoriImpiegato Reparto Capo
Bianchi B Mori
Impiegati RIGHT Reparti
A
NULL C Bruni
C Bruni
Impiegato RepartoRossi ANeri B
Bianchi B
ImpiegatiReparto Capo
B MoriC Bruni
Reparti
Neri B MoriImpiegato Reparto Capo
Bianchi B Mori
Impiegati FULL Reparti
NULL C Bruni
C BruniARossi
Rossi A NULL
Matr Cognome Nome Data di nascita6554 Rossi Mario 05/12/19784678 Neri Paolo 03/11/1976
3456 Rossi Maria 01/02/19789283 Verdi Luisa 12/11/1979
studenti
Codice Titolo Docente01 Analisi Mari02 Chimica Mari04 Chimica Verdi
corsiCorso
04
esami
Matr Voto Codice
3456 30 04
3456 24 02
9283 30 01
6554 26 01
esami
Esercizio 1
Determinare i corsi tenuti dal Prof. Mari
Titolo ( Docente=‘Mari’(corsi) )
Matr Cognome Nome Data di nascita6554 Rossi Mario 05/12/19784678 Neri Paolo 03/11/1976
3456 Rossi Maria 01/02/19789283 Verdi Luisa 12/11/1979
studenti
Codice Titolo Docente01 Analisi Mari02 Chimica Mari04 Chimica Verdi
corsiCorso
04
esami
Matr Voto Codice
3456 30 04
3456 24 02
9283 30 01
6554 26 01
esami
Esercizio 2
Determinare nome, cognome e numero di matricola degli studenti che hanno ricevuto la votazione di 30
Nome, Cognome, Matr ( Voto=30( esami studenti ))
Matr Cognome Nome Data di nascita6554 Rossi Mario 05/12/19784678 Neri Paolo 03/11/1976
3456 Rossi Maria 01/02/19789283 Verdi Luisa 12/11/1979
studenti
Codice Titolo Docente01 Analisi Mari02 Chimica Mari04 Chimica Verdi
corsi
Corso
04
esami
Matr Voto Codice
3456 30 04
3456 24 02
9283 30 01
6554 26 01
esami
Esercizio 3
Determinare il nome e il cognome degli studenti che hanno sostenuto l'esame di Analisi
Algebra Relazionale 71
Matr Cognome Nome Data di nascita6554 Rossi Mario 05/12/19784678 Neri Paolo 03/11/1982
3456 Rossi Maria 01/02/19839283 Verdi Luisa 12/11/1979
studenti
Codice Titolo Docente01 Analisi Mari02 Chimica Mari04 Chimica Verdi
corsi
Corso
04
esami
Matr Voto Codice
3456 30 04
3456 24 01
9283 30 01
6554 26 01
esami
Esercizio 4
Determinare nome, cognome ed eventuali esami sostenuti da tutti gli studenti del corso di laurea che hanno più di 25 anni.
Algebra Relazionale 72
Matr Cognome Nome Data di nascita6554 Rossi Mario 05/12/19784678 Neri Paolo 03/11/1982
3456 Rossi Maria 01/02/19839283 Verdi Luisa 12/11/1979
studenti
Codice Titolo Docente01 Analisi Mari02 Chimica Mari04 Chimica Verdi
corsi
Corso
04
esami
Matr Voto Codice
3456 30 04
3456 24 01
9283 30 01
6554 26 01
esami
Esercizio 5
Determinare nome, cognome degli studenti del corso di laurea che non hanno sostenuto alcun esame.
Join e proiezioniImpiegato Reparto
Rossi ANeri B
Bianchi B
Reparto CapoB MoriC Bruni
Neri B MoriImpiegato Reparto Capo
Bianchi B Mori
Impiegato RepartoNeri B
Bianchi B
Reparto CapoB Mori
Proiezioni e join
Neri B MoriImpiegato Reparto Capo
Bianchi B BruniVerdi A Bini
Neri BImpiegato Reparto
Bianchi BVerdi A
B MoriReparto Capo
B BruniA Bini
Verdi A Bini
Neri B MoriImpiegato Reparto Capo
Bianchi B BruniNeri B Bruni
Bianchi B Mori
Algebra Relazionale 75
Join e proiezioni
R 1(X1), R 2(X2)
X1 (R 1 R2 ) R 1
R(X), X = X1 X2
( X1 (R)) ( X2
(R)) R
Algebra Relazionale 76
Prodotto cartesiano
Che cosa accade se si effettua un join naturale su relazioni senza attributi in comune?
Prodotto cartesiano tra le due relazioni contiene sempre un numero di ennuple pari al
prodotto delle cardinalità degli operandi (le ennuple sono tutte combinabili )
Rossi ANeri B
Bianchi B
Impiegato Reparto
Impiegati
A MoriB BruniB BruniB Bruni
Codice Capo
Reparti
Impiegati Reparti Impiegato Reparto CapoCodice
Rossi A MoriAAARossi A B BruniNeri B MoriANeri B B Bruni
Bianchi B MoriABianchi B B Bruni
Algebra Relazionale 78
Il prodotto cartesiano, in pratica, ha senso solo se seguito da selezione:
Condizione (R1 R2)
L'operazione viene chiamata theta-join e indicata con:
R1 Cond R2
Algebra Relazionale 79
Perché "theta-join"?
La condizione C è spesso una congiunzione (AND) di atomi di confronto A1 A2 dove è uno degli operatori di confronto (=, >, <, …)
se l'operatore è sempre l'uguaglianza (=) allora si parla di equi-join
Rossi ANeri B
Bianchi B
Impiegato Reparto
Impiegati
A MoriB BruniB BruniB Bruni
Codice Capo
Reparti
Impiegati Reparto=Codice Reparti Impiegato Reparto CapoCodice
Rossi A MoriAAARossi A B BruniNeri B MoriANeri B B Bruni
Bianchi B MoriABianchi B B Bruni
Rossi A MoriAAANeri B B Bruni
Bianchi B B Bruni
Equi-join
Algebra Relazionale 81
Rossi ANeri B
Bianchi B
Impiegato Reparto
Impiegati
A MoriB BruniB BruniB Bruni
Reparto Capo
Reparti
Impiegati Reparti
Algebra Relazionale 82
Join naturale ed equi-join
Impiegato Reparto
Impiegati
Reparto Capo
Reparti
Impiegati Reparti
Impiegato,Reparto,Capo (
) Codice Reparto (Reparti)Impiegati Reparto=Codice
( ) )
Producono lo stesso risultato !
Algebra Relazionale 83
prodotto cartesiano o join naturale?
Prodotto cartesiano e Join naturale possono essere ottenuti l’uno a partire dall’altro
R(A,B), S(B,C) Prodotto cartesiano :
R S = A,B,C (R.B=S.B (R S) ) Join naturale :
R S = ( BB’ (R) S)
Operatore di divisione
trovare gli studenti che hanno sostenuto tutti gli esami del corso di laurea Algebra Relazionale 84
Matr Cognome Nome Data di nascita6554 Rossi Mario 05/12/19784678 Neri Paolo 03/11/1982
3456 Rossi Maria 01/02/19839283 Verdi Luisa 12/11/1979
studenti
Codice Titolo Docente01 Analisi Mari02 Chimica Mari04 Fisica Verdi
corsi
Corso
04
esami
Matr Voto Codice
3456 30 04
3456 24 01
9283 30 01
6554 26 01
esami
6554
65542830
0204
Algebra Relazionale 85
Corso
04
esami
Matr Codice
3456 04
3456 01
9283 01
6554 01
Matr,Codice(esami)
6554
65540204
Codice010204
Codice(corsi)
Matr,Codice(esami) Codice(corsi)
Matr
6554
R(XY) / S(X) è una relazione su T(Y) tale che tT(Y) se e solo seesistono n-uple tR in R tali che:-tR [Y]=t-tR [X]=l per ogni n-unpla l di S
Si considerano solo le righe della prima tabella che si combinano con tutte le righe della seconda tabella
Algebra Relazionale 86
Un insieme completo di operazioni
Teorema: L’insieme delle operazioni
{ , , , , - }
è un insieme completo. ESEMPIO
R S=(R S) - (( R-S) ( S- R )) Join naturale = Prod. Cartesiano + Selezione +
Proiezione Divisione= Prodotto Cartesiano + Differenza + Proiezione
Algebra Relazionale 87
Alcune operazioni in algebra relazionale
Esempio: qual è la squadra prima in classifica?
Classifica
Squadra Punti
Inter 36Juve 34
Siena 40
Algebra Relazionale 88
Ridenominazione + Join
Squadra1
Punti1 Squadra2 Punti2
Siena 40 Siena 40
Inter 36 Siena 40
Siena 40 Juve 34
Inter 36 Juve 34
…. … …. …
Algebra Relazionale 89
Squadra1 Punti1 Squadra2 Punti2
Juve 34 Siena 40
Inter 36 Siena 40
Juve 34 Inter 36
Selezione sulla condizione:
(Punti1 Punti2) AND (Squadra1 Squadra2)
Proiezione su
Squadra1, Punti1
Squadra1 Punti1
Juve 34
Inter 36
Classifica 2Squadre che hanno meno punti di almeno un’altra squadra
Squadre che hanno più punti di almeno un’altra squadra
Algebra Relazionale 90
Differenza tra la tabella Classifica e Classifica 2
(dopo opportuna ridenominazione)
Squadra Punti
Siena 40
Classifica
Squadra Punti
Inter 36Juve 34
Siena 40Squadra1 Punti1
Juve 34
Inter 36
Classifica 2
Algebra Relazionale 91
Chiusura transitiva
Supervisione(Impiegato, Capo)
Per ogni impiegato, trovare tutti i superiori (cioè il capo, il capo del capo, e cosi' via)
RossiNeri
ImpiegatoRossiNeri
RossiNeriLupi
MoriBruni
CapoMoriBruniLupiBruniBruniBruniFalchi
RossiNeri
ImpiegatoRossiNeri
RossiNeriLupi
MoriBruni
SuperioreMoriBruniLupiBruniBruniBruniFalchi
Rossi Falchi
Lupi
Lupi
Algebra Relazionale 92
Chiusura transitiva, come si fa?
Nell'esempio, basterebbe il join della relazione con se stessa, previa opportuna ridenominazione
Ma:
RossiNeri
ImpiegatoRossiNeri
RossiNeriLupi
MoriBruni
SuperioreMoriBruniLupiBruniBruniBruniFalchi
Rossi Falchi
RossiNeri
ImpiegatoRossiNeri
RossiNeriLupi
MoriBruni
CapoMoriBruniLupiBruniBruniBruniLupi
LupiLeoniFalchi
Falchi Lupi LeoniRossi Leoni
FalchiFalchi
Algebra Relazionale 93
Chiusura transitiva, impossibile!
Per ogni specifico livello è possibile determinare tutti gli impiegati sorvegliati da un impegato a un certo livello, ma non quelli sorvegliati a tutti i livelli
Non esiste in algebra la possibilità di esprimere l'interrogazione che, per ogni relazione binaria, ne calcoli la chiusura transitiva
Per ciascuna istanza relazione, è possibile calcolare la chiusura transitiva, ma con un'espressione ogni volta diversa: dipende dall’istanza e non dallo schema!
Immaginate una istanza di migliaia di tuple: quanti join servono?
Algebra Relazionale 94
Interrogazioni in algebra relazionale
Una interrogazione su una base di dati è una funzione che restituisce una relazione R su un insieme di attributi X.
Esempi
Impiegati Nome Età StipendioMatricola
Bianchi 37 385998Rossi 34 457309
Bruni 43 425698Neri 42 359553
Mori 45 504076Lupi 46 608123
Supervisione Impiegato Capo
59987309
56989553
4076
56985698
40764076
8123
Algebra Relazionale 96
Trovare matricola, nome, età e stipendio degli impiegati che guadagnano più di 40 milioni
Stipendio>40 (Impiegati)
Algebra Relazionale 97
Nome Età StipendioMatricola
Bianchi 37 385998Rossi 34 457309
Bruni 43 425698Neri 42 359553
Mori 45 504076Lupi 46 608123
Stipendio>40(Impiegati)
Bianchi 37 385998Neri 42 359553
Rossi 34 457309
Bruni 43 425698Mori 45 504076Lupi 46 608123
Rossi 34 457309Bruni 43 425698Mori 45 504076Lupi 46 608123
Algebra Relazionale 98
Trovare matricola, nome ed età degli impiegati che guadagnano più di 40 milioni
Matricola, Nome, Età (Stipendio>40(Impiegati))
Nome Età StipendioMatricola
Bianchi 37 385998Rossi 34 457309
Bruni 43 425698Neri 42 359553
Mori 45 504076Lupi 46 608123
Bianchi 37 385998Neri 42 359553
Rossi 34 457309
Bruni 43 425698Mori 45 504076Lupi 46 608123
Rossi 34 457309Bruni 43 425698Mori 45 504076Lupi 46 608123
Algebra Relazionale 99
Trovare le matricole dei capi degli impiegati che guadagnano più di 40 milioni
Capo (Supervisione Impiegato=Matricola ( Stipendio>40(Impiegati)))
Algebra Relazionale 100
Trovare nome e stipendio dei capi degli impiegati che guadagnano più di 40 milioni
Nome,Stipendio
(Impiegati Matricola=Capo Capo(Supervisione Impiegato=Matricola ( Stipendio>40(Impiegati))))
Capo
5698
4076
8123
Capo (Supervisione Impiegato=Matricola(Stipendio>40(Impiegati)))
Bianchi 37 385998Rossi 34 457309
Bruni 43 425698Neri 42 359553
Mori 45 504076Lupi 46 608123
Nome Età StipendioMatricola
Impiegati
Algebra Relazionale 102
Impiegati Matricola=Capo Capo(Supervisione
Impiegato=Matricola ( Stipendio>40(Impiegati))))
Capo Matricola Nome Età Stipendio
5698 5698 Bianchi 37 38
4076 4076 Mori 45 50
8123 8123 Lupi 46 60
Algebra Relazionale 103
Nome,Stipendio (Impiegati Matricola=Capo
Capo(Supervisione Impiegato=Matricola
(Stipendio>40(Impiegati))))
Nome Stipendio
Bianchi 38
Mori 50
Lupi 60
Nome e stipendio dei capi di impiegati che guadagnano più di 40 milioni
Algebra Relazionale 104
Trovare gli impiegati che guadagnano più del proprio capo, mostrando matricola, nome e stipendio dell'impiegato e del capo
Matr,Nome,Stip,MatrC,NomeC,StipC ( Stipendio>StipC( MatrC,NomeC,StipC,EtàC Matr,Nome,Stip,Età(Impiegati)
MatrC=Capo
(Supervisione Impiegato=Matricola Impiegati)))
Algebra Relazionale 105
Equivalenza di espressioni algebriche
Espressioni E1 e E2 sono equivalenti per lo schema R, E1RE2 se
E1(r) = E2(r)per ogni istanza r di R.
Le due espressioni sono assolutamente equivalenti, E1E2 se
E1 R E2 per ogni schema R.
Algebra Relazionale 106
equivalenza assoluta:
A,B( A>0(R)) A>0 ( A , B(R))
equivalenza: A,B(R1) A ,C(R2) R A ,B,C(R1 R2)
vale solo per gli schemi R per cui l’intersezione tra gli attributi di R1 e R2 è uguale ad A
ESERCIZIO: trovare un controesempio
Algebra Relazionale 107
Trasformazioni di equivalenza
Due espressioni E1 ed E2 equivalenti garantiscono lo stesso risultato, ma questo non significa che la scelta sia indifferente in termini di “risorse” necessarie
Scopi:1. trasformare le espressioni in modo semplice, affinchè sia
ridotto il numero delle operazioni da eseguire2. il costo di una interrogazione viene valutato in termini di
dimensione dei risultati intermedi: in presenza di alternative si sceglie quella col costo minore.
Algebra Relazionale 108
Trasformazioni di equivalenza (2)
Operazioni che sostituiscono una espressione con un’altra ad essa equivalente
1. Atomizzazione delle selezioni
F1F2(E) F1(F2(E)))2. Idempotenza delle proiezioni
X (E) X ( X Y (E))3. Anticipazione della selezione rispetto al join
F (E1 E2) E1 F (E2) se la condizione F fa riferimento solo ad attributi nella
sottoespressione E2
Algebra Relazionale 109
4. Inglobamento di una selezione in un prodotto cartesiano
F (E1 E2) E1 F E2
5. Distributività della selezione rispetto all'unione
F (E1 E2) F (E1) F (E2)
6. Distributività della proiezione rispetto all'unione
X (E1 E2) X(E1) X (E2)
7. Distributività della selezione rispetto alla differenza
F (E1 - E2) F (E1) - F (E2)
Impiegati Nome Età StipendioMatricola
Bianchi 28 385998Rossi 34 457309
Bruni 23 425698Neri 42 359553
Mori 45 504076Lupi 46 608123
Supervisione Impiegato Capo
59987309
56989553
4076
56985698
40764076
8123
Algebra Relazionale 111
Esercizio: Utilizzando le regole di trasformazione dimostrare che le due espressioni sono equivalenti
Capo ( Matr=Imp Età < 30 (IMPIEGATI SUPERVISIONE))
Capo (SUPERVISIONE Matr=Imp ( Età < 30 (IMPIEGATI))
Algebra Relazionale 112
Trovare i numeri di matricola dei capi di impiegati con meno di 30 anni
Capo ( Matr=Imp Età < 30 (IMPIEGATI SUPERVISIONE))
Per calcolare pochi valori effettua un prodotto cartesiano (molto costoso)
Capo ( Età < 30 ( Matr=Imp (IMPIEGATI SUPERVISIONE)))
Capo ( Età<30 (IMPIEGATI Matr=Imp SUPERVISIONE))
REGOLA 1:
REGOLA 4:
Algebra Relazionale 113
Capo ( Età<30 (IMPIEGATI) Matr=Imp SUPERVISIONE)
REGOLA 3
Algebra Relazionale 114
Viste (relazioni derivate)
Spesso è utile mettere a disposizione degli utenti rappresentazioni diverse per gli stessi dati (schema esterno)
Relazioni derivate:relazioni il cui contenuto è funzione del contenuto di altre relazioni (definito per mezzo di interrogazioni)
Relazioni di base: contenuto autonomo (quelle che costituiscono effettivamente la base di dati)
Architettura standard (ANSI/SPARC)a tre livelli per DBMS
BD
Schema logico
Schemaesterno
Schema interno
Schemaesterno
Schemaesterno
utenteutente
utenteutente utente
Algebra Relazionale 116
Viste virtuali e materializzate
Due tipi di relazioni derivate: viste materializzate relazioni virtuali (o viste)
Algebra Relazionale 117
Viste materializzate
relazioni derivate effettivamente memorizzate nella base di dati
vantaggi: immediatamente disponibili per le interrogazioni
svantaggi: ridondanti appesantiscono gli aggiornamenti (il loro contenuto
deve essere mantenuto allineato con quello delle relazioni da cui derivano)
non sono supportate dai DBMS commerciali
Algebra Relazionale 118
Viste
relazioni virtuali (o viste): non sono memorizzate nella base di dati sono supportate dai DBMS commerciali una interrogazione su una vista viene eseguita
"ricalcolando" la vista (o quasi) vengono definite nei sistemi relazionali per
mezzo di espressioni nel linguaggio di interrogazione
Algebra Relazionale 119
Viste, esempio
Una vista:Supervisione = Impiegato,Capo (Afferenza Direzione)
A MoriB Leoni
Reparto CapoRossi ANeri BVerdi B
Impiegato Reparto
Bianchi B B Bruni
Afferenza Direzione
Algebra Relazionale 120
Interrogazioni sulle viste
Sono eseguite sostituendo alla vista la sua definizione:
Capo='Leoni' (Supervisione)
viene eseguita come
Capo='Leoni'( Impiegato,Capo (Afferenza Direzione))
Algebra Relazionale 121
Viste, motivazioni
Schema esterno: ogni utente vede solo ciò che gli interessa e nel modo in cui gli interessa, senza
essere distratto dal resto ciò che e' autorizzato a vedere (autorizzazioni)
Strumento di programmazione: si può semplificare la scrittura di interrogazioni: espressioni
complesse e sottoespressioni ripetute Utilizzo di programmi esistenti su schemi ristrutturati.Invece: L'utilizzo di viste non influisce sull'efficienza delle
interrogazioni
Algebra Relazionale 122
Viste come strumento di programmazione
Trovare gli impiegati che hanno lo stesso capo di Rossi
Senza vista:Impiegato (Afferenza Direzione)
ImpR,RepR Imp,Reparto ( Impiegato='Rossi' (Afferenza Direzione))
Con la vista: Impiegato (Supervisione) ImpR,RepR Imp,Reparto (Impiegato='Rossi' (Supervisione))
Top Related