Architettura di un DBMS

Un DBMS deve garantire una gestione dei dati:
–
–
–
–
–

1
efficiente
concorrente
affidabile
integra
sicura (protetta)
Ciascuno degli aspetti precedenti è supportato dal
DBMS da specifiche componenti, che
complessivamente rappresentano l’architettura del
sistema
Componenti di un DBMS

Efficienza:
–
–
–
–
2
File system: gestisce l'allocazione dello spazio su
disco e le strutture dati usate per rappresentare le
informazioni memorizzate su disco
Buffer manager: responsabile del trasferimento
delle informazioni tra disco e main memory
Query parser: traduce i comandi del DDL e del
DML in un formato interno (parse tree)
Optimizer: trasforma una richiesta utente in una
equivalente ma più efficiente
Componenti di un DBMS

Affidabilità:
–

Concorrenza:
–

Integrity manager: controlla che i vincoli di integrità (per
esempio le chiavi) siano verificati
Sicurezza
–
3
Concurrency controller: assicura che interazioni concorrenti
procedano senza conflitti
Integrità:
–

Recovery manager: assicura che il DB rimanga in uno stato
consistente a fronte di cadute del sistema
Authorization manager: controlla che gli utenti abbiano i diritti
di accesso ai dati
Componenti di un DBMS

Un DBMS contiene inoltre alcune strutture dati che
includono:
–
–
–
–
4
i file con i dati (cioè i file per memorizzare il DB stesso)
i file dei dati di sistema (che includono il dizionario dei dati e le
autorizzazioni)
indici (esempio Btree o tabelle hash)
dati statistici (esempio il numero di tuple in una relazione) che
sono usati per determinare la strategia ottima di esecuzione
Efficienza




5
Finora (Basi di dati 1) abbiamo visto modelli di DBMS
ad alto livello (livello logico)
Tale livello è il livello corretto per gli utenti del DB
Un fattore importante nell'accettazione da parte
dell'utente è dato dalle prestazioni
Le prestazioni del DBMS dipendono dall'efficienza
delle strutture dati e dall'efficienza del sistema
nell'operare su tali strutture dati
Efficienza




6
Esistono varie strutture alternative per
implementare un modello dei dati
La scelta delle strutture più efficienti dipende
dal tipo di accessi che si eseguono sui dati
Normalmente un DBMS ha le proprie strategie
di implementazione di un modello dei dati
Tuttavia l'utente (esperto) può influenzare le
scelte fatte dal sistema (livello fisico)
Mapping di relazioni a file


Per DBMS di piccole dimensioni (es. per PC) una
soluzione spesso adottata è di memorizzare ogni
relazione in un file separato
nel caso di DBMS large-scale questa strategia di base
deve essere estesa (molto spesso il DBMS deve poter
allocare in modo opportuno i record ai blocchi per
minimizzare le operazioni di I/O)
–
–
7
una strategia frequente è di allocare per il DBMS un unico
grosso file, in cui sono memorizzate tutte le relazioni
la gestione di questo file è lasciata al DBMS
Clustering

Si consideri la seguente interrogazione:
SELECT Imp#, Nome, Sede
FROM Impiegati, Dipartimenti
WHERE Impiegati.Dip# = Dipartimenti.Dip#


una strategia di memorizzazione efficiente è basata sul
raggruppamento (clustering) delle tuple che hanno lo
stesso valore dell'attributo di join
il clustering può rendere inefficiente l'esecuzione di
altre interrogazioni
–
8
es. SELECT * FROM Dipartimenti
Clustering
9
Strutture ausiliarie di accesso


10
Spesso le interrogazioni accedono solo un
piccolo sottoinsieme dei dati
Per risolvere efficientemente le interrogazioni
può essere utile allocare delle strutture
ausiliarie che permettano di determinare
direttamente i record che verificano una data
query (senza scandire tutti i dati)
Strutture ausiliarie di accesso

Ogni tecnica deve essere valutata in base a:
–
–
–
–


11
tempo di accesso
tempo di inserzione
tempo di cancellazione
occupazione di spazio
Molto spesso è preferibile aumentare l'occupazione di
spazio se questo contribuisce a migliorare le
prestazioni
Si usa il termine chiave di ricerca per indicare un
attributo o insieme di attributi usati per la ricerca
(diverso dalla chiave primaria)
Strutture ausiliarie di accesso

Una ricerca può essere effettuata per:
–
chiave primaria: il valore della chiave identifica un unico record

–
chiave secondaria: il valore della chiave può identificare più
record

–
Es. i contribuenti con reddito compreso tra 60 e 90 milioni
combinazioni delle precedenti

12
Es. i contribuenti di Genova
intervallo di valori (sia per chiave primaria che per secondaria)

–
Es. il contribuente con codice fiscale GRRGNN69R48
Es. i contribuenti di Genova e La Spezia con reddito compreso tra
60 e 90 milioni
Strutture ausiliarie di accesso
13

Per effettuare la ricerca in modo più efficiente
si può pensare di mantenere il file ordinato
secondo il valore di una chiave di ricerca

in questo caso però la ricerca su altri campi è
inefficiente
Strutture ausiliarie di accesso

Organizzazioni primarie:
–

organizzazioni secondarie:
–

14
impongono un criterio di allocazione dei dati
(organizzazioni ad albero o hash)
uso di indici (separati dal file dei dati) normalmente
organizzati ad albero
in generale si hanno a disposizione più
modalità (cammini) di accesso ai dati
Strutture ausiliarie
di accesso
15
Indici

