Ottimizzazione di interrogazioni con groupby

(1)

UNIVERSITÀ DEGLI STUDI DI PISA

Facoltà di Scienze, Matematiche, Fisiche e Naturali

Laurea Specialistica in Informatica

TESI DI LAUREA

OTTIMIZZAZIONE DI INTERROGAZIONI CON

RAGGRUPPAMENTI

Relatore

Prof. Antonio ALBANO

Candidato

Emanuele DE PASCALE

(2)

A Milvio Capovani,

che nonostante la breve durata della nostra conoscenza,

con le sue preziose parole è stato per me maestro di vita

prima ancora che insegnante universitario.

A Michele,

con cui ho iniziato questa avventura e che è stato con me

prodigo di consigli preziosi che non scorderò mai

(3)

1 “Il vero viaggio di scoperta non consiste nel trovare nuove terre, ma nell’a-vere nuovi occhi” - Marcel Proust

Riassunto

La necessità di produrre analisi multidimensionali dei dati, è diventata di cru-ciale importanza per ogni tipo di organizzazione. In questo contesto, negli ultimi anni, hanno trovato maggior applicazione i sistemi di data warehouse. Tali sistemi si trovano a dover risolvere, su enormi quantità di dati, interroga-zioni SQL che per la maggior parte contenengono gli operatori di giunzione e di raggruppamento. Diventa quindi fondamentale prevedere algoritmi di ottimizzazione delle interrogazioni alternativi a quelli tradizionali.

In questo lavoro, dopo un’analisi di alcune propriet`a dell’operatore di rag-gruppamento, si considera in particolare sotto quali condizioni questo opera-tore si pu`o anticipare rispetto alla giunzione, prima nel caso di giunzioni fra due tabelle e poi nel caso di giunzioni su schemi a stella e a fiocco di neve.

(4)

(5)

Indice

1 INTRODUZIONE 5

1.1 Presentazione del problema . . . 5

1.2 Sistemi per data warehouse . . . 7

1.2.1 Schemi per l’analisi dei dati . . . 7

1.3 Contenuto della tesi . . . 8

2 OPERATORI ED OTTIMIZZAZIONE 11 2.1 L’operatore di raggruppamento . . . 11 2.2 Regole di equivalenza . . . 12 2.2.1 Notazione . . . 12 2.2.2 Definizioni . . . 13 2.2.3 Equivalenze . . . 14 2.3 Ipotesi di lavoro . . . 18 3 RAGGRUPPAMENTO INVARIANTE 21 3.1 Un esempio . . . 21 3.2 Formuliamo il problema . . . 23

3.2.1 Formalizzazione di Galindo Lagaria - Joshi . . . 23

3.2.2 Formalizzazione di Chaudhuri - Shim . . . 26

3.2.3 Formalizzazione di Yan - Larson . . . 26

3.2.4 Riassumiamo . . . 27

3.3 Il raggruppamento invariante . . . 29

4 RAGGRUPPAMENTO PARZIALE 33 4.1 Un esempio . . . 33

4.2 Formuliamo il problema . . . 35

4.2.1 Formalizzazione di Yan - Larson . . . 35

4.2.2 Formalizzazione di Tsois - Sellis . . . 36 3

(6)

4 INDICE

4.2.3 Formalizzazione di Chaudhuri Shim . . . 36

4.3 Il raggruppamento parziale . . . 38

5 RAGGRUPPAMENTO E CONTEGGIO 41 5.1 Un esempio . . . 41

5.2 Formuliamo il problema . . . 42

5.2.1 Formalizzazione di Yan Larson . . . 43

5.2.2 Formalizzazione di Chaudhuri Shim . . . 47

5.3 Raggruppamento e conteggio . . . 48 5.4 Considerazioni finali . . . 49 6 GENERALIZZAZIONE 51 6.1 Interrogazioni n-dimensionali . . . 51 6.2 Schemi a stella . . . 53 6.2.1 Raggruppamento invariante . . . 53 6.2.2 Raggruppamento parziale . . . 55 6.2.3 Raggruppamento e conteggio . . . 57

6.3 Schemi a fiocco di neve . . . 58

6.3.1 Raggruppamento invariante . . . 59 6.3.2 Raggruppamento parziale . . . 61 6.3.3 Raggruppamento e conteggio . . . 64 6.4 Clausola HAVING . . . 66 6.4.1 Raggruppamento invariante . . . 67 6.4.2 Raggruppamento parziale . . . 67 6.4.3 Raggruppamento e conteggio . . . 68 7 CONCLUSIONI 69

(7)

Capitolo 1

INTRODUZIONE

Si presenta il problema dell’analisi multidimensionale di dati, organizzati con schemi a stella o a fiocchi di neve, che pone requisiti particolari all’ottimiz-zazione di interrogazioni SQL con giunzioni e raggruppamenti e si precisano gli aspetti che verranno approfonditi nei successivi capitoli.

1.1 Presentazione del problema

L’ottimizzazione di interrogazioni SQL contententi l’operatore di ragguppa-mento e quello di giunzione negli ultimi anni è stata oggetto di numerosi lavori in quanto alla base di analisi multidimensionali e di applicazioni OLAP (On Line Analytical Processing) che richiedono la gestione di volumi di dati sempre maggiori organizzati in data warehouse, per consentire alle organiz-zazioni di effettuare analisi approfondite delle proprie attività. Tali analisi, dette appunto multidimensionali, risultano essere molto più significative di quelle che si potevano produrre appena una quindicina di anni prima in quan-to basate su un campione molquan-to più grande di dati ed ottenute con una grande varietà di funzioni statistiche.

Un’applicazione OLAP deve consentire la produzione di dati di sintesi a partire da enormi quantità di dati. Sempre più spesso infatti, per il livello decisionale di un’organizzazione, è necessario avere a disposizione rapporti

di sintesi o cruscotti aziendali; questi sono sostanzialmente degli strumenti

che visualizzano indicatori di prestazione delle attivit`a dell’organizzazione. La definizione di applicazione OLAP si trova in [WO]. La maggior parte di queste applicazioni, che sono diventate ormai di cruciale importanza, `e

(8)

6 CAPITOLO 1. INTRODUZIONE

plementata tramite classici sistemi relazionali. Tali sistemi si trovano per`o a dover gestire una mole di dati centinaia di volte superiore a quella per cui era-no stati pensati, e dunque tanto dal mondo dei fornitori dei sistemi, quanto da quello accademico, sono state proposte nuove tecniche per l’ottimizzazione delle interrogazioni che effettuano analisi multidimensionali.

Le interrogazioni per analisi multidimensionali sono generalmente dette

query a stella e richiedono specifiche tecniche di ottimizzazione per

ridur-re significativamente il costo della loro esecuzione. Ad esempio la possibilità di invertire l’ordine dei raggruppamenti e delle giunzioni genera quasi sem-pre, per questo tipo di interrogazioni, una riduzione del costo di esecuzione. Tale possibilità non è contemplata da un ottimizzatore tradizionale. Diversi autori [CSO, GJM, YLI, TSG, YLEA] hanno invece mostrato che, sfruttando proprio il diverso ordinamento fra questi due operatori, si ottiene una valuta-zione più efficiente delle query a stella e quindi una risposta più veloce. Una presentazione delle diverse proposte sarà fatta nella parte iniziale dei succes-sivi capitoli.

Nella trattazione delle problematiche che si esporranno si userà l’algebra relazionale e i problemi si presenteranno come riscritture algebriche, ma il problema generale non è riconducibile a regole di riscrittura perché esso è un problema di ottimizzazione fisica dove le possibili alternative andranno valutate sulla base dei costi di esecuzione. L’ottimizzatore fisico deve però considerare fra i possibili piani di accesso alternativi anche quelli che scatu-riscono dalle regole di riscrittura algebrica dell’operatore di raggruppamento. Esistono comunque una serie di casi in cui il beneficio dell’applicazione delle regole che si vedranno è certo. Queste possono dunque essere applicate senza il bisogno di alcuna valutazione dei costi da parte dell’ottimizzatore fisico. Si pensi ad esempio al caso di un’operatore di giunzione seguito da uno di restrizione; se si anticipano le restrizioni sui due rami figli dellajoin si ottie-ne un’esecuzioottie-ne più efficiente. Un altro caso è rappresentato da una clausola

HAVINGsu un raggruppamento; se tale clausola comporta una restrizione sugli attributi di raggruppamento piuttosto che sul valore delle funzioni di aggrega-zione allora la sua valutaaggrega-zione pu`o essere anticipata accedendo alla relaaggrega-zione prima di effettuare il raggruppamento. Anche in questo caso il beneficio `e certo.

(9)

1.2. SISTEMI PER DATA WAREHOUSE 7

1.2 Sistemi per data warehouse

I sistemi di data warehouse sono diventati lo strumento principe per effettuare analisi multidimensionali di dati storici. Il supporto ai sistemi decisionali offerto da questi strumenti `e di importanza strategica nella pianificazione del

