Permanent Memory e Buffer Manager

I file sono divisi in pagine (physical pages) numerate consecutivamente da 0.

o Quando una physical page è trasferita in main memory è chiamata semplicemente page

Ogni pagina contiene al suo interno dei records, costituiti a loro volta da attributi (o campi)

o Ogni record è identificato nel database tramite un RID (record identifier) costituito dalla

coppia (Numero di pagina, Numero di slot)

Si dice che un file R ha:

Numero di records: Nrec(R)

o Ogni record ha lunghezza costante Lr

I record sono salvati in numero di pagine Npag(R)

o Di dimensione Dpag

Il numero di pagine totali si ottiene anche come:

Npag(R) = Nrec(R) x (Lr / Dpag)

Heap Organization

I dati sono ordinati nell’ordine di inserimento, le pagine sono quindi contigue e possono essere

rappresentate come una lista ordinata

Equality search:

𝑁𝑃𝑎𝑔(R)

2 se la key esiste nel file

Npag(R) se non esiste

Range Search:

Npag(R) perchè tutte le pagine devono essere lette

Sequential Organization

I records sono salvati in ordine sequenziale rispetto a una search-key

Equality search:

𝑁𝑃𝑎𝑔(R)

2 sia che la key esista sia che non esista

Range Search:

Viene cercata una chiave nel range k1 <= k <= k2 il costo è quindi

o Lg Npag(R) + Sf x Npag(R)

o Dove Sf è il selectivity factor ottenuto come

Sf = 𝑘2 – 𝑘1

𝑘max – 𝑘min

Hashing Organization

Una table organization si dice:

Primary organization se determina il modo in cui I records sono fisicamente salvati e quindi come

possono essere recuperati. Si può implementare come una funzione che mappa ogni chiave ad un

record. Una primary organization si dice

o Statica se una volta creata, con l’aggiunta di pagine si va in overflow ed è necessario

riorganizzarla, degradando le performance

o Dinamica Se una volta creata la tabella si evolve gradualmente con l’aggiunta o la

rimozione di records

Altrimenti è detta secondary organization. In questo caso la mappatura di ogni chiave a un record è

implementata con un metodo tabulare, dove vengono elencati tutti gli input ed output. La

secondary organization aiuta a rispondere alle query senza modificare la locazione dei dati.

B+-Trees

Tutti i records sono salvati nele foglie, organizzate come una doppia linked list. Questa organizzazione è

anche detta index sequential organization.

Index Organization (B+-Trees)

Se la tabella è salvata come una heap organization, è definito un indice per ogni key, i cui elementi sono (k,

rid) dove k è il valore per un record e rid è l’identificatore del record.

Clustered Index: Un clustered index su una chiave K di una tabella è creato ordinando la tabella sui

valori della chiave K. Se vengono inseriti nuovi records l’efficenza dell’indice cala perchè i dati non

sono più ordinati fisicamente rispetto alla chiave k. Per cui a volte è necessario ricreare l’indice per

riordinare i dati. Esiste solo un clustered index. In pratica un clustered index ha una struttura

uguale a quella dei dati fisici.

Unclustered Index: Si usa una seconda tabella che contiene puntatori alla riga dei dati che contiene

la chiave. Quindi è più lungo il tempo di scrittura del dato. In pratica un unclustered index ha una

struttura che indica per ogni valore dell’indice la posizione della riga contenente i dati della chiave

Definiamo su una tabella R con una chiave K

Numero di record Nrec(R)

Numero di pagine Npag(R)

Numero di foglie dell’indice su K Nleaf(Idx)

Range Search

Unclustered Index:

Sf(ψ) = 𝑣2 – 𝑣1

𝑘max – 𝑘min

Il costo della ricerca è dato da:

Cs = Ci + CD

Dove Ci è il costo di accesso all’indice e CD è il numero di records che soddisfano una data condizione. In

questo caso:

Ci = Sf(ψ) x Nleaf(Idx)