Idea base: associare al file dei dati una
“tabella'’ nella quale l'entrata iesima memorizza
una coppia (ki ,ri ) dove:
–
–
ki è un valore di chiave del campo su cui l'indice è
costruito
ri è un riferimento al record (ai record) con valore di
chiave ki

16
il riferimento può essere un indirizzo (logico o fisico) di
record o di blocco
Indici: esempio

File dei dati:
chiavi
indirizzi

indice:
chiave ki
c2
c4
c5
c7
c11
17
c5 c2 c11 c7 c4
0 8 16 32 48
indirizzo ri
8
48
0
32
16
Indici



18
Le diverse tecniche differiscono nel modo in cui
organizzano l'insieme di coppie (ki ,ri )
vantaggio nell'uso di un indice:
– la chiave è solo parte dell'informazione contenuta in
un record, quindi l'indice occupa meno spazio del
file dei dati
un indice può comunque raggiungere notevoli
dimensioni che determinano problemi di gestione simili
a quelli del file dei dati
Indici

Esempio:
–
Indice per un file di 50k record, in cui i valori di
chiave sono stringhe di 20 byte e i puntatori sono di
4 byte, richiede circa 1,2Mb



19
ogni entrata nell’indice: 20 + 4 byte
numero max entrate: 50 k
totale: 24 * 50 K = 1,2 Mb
Tipi di indice

20
Gli indici possono essere classificati rispetto a
diverse dimensioni:
– unicità valori chiave di ricerca
– ordinamento dei record nel file di dati
– numero di entrate nell’indice
– numero di livelli
Unicità dei valori di chiave

Indice su chiave primaria:
–

Indice su chiave secondaria:
–
21
indice su un attributo che è chiave primaria per la
relazione (a ogni entrata dell'indice corrisponde un
solo record)
indice su un attributo che non è chiave primaria per
la relazione (ad ogni entrata dell'indice possono
corrispondere più record)
Ordinamento dei record nel file dei
dati

Indice clusterizzato (o indice primario):
–

indice non clusterizzato (o indice
secondario):
–
22
indice sull'attributo secondo i cui valori il file dei dati
è mantenuto ordinato
indice su un attributo secondo i cui valori il file dei
dati non è mantenuto ordinato
Numero di coppie nell’indice

Indice denso
–

Indice sparso
–
23
indice il cui numero di entrate (ki, ri) è pari al
numero di valori di ki
indice il cui numero di entrate (ki, ri) è minore del
numero di valori di ki
Numero di livelli

Indice a singolo livello
–

Indice multilivello
–
24
indice organizzato su un singolo livello
indice organizzato su più livelli
Indici densi e sparsi

Indice denso: l'indice contiene un'entrata per ogni
valore della chiave di ricerca nel file
–
–

Indice sparso: le entrate dell'indice sono create solo
per alcuni valori della chiave.
–
–
25
Ricerca: scansione per trovare il record con valore chiave
uguale al valore cercato
recupero dati fino a che il valore non cambia
Ricerca: scansione fino a trovare il record con il più alto valore
della chiave che sia minore o uguale al valore cercato
scansione sequenziale del file dei dati fino a trovare il record
cercato
Indice denso
26
Indice sparso
27
Indici densi e sparsi



28
Un indice denso consente una ricerca più veloce, ma
impone maggiori costi di aggiornamento
Un indice sparso è meno efficiente ma impone minori
costi di aggiornamento
Poiché molto spesso la strategia è di minimizzare il
numero di blocchi trasferiti, un compromesso spesso
adottato consiste nell'avere una entrata nell'indice per
ogni blocco
Indici multilivello


Un indice anche se sparso può essere di
dimensioni notevoli
Esempio:


29
file di 100000 record, con 10 record per blocco, richiede
un indice con 10000 entrate
se ogni blocco contiene 100 entrate dell’indice: 100 blocchi
Indici multilivello


Se l’indice è piccolo, può essere tenuto in
memoria principale
molto spesso, però, è necessario tenerlo su
disco e la scansione dell’indice può richiedere
parecchi trasferimenti di blocchi
–

Soluzione:
–
30
circa 7 nel nostro esempio, se si utilizza ricerca
binaria
–
si tratta l’indice come un file e si alloca un indice
sparso sull’indice stesso
si parla di indice sparso a due livelli
Indici multilivello

31
se l’indice esterno è
mantenuto in memoria
principale basta accedere
un solo blocco di indice
Tecniche di indicizzazione

32
Le strutture per MS differiscono da quelle per
MM perché si cerca di minimizzare il numero di
blocchi acceduti (che determina il costo della
ricerca)
– basate su alberi (B-tree e varianti)
– basate su tabelle hash
B-Alberi


i B-alberi sono organizzazioni ad albero bilanciato,
utilizzate come strutture di indicizzazione per dati in
memoria secondaria
requisiti fondamentali per indici per memoria
secondaria:
–
–
–
33
bilanciamento: l’indice deve essere bilanciato rispetto ai
blocchi e non ai singoli nodi (è il numero di blocchi acceduti a
determinare il costo I/O di una ricerca)
occupazione minima: è importante che si possa stabilire un
limite inferiore all’utilizzazione dei blocchi, per evitare una
sotto-utilizzazione della memoria
efficienza di aggiornamento: le operazioni di aggiornamento
devono avere costo limitato
B-alberi



34
garantiscono un’occupazione di memoria almeno del
50% (almeno metà di ogni pagina allocata è
effettivamente occupata)
consentono di effettuare l’operazione di ricerca con
costo, nel caso peggiore, logaritmico nella cardinalità
dell’indice (cioè nel numero di valori distinti della
chiave di ricerca)
in un B-albero ogni nodo ha al più m figli, dove m è
l’unico parametro dipendente dalle caratteristiche della
memoria, cioè dalla dimensione del blocco
B-alberi