marketing e nell’analisi delle tendenze di mercato. Oggi, tali sistemi, sono

implementati tramite motori di database tradizionali con l’aggiunta di nuove funzionalità necessarie al differente utilizzo dei primi rispetto a questi ultimi. In effetti la mole di dati presente in un data warehouse non è confrontabile con quella presente in un database per la gestione operativa della logistica e delle attività di un’organizzazione.

Senza entrare nel dettaglio delle caratteristiche tecnologiche dei sistemi di data warehouse si da una breve panoramica dei tipici schemi di relazione che si trovano in un data warehouse

1.2.1 Schemi per l’analisi dei dati

Il classico schema di un data warehouse `e a stella, dove la tabella che oc-cupa il centro della stella, detta tabella dei fatti, contiene gli eventi oggetto dell’analisi; le caratteristiche degli eventi memorizzati nella tabella dei fatti

FACT TABLE

D1 D2 D3

D4 D5 D6

Figura 1.1 Un esempio di schema a stella

sono descritte nelle tabelle delle dimensioni, che rappresentano le punte della stella. Soltanto la tabella dei fatti (TF) `e legata (tramite chiavi esterne) a tutte le altre tabelle mentre non esistono “connessioni” fra relazioni dimensionali.

(10)

8 CAPITOLO 1. INTRODUZIONE

Le tabelle delle dimensioni contengono le informazioni sulle dimensioni di analisi; ad esempio se il fatto è una vendita, la dimensione può essere dove questa vendita è avvenuta. Ancora, in una dimensione possiamo trovare, ad esempio, la completa definizione di un agente, anche se presumibilmente non è significativo conoscere tutti gli ordini di un particolare agente, ma può essere significativo ripartire le vendite per sesso o area geografica dell’agente. Una variante dello schema a stella è lo schema a fiocco di neve (Figura 1.2) , in cui le tabelle dimensionali vengono normalizzate e gli attributi vengono distribuiti in più tabelle connesse alla tabella dimensionale che li ha originati attraverso una chiave esterna.

D2 _D21 D3 D2n D1 D31 D3r D11 D1m F

Figura 1.2 Un esempio di schema a fiocco di neve

1.3 Contenuto della tesi

L’attenzione è sulle proprietà algebriche dell’operatore di raggruppamento utili per l’ottimizzazione delle interrogazioni di analisi dei dati. In partico-lare interessa studiare sotto quali condizioni l’operatore di raggruppamento possa essere anticipato rispetto alla giunzione perché di solito questa strategia consente di produrre piani di accesso migliori.

Nel prossimo capitolo si prende in esame una serie di proprietà di base dell’operatore di raggruppamento e di altri operatori dell’algebra relazionale, che consentiranno poi di giustificare altre proprietà più generali.

Nel Capitolo 3 si considerano giunzioni fra due tabelle e si analizza la prin-cipale propriet`a dell’operatore di raggruppamento detta di raggruppamento

(11)

1.3. CONTENUTO DELLA TESI 9 Nel Capitolo 4 si considera un’altra possibilit`a di anticipazione del raggrup-pamento, detta di raggruppamento parziale che consente l’anticipazione del-l’operatore sulla giunzione quando non vale la propiet`a del raggruppamento invariante.

Nel Capitolo 5 si considera una terza possibilit`a di anticipazione del rag-gruppamento, detta di raggruppamento e conteggio che consente l’anticipa-zione dell’operatore sulla giunl’anticipa-zione quando non vale le propriet`a di raggrup-pamento invariante e parziale per la presenza di funzioni di aggregazione su attributi che non appartengono alla tabella sulla quale si vuole anticipare il raggruppamento.

Nel Capitolo 6 si generalizzano i risultati ottenuti al caso di schemi a stella e a fiocco di neve.

(12)

(13)

Capitolo 2

OPERATORI ED

OTTIMIZZAZIONE

La possibilità di effettuare i raggruppamenti prima delle giunzioni rappresen-ta, per le query a stella, una valida soluzione di ottimizzazione. Naturalmen-te è possibile considerare un tale tipo di straNaturalmen-tegia a partire da una profonda comprensione delle proprietà dell’operatore di raggruppamento e della sua semantica. Si presenta una descrizione dei concetti di base utilizzati nel resto del lavoro, della notazione adottata e si analizzano dal punto di vista algebrico alcune proprietà dell’operatore di raggruppamento. Infine verrano presentate le ipotesi che si formulano e sotto le quali sarà sviluppato il resto del lavoro.

Le proprietà dell’operatore di raggruppamento che si presentano saranno enunciate e dimostrate in forma di regole di equivalenza, tenendo presente che il loro utilizzo non può essere quello di semplici regole di riscrittura. Queste costituiscono comunque una base per le dimostrazioni formali delle proprietà che saranno descritte nei successivi capitoli.

2.1 L’operatore di raggruppamento

L’operatore di raggruppamento riveste un ruolo fondamentale nell’analisi dei dati. Esso verr`a usato con la seguente sintassi:

(14)

12 CAPITOLO 2. OPERATORI ED OTTIMIZZAZIONE

AγF(B) AS C(R)

dove A rappresenta gli attributi di raggruppamento, B quelli di aggregazione ed F le funzioni di aggregazione. I valori calcolati dalle funzioni di aggrega-zione sono ridenominati tramite il costrutto AS. Inoltre faremo l’ipotesi che l’operatore di raggruppamento abbia la possibilità di effettuare anche la pro-iezione degli attributi in A∪ C della relazione R. Di conseguenza si potrà trovare come radice di un albero logico senza la necessità di aggiungervi un nodo di proiezione quale genitore.

La semantica dell’operatore di raggruppamento `e quella di produrre un uni-co reuni-cord t per ogni gruppo di reuni-cord in R uni-con uguale valore per gli attributi in A esteso con i risultati delle funzioni di aggregazione. Il record t sar`a for-mato dagli attributi in A cui vengono concatenati gli attributi in C associato al valore delle funzioni di aggregazione.

Formalmente definiamo la semantica dell’operatore di raggruppamento co-me:

AγF(B)ASC(R) =

x∈ dom(A){x} × γF(B)ASC(σA=x(R))

