ALGEBRA - users.dimi.uniud.itangelo.montanari/algRelit.pdf · ALGEBRA RELAZIONALE Basi di dati...

26

Transcript of ALGEBRA - users.dimi.uniud.itangelo.montanari/algRelit.pdf · ALGEBRA RELAZIONALE Basi di dati...

ALGEBRA RELAZIONALE

Basi di dati |Algebra relazionale 3{0

Linguaggi di interrogazione

(query language)

per basi di dati relazionali

algebra relazionale procedurale

calcolo relazionale dichiarativo teorico

SQL parzialmente dichiarativo realeQBE dichiarativo reale

Basi di dati |Algebra relazionale 3{1

Algebra relazionale

Insieme di operatori

� su relazioni

� che producono relazioni

� e quindi possono essere la base per espressioni complesse

Operatori dell'algebra relazionale:

� unione, intersezione, di�erenza

� ridenominazione

� selezione

� proiezione

� join (join naturale, prodotto cartesiano, theta-join)

Basi di dati |Algebra relazionale 3{2

Operatori insiemistici

� le relazioni sono insiemi

� i risultati debbono essere relazioni

(insiemi di ennuple omogenee)

Quindi

� �e possibile applicare gli operatori insiemistici

(unione, intersezione, di�erenza)

solo a coppie di relazioni de�nite sugli stessi attributi.

Basi di dati |Algebra relazionale 3{3

laureatiMatricola Cognome Et�a7274 Rossi 377432 Neri 399824 Verdi 38

quadriMatricola Cognome Et�a9297 Neri 567432 Neri 399824 Verdi 38

laureati [ quadriMatricola Cognome Et�a7274 Rossi 377432 Neri 399824 Verdi 389297 Neri 56

Basi di dati |Algebra relazionale 3{4

laureatiMatricola Cognome Et�a7274 Rossi 377432 Neri 399824 Verdi 38

quadriMatricola Cognome Et�a9297 Neri 567432 Neri 399824 Verdi 38

laureati \ quadriMatricola Cognome Et�a7432 Neri 399824 Verdi 38

Basi di dati |Algebra relazionale 3{5

laureatiMatricola Cognome Et�a7274 Rossi 377432 Neri 399824 Verdi 38

quadriMatricola Cognome Et�a9297 Neri 567432 Neri 399824 Verdi 38

laureati � quadriMatricola Cognome Et�a7274 Rossi 37

Basi di dati |Algebra relazionale 3{6

paternit�aPadre FiglioAdamo CainoAdamo AbeleAbramo IsaccoAbramo Ismaele

maternit�aMadre FiglioEva CainoEva SetSara IsaccoAgar Ismaele

paternit�a [ maternit�a ??

Basi di dati |Algebra relazionale 3{7

Ridenominazione

� operatore monadico (\unario")

� intuitivamente, \modi�ca lo schema" lasciando inalterata

l'istanza dell'operando

� permette di superare le limitazioni imposte agli operatori

insiemistici

Basi di dati |Algebra relazionale 3{8

paternit�a

Padre FiglioAdamo CainoAdamo AbeleAbramo IsaccoIsacco Giacobbe

�Genitore Padre(paternit�a)

Genitore FiglioAdamo CainoAdamo AbeleAbramo IsaccoIsacco Giacobbe

Basi di dati |Algebra relazionale 3{9

� r(X), relazione

� Y , insieme di attributi con jXj = jY j

� f : X �! Y , iniettiva (e suriettiva)

(funzione di ridenominazione)

la ridenominazione �f(r) di r rispetto a f contiene le ennuple t

de�nite su Y tali che

esista una ennupla t0 2 r

con t0[A] = t[f(A)], per ogni A 2 X

Basi di dati |Algebra relazionale 3{10

La funzione di ridenominazione viene scritta indicando solo gli

attributi su cui �e diversa dall'identit�a, con la notazione (in cui

l'ordinamento �e signi�cativo):

f(A1); f(A2); : : : ; f(Ak) A1; A2; : : : ; Ak

Esempio:

X = Padre,FiglioY = Genitore,Figlio

f(Padre) = Genitoref(Figlio) = Figlio

f si indica con

Genitore Padre

Basi di dati |Algebra relazionale 3{11

paternit�aPadre FiglioAdamo CainoAdamo AbeleAbramo IsaccoAbramo Ismaele

maternit�aMadre FiglioEva CainoEva SetSara IsaccoAgar Ismaele

�Genitore Padre(paternit�a) [ �Genitore Madre(maternit�a)

Genitore FiglioAdamo CainoAdamo AbeleAbramo IsaccoAbramo IsmaeleEva CainoEva SetSara IsaccoAgar Ismaele

Basi di dati |Algebra relazionale 3{12

impiegatiCognome Agenzia StipendioRossi Roma 45Neri Milano 53

operaiCognome Fabbrica SalarioVerdi Latina 33Bruni Monza 32

�Sede,Retribuzione Agenzia,Stipendio(impiegati)[

�Sede,Retribuzione Fabbrica,Salario(operai)

Cognome Sede RetribuzioneRossi Roma 45Neri Milano 53Verdi Latina 33Bruni Monza 32

Basi di dati |Algebra relazionale 3{13

Selezione

� operatore monadico

� produce un risultato che

{ ha lo stesso schema dell'operando

{ contiene un sottoinsieme delle ennuple dell'operando

� produce decomposizioni \orizzontali"

Basi di dati |Algebra relazionale 3{14

impiegatiCognome Nome Et�a StipendioRossi Mario 25 2.000.000Neri Luca 40 3.000.000Verdi Nico 36 4.500.000Rossi Marco 40 3.900.000

�Et�a < 30 _ Stipendio > 4.000.000(impiegati)Cognome Nome Et�a StipendioRossi Mario 25 2.000.000Verdi Nico 36 4.500.000

il risultato di una selezione contiene le ennuple dell'operando che

soddisfano la condizione di selezione

Basi di dati |Algebra relazionale 3{15

� r(X), relazione

� F formula proposizionale su X:

{ cio�e formula ottenuta combinando con i connettivi logici _ (OR), ^(AND), : (NOT),

{ atomi del tipo A�B o A�c

{ con A e B attributi in X

{ c costante \compatibile" con dom(A)

{ e � operatore di confronto (=, 6=, >, <, �, �).

�E de�nito un valore di verit�a per F su ciascuna ennupla t:

{ A�B �e vera su t se t[A] �e in relazione � con t[B]

{ A�c �e vera su t se t[A] �e in relazione � con c

{ F1 _ F2, F1 ^ F2 e :F1 hanno l'usuale signi�cato

la selezione �F (r) di r rispetto a F contiene le ennuple t di r su cui F �e vera

Basi di dati |Algebra relazionale 3{16

Proiezione

� operatore monadico

� produce un risultato

{ de�nito su un sottoschema dell'operando

{ a cui contribuiscono tutte le ennuple dell'operando

� produce decomposizioni \verticali"

� r(X), relazione

� Y sottoinsieme di X

la proiezione �Y (r) di r su Y �eun insieme di ennuple su Y :

f t[Y ] j t 2 r g

Basi di dati |Algebra relazionale 3{17

impiegatiCognome Nome Reparto CapoRossi Mario Vendite De RossiNeri Luca Vendite De RossiVerdi Nico Personale LupiRossi Marco Personale Lupi

�Cognome Nome(impiegati)Cognome NomeRossi MarioNeri LucaVerdi NicoRossi Marco

�Reparto Capo(impiegati)Reparto CapoVendite De RossiPersonale Lupi

Basi di dati |Algebra relazionale 3{18

� il risultato di una proiezione contiene al pi�u tante ennuple

quante l'operando

� pu�o contenerne di meno

� �Y (r) contiene lo stesso numero di ennuple di r se e solo se Y

�e superchiave per r

(N.B.: questa propriet�a �e de�nita a livello di istanza, non a

livello di schema)

Basi di dati |Algebra relazionale 3{19

Join (naturale)

� operatore binario (generalizzabile)

� correla dati di relazioni diverse

� �e l'operatore pi�u caratteristico dell'algebra relazionale

Basi di dati |Algebra relazionale 3{20

r1 Impiegato RepartoRossi venditeNeri produzione

Bianchi produzione

r2 Reparto Capoproduzione Morivendite Bruni

r11r2 Impiegato Reparto CapoRossi vendite BruniNeri produzione Mori

Bianchi produzione Mori

Basi di dati |Algebra relazionale 3{21

il join naturale r11r2 di r1(X1) e r2(X2) �e

una relazione de�nita su X1X2:

f t su X1X2 j esistono t1 2 r1 e t2 2 r2

con t[X1] = t1 e t[X2] = t2g

Basi di dati |Algebra relazionale 3{22

r1 Impiegato RepartoRossi venditeNeri produzione

Bianchi produzione

r2 Reparto Capoproduzione Morivendite Bruni

r11r2 Impiegato Reparto CapoRossi vendite BruniNeri produzione Mori

Bianchi produzione Mori

un join completo

(ogni ennupla contribuisce al risultato)

Basi di dati |Algebra relazionale 3{23

r1 Impiegato RepartoRossi venditeNeri produzione

Bianchi produzione

r2 Reparto Capoproduzione Moriacquisti Bruni

r11r2 Impiegato Reparto CapoNeri produzione Mori

Bianchi produzione Mori

un join con ennuple dangling

(non combinabili con ennuple dell'altra relaione)

Basi di dati |Algebra relazionale 3{24

r1 Impiegato RepartoRossi venditeNeri produzione

Bianchi produzione

r2 Reparto Capoconcorsi Moriacquisti Bruni

r11r2 Impiegato Reparto Capo

un join vuoto

Basi di dati |Algebra relazionale 3{25

r1 Impiegato ProgettoRossi ANeri A

Bianchi A

r2 Progetto CapoA MoriA Bruni

r11r2 Impiegato Reparto CapoRossi A MoriNeri A Mori

Bianchi A MoriRossi A BruniNeri A Bruni

Bianchi A Bruni

un altro join completo

(con jr1j � jr2j ennuple: ogni ennupla di r1 �e combinabile con tutte

le ennuple di r2 e viceversa)

Basi di dati |Algebra relazionale 3{26

� il join di r1 e r2 contiene un numero di ennuple compreso fra 0

e jr1j � jr2j;

� se il join di r1 e r2 �e completo, allora contiene almeno un

numero di ennuple pari al massimo fra jr1j e jr2j;

� se X1 \X2 contiene una chiave per r1 (per r2), allora il join di

r1(X1) e r2(X2) contiene al pi�u jr2j (jr1j) ennuple;

Basi di dati |Algebra relazionale 3{27

paternit�aPadre FiglioAdamo CainoAdamo AbeleAbramo IsaccoAbramo Ismaele

maternit�aMadre FiglioEva CainoEva SetSara IsaccoAgar Ismaele

paternit�a1maternit�a

Padre Figlio MadreAdamo Caino EvaAbramo Isacco SaraAbramo Ismaele Agar

Basi di dati |Algebra relazionale 3{28

� il join di due relazioni sugli stessi attributi �e pari all'intersezione

delle due relazioni:

r1(X)1r2(X) = r1(X) \ r2(X)

� il join naturale �e de�nito anche fra relazioni che non hanno

attributi in comune.

� In tal caso viene chiamato prodotto cartesiano.

� Il prodotto cartesiano di r1 e r2 contiene sempre

jr1j � jr2j ennuple.

� Non si tratta del tradizionale prodotto cartesiano fra insiemi

Basi di dati |Algebra relazionale 3{29

impiegatiImpiegato ProgettoRossi ANeri ANeri B

progettiCodice Nome

A VenereB Marte

impiegati1 progettiImpiegato Progetto Codice NomeRossi A A VenereNeri A A VenereNeri B A VenereRossi A B MarteNeri A B MarteNeri B B Marte

Basi di dati |Algebra relazionale 3{30

� il join naturale �e commutativo:

r11r2 = r21r1, per ogni r1 e r2

� il join naturale �e associativo:

r11(r21r3) = (r11r2)1r3, per ogni r1, r2, r3

�E quindi possibile de�nire un operatore di join n-ario (attraverso

applicazioni ripetute dell'operatore binario).

Una de�nizione equivalente:

r1(X1)1r2(X2)1 : : :1rn(Xn) (in breve 1ni=1ri):

f t su X1 : : : Xn j esistono t1 2 r1; : : : ; tn 2 rn;

con t[X1] = t1; : : : ; t[Xn] = tng

Dimostrazione: per induzione.

Basi di dati |Algebra relazionale 3{31

Join e proiezione: propriet�a

Join e proiezione sono (quasi) inversi.

� r1(X1) e r2(X2)

{ �X1(r11r2) � r1

{ �X1(r11r2) = r1 e �X2

(r11r2) = r2 se e solo se

il join di r1 e r2 �e completo

{ il join di �X1(r11r2) e �X2

(r11r2) �e completo

� r(X); X = X1X2

{ �X1(r)1�X2

(r) � r

{ se �X1(r)1�X2

(r) = r diciamo che

r si decompone senza perdita su X1 e X2

{ �X1(r)1�X2

(r) si decompone senza perdita su X1 e X2

Queste propriet�a sono generalizzabili al join n-ario.

Basi di dati |Algebra relazionale 3{32

Theta-join

Un'operatore derivato.

Siano r1 e r2 due relazioni senza attributi in comune.

r11F r2 = �F(r11r2)

Il theta-join �e un prodotto cartesiano seguito da una selezione.

Se F �e una congiunzione di atomi di uguaglianza, abbiamo un

equi-join.

Basi di dati |Algebra relazionale 3{33

impiegatiImpiegato ProgettoRossi ANeri ANeri B

progettiCodice Nome

A VenereB Marte

impiegati 1Progetto=Codice progetti

Impiegato Progetto Codice NomeRossi A A VenereNeri A A VenereNeri B B Marte

Basi di dati |Algebra relazionale 3{34

Espressioni ed interrogazioni

Un'interrogazione �e una funzione che, applicata a istanze di base

di dati, produce istanze di relazione.

� U1 insieme (in�nito) numerabile di attributi

(per semplicit�a tutti sullo stesso dominio);

U insieme di tutte le relazioni su attributi in U1

� R schema di base di dati;

I(R) insieme delle istanze di R

Un'interrogazione Q �e una funzione:

Q : I(R)! U

Basi di dati |Algebra relazionale 3{35

Di solito gli attributi del risultato sono �ssati.

Esiste X � U1 tale che

Q : I(R)! X

dove X �e l'insieme di tutte le relazioni su X

Q(r) indica il risultato dell'applicazione di Q ad r

(pu�o non essere de�nito | Q �e in generale una funzione parziale).

Basi di dati |Algebra relazionale 3{36

Le espressioni dei vari linguaggi di interrogazione (es. l'algebra

relazionale) \rappresentano" o \realizzano" interrogazioni: ogni

espressione de�nisce una funzione.

E(r) �e il il risultato dell'applicazione di E ad r

Basi di dati |Algebra relazionale 3{37

Due espressioni (dello stesso linguaggio o di due linguaggi diversi)

sono equivalenti se rappresentano la stessa interrogazione:

� E1 �R E2 se E1(r) = E2(r) per ogni r 2 I(R).

� E1 � E2 se E1 �R E2 per ogni schema R de�nibile su U1.

�AB(�A>0(R)) � �A>0(�AB(R))

�AB(R1) 1 �AC(R2) �R �ABC(R1 1 R2)

(se R contiene R1(X1) e R2(X2) e X1 \X2 = A)

Basi di dati |Algebra relazionale 3{38

Due linguaggi sono equivalenti se permettono di formulare le

stesse interrogazioni.

� L1 �e espressivo almeno quanto L2 se

per ogni espressione E2 di L2 e

per ogni schema di base di dati R

esiste un'espressione E1 di L1 tale che E1 �R E2.

� L1 e L2 sono equivalenti se

ognuno �e espressivo almeno quanto l'altro.

Basi di dati |Algebra relazionale 3{39

In algebra relazionale, le interrogazioni su uno schema di base di

dati R vengono formlate con espressioni i cui atomi sono:

� (nomi di) relazione in R (le \variabili");

� relazioni costanti (che non fanno parte delle istanze di R).

Abbiamo variabili e costanti come nelle espressioni di altre algebre

note.

Basi di dati |Algebra relazionale 3{40

Relazioni costanti:

� Per ogni relazione su

PERSONE(Nome,Sesso,: : :)

generare una relazione con associato agli uomini il titolo

\Signor" e alle donne \Signora".

� I due valori non sono contenuti nella base di dati e gli operatori

non possono \creare" valori.

� Il risultato desiderato si ottiene con:

PERSONE 1 TITOLI

dove TITOLI �e una relazione costante:

TITOLI Sesso TitoloM SignorF Signora

Basi di dati |Algebra relazionale 3{41

p1 Nome Sesso : : :

Neri F : : :

Bianchi F : : :

Verdi M : : :

p1 1 TITOLI

Titolo Nome Sesso : : :

Signora Neri F : : :

Signora Bianchi F : : :

Signor Verdi M : : :

p2 Nome Sesso : : :

Rossi M : : :

Bini F : : :

p2 1 TITOLI

Titolo Nome Sesso : : :

Signor Rossi M : : :

Signora Bini F : : :

Basi di dati |Algebra relazionale 3{42

PERSONE(Nome,Eta,Reddito)

PATERNITA(Padre,Figlio)

MATERNITA(Madre,Figlio)

persone Nome Eta RedditoAndrea 27 21Aldo 25 15Maria 55 42Anna 50 35Filippo 26 30Luigi 50 40Franco 60 20Olga 30 41Sergio 85 35Luisa 75 87

maternitaMadre FiglioLuisa MariaLuisa LuigiAnna OlgaAnna FilippoMaria AndreaMaria Aldo

paternitaPadre FiglioSergio FrancoFranco AndreaFranco AldoLuigi OlgaLuigi Filippo

Basi di dati |Algebra relazionale 3{43

\Trovare nome e reddito delle persone con meno di 30 anni"

�Nome;Reddito(�Eta<30(persone))

Nome RedditoAndrea 21Aldo 15Filippo 30

Basi di dati |Algebra relazionale 3{44

\Trovare i padri di persone che guadagnano pi�u di venti milioni"

�Padre(paternita1Figlio=Nome (�reddito>20(persone)))

PadreFrancoLuigi

Basi di dati |Algebra relazionale 3{45

\Trovare i padri i cui �gli guadagnano tutti pi�u di venti milioni"

�Padre(paternita)�

��Padre(paternita1Figlio=Nome (�reddito�20(persone)))

PadreLuigi

Basi di dati |Algebra relazionale 3{46

\Trovare le persone che guadagnano pi�u dei rispettivi padri,

mostrandone nomi, redditi e nomi dei rispettivi padri"

�N ;R;P(�R>RP((persone 1N=F paternita)

1P=NP

(�NP ;EP ;RP N;E;R(persone))))

Nome Reddito PadreAndrea 21 FrancoOlga 41 Luigi

Basi di dati |Algebra relazionale 3{47

Schema della base di dati di una dinastia reale:

REIGNS (Sovereign, From, To)

PERSONS (Name, Sex, Birth, Death)

FATHERHOOD (Father, Child)

MOTHERHOOD (Mother, Child)

Basi di dati |Algebra relazionale 3{48

reignsSovereign From ToJames I 1603 1625Charles I 1625 1648Charles II 1660 1685James II 1685 1688Mary II 1688 1694Anne 1702 1714

personsName Sex Birth DeathJames I M 1566 1625Elizabeth F 1590 1662Charles I M 1600 1649Charles II M 1630 1685Mary F 1631 1659

James II M 1633 1701Henrietta A. F 1640 1670

Mary II F 1662 1694Anne F 1665 1714

James F.E. M 1686 1766

fatherhoodFather Child

Lord Darnley James IJames I ElizabethJames I Charles ICharles I Charles IICharles I MaryCharles I James IICharles I Henrietta A.James II Mary IIJames II AnneJames II James F.E.

motherhoodMother Child

Mary Stuart James IAnne of Denmark ElizabethAnne of Denmark Charles IHenrietta Maria Charles IIHenrietta Maria MaryHenrietta Maria James IIHenrietta Maria Henrietta A.Anne Hyde Mary IIAnne Hyde Anne

Mary of Modena James F.E.

Basi di dati |Algebra relazionale 3{49

REIGNS (Sovereign, From, To)

PERSONS (Name, Sex, Birth, Death)

FATHERHOOD (Father, Child)

MOTHERHOOD (Mother, Child)

\i sovrani che hanno regnato �no alla morte"

(�Name,Death Sovn,To(REIGNS)) 1 PERSONS

Name Sex Birth From DeathJames I M 1566 1603 1625Charles II M 1633 1660 1685Mary II F 1662 1688 1694Anne F 1665 1702 1714

Basi di dati |Algebra relazionale 3{50

REIGNS (Sovereign, From, To)PERSONS (Name, Sex, Birth, Death)

FATHERHOOD (Father, Child)MOTHERHOOD (Mother, Child)

\i �gli (noti alla base di dati) dei sovrani della famiglia"

�Sovn, Child(REIGNS 1 (�Sovn Father(FATHERHOOD) [

�Sovn Mother(MOTHERHOOD))

Sovereign Child

James I ElizabethJames I Charles ICharles I Charles IICharles I MaryCharles I James IICharles I Henrietta A.James II Mary IIJames II AnneJames II James F.E.

Basi di dati |Algebra relazionale 3{51