Un B-albero di ordine m (m  3) è un albero bilanciato
che soddisfa le seguenti proprietà:
–
–
–


35
ogni nodo contiene al più m - 1 elementi
ogni nodo contiene almeno m / 2  1 elementi,
la radice può contenere anche un solo elemento
ogni nodo non foglia contenente j elementi ha j +1 figli
ogni nodo ha una struttura del tipo:
p0(k1, r1)p1(k2, r2)p2 . . . pj-1(kj, rj)pj
dove j è il numero degli elementi del nodo
B-alberi
In ogni nodo



p0(k1, r1)p1 (k2, r2)p2 . . . pj-1(kj, rj)pj
k1, ... , kj sono chiavi ordinate, cioè k1 < k2 < ... < kj
nel nodo sono presenti j + 1 riferimenti ai nodi figli
p0,..., pj e j riferimenti al file dei dati r1, ... , rj
per ogni nodo non foglia, detto K(pi) (i = 1, ... , j)
l’insieme delle chiavi memorizzate nel sottoalbero di
radice pi, si ha:
–
–
36
–
y  K(p0), y < k1
y  K(pi), ki < y < ki+1, i = 1, ... , j - 1
y  K(pj), y > kj
B-alberi

37
Formato di un nodo di un B-albero
B-alberi

38
Esempio di B-albero di ordine 5
B+-alberi

Un B-albero è molto efficiente per la ricerca e la
modifica dei singoli record
–

un B-albero non è però particolarmente adatto per
elaborazioni di tipo sequenziale nell’ordine dei valori di
chiave, né per la ricerca dei valori di chiave compresi
in un certo intervallo
–

39
ad esempio, con m = 100 e N = 1000000 la ricerca di una
chiave comporta al massimo 4 accessi a disco
la ricerca del successore di un valore di chiave può
comportare la scansione di molti nodi
per ovviare a questo problema è stata proposta una
variante dei B-alberi, nota come B+-alberi
B+-alberi

Idea principale: in un B-albero, i valori di chiave
svolgono una duplice funzione:
–
–

nei B+-alberi queste funzioni sono mantenute
separate:
–
–
40
separatori: per determinare il cammino da seguire nella
ricerca
valori di chiave: permettono di accedere all’informazione ad
essi associata
le foglie contengono tutti i valori di chiave
i nodi interni (organizzati a B-albero) memorizzano dei
separatori la cui sola funzione è determinare il giusto cammino
nella ricerca di una chiave
B+-alberi


i nodi foglia sono inoltre collegati a lista, per
facilitare ricerche per intervalli di chiavi o
sequenziali (+ puntatore alla testa di tale lista,
per accedere velocemente al valore di chiave
minimo)
parziale duplicazione delle chiavi
–
–
41
le entrate dell’indice (chiavi e riferimenti ai dati)
sono solo nelle foglie
la ricerca di una chiave deve individuare una foglia
B+-alberi


42
il sottoalbero sinistro di un separatore contiene
valori di chiave minori del separatore, quello
destro valori di chiave maggiori od uguali al
separatore
nel caso di chiavi alfanumeriche facendo uso di
separatori di lunghezza ridotta si risparmia
spazio
B+-alberi

Un B+-albero di ordine m (m  3) è un albero
bilanciato che soddisfa le seguenti proprietà:
ogni nodo contiene al più m - 1 elementi
– ogni nodo, tranne la radice, contiene almeno
m / 2  1 elementi, la radice può contenere anche un
solo elemento
– ogni nodo non foglia contenente j elementi ha j +1
figli
–
43
B+-alberi

ogni nodo foglia ha una struttura del tipo:
(k1, r1)(k2, r2) . . . (kj, rj)
dove:
–
–
–

44
j è il numero degli elementi del nodo
k1, ... , kj sono chiavi ordinate, cioè k1 < k2 < ... < kj
r1, ... , rj sono j riferimenti al file dei dati
ogni nodo foglia ha un puntatore al nodo foglia
precedente e successivo
B+-alberi

ogni nodo non foglia ha una struttura del tipo:
p0k1p1k2p2 . . . pj-1kjpj
dove:
–
–
–
45
j è il numero degli elementi del nodo
k1, ... , kj sono chiavi ordinate, cioè k1 < k2 < ... < kj
p0, … , pj sono j+1 riferimenti ai nodi figli
B+-alberi

46
per ogni nodo non foglia, detto K(pi) (i = 0, ... ,
j) l’insieme delle chiavi memorizzate nel
sottoalbero di radice pi, si ha:
–
 y  K(p0), y < k1
–
 y  K(pi), ki  y < ki+1, i = 1, . . . , j - 1
–
 y  K(pj), y  kj
–
ogni ki, per i = 1, . . . , j è l’elemento minimo di K(pi)
B+-alberi
47
B+-alberi

48
Esempio di B+-albero di ordine 5
B+-alberi: confronto con B-alberi




49
HP: parità di dimensione dei nodi
la ricerca di una singola chiave è più costosa in media
in un B+-albero (si deve necessariamente raggiungere
sempre la foglia per ottenere il puntatore ai dati)
per operazioni che richiedono il reperimento dei record
ordinati in base al valore della chiave o per intervalli di
chiave i B+- alberi sono da preferirsi (il collegamento a
lista delle foglie elimina la necessità di accedere ai
nodi ad altri livelli)
il B-albero è più conveniente per quanto riguarda
l’occupazione di memoria (le chiavi sono memorizzate
una volta sola)
Organizzazioni hash