dove con dom(A) si denota il dominio dei valori attivi per α(A). Con dominio dei valori attivi si intende il dominio dei valori presenti nella relazione R per gli attributi in A.

2.2 Regole di equivalenza

Si vedono ora alcune regole di equivalenza fra espressioni dell’algebra rela-zionale; sfruttando la definizione degli operatori relazionali definiremo alcu-ne regole di base che saranno utilizzate alcu-nella dimostrazioalcu-ne delle successive propriet`a.

2.2.1 Notazione

Nelle dimostrazioni e negli enunciati oggetto delle prossime sezioni utilizze-remo la notazione dell’algebra relazionale; in particolare indicheutilizze-remo con: – π_Xb (R) l’operazione di proiezione degli attributi in X della relazione R

(15)

2.2. REGOLE DI EQUIVALENZA 13 – πX(R) l’operazione di proiezione degli attributi in X della relazione R con

eliminazione dei duplicati

– t[A] il valore che assume il record t sugli attributi in A – α(X) l’insieme degli attributi in X.

– t₁[A] ◦ t₂[B] la concatenazione dei record t₁ e t₂

Infine con le lettere R e D indicheremo delle relazioni mentre con la lettera

E denoteremo una generica espressione relazionale

2.2.2 Definizioni

Le seguenti definizioni costituiscono la base delle dimostrazioni che affronte-remo nelle prossime sezioni; per una trattazione pi`u approfondita di quanto si vede di seguito si rimanda a [AGOB].

1. Sia E un’espressione relazionale e φ una condizione su attributi in E:

t ∈ σφ(E) ⇔ t ∈ E ∧ φ(t).

2. Sia X ⊆ α(E):

t ∈ πX(E) ⇔ ∃t (t ∈ E ∧ t[X] = t)

3. Siano E₁ed E₂espressioni relazionali:

t ∈ (E₁ _φ E₂) ⇔ ∃t, t(t ∈ E₁ ∧ t ∈ E₂ ∧ t ◦ t= t ∧ φ(t))

4. Sia E un’espressione relazionale con A, B ⊆ α(E):

AγF(B)ASC(E) = ∅, se E = ∅

5. Se A= ∅

– γ_F_(B)_AS_C(E) = ∅ se E = ∅

– γ_F_(B)_AS_C(E) = {[C = F (B)]} se E = ∅ 6. E× ∅ = ∅ × E = ∅

7. Sia Y ⊆ X, E un’espressione relazionale X ⊆ α(E):

π_Yb(π_Xb (E)) ≡ πb_Y(E))

8. Data una funzione di aggregazione f , si pu`o in generale sostituirla con un’altra f che gode della propriet`a

(16)

questo rende il calcolo delle funzioni meno costoso. Le fsono: – Se f = MAX → f = identita – Se f = MIN → f = identita – Se f = SUM → f = identita – Se f = AV G → f = identita – Se f = count → f = 1

2.2.3 Equivalenze

Si presentano ora delle equivalenze fra espressioni algebriche che usano γ: 1. Siano A e B due insiemi di attributi; se A∪ B ⊆ X:

AγF(B)ASC(πXb (E)) = AγF(B)ASC(E) (2.1)

Dimostrazione

t ∈AγF(B)ASC(πXb (E))

⇔ t ∈ (_x_∈_{dom(A) {} x} × γ_F_(B)_AS_C(σA=x(πXb (E))))

⇔ t ∈ (_x∈_{dom(A) {x} × γ} F(B)ASC(πbX(σA=x(E)))) Per la regola 7 e per

le ipotesi fatte sull’operatore di raggruppamento possiamo passare a

t ∈ ( x∈dom(A) {x} × γF(B)ASC(σA=x(E))) ⇔ t ∈ AγF(B)ASC(E) 2. Se A `e una superchiave di E:

AγF(B)(E) = πA,F(B)(E) (2.2)

Dimostrazione

t ∈AγF(B) AS C(R)

⇔ t ∈ (_x_∈_{dom(A) {x} × γ} F(B)ASC(σA=x(E)))

⇔ t ∈ (_x_∈_{dom(A) {} x} × (σA=x(E)))

poich`e A `e una superchiave di R per ogni valore che assume l’n-upla x esi-ste esattamente un record con quel valore per gli attributi in α(A)(infatti x varia sul dominio dei valori attivi). Possiamo usare la regola 8 per trasfor-mare le funzioni di aggregazione in F e passare a:

t ∈ (

x∈dom(A) {x}×(σA=x(E))) ⇔ t ∈ (

x∈dom(A) {x}×πA,F(σA=x(E)))

(17)

2.2. REGOLE DI EQUIVALENZA 15

3. Se A `e un insieme di attributi e φ `e una restrizione che usa solo attributi in

A: σφ(AγF(B)ASC(E)) = AγF(B)ASC(σφ(E)) (2.3) Dimostrazione t ∈ σφ(AγF(B)ASC(E)) ⇔ t ∈ (AγF(B)ASC(E)) ∧ φ(t) ⇔ t ∈ (_x_∈_{dom(A) {} x} × γ_F_(B)_AS_C(σA=x(E))) ∧ φ(t)

⇔ t ∈ (_x_∈_dom_{(A) ∧ φ {x} × γ} F(B)ASC(σA=x(E)))

Infatti se φ elimina un record t risultato di AγF(R), dal momento che

uti-lizza solo attributi in A, eliminer`a da E tutti i record che hanno originato t che per definizione dell’operatore γ hanno lo stesso valore per t[A]. Allo-ra:

t ∈ (

x∈dom(A) ∧ φ {x} × γF(B)ASC(σA=x(E)))

⇔ t ∈ (_x_∈_{dom(A) {x} × γ} F(B)ASC(σ(A=x) ∧ φ(E)))

⇔ t ∈ (_x_∈_{dom(A) {} x} × γ_F_(B)_AS_C(σA=x(σφ(E))))

⇔ t ∈ AγF(B)ASC(σφ(E))

4. Siano A e B insiemi di attributi e v un valore ammissibile per gli attributi in α(B): σC<v(AγM IN(B)ASC(E)) =AγM IN(B)ASC(σB<v(E)) (2.4) Dimostrazione t ∈ σC<v(AγM IN(B)ASC(E)) ⇔ t ∈ (AγM IN(B)ASC(E)) ∧ t[C] < v ⇔ t ∈ (_x_∈_{dom(A) {x} × γ} M IN(B)ASC(σA=x(E))) ∧ t[C] < v ⇔ t ∈ (_x_∈_{dom(A) {} x} × σC<v(γM IN(B)ASC(σA=x(E)))) ⇔ t ∈ (_x_∈_{dom(A) {x} × γ} M IN(B)ASC(σA=x ∧ B<v(E)))

Infatti, se σC<velimina un record r il cui valore del campo C `e minimo tra

quelli di σA=x(E), allora ogni record ri ∈ σA=x(E) ha ri[B] ≥ r[C] ≥ v,

e quindi viene eliminato anticipando la restrizione. Si ha:

t ∈ (

(18)

⇔ t ∈ (_x_∈_{dom(A) {} x} × γ_{M IN}_(B)_AS_C(σA=x(σB<v(E))))

⇔ t ∈ AγM IN(B)ASC(σB<v(E))

L’equivalenza vale anche sostituendo < con≤.

5. Siano A e B insiemi di attributi e v un valore ammissibile per gli attributi in α(B): σC>v(AγM AX(B)ASC(E)) =AγM AX(B)ASC(σB>v(E)) (2.5) Dimostrazione t ∈ σC>v(AγM AX(B)ASC(E)) ⇔ t ∈ (AγM AX(B)ASC(E)) ∧ t[C] > v ⇔ t ∈ (_x_∈_{dom(A) {x} × γ} M AX(B)ASC(σA=x(E))) ∧ t[C] > v ⇔ t ∈ (_x_∈_{dom(A) {} x} × σC>v(γM AX(B)ASC(σA=x(E)))) ⇔ t ∈ (_x_∈_{dom(A) {x} × γ} M AX(B)ASC(σA=x ∧ B>v(E)))

Infatti, se σC>velimina un record r il cui valore del campo C `e massimo tra

