Si dimostra ora l’ultima delle propriet`a oggetto del lavoro; riprendendo il caso diraggruppamento invarianteil seguente teorema generalizza quanto gi`a dimo- strato consentendo il calcolo di una classe di funzioni di aggregazione pi`u ampia.
Proposizione 12 Sia α(X) l’insieme degli attributi in X e Cj una equi- giunzione, con Cj = (fk = pk), con fkla chiave esterna di R e pk la chiave
primaria di D.
AγF(R CjD) ≡ πAb∪H∪X((A∪α(Cj)−α(D)γH∪{count(∗) AS GBCount}(R)) Cj D)
(5.1) se e solo se:
1. l’attributo fkdi giunzione di R `e determinato dagli attributi A di raggrup-
pamento della relazione R C
j D
2. F = H ∪ G con H un insieme di funzioni di aggregazione con attributi di
R e G un insieme di funzioni di aggregazione{f(ai)} decomponibili che
usano attributi aidi D
dove X `e un insieme di espressioni tale che
– ai× GBCount AS f(ai) ∈ X, se f(ai) ∈ F `eSUM(ai),
– ai ∈ X, se f(ai) ∈ F `eMIN(ai),MAX(ai),AVG(ai),
– GBCount AS f(ai) ∈ X, se f(ai) ∈ F `eCOUNT(ai).
Se in F le funzioni di aggregazione sono ridenominate con AS, X `e un insieme di espressioni tale che
– ai× GBCount AS fi ∈ X, se f ∈ F `eSUM(ai) ASfi,
– fi ∈ X, se f ∈ F `eMIN(ai) ASfi,MAX(ai) ASfi,AVG(ai) ASfi,
5.4. CONSIDERAZIONI FINALI 49
Dimostrazione Per semplicit`a si considera il caso di un unico attributo di ag-
gregazione a di S e H = φ. Poich´e A → fk → pk → a, per la regola di
equivalenza 2.9:
AγF(R fk=pk D) ≡ πbA∪X(A∪{a}γCOU N T(∗) AS GBCount(R fk=pkD))
per la proposizione 4
AγF(R fk=pk D) ≡
πb
A∪X(πAb∪{a}∪{GBCount}((A∪α(Cj)−α(D)γCOU N T(∗) AS GBCount(R)) fk=pk D))
poich´e A∪ X `e un insieme di espressioni che interessano attributi che sono in A∪ {a} ∪ {GBCount}, il π interno `e superfluo e quindi:
AγF(R fk=pk D) ≡ πbA∪X((A∪α(Cj)−α(D)γCOU N T(∗) AS GBCount(R)) fk=pk D)
5.4
Considerazioni finali
L’ultima trasformazione vista `e simile a quanto visto nel caso diraggruppa- mento invariante. In effetti l’ipotesi che si `e lasciata cadere, e cio`e che gli attributi di aggregazione siano della tabella dei fatti, non crea particolari pro- blemi se si calcolano funzioni che coinvolgono anche attributi delle relazioni dimensionali ma che possono essere calcolate a partire dalla cardinalit`a dei gruppi che si creano sulla tabella dei fatti. Questo `e proprio quanto avviene nella propriet`a di raggruppamento e conteggio in cui si ammette il calcolo di funzioni su attributi provenienti dalle tabelle dimensionali.
Osserviamo ancora che questa propriet`a pu`o essere utilizzata in combina- zione con la propriet`a di raggruppamento invariante per poter anticipare il raggruppamento sulla tabella dei fatti. Se l’interrogazione si presenta nella forma:
AγF(R fk=pk D)
ma(A → fk) `e possibile anticipare il raggruppamento utilizzando la propriet`a
di raggruppamento parziale e combinandola con quella di raggruppamento e conteggio. Se le funzioni in F sono decomponibili possiamo riscrivere l’espressione relazionale ottenendo:
50 CAPITOLO 5. RAGGRUPPAMENTO E CONTEGGIO
AγF(R fk=pk D) ≡AγFg(A∪fkγFl(R fk=pkD))
I gruppi che si creano nel primo raggruppamento sono pi`u piccoli in quan- to creati a partire da un maggior numero di attributi; l’espressione si pre- senta ora in una forma tale da consentire l’applicazione della propriet`a di raggruppamento e conteggio:
AγFg(A∪fkγFl(R fk=pk D)) ≡
AγFg(π
b
A∪H∪X((A∪{fk}γH∪{count(∗) AS GBCount}(R)) fk=pkD))
Abbiamo visto quindi un metodo che, grazie a trasformazioni successive dell’espressione relazionale da risolvere, ci consente di anticipare il raggrup- pamento sulla tabella dei fatti. Anche laddove le condizioni necessarie all’ap- plicazione delle 3.3, 4.1, 5.1, non fossero rispettate, le ultime trasformazioni ci consentono di portare l’espressione in una forma che permette di anticipare l’operazione di raggruppamento. Come gi`a abbiamo sottolineato nelle sezio- ni iniziali, queste manipolazioni non devono essere interpretate quali regole per la riscrittura delle espressioni e l’anticipazione dei raggruppamenti, ma come una “possibilit`a” da valutare da parte dell’ottimizzatore. L’effettivo be- neficio che queste apportano all’esecuzione del piano di accesso deve essere attentamente valutata di volta in volta.
Capitolo 6
GENERALIZZAZIONE
Si espongono adesso alcune generalizzazioni dei risultati ottenuti nei prece- denti capitoli. In particolare si analizzano su schemi a stella e schemi a fiocco di neve le propriet`a diraggruppamento invariante, raggruppamento parziale, rag- gruppamento e conteggio. Si analizza altresi la possibile presenza di clausole
HAVINGnell’interrogazione ed il conseguente comportamento dell’ottimizza- tore nel caso di anticipazione del raggruppamento.
6.1
Interrogazioni n-dimensionali
Per le prossime sezioni faremo riferimento ad interrogazioni della forma:
SELECT AR, AD, F(B)
FROM R,D1, . . . , Dn
WHERE Cj
GROUP BY AR, AD1, . . . , ADn
dove Cj rappresenta le condizioni di giunzione fra R e le n tabelle dimensio-
nali Di: Cj = (fk1 = pk1∧ fk2 = pk2 ∧ . . . ∧ fkn = pkn). Possiamo rappre-
sentare una giunzione fra n tabelle come R Cj {D1, . . . , Dn} o in alternativa
come(((R C
j1D1) Cj2D2) . . . CjnDn). Una tale scrittura probabilmente fa-
vorisce la visione ad albero del problema e dunque da un’idea pi`u immediata di quello che si vuole mostrare. Vediamone una rappresentazione
52 CAPITOLO 6. GENERALIZZAZIONE AγF(B) fkn= pkn . . . Dn fk2= pk2 fk1= pk1 D2 F D1
Figura 6.1 Un albero conngiunzioni
Nelle prossime sezioni si mostrano dei risultati le cui dimostrazioni si ottengo- no applicando ricorsivamente, all’albero logico associato all’interrogazione, le propriet`a viste nei capitoli 3, 4, 5. Le proposizioni forniscono delle condi- zioni necessarie per anticipare il raggruppamento sulla tabella dei fatti. Negli altri casi, quelli in cui tali condizioni non sono rispettate, `e necessario valuta- re ricorsivamente la possibilit`a di anticipare il raggruppamento a partire dalla radice dell’albero combinand fra loro le proposizioni studiate. Se indichiamo con Rla generica relazione ottenuta dopo un numero qualsiasi delle giunzio- ni da effettuare si pu`o controllare se sia R a godere delle propriet`a 3.3, 4.1 o 5.1 anticipando eventualmente su questa il raggruppamento. Si osserva che una tale tecnica, oltre a non garantire la possibilit`a di anticipare il raggrup- pamento sulla tabella dei fatti, `e costosa dal punto di vista computazionale. In effetti pu`o accadere che diversi nodi dell’albero godano delle propriet`a studiate e che queste possano essere combinate in diverse forme. Le possi- bili soluzioni diventano quindi proporzionali al numero di relazioni coinvolte nell’interrogazione e qualora questo sia grande la ricerca della soluzione otti- ma diventa eccessivamente costosa. Per questa ragione riteniamo interessante fornire delle condizioni che siano immediatamente valutabili consentendo di anticipare il raggruppamento sulla tabella dei fatti. Tale tabella `e, per le sue caratteristiche, quella che apporta il maggior contributo in termini di numero di record.
6.2. SCHEMI A STELLA 53
6.2
Schemi a stella
Nella sezione 1.2.1 abbiamo presentato una delle possibili implementazioni, nei sistemi relazionali, di un sistema per analisi multidimensionali dei dati: lo schema a stella. Ricordiamo che uno schema a stella prevede una tabel- la centrale (tabella dei fatti) che riferisce -tramite chiavi esterne- le tabelle dimensionali. Su queste ultime non esistono relazioni gerarchiche fra gli at- tributi o comunque non sono rappresentate in maniera esplicita. Vediamo cosa accade nell’applicazione della propriet`a di raggruppamento invariante ad un’interrogazione come quella presentata in sezione 6.1
6.2.1
Raggruppamento invariante
Con riferimento alla Figura 6.1 si pu`o immaginare di valutare ricorsivamen- te le condizioni previste dalla propriet`a diraggruppamento invarianteper anti- cipare il raggruppamento. La caratteristica degli schemi a stella suggerisce l’idea che per soddisfare le condizioni sia necessario che gli attributi di rag- gruppamento determinino tutte le chiavi esterne per le tabelle dimensionali coinvolte nell’interrogazione. L’altra assunzione, quella relativa agli attributi di aggregazione, ci dice che questi devono appartenere tutti alla tabella su cui si anticipa il raggruppamento. Diciamo quindi che:
Proposizione 13 Siano D1, . . . , Dnrelazioni riferite da R tramite le chiavi
esterne{fk1, . . . , fkn}. L’equivalenza:
AγF(R Cj{D1, . . . , Dn}) ≡ πAb∪F((((AR∪α(Cj) −α(Di)γF(R)) Cj1 D1) . . . CjhDh))
`e valida se:
1. gli attributi di giunzione di R con tabelle dimensionali {D1, . . . , Dh} ⊆
{D1, . . . , Dn} con attributi in A (diversi dalla pk) sono determinati dagli
attributi A di raggruppamento di R Cj {D1, . . . , Dh}
2. gli attributi di aggregazione in F sono attributi di R.
Esempio 8 Si consideri la base di dati:
Ordini(PKord, FKprod*, FKdata*, FKag*, prezzo, qt) Prodotti(PKprod, FKfil*, pNome, costo)
Filiali(PKfil, fNome, citt`a, provincia, regione) Agenti(PKag, aNome, citt`a, provincia, regione)
54 CAPITOLO 6. GENERALIZZAZIONE
Date(PKdata, giorno, mese, anno)
e l’interrogazione
SELECT P.pNome, SUM(qt) AS quantit a, SUM(prezzo) AS incasso FROM Ordini O, Agenti A, Prodotti P
WHERE O.FKag=A.PKag AND O.FKprod=P.PKprod GROUP BY O.FKprod, P.pNome
Il classico piano di accesso per la risoluzione `e rappresentato dal seguente albero logico:
O.FKprod, P.PKprod, P.pNomeγSU M(qt), SUM(prezzo)
O.FKprod=P.PKprod O.FKag=A.PKag Prodotti Agenti Ordini
Possiamo invece sfruttare la proposizione appena vista per anticipare il raggruppa- mento. Infatti vale che gli attributi di raggruppamento PKprod,pNome sono deter- minati dall’attributoFKproddiOrdini. Il primo `e determinato daFKprodin quanto si impone un vincolo di uguaglianza nella giunzione. Il secondo `e determinato daPK- prodper come sono definite le chiavi primarie negli schemi relazionali. Applicando la propriet`a si ottiene il seguente albero logico:
πb P.pNome,SUM(qt),SUM(prezzo) O.FKprod=P.PKprod Prodotti O.FKag=A.PKag Agenti O.FKprodγSU M(qt), SUM(prezzo) Ordini
6.2. SCHEMI A STELLA 55
6.2.2
Raggruppamento parziale
La propriet`a diraggruppamento parziale si estende al caso di interrogazioni su schemi a stella come segue:
Proposizione 14 Siano D1, . . . , Dn tabelle dimensionali in giunzione con
R tabella dei fatti; sia R Cj{D1, . . . , Dn} la relazione rappresentata dallajoin
fra R e le Di:
AγF(R Cj {D1, . . . , Dn}) ≡AγFg(AR∪α(Cj) −α(Di)γFl(R) Cj {D1, . . . , Dn})
se:
1. Gli attributi di aggregazione appartengono ad R. 2. F contiene solo funzioni decomponibili.
Esempio 9 Si consideri lo schema
Ordini(PKord, FKprod*, FKdata*, FKag*, prezzo) Prodotti(PKprod, FKfil*, pNome, costo)
Filiali(PKfil, fNome, citt`a, provincia, regione) Agenti(PKag, aNome, citt`a, provincia, regione) Date(PKdata, giorno, mese, anno)
e l’interrogazione:
SELECT O.FKdata, P.pNome, A.aNome, SUM(prezzo) AS totale FROM Ordini O, Agenti A, Prodotti P
WHERE O.FKag=A.PKag AND O.FKprod=P.PKprod GROUP BY P.pNome, A.aNome, A.PKag
L’interrogazione non gode della propriet`a di raggruppamento invariante in quanto l’insieme degli attributi di raggruppamento: {P.pNome, A.aNome, A.P Kag} non determina quello degli attributi di giunzione. L’albero logico associato all’interroga- zione `e:
56 CAPITOLO 6. GENERALIZZAZIONE
pNome,aNome,PKagγSU M(prezzo) AS totale
FKprod=PKprod
FKag=PKag Prodotti
Ordini Agenti
Ci`o nonostante vale che gli attributi di aggregazione sono contenuti nel nodoOr- dinie dal momento che la somma totale degli articoli venduti pu`o essere ottenuta a partire da somme parziali si pu`o modificare il piano di accesso “spingendo” il nodo diGroupByprima dell’ultimajoinottenendo:
pNome,aNome,PKagγSU M(P ) AS totale
FKprod=PKprod
FKdata,PKag,aNomeγSU M(prezzo) AS P Prodotti
FKag=PKag
Ordini Agenti
Si osserva ancora che il raggruppamento pu`o essere ulteriormente anticipato sfrut- tando il fatto che O.F Kag→ A.P Kag → A.aNome e quindi utilizzando la regola 2.6 si ottiene il seguente albero:
pNome,aNome,PKagγSU M(P ) AS totale
FKprod=PKprod
FKag=PKag Prodotti
FKagγSU M(prezzo) AS P Agenti
6.2. SCHEMI A STELLA 57
6.2.3
Raggruppamento e conteggio
Per concludere questa sezione sugli schemi a stella vediamo come si forma- lizza la propriet`a diraggruppamento e conteggiosu questo genere di schemi:
Proposizione 15 Siano D1, . . . , Dnrelazioni dimensionali ed{fk1, . . . , fkn}
le chiavi esterne di R per le Di. Sia inoltre α(X) l’insieme degli attributi in
X e Cj una equigiunzione, con Cj = (fki = pki) i = 1, . . . , n
AγF(R Cj {D1, . . . , Dn} ≡ πAb∪X(AR∪fkiγH∪count(∗)(R) Cj {D1, . . . , Dn}
se:
1. A → fki i= 1, . . . , n
2. F = H ∪ G con H un insieme di funzioni di aggregazione con attributi di
R e G un insieme di funzioni di aggregazione{f(ai)} decomponibili che
usano attributi aidi Dj
dove X `e un insieme di espressioni tale che
– ai× GBCount AS f(ai) ∈ X, se f(ai) ∈ F `eSUM(ai),
– ai ∈ X, se f(ai) ∈ F `eMIN(ai),MAX(ai),AVG(ai),
– GBCount AS f(ai) ∈ X, se f(ai) ∈ F `eCOUNT(ai).
Se in F le funzioni di aggregazione sono ridenominate con AS, X `e un insieme di espressioni tale che
– ai× GBCount AS fi ∈ X, se f ∈ F `eSUM(ai) ASfi,
– fi ∈ X, se f ∈ F `eMIN(ai) ASfi,MAX(ai) ASfi,AVG(ai) ASfi,
– GBCount AS fi ∈ X, se f ∈ F `eCOUNT(ai) ASfi.
Esempio 10 Si consideri la base di dati:
Ordini(PKord, FKprod*, FKdata*, FKag*, prezzo) Prodotti(PKprod, FKfil*, pNome, costo)
Filiali(PKfil, fNome, citt`a, provincia, regione) Agenti(PKag, aNome, citt`a, provincia, regione) Date(PKdata, giorno, mese, anno)
58 CAPITOLO 6. GENERALIZZAZIONE
SELECT P.pNome, SUM(costo) AS C
FROM Ordini O, Agenti A, Prodotti P, Date D
WHERE O.FKag=A.PKag AND O.FKprod=P.PKprod AND O.FKdata=D.PKdata GROUP BY O.FKprod
Ancora una volta vediamo che l’albero logico associato all’interrogazione `e il se- guente: O.FKprodγSU M(costo) AS C O.FKprod=P.PKprod O.FKag=A.PKag Prodotti O.FKdata=D.PKdata Agenti Ordini Date
L’interrogazione si presenta in una forma che consente l’applicazione della trasfor- mazione di raggruppamento e conteggio. Applicando questa propriet`a si pu`o antici- pare il raggruppamento ma `e necessario calcolare la somma dei costi con un diverso algoritmo; l’albero logico che si ottiene `e il seguente:
πbP.pNome, (costotimesGBcount) AS C
O.FKprod=P.PKprod O.FKag=A.PKag Prodotti O.FKdata=D.PKdata Agenti
O.FKprodγCount(∗) AS GBcount
Ordini
Date