Si da ora la definizione, e relativa dimostrazione, della propriet`a diraggrup- pamento parzialenella maniera che riteniamo pi`u opportuna dal punto di vista relazionale nonch`e dell’estensione di questa al caso n-dimensionale e quindi degli schemi a stella ed a fiocco di neve. Nell’enunciare la propriet`a si fa uso della definzione 3.
Proposizione 8 Sia α(X) l’insieme degli attributi in X e Cj una equigiun- zione, con Cj = (fk = pk), con fk la chiave esterna di R e pk la chiave pri-
maria di S; sia inoltre AR, AD una partizione dell’insieme A con AR⊆ α(R)
ed AD ⊆ α(D).
AγF(R Cj D) ≡AγFg((AR∪α(Cj)−α(D)γFl(R)) CjD)(4.1)
4.3. IL RAGGRUPPAMENTO PARZIALE 39 1. l’attributo fk di giunzione di R non `e determinato dagli attributi A di
raggruppamento della relazione R Cj S
2. R ha la propriet`a di raggruppamento parziale, allora
Dimostrazione
Per la propriet`a di raggruppamento parziale e per la regola di equivalenza 2.8, ponendo B = A ∪ {fk}:
AγF(R fk=pk D) ≡A γFg(A∪{fk}γFl(R fk=pk D))
per la proposizione 4
AγF(R fk=pk D) ≡AγFg(πAb∪{fk}∪Fl((A∪{fk}−α(D)γFl(R)) fk=pkD))
e infine, per la regola di equivalenza 2.1:
AγF(R fk=pk D) ≡AγFg(A∪{fk}−α(D)γFl(R)) fk=pkD)
Capitolo 5
RAGGRUPPAMENTO E
CONTEGGIO
Si illustra ora l’ultima delle trasformazioni studiate in merito all’anticipazione del raggruppamento rispetto alla giunzione. Allo stesso modo delraggruppa- mento parziale la seguente raggruppamento e conteggio pu`o essere vista come una generalizzazione della propriet`a diraggruppamento invariante. Essa `e in- fatti ottenuta rilassando alcuni dei vincoli imposti per formalizzare quella pro- priet`a. Ancora una volta, ricalcando lo stile dei precedenti capitoli, si vedr`a un esempio, la formalizzazione di ci`o che si studia, un’analisi di diverse so- luzioni ed infine un enunciato formale con condizioni necessarie e sufficienti per anticipare il raggruppamento rispetto alla giunzione anche in questo caso.
5.1
Un esempio
Esempio 5 Si consideri lo schema:
Ordini(PKord, FKprod*, FKdata*, FKag*, qt, prezzo) Agenti(PKag, aNome, citt`a, provincia, regione) Date(PKdata, anno, mese, giorno)
Prodotti(PKprod, FKfil*, pNome, costo) Filiali(PKfil, fNome, citt`a, provincia, regione
e l’interrogazione:
42 CAPITOLO 5. RAGGRUPPAMENTO E CONTEGGIO
SELECT O.FKprod, SUM(P.costo) AS c FROM Ordini O, Prodotti P
WHERE O.FKprod = P.PKprod GROUP BY O.FKprod;
In figura `e mostrato il piano di esecuzione in forma algebrica che trova un ottimizza- tore tradizionale:
O.FKprodγSU M(P.costo) AS c
O.FKprod = P.PKprod
Prodotti P Ordini O
anticipando il raggruppamento si ottiene invece il seguente piano:
πbO.FKprod, costo×GBCount AS c
O.FKprod = P.PKprod
O.FKprodγCOU N T(∗) AS GBCount Prodotti P
Ordini O
5.2
Formuliamo il problema
In merito alla trasformazione diraggruppamento e conteggiola letteratura non `e sicuramente vasta come nei casi precedentemente analizzati. Anche que- sta trasformazione si ricava a partire da quella di raggruppamento invariante. Se per il raggruppamento parziale si `e lasciata cadere l’ipotesi che gli attri- buti di raggruppamento determinino quelli di giunzione, ora si ammette che questo sia vero e si consente che gli attributi di aggregazione dell’interroga- zione appartengano anche alle tabelle dimensionali. Possiamo quindi vedere le interrogazioni di interesse come:
SELECT AR, AD, F(BR, BD) FROM R, D
WHERE Cj
5.2. FORMULIAMO IL PROBLEMA 43 dove BR, BD denotano una partizione dell’insieme B allo stesso modo degli
attributi in A partizionati in AR, AD. Ancora una volta siamo interessati a
studiare l’esistenza e l’eventuale struttura di un insieme A tale che:
AγF(R Cj D) ≡ πbA∪F(AγF(R) Cj D)
si avr`a che A ⊆ α(R) mentre, come gi`a detto, vale B ⊆ α(R) ∪ α(D) Si analizzano ora le formalizzazioni della propriet`a diraggruppamento e con- teggio. Anche in questo caso si vedono dapprima le formalizzazioni che im- pongono condizioni pi`u restrittive per poi arrivare a quelle che abbracciano casi pi`u ampi.
5.2.1
Formalizzazione di Yan Larson
Ancora una volta esaminiamo la formalizzazione proposta in [YLEA]. I due autori individuano la propriet`a di interesse se pur con vincoli piuttosto re- strittivi. La trasformazione che gli autori definiscono eager count anticipa il raggruppamento rispetto alla giunzione anticipandolo sulla relazione esterna dellajoin.
Proposizione 9 Siano AR, ARdue insiemi di attributi di R, A= AR∪ AD
e B= BR∪ BD; l’equivalenza:
AγF(BR,BD)(R Cj D) ≡AγFa(BD,CN T)(ARγF(BR,count(∗) AS CNT )(R) CjD)
`e valida se:
1. le f ∈ F da calcolare su BD sono calcolabili a partire dal valore che
assume l’attributo CN T calcolato nel primo dei raggruppamenti 2. AR→ AR∪ α(Cj)
Ancora una volta si osserva che la seconda condizione impone un vincolo molto forte per l’applicabilit`a della trasformazione. In effetti, anche avendo esteso il caso di raggruppamento invariante, ci si rende conto che la trasfor- mazione `e molto simile. Questa viene ulteriormente estesa, consentendo il calcolo di pi`u funzioni di aggregazione, con la seguente proposizione:
Proposizione 10 Siano R e D due relazioni con AR, AR ⊆ α(R) ed
44 CAPITOLO 5. RAGGRUPPAMENTO E CONTEGGIO
AγF(B)(R Cj D) ≡AγFg(B),Fa(BD,CN T)((ARγFl(BR,count(∗) AS CNT )(R) Cj D))
`e vera se:
1. Le funzioni di aggregazione sono decomponibili 2. AR→ AR∪ α(Cj)
3. Le funzioni in F da calcolare su BD possono essere calcolate a partire dal
valore che assume l’attributo COUNT nel primo dei due raggruppamenti Negli alberi logici trasformati compare il termine Fa che sta ad indicare
quella che gli autori definiscono funzione di aggregazione duplicata. In effetti le funzioni di aggregazione che si calcolano possono essere ottenute anche come: f(arg1, . . . , argn, count) dove count `e un attributo calcolato in una
precedente aggregazione.
Esempio 6 Sia F un vettore di funzioni del tipo
F(C1, C2, C3) = (SUM(C1), MAX(C2), MIN(C3)) abbiamo che F pu`o essere
calcolato anche come: Fa(C1, C2, C3, count) = (C1∗count, MAX(C2), MIN(C3)).
Chiaramente il valore di count deve essere ottenuto da un operatore relazionale della forma:C1γCOU N T(∗)(R). Diciamo che count `e ilfattore di duplicazionementre Fa
`e lafunzione di aggregazione duplicata.
Tale generalizzazione non consente comunque l’anticipazione come vista nell’esempio. Le condizioni sugli attributi di raggruppamento rimangono molto forti e nonostante si abbracci un caso pi`u ampio in merito al calcolo delle funzioni di aggregazione l’applicabilit`a rimane limitata.
Esempio 7 Con il seguente esempio si intende chiarire la differenza fra le due formalizzazioni appena viste. Si consideri la base di dati
Ordini(PKord, FKprod*, FKdata*, FKag*, qt, prezzo) Agenti(PKag, aNome, citt`a, provincia, regione) Date(PKdata, anno, mese, giorno)
Prodotti(PKprod, FKfil*, pNome, costo) Filiali(PKfil, fNome, citt`a, provincia, regione
5.2. FORMULIAMO IL PROBLEMA 45
SELECT P.PKprod, (SUM(O.prezzo)-SUM(P.costo)) FROM Prodotti P, Ordini O
WHERE O.FKprod=P.PKprod GROUP BY P.PKprod,O.FKprod
risolvendo la query secondo una classica strategia di accesso ai dati effettuerem- mo la giunzione fra le relazioni Ordini e Prodotti per poi calcolare le funzioni di aggregazione richieste ottenendo:
P.PKprod,O.FKprodγ(SUM(O.prezzo) − SUM(P.costo))
P.PKprod=O.FKprod
Prodotti Ordini
Sfruttando invece la prima delle due formalizzazioni viste si ottengono i seguenti insiemi
– AR= {F Kprod}
– AD = {P Kprod}
– BR= {prezzo}
– BD = {costo}
e si calcola la somma dei costi con la funzione di aggregazione duplicata Fa de-
finita come Fa(BD, count(∗)) = costo × count(∗). `E dunque possibile valutare
l’interrogazione con la strategia alternativa rappresentata dal seguente albero:
O.FKprod,P.PKprodγp− (costo × count(∗))
P.FKprod=P.PKprod
FKprodγSU M(prezzo) AS p, count(∗) Prodotti
46 CAPITOLO 5. RAGGRUPPAMENTO E CONTEGGIO
Con la prima delle due formalizzazioni viste si ottiene la trasformazione che abbiamo appena esaminato. La seconda invece consente di anticipare il raggruppamento per interrogazioni del tipo:
SELECT P.pNome, (SUM(O.prezzo)-SUM(P.costo)) FROM Prodotti P, Ordini O
WHERE O.FKprod=P.PKprod GROUP BY P.pNome
In questo caso la funzione da calcolare sull’insieme BR deve essere scomposta
in due funzioni (globale e locale) che calcolino progressivamente il valore richiesto e che consentano quindi di anticipare il raggruppamento rispetto alla giunzione. La funzione SU M si scompone in due stage di calcolo in cui altro non si fa che sommare i risultati parziali prodotti dal primo raggruppamento sull’attributoFKprodnel risul- tato totale raggruppando sull’attributopNome. Il calcolo delle funzioni sull’insieme
BDinvece avviene come nel caso precedente tramite la Fa(BD, count(∗)). Vediamo
direttamente l’albero in cui il raggruppamento `e stato anticipato sulla tabella dei fatti:
pNomeγSU M(p) − (costo × count(∗))
O.FKprod=P.PKprod
FKprodγSU M(prezzo) AS p, count(∗) Prodotti
Ordini
La principale differenza fra le formalizzazioni sta nel calcolo delle funzioni di aggre- gazione. Nella seconda si ammette il calcolo di funzioni di aggregazione decomponi- bili per l’insieme di attributi di aggregazione contenuto nella tabella dei fatti mentre per gli altri attributi di aggregazione si calcolano funzioni il cui valore `e calcolabile come in 6. Nella prima invece si ammette esclusivamente il calcolo di questo genere di funzioni, siano esse sull’insieme BRo sull’insieme BD.
5.2. FORMULIAMO IL PROBLEMA 47
5.2.2
Formalizzazione di Chaudhuri Shim
Si vede un’ulteriore formulazione, proposta in [CSO], che differisce nello stile da quanto appena visto. La propriet`a diraggruppamento e conteggioviene pre- sentata ancora una volta come trasformazione fra alberi logici, introducendo altre propriet`a di cui i nodi dell’albero devono godere.
Calcolo delle funzioni di aggregazione
Oltre alle definizioni per i nodi dell’albero si utilizzano delle regole per il calcolo delle funzioni di aggregazione decomponibili. Siano R e D due rela- zioni e supponiamo che r sia un record ottenuto in R raggruppando N records
r1, . . . , rN. Naturalmente, considerato il tipo dijoinche prendiamo in esame,
esister`a un unico record s di S con cui r `e in giunzione. Il calcolo delle fun- zioni di aggregazione deve essere effettuato quindi su un insieme consistente di N copie del record s che possiamo denotare con (Ns). La seguente tabella esprime il calcolo delle funzioni di aggregazione su un siffatto record:
Min(Ns)=s Max(Ns)=s Avg(Ns)=s Count(*)(Ns)=N
Sum(Ns)=N*s
Si vedono ora le definizioni per i nodi dell’albero per poi presentare la tra- sformazione cos`ı come formulata dagli autori.
Definizione 4 General groupby: `E l’operatore di raggruppamento che oltre a raggruppare calcola il numero di record in ogni gruppo. Se i dati dell’operan- do hanno gi`a un attributo di tipogroupcountallora, per ogni gruppo, calcola la somma dei valori di tale attributo.
Definizione 5 Aggregate join: `E l’operatore dijoin classico che gestisce an- che la join fra gruppi con un attributo di tipogroupcountutilizzando le identit`a della tabella di sopra.
A questo punto la propriet`a si formalizza come:
Proposizione 11 Dato un albero logico T , per ogni nodo n dell’albero, l’albero Tottenuto da T tramite le seguenti modifiche:
48 CAPITOLO 5. RAGGRUPPAMENTO E CONTEGGIO
– Rimpiazzando ognijoinantenata di n con unAggregate join
– Ponendo uno o pi`uGeneral groupbycome genitore di n o dei suoi antenati
`e equivalente a T .