quelli di σA=x(E), allora ogni record ri ∈ σA=x(E) ha ri[B] ≤ r[C] ≤ v,

e quindi viene eliminato anticipando la restrizione. Vale allora:

t ∈ (

x∈dom(A) {x} × γM AX(B)ASC(σA=x ∧ B>v(E)))

⇔ t ∈ (_x_∈_{dom(A) {x} × γ} M AX(B)ASC(σA=x(σB>v(E))))

⇔ t ∈ AγM AX(B)ASC(σB>v(E))

L’equivalenza vale anche sostituendo > con≥.

6. Se A e b sono attributi di E, b ∈ A, A → b e F sono funzioni di aggregazione su attributi di E: AγF(E) ≡ πAb∪F(A∪{b}γF(E)) (2.6) Dimostrazione t ∈AγF(E) ⇔ t ∈ (_x_∈_{dom(A) × γ} F(B)(σA=x(E))) ⇔ t ∈ (_x_∈_dom(A_{∪ {b}) × γ}F(B)(σA=x(E)))

Infatti: supponiamo che t sia generato dall’aggregazione di due soli record

t₁, t₂. Vale che A→ b e dati t₁, t₂ ∈ E (t₁[A] = t₂[A] ⇔ t₁[A ∪ {b}] = t₂[A ∪ {b}] ⇔ t ∈A∪{b}γF(E)

(19)

2.2. REGOLE DI EQUIVALENZA 17

7. Siano R e D due relazioni, A = AR ∪ AD, con AR e AD insiemi non

vuoti di attributi di R e di D, AD una superchiave di D e F sono funzioni

di aggregazione su AR, allora AγF(R × D) ≡ πAb∪F((ARγF(R)) × D) (2.7) Dimostrazione t ∈AγF(R × D) ⇔ t ∈ (_x₁_∈_dom(A R) x2∈dom(AD) {x1x2} × γF(σARAD=x1x2(R × D))) ⇔ t ∈ (_x 1∈dom(AR) {x1}×γF(σAR=x1(R)))×( x2∈dom(AR) {x2}×γF(σAD=x2(D))) ⇔ t ∈ (_x₁_∈_dom(A R) {x1} × γF(σAR=x1(R))) × D ⇔ t ∈ARγF(R) × D ⇔ t ∈ πb A∪F((ARγF(R)) × D) sfruttando la regola 6. Infatti: sia E₁ = ( x₁ ∈ dom(AR) x₂ ∈ dom(AD){x1 x₂} × γF(σARAD=x1x2(R × D)))

poich`e AR∩ AD = ∅ possiamo distribuire l’unione rispetto al prodotto

cartesiano in E₁; otteniamo cos`ı: t∈

(_x

1∈dom(AR) {x1}×γF(σAR=x1(R)))×(

x2∈dom(AR) {x2}×γF(σAD=x2(D)))

inoltre vale che si raggruppa su una chiave di D quindi il risultato di:

x₂ ∈ dom(AD)

{x2}(σAD=x2(D))

contiene esattamente un record ∀ α(AD) ed `e in definitiva uguale alla

relazione D stessa.

8. Se le funzioni di aggregazione in F sono decomponibili, A ⊂ V , V =

A∪ C e A → V : AγF(B) AS C(R) ≡A γFg(VγFl(R)) (2.8) Dimostrazione t ∈AγFg(VγFl(R) ⇔ t ∈ (_x_∈_{dom(A) {x} × γ} Fg(σA=x( x₁∈dom(V ) {x1} × γFl(σV=x1(R)))))

(20)

⇔ t ∈ [_x_∈_{dom(A) {} x}×γFg(σA=x(

x1∈dom(A∪ C) {x1} × γFl(σA∪C=x1(R))))]

⇔ t ∈ [_x_∈_{dom(A) {x} × γ} Fg(σA=x(A∪CγFl(R)))]

Dal momento che i record che vengono raggruppati sul valore della coppia

(α(A), α(C)) saranno successivamente raggruppati sul valore dei soli

at-tributi in α(A). In altre parole, se anche due record differiscono sul valore di α(C) ma non su α(A) questi saranno uniti nel secondo raggruppamento. Possiamo quindi concludere che:

t ∈ [

x∈dom(A) {x} × γFg(σA=x(A∪CγFl(R)))]

If f t∈ (AγFg(BγFl(R)))

9. Sia a ∈ A un attributo di R tale che A → a ed F un insieme di funzioni di aggregazione su a:

AγF(R) ≡ πAb∪X(A∪{a}γcount(∗) AS GBcount(R)) (2.9)

dove X `e un insieme di espressioni tale che

– a× GBCount AS a ∈ X, se f ∈ F èSUM(a) AS a, – a∈ X, se f ∈ F èMIN(a) AS a,MAX(a) AS a,AVG(a) AS a, – GBCount AS a∈ X, se f ∈ F èCOUNT(a) AS a.

Dimostrazione

t ∈AγF(R)

⇔ t ∈ [_x_∈_{dom(A) {} x} × γF(σA=x(R))]

⇔ t ∈ [_x_∈_dom(A_{∪ {a}) {x} × γ}F(σA∪{a}=x(R))]

⇔ t ∈ (A∪{a}γF(R)); per la regola 2.6 e per le ipotesi sull’insieme X

⇔ t ∈ πb

A∪X(A∪{a}γcount(∗) AS GBcount(R))

2.3 Ipotesi di lavoro

Nel resto del lavoro, salvo ove diversamente specificato, si considera l’otti-mizzazione di interrogazioni del seguente tipo:

SELECT AR, AD, F(B)

(21)

2.3. IPOTESI DI LAVORO 19

WHERE Cj

GROUP BY AR, AD

conBgli attributi di aggregazione, Fle funzioni di aggregazione ed AR, AD

gli attributi di raggruppamento appartenenti ad R e D rispettivamente. Nel seguito A = AR ∪ AD. In particolare ci concentreremo sulla possibilit`a di

effettuare il raggruppamento prima della giunzione. Nel farlo si considerano casi di interrogazioni con due sole relazioni per non appesantire la notazione e la trattazione del problema; in un secondo momento vedremo una generalizza-zione dei problemi affrontati. In questo caso l’interrogageneralizza-zione potr`a riguardare un numero qualsiasi di relazioni. Si stabilisce inoltre che:

– le giunzioni sono equigiunzioni fra chiavi esterne e chiavi primarie. Tali chiavi sono composte di un unico attributo e sono sempre definite. La condizione di giunzione `e dunque: Cj = (fk = pk)

– le tabelle non contengono valori nulli

Nel resto del lavoro, inoltre, capiter`a di utilizzare -con una leggera imprecisione-i termimprecisione-inimprecisione-i: imprecisione-interrogazimprecisione-ione SQL, espressimprecisione-ione algebrimprecisione-ica o albero logimprecisione-ico come

sinonimi. In effetti sappiamo che ad ogni interrogazione SQL `e possibile

associare un’espressione dell’algebra relazionale che la rappresenti e che ta-le espressione possa essere scritta tanto in forma di stringa quanto in for-ma di albero logico con l’idea di dare una pi`u immediata rappresentazione dell’ordinamento fra i diversi operatori che vi compaiono.

Infine, gli esempi che si troveranno nel seguito saranno riferiti al seguente schema di relazione salvo ove diversamente specificato.

(22)

20 CAPITOLO 2. OPERATORI ED OTTIMIZZAZIONE ORDINI AGENTI DATE PRODOTTI FILIALI PKord FKprod FKdata FKag PKag aNome città provincia regione PKdata anno mese giorno PKprod pNome costo FKfil PKfil fNome città provincia regione qt prezzo

(23)

Capitolo 3

RAGGRUPPAMENTO

INVARIANTE

Si presenta con un esempio il primo caso in cui è possibile anticipare il rag-gruppamento rispetto alla giunzione e di seguito una definizione formale del problema che si vuole studiare. Infine, dopo un’analisi di diverse formalizza-zioni della proprietà oggetto di studio, si darà un enunciato con condiformalizza-zioni ne-cessarie e sufficienti per anticipare il raggruppamento rispetto alla giunzione sotto determinate ipotesi.

3.1 Un esempio

Si consideri il seguente esempio:

Esempio 1 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

Supponiamo di voler eseguire la seguente interrogazione:

(24)

22 CAPITOLO 3. RAGGRUPPAMENTO INVARIANTE

SELECT O.FKag, A.aNome, SUM(O.qt) AS amt FROM Ordini O, Agenti A

WHERE O.FKag=A.PKag AND A.regione=’Toscana’ GROUP BY O.FKag,A.aNome

Un possibile albero logico per l’esecuzione prodotto da un ottimizzatore classico `e il seguente:

O.FKag, A.aNomeγSU M(O.qt) AS amt

O.FKag = A.PKag

σA.regione = ’Toscana’

Ordini O

Agenti A

La natura dell’interrogazione, nonchè lo schema su cui questa si effettua, ci inducono a valutare più attentamente i possibili alberi logici. Si osserva che poichè

– il predicato di giunzione interessa solo fke pk

– il raggruppamento avviene sulla chiave esterna

si possono raggruppare gli ordini in base all’agente che li ha commissionati ed in un secondo momento risalire, tramite lajoin sulle chiavi, al nome dell’agente coin-volto (attributo richiesto nella clausola SELECT e GROUP BY). Si osserva altresi che:F KAg → P KAg → aNome. La proprietà 2.6 ci consente di raggruppare esclusivamente sull’attributo FKag ottenendo lo stesso risultato. Inoltre, poichè il calcolo delle funzioni di aggregazione avviene su soli attributi della relazione Ordini, il risultato ottenuto eseguendo prima la giunzione e poi il raggruppamento è seman-ticamente equivalente (a meno di una proiezione) a quello ottenuto eseguendo prima il raggruppamento e poi la giunzione. L’albero logico alternativo che si ottiene è:

π_{O.FKag, A.aNome, amt}b

O.FKag = A.PKag

O.FKagγSU M(O.qt) AS amt σA.regione = ’Toscana’

(25)

3.2. FORMULIAMO IL PROBLEMA 23

In questo secondo caso, l’operazione di raggruppamento effettuata prima della giunzione con la tabellaAgenti, riduce la dimensione della relazioneOrdini. Lajoin

successiva riceve dunque dei dati in ingresso che saranno processati più velocemente con conseguente riduzione del costo computazionale. Si osserva che, sotto determi-nate condizioni, la seconda strategia proposta, cioè l’esecuzione delGroupByprima dellajoin, è meno efficiente della prima; ad esempio:

– Sono presenti indici di giunzione fra le relazione

– Lajoinriduce consistentemente la dimensione delle relazioni

Con questo esempio si è messo in risalto che può essere più efficiente, per un otti-mizzatore, utilizzare la seconda strategia di accesso ai dati rispetto alla prima.

3.2 Formuliamo il problema

Allo scopo di risolvere il problema di quando poter correttamente anticipare ilgroupbysi analizza la formalizzazione dello stesso da parte di diversi autori. Ciò che si vuole mettere in evidenza è il tipo di vincoli che tali formalizzazio-ni impongono; per farlo vedremo dapprima quelle che impongono condizioformalizzazio-ni più restrittive per poi arrivare alle formalizzazioni che abbracciano casi più ampi. Possiamo formulare il problema che affronteremo nelle prossime se-zioni dicendo che, considerate interrogase-zioni come quelle presentate in 2.3, si vuole capire in quali casi è possibile anticipare il γ, sostituendolo even-tualmente con una proiezione, sulla tabella R. Il problema è quindi quello di individuare l’esistenza e l’eventuale struttura di un insieme A con:

AγF(B)(R _f_k_=p_k D) ≡ πA,F(B)((AγF(B)(R) _f_k_=p_k D))

Chiaramente varrà A ⊆ α(R) ed informalmente diremo che la relazione R gode della proprietà diraggruppamento invariantese è possibile anticipare il γ.

3.2.1 Formalizzazione di Galindo Lagaria - Joshi

La prima formalizzazione che andiamo ad esaminare `e quella proposta in [GJM]. In questo caso gli autori esprimono la propriet`a di

(26)

raggruppamen-24 CAPITOLO 3. RAGGRUPPAMENTO INVARIANTE

to invariante fornendo delle condizioni cui gli attributi di raggruppamento e quelli interessati dal predicato di giunzione devono uniformarsi;

Proposizione 1 Sia α(X) l’insieme degli attributi in X

AγF(B)(R _C_j D) ≡ πA,F(B)(AR∪{fk}γF(B)(R) _C_j (D)) (3.1)

se:

1. ogni attributo di giunzione di R `e anche un attributo di raggruppamento 2. la chiave della relazione D `e fra gli attributi di raggruppamento

3. B ⊆ α(R)

La prima e la seconda condizione, garantiscono che un record di D sia incluso al pi`u in un gruppo durante la fase di aggregazione. La terza invece assicura che le funzioni di aggregazione siano calcolabili all’interno della sola relazione R. Delle condizioni fornite dagli autori appare come pi`u restrittiva la seconda. Nell’esempio che segue si mostra che tale condizione garantisce la correttezza semantica del raggruppamento anche nel caso di una giunzione che non sia di tipo chiave esterna - chiave.

Esempio 2 Si consideri la base di dati:

Ordini(PKord, FKprod*, FKdata*, FKag*, aNome, 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

in cui l’attributoaNomedella relazioneAgenti`e stato replicato nella relazioneOrdini. Si vuole risolvere la seguente interrogazione:

SELECT O.FKag, A.citt`a, SUM(O.qt) AS amt FROM Ordini O, Agenti A

WHERE O.aNome=A.aNome AND A.regione=’Toscana’ GROUP BY a.PKag

(27)

Ordini

PKord FKprod FKag prezzo qt aNome

1 1 1 100 12 A

2 400 2 20 1 A

3 14 1 55 3 A

4 21 2 31 5 A

Agenti

PKag aNome citt`a provincia regione

1 A PISA PISA TOSCANA

2 A LIVORNO LIVORNO TOSCANA

due istanze di relazione; immaginando di proiettare le relazioni sui soli attributi di interesse dell’interrogazione si ottiene, dopo la giunzione:

FKag PKag aNome citt`a qt

1 1 A PISA 12 1 2 A LIVORNO 12 2 1 A PISA 1 2 1 A LIVORNO 1 1 1 A PISA 3 1 1 A LIVORNO 3 2 1 A PISA 5 2 2 A LIVORNO 5

e dopo il raggruppamento si trova proprio quello che l’interrogazione richiede. Si nota che, per quanto la chiave della relazioneAgentisia presente fra gli attributi di raggruppamento, questo non garantisce che si possa anticipare il raggruppamento suOrdini. L’interrogazione dovrebbe essere riscritta considerando di raggruppare gli ordini sulla chiave esterna, peraltro garantendo ugualmente la correttezza del risulta-to. Se si raggruppasse sui soli attributi diOrdinipresenti nella clausolaGroupBy, si perderebbe completamente l’informazione relativa all’agente che ha commissionato l’ordine.

(28)

3.2.2 Formalizzazione di Chaudhuri - Shim

Un’alternativa a quanto visto finora `e proposta in [CSO]. In questa si for-malizza la nozione di raggruppamento invariante come propriet`a dell’albero logico associato all’interrogazione. Piuttosto che dare condizioni sugli attri-buti cos`ı come visto nella precedente sezione si danno delle definizioni circa i nodi dell’albero logico che consentono di formalizzare il raggruppamento invariante come una trasformazione fra alberi. Essendoci posti nel caso bi-dimensionale (tabella dei fatti ed una dimensione) si riportano le definizioni adattate al problema cos`ı come posto in 3.2

Vediamo alcune definizioni:

– Definizione 1 Gli attributi necessari di R sono l’unione degli attributi di giunzione e degli attributi di raggruppamento dell’interrogazione contenuti in R

– Definizione 2 Gli attributi di aggregazione candidati di R sono gli attri-buti di aggregazione dell’interrogazione contenuti in R, ma che non sono tra gli attributi necessari del nodo

a questo punto si definisce la propriet`a di raggruppamento invariante come: Proposizione 2 R ha la propriet`a di raggruppamento invariante se valgono

le seguenti condizioni:

1. ogni attributo di aggregazione dell’interrogazione `e un attributo di aggre-gazione candidato di R

2. ogni attributo di giunzione di R `e anche un attributo di raggruppamento dell’interrogazione

3.2.3 Formalizzazione di Yan - Larson

Vediamo ora la soluzione proposta in [YLI]. L’approccio in questo caso è leggermente differente. Si mostra in ogni caso che le conclusioni cui si arriva sono semanticamente equivalenti; gli autori, a differenza di quanto visto fino-ra, non fanno ipotesi sul tipo di giunzione. L’ipotesi è piuttosto quella che gli attributi di aggregazione siano tutti sulla tabella dei fatti. La proprietà di rag-gruppamento invariante in questo caso è esperessa in termini di dipendenze funzionali. Si permette inotre che le chiavi di giunzione assumano il valore

(29)

3.2. FORMULIAMO IL PROBLEMA 27 Proposizione 3 Sia A={AR∪AD} ed A+ = {A∪α(Cj)}. R ha la propriet`a

di raggruppamento invariante

AγF(B)(R _C_jD) ≡ πA,F(B)((AR∪fkγF(B)(R) _C_j D)) (3.2)

se valgono le seguenti condizioni sulla relazione (R _C_j D)

1. DF₁ : A → A+

2. DF₂ : A → RowId(D) `

E interessante allora approfondire il significato delle DF₁ e DF₂; possiamo riscrivere la DF₁ come:

DF₁ : A → A ∪ α(Cj) come noto dai risultati dell’algebra classica ogni

insieme determina banalmente se stesso, quindi concludiamo che:

DF₁ : A → α(Cj); per quanto riguarda invece la DF2gli autori

sottolinea-no che il RowId(D) è un attributo associato ad ogni record in D che, anche se non previsto dallo schema di relazione (e quindi “mantenuto” dal sistema), identifica univocamente il record. Chiaramente questa ipotesi è sinonimo del richiedere che lajoin sia appunto di tipo chiave esterna-chiave. In effetti le chiavi sono attributi, quasi sempre, privi di semantica; determinare un attribu-to privo di semantica è possibile in generale se si possiede una “copia” di que-sto (una chiave esterna) in un’altra relazione. In queque-sto lavoro, per la prima volta, si tocca un tasto centrale in merito all’anticipazione del raggruppamen-to. Già dall’esempio 2 si era avuta l’idea che fosse sufficiente che gli attributi di aggregazione determinassero la riga della relazione dimensionale in giun-zione con le righe della tabella dei fatti. Tale intuigiun-zione viene qui formalizzata generalizzando e semplificando le precedenti formalizzazioni viste.

3.2.4 Riassumiamo

La semplicità della trasformazione di raggruppamento invariante è notevole dal momento che questa ci permette di spostare un nodo di raggruppamento nell’albero logico dell’interrogazione senza quasi modificarne la notazione. Nelle precedenti sezioni abbiamo visto come sia possibile formalizzare il con-cetto. Fra le tecniche utilizzate abbiamo visto formalizzazioni su alberi logici e su insiemi di attributi. Su questi ultimi inoltre abbiamo visto che esiste la possibilità di specificare i vincoli che la proprietà impone sia come restrizioni sugli attributi che come insieme di dipendenze funzionali. In alcuni casi, a

(30)

seconda della tecnica utilizzata per risolvere l’interrogazione, l’anticipazione avviene ponendo come relazione interna dellajoinquella dei fatti piuttosto che quella delle dimensioni. Si osserva che l’interrogazione vista nell’esempio 1 pu`o essere riscritta come

SELECT A.aNome, O.FKag, amt FROM Agenti A,(

SELECT O.FKag, SUM(O.qt) AS amt FROM Ordini O

GROUPBY O.FKag ) WHERE O.FKag=A.PKag AND A.regione=’Toscana’;

Questa `e infatti la tecnica utilizzata in [GJM]. Si tende ad una riscrittura del-l’interrogazione in questa forma per poi ottimizzarne l’esecuzione. In effetti in questa forma l’interrogazione `e sintatticamente corretta e consente di rag-gruppare gli ordini in base alla chiave esternaFKagdiOrdini perAgenti; nel-la precedente forma era obbligatorio raggruppare tanto sulnel-la chiave esterna

FKagquanto sull’attributo aNome di Agenti in quanto entrambi attributi pre-senti nella clausola SELECT. Conseguenza dell’utilizzo di tale tecnica è che l’anticipazione non avviene sulla parte sinistra dell’albero come visto nell’e-sempio quanto su quella destra. Per quanto riguarda la struttura dell’albero logico per interrogazioni che coinvolgano più di una relazione SystemR pro-pone due euristiche che riducono lo spazio di ricerca della soluzione ottima. In [AAC] si mostra come queste regole che producono alberi profondi a si-nistra aumentino la possibilità di utilizzare algoritmi alternativi per eseguire le giunzioni. Altri approcci sono mostrati in [SMK, KS] e sono basati su tecniche di ricerca euristica o di programmazione dinamica. Infine, nell’ul-tima formalizzazione presentata, Yan e Larson ipotizzano che gli attributi di aggregazione siano contenuti in R e danno come condizione per l’anticipa-zione la giunl’anticipa-zione di tipo chiave esterna-chiave, differentemente da quanto si era visto prima. In effetti, negli altri casi, si ipotizza la giunzione di tipo chiave esterna-chiave e si impone come condizione per l’anticipazione che gli attributi di aggregazione siano contenuti in R. A prescindere dalla tecni-ca utilizzata per formalizzare il concetto abbiamo visto che i vincoli che la proprietà impone riguardano gli attributi di raggruppamento, quelli di aggreg-zione e quelli di giunaggreg-zione. Si è anche visto che la discriminante principale fra le diverse formalizzazioni è nelle condizioni relative agli attributi di giun-zione. Nei primi due lavori [GJM] [CSO] infatti si afferma che tali attributi

(31)

3.3. IL RAGGRUPPAMENTO INVARIANTE 29 devono essere anche di raggruppamento. Si passa poi ad una generalizzazio-ne del concetto dicendo che `e sufficiente che gli attributi di raggruppamento determinino quelli di giunzione. Si osserva che: dati due insiemi di attributi

A e B tali che

(A → B) ⇒ (AγF(R) ≡A∪BγF(R))

come visto in 2.6. Possiamo quindi affermare che le prime formalizzazio-ni abbracciano solo un sottoinsieme dei casi in cui `e possibile anticipare il raggruppamento. Nel seguito, riprendendo il lavoro di [ABSD], si formula la nozione di raggruppamento invariante nella forma che riteniamo essere la migliore sia per quanto riguarda la trattazione dal punto di vista algebrico che della generalizzazione al caso n-dimensionale

3.3 Il raggruppamento invariante

L’ultima formalizzazione che si analizza `e quella proposta in [ABSD]. Vedia-mola:

Proposizione 4 Sia A = AR∪ AD con AR ⊆ α(R) ed AD ⊆ α(D) e _C_j

una equigiunzione, con Cj = (fk = pk), dove fk `e la chiave esterna di R per

D e pk la chiave primaria di D.

R ha la propriet`a di raggruppamento invariante

AγF(R _C_j D) ≡ πbA∪F(AR∪{fk}γF(R)) _C_j D) (3.3)

se e solo se valgono le seguenti condizioni:

1. l’attributo fkdi giunzione di R `e determinato dagli attributi A di

raggrup-pamento della relazione R _C_j D;1

2. gli attributi di aggregazione in F sono attributi di R.

1. In assenza di restrizioni su D, se A sono attributi solo di R, si raggruppa solo su A, e la giunzione a destra diventa inutile, avendo supposto fkcon valori non nulli. La giunzione serve solo se in A vi sono chiavi di D diverse dalla pk, oppure dei filtri.

(32)

Nota sulle dimostrazioni

La dimostrazione della proprietà che segue e delle altre che si troveranno nel lavoro sono basate sulle regole di riscrittura presentate in sezione 2.2.3. Con tali dimostrazioni si prova che le condizioni che si danno per l’anticipazione del raggruppamento rispetto alla giunzione sono necessarie e sufficienti. È dunque necessario provare la validità di “entrambi i versi” della trasformazio-ne. Ad una prima occhiata potrebbe sembrare che ciò non avviene; vogliamo richiamare l’attenzione sul fatto che, essendo le dimostrazioni basate appunto su una serie di regole di riscrittura, queste valgono proprio per entrambi i versi della dimostrazione.

Nel dimostrare le propriet`a si far`a quindi uso del seguente schema:

P ⇔ Q

sar`a provato, grazie alle regole di equivalenza, come:

P ⇔ R₁ ⇔ R₂ ⇔ . . . ⇔ Rn ⇔ Q

dove le R₁, . . . , Rn rappresentano appunto le regole precedentemente

dimo-strate. Percorrendo all’indietro il cammino utilizzato per la dimostrazione della sufficienza delle condizioni si ottiene la dimostrazione della necessit`a delle stesse.

Dimostrazione

AγF(R _f_k_=p_k D) ≡A γF(σfk=pk(R × D))

se in R _f_k_=p_kD, A → fk (condizione 1), allora A → pk perch´e fk = pk e

quindi per la regola di equivalenza 2.6:

AγF(R _f_k_=p_kD) ≡ πAb∪F(A∪{fk,pk}γF(σfk=pk(R × D)))

per la regola di equivalenza 2.3:

AγF(R _f_k_=p_kD) ≡ πAb∪F(σfk=pk(A∪{fk,pk}γF(R × D)))

se ogni attributo di aggregazione in F `e un attributo di R (come nelle nostre ipotesi), allora per la regola di equivalenza 2.7:

AγF(R _f_k_=p_kD) ≡ πAb∪F(σfk=pk(π

b

(33)

3.3. IL RAGGRUPPAMENTO INVARIANTE 31

AγF(R _f_k_=p_kD) ≡ πAb∪F(πAb∪{fk,pk}∪F(σfk=pk((A∪{fk}−α(D)γF(R)) × D)))

infine, poich´e la proiezione interna `e superflua:

AγF(R _f_k_=p_k D) ≡ πAb∪F((A∪{fk}−α(D)γF(R)) _f_k_=p_kD)

(34)

(35)

Capitolo 4

RAGGRUPPAMENTO

PARZIALE

Il problema di ottimizzazione delle interrogazioni con groupby è stato par-zialmente illustrato nelle precedenti sezioni introducendo la proprietà di rag-gruppamento invariante. Si illustra ora una seconda proprietà che consente l’anticipazione del raggruppamento rispetto alla giunzione. A differenza di quanto visto per ilraggruppamento invariantein questo caso il raggruppamento viene spezzato in due passi. Di questi solo uno viene eseguito prima della giunzione. Lo scopo della trasformazione è, cos`ı come nel caso precedente, quello di ridurre la dimensione dei risultati intermedi con l’intento di otte-nere un beneficio nell’esecuzione delle operazioni necessarie a calcolare il risultato finale. Lo stile del capitolo ricalca quello del precedente; si vedrà dunque, dopo un esempio, una formalizzazione del problema che si studia ed una serie di soluzioni proposte da diversi autori [YLEA, CSO, TSG]. Infine si fornirà un enunciato con condizioni necessarie e sufficienti per applicare la trasformazione ad espressioni relazionali che rispettino determinate ipotesi.

4.1 Un esempio

Si consideri il seguente esempio

Esempio 3 Si consideri la base di dati

(36)

34 CAPITOLO 4. RAGGRUPPAMENTO PARZIALE

Si vuole risolvere l’interrogazione:

SELECT P.FKfil, sum(O.qt) AS q FROM Ordini O, Prodotti P WHERE O.FKprod = P.PKprod

AND P.costo = 100 GROUP BY P.FKfil;

In figura `e mostrato il piano di esecuzione in forma algebrica che trova un ottimiz-zatore tradizionale: P.FKfilγSU M(O.qt) AS q O.FKprod = P.PKprod σcosto = 100 Prodotti P Ordini O

anticipando il raggruppamento si ottiene invece il seguente piano

P.FKfilγSU M(q) AS q

O.FKprod = P.PKprod

O.FKprodγSU M(O.qt) AS q σcosto = 100

Ordini O Prodotti P

Si noti come nel piano i due raggruppamenti non siano ridondanti, ma calcolino

(37)

4.2 Formuliamo il problema

Per iniziare l’analisi del problema di raggruppamento parziale si vede co-me diversi autori abbiano formalizzato tale nozione. Si considerano ancora una volta interrogazioni del tipo introdotto in 2.3 e si lascia cadere l’ipotesi che gli attributi di raggruppamento determinino quelli di giunzione. Siamo interessati a capire sotto quali condizioni sia possibile anticipare il raggrup-pamento nell’albero logico associato all’interrogazione. In questo caso, per le ipotesi fatte, sarà necessario aggiungere almeno un altro raggruppamento che convogli i gruppi creati dal primo nei gruppi “originali” e completi il calcolo delle funzioni di aggregazione. Quindi, conseguenza dell’applicazione di tale trasformazione ad un albero logico è che un nodo di raggruppamento sia rim-piazzato da più nodi di raggruppamento nell’albero logico trasformato. Ciò che si vuole individuare è l’esistenza ed eventuale struttura di un insieme A tale che:

AγF(R _C_j D) ≡AγFg(AγFl(R) Cj D))