50
Le organizzazioni hash sono usate principalmente per
l’organizzazione primaria dei dati
l’uso di indici ha lo svantaggio che è necessario
eseguire la scansione di una struttura dati per
localizzare i dati
questo perché l’associazione
(chiave, indirizzo)
è mantenuta in forma esplicita
un’organizzazione hash utilizza una funzione hash H
che trasforma ogni valore di chiave in un indirizzo
per effettuare la ricerca, data una chiave k, si calcola
semplicemente H(k)
Organizzazioni hash





51
Ogni indirizzo generato dalla funzione hash individua
una pagina logica, o bucket
il numero di elementi che possono essere allocati nello
stesso bucket determina la capacità c dei bucket
se una chiave viene assegnata a un bucket che già
contiene c chiavi si ha un trabocco (overflow)
la presenza di overflow può richiedere l’uso di un’area
di memoria separata, detta area di overflow
l’area di memoria costituita dai bucket indirizzabili dalla
funzione hash è detta area primaria
Organizzazioni hash
c
h(key) mod M
key
h
0
1
2
…
c
…
…
…
…
M-1
area primaria area di overflow
52
Organizzazioni hash



Una funzione hash genera M indirizzi (0, . . . ,M - 1)
tanti quanti sono i bucket dell’area primaria
organizzazione statica: il valore di M è costante (il
dimensionamento dell’area primaria è parte integrante
del progetto dell’organizzazione)
organizzazione dinamica: l’area primaria si espande
e contrae, per adattarsi al volume effettivo dei dati (si
usano più funzioni hash)
–
–
53
Hash lineare (non lo vediamo)
Hash estensibile
Hashing estensibile



54
l’hashing estensibile fa uso di una struttura
ausiliaria, detta direttorio
il direttorio è un insieme di 2p celle, con indirizzi
da 0 a 2p-1, con p >= 0 profondità del direttorio
l’espansione dell’area dati avviene
aggiungendo una nuova pagina ogni volta che
si tenta di inserire un record in una pagina
satura
Hashing estensibile


55
idea: fare uso di una funzione hash che, dato un valore
di chiave ki, restituisce non un indirizzo di bucket, ma
una stringa binaria di opportuna lunghezza (ad
esempio, 32 bit) detta pseudochiave
la funzione hash associa ad ogni chiave una
pseudochiave di cui si considerano i primi p bit per
accedere direttamente ad una delle 2p celle, ognuna
contenente un puntatore ad un bucket
Hashing estensibile: esempio
56
Hashing estensibile


57
ogni bucket ha una profondità locale p’<=p
(mantenuta nel bucket) che indica il numero
effettivo di bit usati per allocare le chiavi nel
bucket stesso
una cella del direttorio contiene il riferimento ad
una pagina dell’area dati contenente tutte e
sole le registrazioni con pseudochiavi con lo
stesso prefisso di lunghezza p’
Hashing estensibile: esempio
p=3
58
Hashing estensibile

per effettuare la ricerca di un record:
–
–
–
59
si estraggono i primi p bit dalla pseudochiave
si accede l’entrata dell’indice che corrisponde alla
stringa di p bit
dall’entrata si determina l’indirizzo della pagina del
file che contiene il record cercato
Hashing estensibile

per effettuare l’inserimento di un record:
–
–
60
inizialmente si ha un solo bucket e p = p’ = 0
quando si deve inserire un record in una pagina
satura di profondità p’, se p = p’ innanzitutto si
raddoppia il direttorio e si incrementa p di 1,
copiando i valori dei puntatori nelle nuove celle
corrispondenti
Hashing estensibile
–
–
61
sia nel caso p = p’ che nel caso p’ < p, si alloca un
nuovo bucket e si distribuiscono le chiavi tra i due
bucket (quello saturo e quello appena allocato)
facendo uso del p’+1-esimo bit delle pseudochiavi
per i due bucket si pone a p’+1 la profondità locale e
si aggiorna il direttorio facendo in modo che una sua
cella contenga un riferimento al nuovo bucket
Esempio 1
62
Esempio 2
63
Esempio 2 – cont.
64
Esempio 3
65
Confronto tra indici e hashing

se la maggior parte delle interrogazioni ha la
forma
SELECT A1,A2,......An FROM R WHERE Ai=C

la tecnica hash è preferibile
infatti:
–
–
66
la scansione di un indice ha un costo proporzionale
al logaritmo del numero di valori in R per Ai
in una struttura hash il tempo di ricerca è
indipendente dalla dimensione della base di dati
Confronto tra indici e hashing

gli alberi sono preferibili se le interrogazioni
usano condizioni di range
SELECT A1,A2,......An FROM R
WHERE C1 < Ai < C2

67
è infatti difficile determinare funzioni hash che
mantengono l’ordine
Definizione di cluster e indici in
SQL



68
la maggior parte dei DBMS relazionali fornisce varie
primitive che permettono al progettista della base di
dati di definire la configurazione fisica dei dati
queste primitive sono rese disponibili all’utente come
comandi del linguaggio SQL
non esiste uno standard, ma la sintassi non differisce
molto nei vari sistemi per quanto riguarda i comandi
principali
Definizione di cluster e indici in
SQL


69
i comandi più importanti sono il comando per la
creazione di indici, su una o più colonne di una
relazione, e il comando per la creazione di cluster
un cluster permette di memorizzare fisicamente
contigue le tuple di una o più relazioni che hanno lo
stesso valore per una o più colonne, dette colonne del
cluster
Definizione di cluster e indici in
SQL

