& %
Equivalenza di Espressioni Algebriche
Angelo Montanari
Dipartimento di Matematica e Informatica Universit`a di Udine
& %
Introduzione
L’equivalenza di espressioni dell’algebra relazionale viene sfruttata nella fase di ottimizzazione algebrica delle interrogazioni:
• le interrogazioni formulate nel linguaggio SQL vengono
tradotte in espressioni (equivalenti) dell’algebra relazionale
• il costo dell’esecuzione di un’interrogazione viene valutato in termini delle dimensioni dei risultati intermedi (della
valutazione dell’espressione dell’algebra relazionale);
in presenza di varie espressioni alternative equivalenti, viene scelta quella con costo minore
Vengono utilizzate delle trasformazioni di equivalenza:
operazioni che sostituiscono un’espressione con un’altra a essa equivalente
& %
Equivalenze assolute e dipendenti dallo schema
Diversi tipi di equivalenza:
(1) Equivalenza dipendente dallo schema.
E1 ≡R E2 se E1(r) = E2(r) per ogni r ∈ R
(2) Equivalenza assoluta (non dipendente dallo schema).
E1 ≡ E2 se E1 ≡R E2 per ogni schema R Un esempio di equivalenza assoluta:
ΠAB(σA>0(R1)) ≡ σA>0(ΠAB(R1)) Un esempio di equivalenza dipendente dallo schema:
ΠAB(R1) ./ ΠAC(R2) ≡R ΠABC(R1 ./R2)
che vale se e solo se in R l’intersezione tra gli insiemi di attributi di R1 e di R2 `e pari ad A.
& %
Un primo insieme di trasformazioni - 1
Atomizzazione delle selezioni: una congiunzione di selezioni pu`o essere sostituita da una sequenza di selezioni atomiche
σF1∧F2(E) ≡ σF2(σF1(E)) con E espressione qualsiasi.
Idempotenza delle proiezioni: una proiezione pu`o essere trasformata in una sequenza di proiezioni che eliminano i vari attributi in varie fasi
πX(E) ≡ πX(πXY (E))
con E espressione definita su un insieme di attributi che contiene X e Y .
& %
Un primo insieme di trasformazioni - 2
Anticipazione della selezione rispetto al join (pushing selections down):
σF(E1 ./ E2) ≡ E1 ./ σF(E2)
se la condizione F coinvolge solo attributi della sottoespressione E2. Anticipazione della proiezione rispetto al join (pushing
projections down):
πX1Y2(E1 ./ E2) ≡ E1 ./ πY2(E2) con E1 definita su X1, E2 definita su X2, Y2 ⊆ X2 e
(X1 ∩ X2) ⊆ Y2 (gli attributi di X2 \ Y2 non sono coinvolti nel join).
& %
Una trasformazione derivata
Combinando la regola di anticipazione della proiezione rispetto al join con la regola di idempotenza delle proiezioni, si ottiene la seguente regola derivata (che elimina da subito gli attributi che non sono coinvolti nel join e non compaiono nel risultato finale):
πY (E1 ./F E2) ≡ πY (πY1(E1) ./F πY2(E2))
dove, assumendo che E1 sia definita su X1, E2 sia definita su X2 e J1 (rispettivamente J2) sia il sottoinsieme di X1 (rispettivamente X2) coinvolto nell’operazione di join, si ha che:
Y1 = (X1 ∩ Y ) ∪ J1 Y2 = (X2 ∩ Y ) ∪ J2
& %
Un esempio - 1
Interrogazione: trovare i nomi dei dipartimenti il cui manager guadagna pi`u di 80000 euro.
Soluzione non ottimizzata:
πDN OM E(σCF =M AN AGER∧ST IP EN DIO>80000
(IM P IEGAT O ./ DIP ART IM EN T O)) che si pu`o riscrivere come:
πDN OM E(σCF =M AN AGER(σST IP EN DIO>80000
(IM P IEGAT O ./ DIP ART IM EN T O)))
& %
Un esempio - 2
La precedente espressione pu`o a sua volta essere riscritta nel modo seguente:
πDN OM E(σST IP EN DIO>80000(IM P IEGAT O) ./CF =M AN AGER DIP ART IM EN T O)
che pu`o a sua volta essere riscritta come:
πDN OM E(πCF(σST IP EN DIO>80000(IM P IEGAT O)) ./CF =M AN AGER DIP ART IM EN T O)
P.S. La regola derivata descritta in precedenza potrebbe essere utilizzata per ridurre da subito le dimensioni delle due relazioni..
& %
Un secondo insieme di trasformazioni - 1
Distributivit`a della selezione rispetto all’unione:
σF(E1 ∪ E2) ≡ σF(E1) ∪ σF(E2)
Distributivit`a della selezione rispetto alla differenza:
σF(E1 \ E2) ≡ σF(E1) \ σF(E2)
Distributivit`a della proiezione rispetto all’unione:
πX(E1 ∪ E2) ≡ πX(E1) ∪ πX(E2)
Non vale la distributivit`a della proiezione rispetto alla differenza.
Ad esempio, date R1(A, B) e R2(A, B)
πA(R1 \ R2) 6≡ πA(R1) \ πA(R2)
non vale se R1 e R2 contengono tuple uguali su A e diverse su B
& %
Un secondo insieme di trasformazioni - 2
Trasformazioni basate sulla corrispondenza tra operatori insiemistici e selezioni complesse:
σF1∨F2(R) ≡ σF1(R) ∪ σF2(R)
σF1∧F2(R) ≡ σF1(R) ∩ σF2(R) ≡ σF1(R) ./ σF2(R) σF1∧¬(F2)(R) ≡ σF1(R) \ σF2(R)
Propriet`a distributiva del join rispetto all’unione:
E1 ./ (E2 ∪ E3) ≡ (E1 ./ E2) ∪ (E1 ./ E3)
N.B. Risultati intermedi vuoti (relazioni prive di tuple) permettono di semplificare le espressioni (join/prodotto cartesiano con la
relazione vuota come uno degli operandi producono quale risultato la relazione vuota).