Ancora una volta si avr`a che A ⊆ α(R)

4.2.1 Formalizzazione di Yan - Larson

La prima formalizzazione che si espone `e quella formulata in [YLI].

Proposizione 5 Siano R e D due relazioni con A_R, AR⊆ α(R) ed ADun

insieme di attributi in α(D). L’equivalenza:

AγF(B)(R _C_j D) ≡AR∪ADγFg(B)((A_RγFl(B)(R) CjD))

`e vera se:

1. Le funzioni di aggregazione sono decomponibili 2. B ⊆ α(R)

3. A_R→ AR∪ α(Cj)

Le condizioni individuate sono molto forti e limitano l’applicabilit`a della trasformazione. Ci si rende conto che utilizzando tali regole non sarebbe pos-sibile anticipare il raggruppamento cos`ı come visto nell’esempio. Infatti in quel caso non `e soddisfatta la terza condizione imposta dagli autori.

(38)

4.2.2 Formalizzazione di Tsois - Sellis

Un ulteriore formulazione della proprietà di raggruppamento parziale è dovu-ta a Tsois - Sellis in [TSG]. La formalizzazione è molto simile alla precedente e impone vincoli fra gli attributi di raggruppamento.

Proposizione 6 Sia A = AR∪ AD con AR, AD contenuti in R e D