il comando per la creazione di un indice in SQL
ha il seguente formato:
CREATE INDEX Nome Indice
ON Nome Relazione(Lista Nomi Colonne) |
Nome Cluster
[ASC | DESC];
dove
–
–
70
Nome Indice è il nome dell’indice che si crea
la clausola ON specifica l’oggetto su cui è allocato
l’indice
Definizione di cluster e indici in
SQL

Tale oggetto può essere:
–
–

l’indice può essere allocato su più colonne
–

71
una relazione: si devono specificare i nomi delle colonne su
cui l’indice è allocato
un cluster: l’indice viene allocato automaticamente su tutte le
colonne del cluster
i valori della chiave sono ottenuti come concatenazione di tutti
i valori di tali colonne, normalmente esiste un limite al numero
di colonne (es. in Oracle 16)
le opzioni ASC e DESC specificano se i valori della
chiave dell’indice devono essere ordinati in modo
crescente o decrescente
–
ASC è il default
Definizione di cluster e indici in
SQL - Esempio
72

L’indice creato è in genere un B+-tree o una
sua variante

Per allocare un indice sulla colonna stipendio
della relazione Impiegati
CREATE INDEX idxstipendio
ON Impiegati (stipendio);
Definizione di cluster e indici in
SQL

Definizione di indici clusterizzati (DB2):
CREATE INDEX Nome Indice
ON Nome Relazione(Lista Nomi Colonne)
CLUSTER;


73
una tabella può avere un solo indice
clusterizzato
se la tabella è non vuota quando si crea
l’indice clusterizzato i dati non vengono
automaticamente raggruppati (è necessario
usare una speciale utility REORG)
Definizione di cluster e indici in
SQL

Comando per la creazione di un cluster:
CREATE CLUSTER NomeCluster
(NomeCol1 Dominio_1, . . ,NomeColn Dominio_n)
[INDEX | HASH IS Expr |
HASHKEYS Intero];


NomeCluster è il nome del cluster che si definisce
(NomeCol1 Dominio_1, . . ., NomeColn Dominio_n),
con n >= 1, è la specifica delle colonne del cluster
–
74
tale insieme di colonne è detto chiave del cluster
Definizione di cluster e indici in
SQL

Ogni cluster è sempre associato ad una struttura di
accesso ausiliaria
–
Index:



–
Hash:



75
vengono clusterizzate tuple con lo stesso valore per la chiave del
cluster e indicizzate tramite un indice di tipo B+-albero (default)
conviene se si hanno frequenti interrogazioni di tipo range sulla
chiave del cluster o se le relazioni possono aumentare di
dimensione in modo impredicibile
cluster di tipo index
vengono clusterizzate le tuple con lo stesso valore di hash per la
chiave del cluster e indicizzate tramite una funzione hash
conviene se si hanno frequenti interrogazioni con predicati di
uguaglianza su tutte le colonne e se le relazioni sono statiche
cluster di tipo hash
Definizione di cluster e indici in
SQL - cluster di tipo hash




76
Il DBMS fornisce sempre una funzione hash interna che viene
usata come default (spesso basata sul metodo della divisione)
l’opzione HASHKEYS permette di specificare il numero di valori
della funzione hash
questo valore (se non è un numero primo) viene arrotondato dal
sistema al primo numero primo maggiore
tale valore viene usato come argomento dell’operazione di modulo
usata dal sistema per generare i valori della funzione hash
Definizione di cluster e indici in
SQL - Esempio