CD = Erec = Sf(ψ) x Nrec(R)

Infatti i record non sono ordinati sull’indice k quidi il numero di pagine da leggere è Erec Per cui il costo è

dato da:

Cs = Ci + CD = [ Sf(ψ) x Nleaf(Idx) ] + [ Sf(ψ) x Nrec(R) ] =

= [ Sf(ψ) x (Nleaf(Idx) + Nrec(R)) ]

Per operazioni con l’index è più conveniente rispetto ad una tableScan solo se Cs < Npag(R)

Clustered Index:

I records sono sempre ottenuti usando l’indice, anche se è stato costruito dai record ordinati, se ci sono

stati altri inserimenti non è detto che i records siano ancora ordinati, si dice quindi che i record sono quasi

ordinati (almost sorted)

Il numero di pagine quindi per trovare Erec è dato da:

Sf(ψ) x Npag(R)

Mentre il costo generale della ricerca con l’uso dell’indice diventa:

Cs = Ci + CD = [ Sf(ψ) x Nleaf(Idx)] + [Sf(ψ) x Npag(R) ] =

= [ Sf(ψ) x (Nleaf(Idx) + Npag(R)) ]

Per operazioni con l’index è più conveniente rispetto ad una tableScan perchè è sempre < Npag(R)

Non-Key Attribute Organizations

Organizzazione sugli attributi, ovvero strutture che recuperano dati di una tabella che soddisfano una certa

query su attirubuti non chiave, ovvero attributi che non identificano univocamente un record.

Inverted indexes

Un inverted index I su un attrributo non chiave K di una tabella R è una lista ordinate dei dati dove per ogni

valore k della chiave K vi è un numjero di records n contenente quell dato valore e la lista ordinate dei RID

di quei record.

In pratica Dato un attributo non-chiave, viene creata una tupla composta da 3 elementi

K: Ovvero l’attributo, con tutti i suoi valori possibili.

o Ad esempio in un tabella, un campo quantità può avere diversi valori per ogni riga, nella

colonna k verranno elencati tutti i possibili valori che assume k

N: Ovvero il numero di records che hanno quel dato valore di k

o Nell’esempio precedente, se ad esempio ci sono 4 righe con Quantità = 2 allora avrò k =

quantità = 2 e n subito affianco con 4

K n

2 4

RID List: Ovvero la lista dei RID dei records contenenti quel dato valore, di conseguenza, se ad

esempio n = 4 allora avrò una RID list di lunghezza 4, con 4 RID differenti

Performance

Nrec(R) Il numero di records di R

Npag(R) Il numero di pagine occupate da R

LR Numero di bytes utilizzati per rappresentare il valore di un singolo record

NI(R) Numero di indici su R

LI Il numero medio di bytes utilizzati per rappresentare il valore di una chiave sull’indice I

Nkey(I) Il numero di chiavi distinte nell’indice I

Nleaf(I) Il numero di foglie nell’indice I

LRID Il numero di bytes utilizzati per rappresentare il RID di un record

Equality Search

Operazione di ricerca per una condizione A = c oppure A = B

Cs = CI + CD

CI Costo per accedere le pagine dell’index per trovare i RIDs dei record che soddisfano la condizione

CD Costo per accedere alle pagine dei dati (I records nella RID list)

Sf(A = v) = 1

𝑁𝑘𝑒𝑦(A) se invece non esiste un indice su A si approssima a 1/ 10

Sf(A = B) = 1