rispet-tivamente, e siano entrambi i membri dell’equivalenza seguente delle espres-sioni algebriche corrette:

AγF(B)(R _C_j D) ≡AγFg(B)(A_RγFl(B)(R) CjD))

l’equivalenza `e valida se:

1. F contiene funzioni di aggregazione decomponibili 2. A_R→ AR∪ α(Cj)

4.2.3 Formalizzazione di Chaudhuri Shim

Riprendiamo, cos`ı come fatto per il raggruppamento invariante, la formaliz-zazione delraggruppamento parzialeproposta in [CSO]. Gli autori danno una definizione diraggruppamento parzialeper un nodo di un albero logico per poi formalizzare la nozione come trasformazione fra alberi logici.

Definizione 3 Un nodo n di un albero logico gode della propriet`a di rag-gruppamento parzialese contiene tutti gli attributi di aggregazione dell’interro-gazione.

Proposizione 7 Sia T un albero logico ed R un nodo di tale albero che gode della proprietà di raggruppamento parziale. L’albero T ottenuto da T aggiungendo uno o più nodi di raggruppamento come genitori o antenati di R è equivalente a T .

Si nota che questa formulazione risulta pi`u interessante in quanto le uniche assunzioni che si fanno per poter anticipare il raggruppamento sono quelle relative agli attributi di aggregazione dell’interrogazione. A differenza della precedente non si impone alcun vincolo fra gli attributi di raggruppamento del primo groupby e quelli dei raggruppamenti successivi. In generale tali vincoli sono dettati dal calcolo delle funzioni di aggregazione decomponibili e dall’algoritmo che si usa per calcolarle.