Cluster di tipo indice:
CREATE CLUSTER Personale(D# NUMBER);
CREATE INDEX idxpersonnel
ON CLUSTER Personale;

Cluster di tipo hash:
CREATE CLUSTER Personale
(D# NUMBER) HASHKEYS 10;
dato che l’opzione HASHKEYS ha valore 10, il numero
di valori generati dalla funzione hash è 11 (primo
numero primo > 10)
77
Definizione di cluster e indici in
SQL - cluster di tipo hash


È possibile cambiare la funzione hash da utilizzare
tramite l’opzione HASH IS
questa opzione può tuttavia essere usata solo se:
–
–
–
78
la chiave del cluster è composta da campi di tipo intero
l’espressione deve restituire valori positivi
+ altre condizioni
Definizione di cluster e indici in
SQL - cluster di tipo index


se il cluster è di tipo index, prima di poter eseguire
interrogazioni o modifiche è necessario creare un
indice sul cluster tramite il comando di CREATE INDEX
un cluster può includere una o più relazioni
–
–

79
singola relazione: il cluster è usato per raggruppare le tuple
della relazione aventi lo stesso valore per le colonne che sono
chiavi del cluster
più relazioni: il cluster viene usato per raggruppare le tuple di
tutte le relazioni aventi lo stesso valore per la chiave del
cluster (join efficienti su colonne che sono parte della chiave
del cluster)
una relazione deve essere inserita nel cluster al
momento della creazione
Definizione di cluster e indici in
SQL - Esempio

per inserire nel cluster Personale le relazioni
Impiegati e Dipartimenti
CREATE TABLE Impiegati
(Imp# Decimal(4) NOT NULL,
Dip# Decimal(2))
CLUSTER personale (Dip#);
CREATE TABLE Dipartimenti
(Dip# Decimal(4) NOT NULL)
CLUSTER personale (Dip#);
80
Definizione di cluster e indici in
SQL - Esempio

81
i nomi delle colonne delle relazioni su cui si
esegue il clustering non devono
necessariamente avere lo stesso nome della
colonna del cluster, devono però avere lo
stesso tipo
Ottimizzazione delle interrogazioni
82
Ottimizzazione di interrogazioni
83

abbiamo visto finora come organizzare i dati in un DB

normalmente le decisioni sulle strutture da allocare
sono determinate durante la progettazione fisica della
base di dati

la modifica di tali strutture in seguito può essere
costosa

quindi quando una interrogazione è presentata al
sistema occorre determinare il modo più efficiente per
eseguirla usando le strutture disponibili
Ottimizzazione di interrogazioni
84

nell’elaborazione di interrogazioni si trasforma quindi
una query in un query plan

Esempio:
SELECT B,D
FROM R,S
WHERE R.A = “c”  S.E = 2  R.C=S.C
Ottimizzazione di interrogazioni
85
R A
B
C
a
1
10
b
1
c
S C
D
E
10
x
2
20
20
y
2
2
10
30
z
2
d
2
35
40
x
1
e
3
45
50
y
3
Ottimizzazione di interrogazioni

Risposta:
B
2


Come eseguiamo tale interrogazione?
Una possibile strategia è:
–
–
–
86
D
x
fare il prodotto Cartesiano
selezionare le tuple
effettuare la proiezione
Ottimizzazione di interrogazioni
RXS
87
R.A R.B R.C S.C S.D S.E
a
1
10
10
x
2
a
.
.
1
10
20
y
2
C
.
.
2
10
10
x
2
Ottimizzazione di interrogazioni



I piani di esecuzione possono essere descritti
per mezzo dell’algebra relazionale
il piano descritto è
B,D [ sR.A=“c” S.E=2  R.C = S.C (RXS)]
Piano I
B,D
sR.A=“c” S.E=2  R.C=S.C
88
X
R
S
Ottimizzazione di interrogazioni

Altra possibile strategia
B,D
Piano II
89
sR.A = “c”
sS.E = 2
R
S
natural join
Ottimizzazione di interrogazioni
R
A B C
s (R)
s(S)
C D E
a 1 10
A B C
C D E
10 x 2
b 1 20
c 2 10
10 x 2
20 y 2
c 2 10
20 y 2
30 z 2
d 2 35
30 z 2
40 x 1
e 3 45
90
S
50 y 3
Ottimizzazione di interrogazioni


Piano III
si utilizzano gli indici R.A e S.C
–
–
–
–
91
si usa l’indice R.A per selezionare le tuple di R con
R.A = “c”
per ogni valore di R.C trovato si usa l’indice su S.C
per trovare le tuple che matchano
si eliminano le tuple di S tali che S.E  2
si concatenano le tuple di R e S risultanti,
proiettando su B e D
Ottimizzazione di interrogazioni
R
A B C
a 1 10
b 1 20
A=“c”
I2
<c,2,10> <10,x,2>
check=2?
output: <2,x>
e 3 45
92
C
I1
c 2 10
d 2 35
S
C D E
10 x 2
20 y 2
30 z 2
40 x 1
50 y 3
tupla successiva:
<c,7,15>
Ottimizzazione di interrogazioni



93
per interrogazioni complesse esistono più
strategie possibili
il costo di determinare la strategia ottima può
essere elevato
il vantaggio in termini di tempo di esecuzione
che se ne ricava è tuttavia tale da rendere
preferibile eseguire l'ottimizzazione
Ottimizzazione di interrogazioni
Esempio
 Consideriamo le relazioni



Supponiamo di voler trovare il nome degli studenti e la
data degli esami per gli studenti che hanno sostenuto
BD con 30



94
Studenti(MatrS,Nome,Ind,AltreInfo)
Esami(Corso,MatrS,Voto,Data)
SELECT Nome,Data
FROM Studenti NATURAL JOIN Esami
WHERE Corso ='BD' AND Voto =30
Ottimizzazione di interrogazioni



95
Consideriamo un database con 2.000 studenti e
20.000 esami, di cui 500 di BD e di questi solo 50 con
30 (consideriamo solo la scansione sequenziale delle
relazioni)
Se si fa il prodotto cartesiano delle due relazioni, si
ottiene una relazione temporanea con 40.000.000
tuple, da queste si estraggono poi le 50 tuple
desiderate (costo proporzionale a 120.000.000
accessi)
Se si selezionano i 50 esami di BD con 30 e poi si fa il
join di questa relazione temporanea con Studenti si ha
un costo proporzionale a 120.050
Passi nell’esecuzione di
un’interrogazione

Parsing
–

Trasformazioni algebriche
–
–
96
Viene controllata la correttezza sintattica della query e ne
viene generata una rappresentazione interna (parse tree)
La query viene trasformata in una query equivalente ma più
efficiente da eseguire (ci si basa sulle proprietà dell'algebra
relazionale)
Esempi:
 eseguire le operazioni di selezione prima possibile
 evitare join che rappresentano prodotti Cartesiani
Efficienza - Passi nell’esecuzione di
un’interrogazione


97
Selezione della strategia
– si determina in modo preciso come la query sarà eseguita
(per esempio si determina che indici si useranno)
– la scelta della strategia è fatta principalmente in base al
numero di accessi a disco
Esecuzione della strategia scelta
– è possibile eseguire alcuni dei passi a tempo di compilazione
del programma (DB2 e System R usano questa strategia) o a
tempo di esecuzione (Oracle usa questa strategia)
Passi nell’esecuzione di
un’interrogazione
parse
parse tree
SQL query
convert
answer
logical query plan
apply laws
“improved” l.q.p.
estimate result sizes
l.q.p. +sizes
consider physical plans
98
execute
statistics
Pi
pick best
{(P1,C1),(P2,C2)...}
estimate costs
{P1, P2, …}
Passi nell’esecuzione di
un’interrogazione

Esempio: query SQL
SELECT title
FROM StarsIn
WHERE starName IN (
SELECT name
FROM MovieStar
WHERE birthdate LIKE ‘%1960’);
Trovare i film in cui hanno recitato attori nati nel 1960
Schema:
StarsIn(title,year,starName)
MovieStar(name, address, gender,birthdate)
99
Passi nell’esecuzione di
un’interrogazione - parse tree
<Query>
<SFW>
SELECT <SelList> FROM
<FromList>
<Attribute>
<RelName>
title
StarsIn
WHERE
<Condition>
<Tuple> IN <Query>
<Attribute>
( <Query> )
starName
SELECT
10
0
<SelList> FROM
<FromList>
<Attribute>
<RelName>
name
MovieStar
WHERE
<SFW>
<Condition>
<Attribute> LIKE <Pattern>
birthDate
‘%1960’
Passi nell’esecuzione di
un’interrogazione - algebra
title
s
StarsIn
<condition>
<tuple>
<attribute>
10
1
starName
IN
name
sbirthdate LIKE ‘%1960’
MovieStar
Passi nell’esecuzione di
un’interrogazione: logical query plan
title
sstarName=name

StarsIn
name
sbirthdate LIKE ‘%1960’
10
2
MovieStar
Passi nell’esecuzione di un’interrogazione:
improved logical query plan
title
starName=name
StarsIn
name
sbirthdate LIKE ‘%1960’
10
3
MovieStar
Passi nell’esecuzione di un’interrogazione:
stima della dimensione del risultato
necessità di determinare
la dimensione

StarsIn
10
4
s
MovieStar
Passi nell’esecuzione di
un’interrogazione: physical plan
Hash join
10
5
Parametri: ordine di esecuzione dei join,
dimensione della memoria, attributi su
cui si proietta,...
SEQ scan
index scan
StarsIn
MovieStar
Parametri:
condizione di selezione,...
Passi nell’esecuzione di
un’interrogazione: stima dei costi
L.Q.P.
10
6
P1
P2
….
Pn
C1
C2
….
Cn
Scelta del piano di esecuzione migliore
Ottimizzazione di interrogazioni

Un piano di esecuzione di un’interrogazione consiste
quindi in:
–
–
10
7
un ordine di esecuzione delle varie operazioni relazionali
una strategia per l’esecuzione di ogni operazione
Progettazione fisica
10
8
Progettazione fisica



10
9
Dopo la progettazione concettuale e logica dello schema
con le metodologie viste, e la definizione del livello
esterno (viste) abbiamo gli schemi logico e esterno della
base di dati
bisogna però ancora scegliere gli indici e decidere le
strategie di memorizzazione delle relazioni
inoltre gli schemi logici ed esterni ottenuti dalla
progettazione possono dover essere rivisti per esigenze
legate alle prestazioni
Progettazione fisica

11
0
il primo passo per effettuare questa fase di progettazione
è capire il workload:
– quali sono le query più importanti e con che frequenza
vengono eseguite
– quali sono gli aggiornamenti più importanti e con che
frequenza vengono eseguiti
– le prestazioni desiderate/necessarie per tali
interrogazioni e aggiornamenti
Progettazione fisica

Per ogni query nel workload bisogna chiedersi:
–
–
–

Per ogni update nel workload bisogna chiedersi:
–
–
11
1
a quali relazioni accede?
quali attributi ritrova?
quali attributi sono coinvolti in condizioni di selezione/join?
quanto selettive saranno queste condizioni?
quali attributi sono coinvolti in condizioni di selezione/join?
quanto selettive saranno queste condizioni?
il tipo di update (INSERT/DELETE/UPDATE) e gli attributi che
saranno coinvolti nell’aggiornamento
Progettazione fisica
Decisioni da prendere
 quali indici creare
–
–
–

per ogni indice, di che tipo deve essere
–
11
2
quali relazioni devono avere indici
su quali attributi
più di un indice per relazione
clusterizzato? hash/tree? denso/sparso?
Progettazione fisica
Decisioni da prendere
 bisogna modificare lo schema? (tuning schema logico)
– si può decidere di scegliere uno schema in 3NF piuttosto che in
BCNF
– il workload può influenzare le scelte fatte nello scomporre una
relazione in 3NF o BCNF (seguire schemi di normalizzazione
alternativi)
11
3
–
si può scomporre ulteriormente uno schema BCNF
–
si può denormalizzare (cioè disfare un passo di normalizzazione),
o si possono aggiungere campi ad una relazione
–
si può effettuare una scomposizione orizzontale
Progettazione fisica
Decisioni da prendere
 Bisogna modificare le interrogazioni? (tuning delle interrogazioni)
 se un’interrogazione è più lenta di quel che ci si aspetta bisogna
controllare se le statistiche sono troppo vecchie
 a volte più succedere che il DBMS non stia eseguendo il piano
che si pensa - tipicamente questo succede per:
–
–
–
–

11
4
selezioni che coinvolgono valori nulli
selezioni che coinvolgono espressioni aritmetiche o su stringhe
selezioni che coinvolgono condizioni in OR
mancanza di caratteristiche quali strategie index-only o alcuni metodi
di join o stima inesatta delle dimensioni
si deve controllare quale piano viene effettivamente utilizzato e
aggiustare la scelta degli indici o riscrivere l’interrogazione
Progettazione fisica
Scelta degli indici
 Un possibile approccio è:
– si considerano una alla volta le query più importanti
– si considera il piano di esecuzione migliore utilizzando gli
indici attualmente disponibili
– se con un indice addizionale si avrebbe un piano di
esecuzione migliore, lo si aggiunge
 prima di creare un indice, però, bisogna anche considerare
l’impatto degli aggiornamenti sul workload!
 trade-off:
11
5
–
–
gli indici possono velocizzare le query ma rallentare gli aggiornamenti
inoltre richiedono spazio su disco
Progettazione fisica
Scelta degli indici
 gli attributi che appaiono in una clausola WHERE sono
candidati come chiavi per un indice
–
–
–


11
6
se la condizione è di uguaglianza può essere meglio un indice hash
se la condizione è di tipo range si preferisce un indice ad albero
la clusterizzazione su tale attributo è particolarmente utile in caso di
query tipo range, ma può essere utile anche per l’uguaglianza se ci
sono duplicati
bisogna cercare di scegliere indici che siano utilizzabili nel
maggior numero possibili di query
un solo indice per relazione può essere clusterizzato, per
sceglierlo ci si basa sulle interrogazioni importanti che
trarrebbero maggior vantaggio dalla clusterizzazione
Progettazione fisica
Scelta degli indici
 se la clausola WHERE di un’interrogazione importante
contiene diverse condizioni si considerano anche indici
con chiave multi-attributo
– se si hanno selezioni di tipo range, l’ordine degli
attributi deve essere scelto attentamente in modo da
corrispondere a quello del range
– si noti anche che questo tipo di indici a volte
permettono strategie index-only per query importanti
11
7

si noti anche che per le strategie index-only, il clustering non è
importante!
Progettazione fisica
SELECT E.ename, D.mgr
FROM Emp E, Dept D
WHERE D.dname=‘Toy’ AND E.dno=D.dno
Esempio



11
8
un indice hash su D.dname permette la selezione di ‘Toy’
– non serve quindi un indice su D.dno
un indice hash su E.dno permette di ritrovare le tuple di
Emp che matchano per ogni tupla di Dept selezionata
se la clausola WHERE includesse: “... AND E.age=25”?
– si potrebbero ritrovare le tuple di Emp usando l’indice
su E.age, e poi effettuare il join cercando le tuple di
Dept che soddisfano la condizione su dname (analogo
alla strategia utilizzando l’indice su E.dno)
– se si ha già un indice su E.age, questa query non
motiva l’aggiunta di un indice su E.dno
Progettazione fisica
SELECT E.ename, D.mgr
FROM Emp E, Dept D
WHERE E.sal BETWEEN 10000 AND 20000
AND E.hobby=‘Stamps’ AND E.dno=D.dno
Esempio

Visto che le selezioni sono su Emp, si parte da li a valutare
l’interrogazione
–

potrebbe essere utile un indice hash su D.dno
che indici si dovrebbero costruire su Emp?
–
–
si potrebbe usare un indice di tipo B+ tree su E.sal O un indice su
E.hobby
uno solo di tali indici è necessario e qual è meglio dipende dalla selettività
delle condizioni


11
9

in generale (ma non è detto!), le selezioni con uguaglianza sono più selettive
di quelle di tipo range
si noti come la scelta degli indici sia guidata dai piani che ci
aspettiamo che l’ottimizzatore considerà per la query
bisogna avere chiaro come funzionano gli ottimizzatori!
Progettazione fisica
Clustering
 si può usare un indice di tipo B+
tree su E.age
quanto selettiva è la condizione?
– l’indice è clusterizzato?
 interrogazione con GROUP BY
– se molte tuple hanno E.age > 10, l’uso
dell’indice su E.age seguito
dall’ordinamento delle tuple ritrovate
può essere costoso
– un indice clusterizzato su E.dno può
essere meglio
SELECT E.dno
FROM Emp E
WHERE E.age>40
–
12
0

query di uguaglianza con duplicati:
–
è vantaggioso clusterizzare su
E.hobby
SELECT E.dno, COUNT (*)
FROM Emp E
WHERE E.age>10
GROUP BY E.dno
SELECT E.dno
FROM Emp E
WHERE E.hobby=Stamps
Progettazione fisica
Indici multi-attributo
 per ritrovare record di Emp con age=30 AND sal=4000, un
indice su <age,sal> è meglio di un indice su age o un
indice su sal
tali indici sono anche detti indici compositi o concatenati
– la scelta della chiave dell’indice è ortogonale al clustering etc.
 se la condizione è: 20<age<30 AND 3000<sal<5000:
– indici ad albero clusterizzati su <age,sal> o <sal,age> sono la
soluzione migliore
 se la condizione è: age=30 AND 3000<sal<5000:
– un indice clusterizzato su <age,sal> è molto meglio di un indice
<sal,age>
–
12
1

gli indici compositi sono però più grossi e vengono
aggiornati più spesso
Progettazione fisica
SELECT D.mgr
FROM Dept D, Emp E
WHERE D.dno=E.dno
<E.dno>
Piani Index-Only
 un certo numero
<E.dno> SELECT E.dno, COUNT(*)
di query può
FROM Emp E
GROUP BY E.dno
essere risolto
senza ritrovare
<E.dno,E.sal> SELECT E.dno, MIN(E.sal)
tuple da una o più
FROM Emp E
(ad albero)
delle relazioni
GROUP BY E.dno
coinvolte se è
SELECT AVG(E.sal)
disponibile un <E. age,E.sal> o FROM Emp E
indice opportuno<E.sal, E.age>
WHERE E.age=25 AND
12
2
(ad albero)
E.sal BETWEEN 3000 AND 5000
Riferimenti
12
3

Raghu Ramakrishnan, Johannes Gehrke “Database
Management Systems - Second Edition” McGraw Hill,
2000

Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer
Widom “Database System Implementation” Prentice
Hall, 2000