max(𝑁𝑘𝑒𝑦(A),𝑁𝑘𝑒𝑦(B) Se esiste un indice solo su A si approssima a

1

𝑁𝑘𝑒𝑦(A) , invece se

non esiste un indice si approssima a 1/10

Il costo CI si approssima solitamente al costo per accedere alle foglie

CI = Sf(ψ) x Nleaf(I) = 1/ Nkey(I) x Nleaf(I) =

= 𝑁𝑙𝑒𝑎𝑓(I)

𝑁𝑘𝑒𝑦(I)

Se l’indice è unclustered è necessario calcolare una stima del numero di records Erec che soddisfano la

query. Per una semplice condizione A = v, Erec equivale alla lunghezza media della rid-list:

Erec = 𝑁𝑟𝑒𝑐(R)

𝑁𝑘𝑒𝑦(I)

La funzione Φ(k,n) è detta Cardenas formula ed è una stima del numero di pagine (in un file di n pagine)

che contengno almeno un odei k rcords da recuperare usando la rid-list ordinata.

La funzione si approssima come:

Φ(k,n) = 𝑛 (1 − (1 − 1

n)𝑘)

In genere si approssima come

Φ(k,n) ≈ min(k,n)

Il costo CD si approssima invece come:

Se l’indice è unclustered

CD = Φ(Erec, Npag(R)) ≈ min( Erec, Npag(R) )

Se l’indice è clustered

CD = 1

𝑁𝑘𝑒𝑦(I) x Npag(R) =

𝑁𝑝𝑎𝑔(R)

𝑁𝑘𝑒𝑦(I)

Range Search

Operazione di ricerca per una condizione v1 <= A <= v2

Sf(v1 <= A <= v2) = 𝑣2 – 𝑣1

max(𝐴)–min (A) Si approssima a 1/4

Sf(A > c) = max (A) – c

max(𝐴)–min (A) Si approssima a 1/3

Sf(A < c) = c− min (A)

max(𝐴)–min (A) Si approssima a 1/3

Sf(A < B) = 1/3

In generale Sf(ψ1 v ψ2) = Sf(ψ1) + Sf(ψ2) - Sf(ψ1) x Sf(ψ2)

Il costo della ricerca è sempre Cs = CI + CD

Il costo per acceder all’indice è stimato come il costo per visitare le foglie che contengono la rid-list:

CI = Sf(ψ) x Nleaf(I)

Dove Sf(ψ) è il selectivity factor per la condizione v1 <= A <= v2

Sf(ψ) = 𝑣2 – 𝑣1

max(𝐴)–min (A) Si approssima a 1/4

Il numero di accessi alla pagina CD è stimato come:

CD = NoIndexKeyValues x NoPageAccessesForRidList

Dove NoIndexKeyValues = Sf(ψ) x Nkey(I)

Mentre NoPageAccessesForRidList dipende dal fatto che I dati siano ordinate o meno sull’indice, quindi sul

fatto che l’indice sia clustered o unclustered

Quindi il costo CD si approssima come

Se l’indice è unclustered

CD = [ Sf(ψ) x Nkey(I) ] x [Φ( 𝑁𝑟𝑒𝑐(R)𝑁𝑘𝑒𝑦(I)

, Npag(R)) ]

Dove Nrec(R) / Nkey(I) è la lunghezza media delle rid-lists

Se l’indice è clustered

CD = [ Sf(ψ) x Nkey(I) ] x [ 1

𝑁𝑘𝑒𝑦(I) x Npag(R) ]

= Sf(ψ) x Npag(R)

Transaction and Recovery management

Le transazioni sono un gruppo di operazioni sul db che garantiscono che vengono eseguite tutte insieme in

modo atomico e che garantiscano un consistent state del database.

Una transazion e è una sequenza di operazioni sul database e su dati temporanei che rispetta le seguenti

proprietà:

Atomicity : Solo le transazione terminate normalmente (committed transactions) cambiano il

database. Se l’esecuzione di una transazione è interrotta a causa di un problema (aborted

transaction) lo stato del database deve rimanere immutato come se non fosse stata eseguita

nessuna operazione della transazione interrotta

Isolation: Quando una transazione è eseguita in contemporanea con altre l’effetto finale dev’essere

lo stesso come se fosse stata eseguita da sola

Durability: L’effetto di una transazione completata (committed) sul database permane anche a

eventuali problemi o failures, ovvero è irrevocabile.

Undo-Redo algorithms

Si dice che un algoritmo di recovery richiede un undo se un update di qualche transazione non terminata

(uncommitted) è salvato nel db. Se avviene un failure, il recovery algorithm deve rifare gli update copiando

l’immagine del database dal log del db.

Un algoritmo di recovery richiede un redo se una transazione è terminata (committed) prima che tutti i suoi

updates vengano salvati nel db. Se avviene un system failure dopo che la transazione termini ma prima che

gli updates vengano salvati nel database, il recovery algoritm deve fare il redo degli updates copiando

l’immagine dopo la transazione dal log del db.

Checkpoint

Quando parte una procedure di checkpoint:

Vengono sospese le attivazioni di nuove transazioni

Il sistema aspetta che terminano tutte le transazioni attive

Tutte le pagine presenti nel buffer che sono state modificate sono scritte in memoria permanente e

i record scritti nel log (flush operation)

Il CKP record è scritto nel log

Un puntatore a CKP è salvato in un file speciale chiamato restart file

Il sistema permette l’attivazionedi nuove transazioni

Undo – NoRedo Algorithm

Non si fa mai il redo di una transazione dopo un system failure. Viene scritta nel log solo la before-image.

L’operazione di restart è efficiente.

NoUndo-Redo Algorithm

Non si fa mai l’undo di una transazione

Undo-Redo Algorithm

Vengono rifatti sia gli undo che i redo delle transazioni.

Recovery from system and media failures

In caso di un system failure, per recuperare il db bisogna invocare l’operatore di restart (warm restart):

Portare il db nello stato committed rispettando l’esecuzione fino al failure

Ricominciare le normali operazioni di sistema

Fase di rollback, In questa fase si legge il log dalla fine all’inizio:

1. Per fare l’undo se necessario degli updates relativi alle transazioni NON terminate

2. Per trovare un insieme di identificatori di transazioni che sono terminate con successo così da

rifare le loro operazioni.

In particolare si fanno le seguenti operazioni fino al primo checkpoint trovato, costruendo due insiemi

inizialmente vuoti:

Lr (insieme di transazioni che devono essere rifatte, to redo transactions)

Lu (insieme di transazioni che devono essere annullate, to undo transactions)

Se un record è (commit, Ti), Ti è aggiunto a Lr

Se un record è l’update di una transazione Ti , e se Ti non fa parte di Lr, l’operazione è annullata

(undone) e Tè aggiunto a Lu

Se un record è (begin, Ti), Ti è rimosso da Lu

Se un record è (CKP, L), per ogni Ti che fa parte di L, se Ti non appartiene a Lr allora Ti è aggiunto a Lu.

Se Lu non è vuoto, la fase di rollback continua dopo il checkpoint fino ca che Lu non è vuoto.

Fase di rollforward : In questa fase si legge il log dall’inizio alla fine dal primo record dopo il checkpoint per

rifare tutte le oprazioni della transazione Ti terminata con successo, dove Ti appartiene a Lr. Quando un

record è del tipo (commit, Ti ), Ti è rimosso da Lr e questa fase termina quando Lr è vuoto.

Relational Operators

Ogni relazione ha attributi senza valori null, e sono salvati in un file heap con una organizzazione primaria

index sequential. Vengono usati indici su uno o più attributi. Gli indici sono organizzati come B+-Tree e

quelli per attributi non-key sono inverted indexes, con liste RID ordinate. Distinguiamo inoltre tra:

Clustered Index: Index costruito su uno o più attributi di una relazione, ordinati sull’index key.

Accedere ai dati con una scansione delle foglie del non richiede accessi ripetuti alla stessa pagina

della relazione. Una relazione può avere solo un clustered index.

Unclustered index: Costruito su uno o più attributi che non sono usati per ordinare la relazione.

Accedere ai dati con una scan delle fogli del B+-Tree può causare accessi casuali alle pagine della

relazione, che possono essere visitate più di una volta.

Il costo stimato C per eseguire un physical operator è il numero di pagine rette o scritte in permanent

memory per produrre il risultato. In genere:

C = CI + CD

Dove CI è il costo per accedere alle index pages pe rtrovare i RIDs dei record che soddisfano la condizione.

CD è il costo per accedere alle data pages che contengono i records. Se vengono usati gli index il costo CI è

solitamente approssimato al costo per accedere alle foglie.

Physical Operators

SCAN

In tutti i casi, essendo una scan della tabella

Erec = Nrec(R)

TableScan(R)

Retituisce i records di R nell’ordine in cui sono salvate (unsorted)

Costo C = Npag(R)

SortScan(R, {A})

Restituisce i record di R ordinati secondo l’attributo A. L’ordinamento è fatto con un merge sort. Il

costo dipende dal valore Npag(R), dal numero di pagine B del buffer e dall’implementazione del

mergesort.

Il costo del SortScan è :

o C = Npag(R) Se Npag(R) < B

o C = 3 x Npag(R) Se Npag(R) <= B x (B-1)

o C = Npag(R) + 2 x Npag(R) x logB-1 (Npag(R) / b) altrimenti

In genere si assume che Npag(R) <= B x (B-1)

IndexScan(R, I)

Restituisce i records di R ordinati secondo gli attributi Ai dell’indice I

Il costo dipende dal tipo di indice e dal tipo di attributo:

o C = Nleaf(I) + Npag(R) se I è clustered

o C = Nleaf(I) + Nrec(R) se I è su una key di R

o C = Nleaf(I) + [ Nkey(I) x Φ( 𝑁𝑟𝑒𝑐(𝑅)

𝑁𝑘𝑒𝑦(𝐼) , Npag(R) ]

IndexSequentialScan(R, I)

Restituisce I records di R ordinate solo se la primary organization è index sequantial su I. Ordinato

sulla primary key.

Il costo è

o C = Nleaf(I)

PROJECTION

Project(O, {A})

Restituisce i records della proiezione dei records di O sull’attributo A

Il costo è:

o C = C(O)

La cardinalità del risultato è data dalla cardinalità di O (nel physical plan è data quindi della

cardinalità degli operatori che stanno sotto):

o Erec = Nrec(O)

IndexOnlyScan(R, I, {A})

Restituisce i record ordinati sulla proiezioni senza duplicati dei records sull’attributo A. Usabile solo

se gli attributi A da proiettare fanno parte dell’indice I (o se gli attributi da proiettare hanno come

prefissi A)

Il costo è:

o C = Nleaf(I)

La cardinalità del risultato è

o Erec = Nrec(R)

DUPLICATE ELIMINATION (DISTINCT)

La cardinalità del risultato è stimata come:

Erec = Nkey(Ai) Se Ai è il solo attributo di O, con Nkey(Ai) valori distinti

Erec = min(Erec (O)/2, Π Nkey(Ai)) Se vi sono n attributi A1,....,An e ogni attributo ha Nkey(Ai)

valori distinti

Distinct(O)

I records di O DEVONO essere ordinati, così che i duplicati siano affianco. L’operatore restituisce i

records di O ordinati senza duplicati

Il costo è:

o C = C(O)

HashDistinct(O)

Non richiede un input ordinato, ma equivale a fare un sort + distinct e restituisce i records NON

ordinati

Il costo è:

o C = C(O) + 2 x Npag(O)

SORTING

Sort(O, {Ai})

Utilizza il piped merge sort per ordinare i records di O

Il costo è:

o C = C(O) Se Npag(O) < B

o C = C(O) +2 x Npag(O) Se Npag(O) <= B x (B-1)

o C = C(O) + 2 x Npag(O) x logB-1 (Npag(O) / B) altrimenti

La cardinaliutà è:

o Erec = Nrec(O)

SELECTION

Eccetto per Filter, la cardinalità è:

Erec = Sf(ψ) x Nrec(R) In quanto agiscono su R (Filter invece agisce su O)

Filter(O,ψ)

Restituisce i records di O che soddisfano la condizione ψ

Il costo è:

o C = C(O)

IndexFilter(R, I, ψ)

Restituisce i record di R che soddisfano la condizione ψ con l’uso dell’index I, definito sugli attributi

di ψ. Usabile SOLO se ψ è una condizione sugli attributi dell’indice I. Dato che ha come input la

tabella R, può essere usato SOLO come foglia di un physical plan.

Il costo è dato da: C = CI + CD

Dove Ci = Sf(ψ) x Nleaf(I)

Mentre CD dipende dal tipo di indice e dall’attributo su cui è definito:

CD = Sf(ψ) x Npag(R) Se I è clustered

CD = NoListToVisit x NoPageToVisitForList = Sf(ψ) x Nkey(I) x [ Φ( 𝑁𝑟𝑒𝑐(𝑅)

𝑁𝑘𝑒𝑦(𝐼) , Npag(R) ]

Se I è unclustered ed è definito su unna non-key di R

CD = Sf(ψ) x Nrec(R) Se I è unclustered ed è definito su una key di R

IndexSequentialFilter(R, I, ψ)

Da usare solo se ψ è una condizione su I. Restituisce i record ordinati di R

Il costo è:

o C = Sf(ψ) x Nleaf(I)

IndexOnlyFilter(R, I, {Ai}, ψ)

Operatore che esegue anche la proiezione sugli attributi {Ai} , usare solo se ψ è una condizione sugli

attributi I. I risultati sono ordinati. Se {Ai} include una key, i risultati sono senza duplicati

Il costo è:

o C = Sf(ψ) x Nleaf(I)

OrIndexFilter(R, {Ii, ψi}) e AndIndexFilter(R, {Ii, ψi})

Usabile con condizioni ψ1 ᴧ ψ2 ᴧ ..... ᴧ ψn per l’And

O per condizioni ψ1 v ψ2 v ..... v ψn per l’Or

Dove ψi è una condizione sull’indice I

Costo C = CI + CD

Dove CI = ∑ 𝐶𝐼𝑘𝑛

𝑘=1 Ovvero la somma di tutti i CI

Mentre CD = Φ(Erec, Npag(R))

Dove Erec = Sf(ψ) x Nrec(R)

GROUPING

La cardinalità è la stessa del caso del distinct:

Erec = Nkey(Ai) Se Ai è il solo attributo di O, con Nkey(Ai) valori distinti

Erec = min(Erec (O)/2, Π Nkey(Ai)) Se vi sono n attributi A1,....,An e ogni attributo ha Nkey(Ai)

valori distinti

GroupBy(O, {Ai}, {fi})

Per essere usato irecord devono essere ordinati sugli attributi {Ai}, così che i record di ogni gruppo

siano affianco. Restituisce i record ordinati su {Ai}

Il costo è:

o C = C(O)

HashGroupBy(O, {Ai}, {fi})

NON richiede l’input ordinato ed anche il risultato NON è ordinato

Il costo è un pò alto:

o C = C(O) + 2 x Npag(O)

JOIN

La cardinalità in tutti I casi è:

Erec = Sf(ψj) x Erec(OE) x Erec(OI)

NestedLoop(OE, OI, ψj)

Si può usare per qualsiasi condizione ψj

Conviene che l’operatore esterno abbia un numero di record e di pagine inferiore a quello interno

Il risultato è ordinato sugli attributi di OE

Il costo è:

o CNL = C(OE) + Erec(OE) x C(Oi)

PageNestedLoop(OE, OI, ψj)

Meglio del nestedLoop in quanto si considerano le NpagOE anzi che Nrec OE , il risultato del join non è

ordinato

Conviene che all’esterno ci sia una relazione con il minor numero di pagine

Il costo è:

o CPNL = C(OE) + Npag(OE) x C(Oi)

Se gli operandi sono table scan

o CPNL = Npag(R) + Npag(R) x Npag(S)

o CPNL = Npag(S) + Npag(S) x Npag(R)

Conviene quindi che l’operando esterno sia quello con MENO pagine

Conviene rispetto al NestedLoop in quanto Npag(R) < Nrec(R), ma produce risultati non ordinati

BlockNestedLoop(OE, OI, ψj)

Un miglioramento del PageNestedLoop

Il costo è CBNL = Npag(R) + [ 𝑁𝑝𝑎𝑔(𝑅)

𝐵 ] x Npag(S)

o Dove B è la dimensione del buffer, se B riesce a contenere una delle due relazioni il costo si

riduce a Npag(R) + Npag(S)

IndexNestedLoop(OE, OI, ψj)

L’operatore richiede che:

o Il join sia un equi-join (ψj = (OE.Ai = OI.Aj)

o La foglia dell’operando interno sia un IndexFilter(S, I, ψj), con S una relazione e I un indice

sugli attributi del join Aj di S.

Il risultato è ordinato sugli attributi di OE

Il costo è:

o CINL = C(OE) + Erec(OE) x (CI + CD)

o Dove (CI + CD) è il costo per recuperare i matching records di S con un record di OE, e

dipende dal tipo di index (clustered o no) e sul fatto che l’attributo del join di S sia una

chiave o una Foreign key, fermo restando che la condizione sia in predicato di uguaglianza

MergeJoin(OE, OI, ψj)

Funziona solo se:

o Il join è un equi-join (ψj = (OE.Ai = OI.Aj)

o I records di OE e OI sono ordinati sugli attributi del join OE.Ai e OI.Aj

o Nella condizione del join OI.Aj è una chiave per OE (Foreign Key)

Il risultato è ordinato sugli attributi di OE

Il costo è:

o CMJ= C(OE) + C(OI)

HashJoin(OE, OI, ψj)

Il risultato non è ordinato sui join attributes

Il costo è quello del MergeJoin con l’aggiunta di un sorting:

o CMJ= C(OE) + C(OI) + Npag(OE) + Npag(OI)

Query Optimization

DISTINCT Elimination

Sia A l’insieme degli attributi proiettati dalla query. Se A+ contiene la key di OGNI tabella usata nella query,

allora il distinct è inutile. Se nella query c’è un GroupBy, allora affinchè il distinct sia inutile A+ deve

contenere i grouping attributes.

Per il calcolo di A+ (Closure di A):

Aggiungere ad A+ tutti gli attributi X tali che nel “Where” della query appaia X = c dove c è una costante.

Aggiungere anche tutti gli attributi Y tali che, se Z è un sottoinsieme di A+ e Z = Y nel Where. Infine se Z è

una key di una tabella, aggiungere a A+ tutti gli attributi di quella tabella.

In pratica si aggiungono alla closure di A tutti gli attributi che posso ottenere partendo dagli attributi

presenti nel Where.

GROUP BY Elimination

Il Group By è inutile se ogni gruppo risultante ha 1 solo record o se c’è un solo gruppo

WHERE - SUBQUERY Elimination

Nel caso di query con Exists e subquery semplice (Tipo “SELECT FROM WHERE”) si può rimuovere la

subquery portando all’esterno le condizioni del where della subquery e aggiungendo un distinct.

Esempio: SELECT * FROM R WHERE EXISTS (SELECT * FROM T WHERE a = 3) diventa

SELECT DISTINCT FROM R,T WHERE a = 3

VIEW merging

Un GroupBy può essere portato sopra il join in questo modo:

In genere per fare il view merging si sostituisce il logical plan della view e lo si inserisce nella quey

(solitamente con un join)

PRE-GROUPING

In alcuni casi è possibile eseguire il GroupBy prima del join:

In pratica si aggiungono ai grouping attributes gli attributi della condizione Cj del join e si rimuovono gli

attributi della relazione esterna del join. Dopo il join si proiettano i grouping attributes originali insieme ad

eventuali funzioni aggregate . Tutto questo si può fare SOLO se X -> fk (La foreign key della relazione interna

è determinata dai grouping attributes) e se le funzioni F usano solo attributi di R.