(39)

Esempio 4 Si consideri la base di dati

e la seguente interrogazione che calcola il totale delle vendite per citt`a:

SELECT F.citt `a, SUM(O.prezzo) AS FROM Ordini O, Prodotti P, Filiali F

WHERE O.FKprod = P.PKprod AND P.FKfil = F.PKfil GROUP BY F.citta;

Che sarebbe naturalmente valutata producendo il seguente albro logico:

F.cittaγSU M(P.prezzo) P.PKprod=O.FKprod F.PKfil=P.FKfil Ordini Filiali Prodotti

Se per ogni prodotto esiste un gran numero di ordini una strategia alternativa e di costo paragonabile `e espressa dal seguente albero logico:

F.cittaγSU M(p₂) P.FKfil = F.PKfil P.FKfilγSU M(p₁) AS p₂ Filiali O.FKprod=P.PKprod

O.FKprodγSU M(prezzo) AS p₁ Prodotti

(40)

Osserviamo che la seconda strategia proposta prevede un diverso ordinamento fra le giunzioni. Se quello della prima strategia era un ordinamento ottimale (in quanto le relazioni di cardinalità minore erano poste sempre sul ramo esterno dellajoin) nella seconda è necessario valutare attentamente la riduzione di cardinalità delle relazioni ad opera del γ. L’ottimizzatore dovrà dunque valutare quale membro della seguente equivalenza: = F.cittaγSU M(p₂) P.FKfil = F.PKfil P.FKfilγSU M(p1) AS p2 Filiali O.FKprod=P.PKprod

O.FKprodγSU M(prezzo) AS p₁ _Prodotti

Ordini F.cittaγSU M(P.prezzo) P.PKprod=O.FKprod F.PKfil=P.FKfil Ordini Filiali Prodotti

sia il meno costoso.

4.3 Il raggruppamento parziale

Si da ora la definizione, e relativa dimostrazione, della proprietà di raggrup-pamento parzialenella maniera che riteniamo più opportuna dal punto di vista relazionale nonchè dell’estensione di questa al caso n-dimensionale e quindi degli schemi a stella ed a fiocco di neve. Nell’enunciare la proprietà si fa uso della definzione 3.

Proposizione 8 Sia α(X) l’insieme degli attributi in X e _C_j 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 _C_j D) ≡AγFg((AR∪α(Cj)−α(D)γFl(R)) CjD)(4.1)

(41)

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 _C_j 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 _f_k_=p_k D) ≡A γFg(A∪{fk}γFl(R fk=pk D))

per la proposizione 4

AγF(R _f_k_=p_k 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 _f_k_=p_k D) ≡AγFg(A∪{fk}−α(D)γFl(R)) fk=pkD)

(42)

(43)

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 del raggruppa-mento parziale la seguente raggruppamento e conteggio può essere vista come una generalizzazione della proprietà diraggruppamento invariante. Essa è in-fatti ottenuta rilassando alcuni dei vincoli imposti per formalizzare quella pro-prietà. Ancora una volta, ricalcando lo stile dei precedenti capitoli, si vedrà un esempio, la formalizzazione di ciò 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:

e l’interrogazione:

(44)

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:

πb_{O.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

(45)

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 _C_j D) ≡ πbA∪F(AγF(R) _C_j D)

si avrà che A ⊆ α(R) mentre, come già detto, vale B ⊆ α(R) ∪ α(D) Si analizzano ora le formalizzazioni della proprietà diraggruppamento e con-teggio. Anche in questo caso si vedono dapprima le formalizzazioni che im-pongono condizioni più restrittive per poi arrivare a quelle che abbracciano casi più 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. A_R→ AR∪ α(Cj)

Ancora una volta si osserva che la seconda condizione impone un vincolo molto forte per l’applicabilità della trasformazione. In effetti, anche avendo esteso il caso di raggruppamento invariante, ci si rende conto che la trasfor-mazione è molto simile. Questa viene ulteriormente estesa, consentendo il calcolo di più funzioni di aggregazione, con la seguente proposizione:

Proposizione 10 Siano R e D due relazioni con A_R, AR ⊆ α(R) ed

(46)

AγF(B)(R _C_j D) ≡AγFg(B),Fa(BD,CN T)((A_RγFl(BR,count(∗) AS CNT )(R) _C_j D))

`e vera se:

1. Le funzioni di aggregazione sono decomponibili 2. A_R→ 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(arg₁, . . . , argn, count) dove count `e un attributo calcolato in una

precedente aggregazione.

Esempio 6 Sia F un vettore di funzioni del tipo

F(C1, C₂, C₃) = (SUM(C₁), MAX(C₂), MIN(C₃)) 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

(47)

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

(48)

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.

(49)

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

r₁, . . . , 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: