Progettazione fisica

La progettazione fisica permette la rappresentazione dello schema logico per mezzo di strutture fisiche di memorizzazione. Ad, esempio una relazione può essere realizzata fisicamente per mezzo di un file sequenziale, o di un file hashed o di file sequenziale con uno o più indici.

Ogni tupla della relazione viene memorizzata come un record fisico nella struttura dati scelta, e ogni componente della tupla è memorizzata in un campo del record fisico.

4.1 Strutture fisiche di accesso

Le strutture fisiche di accesso descrivono il modo in cui vengono organizzati i dati per garantire operazioni di ricerca e di modifica efficienti da parte dei programmi applicativi. In genere, ciascun DBMS ha a disposizione un numero abbastanza limitato di tipi di strutture di accesso; ad esempio, nei sistemi relazionali sono disponibili semplici indici, che vengono definiti dal progettista tramite istruzioni DDL. In questo paragrafo considereremo strutture sequenziali, ad accesso calcolato e ad albero (B-tree).

Le strutture sequenziali sono caratterizzate da una disposizione sequenziale delle tuple in memoria di massa; il file è costituito da vari blocchi di memoria consecutivi, e le tuple vengono inserite nei blocchi rispettando una sequenza. Tale sequenza può essere di vari tipi:

· In una organizzazione entry-sequenced, la sequenza delle tuple è indotta dal loro ordine di immissione.

· In una organizzazione ISAM, la sequenza delle tuple dipende dal valore assunto in ciascuna tupla da un campo di ordinamento.

Una struttura sequenziale entry-sequenced è ottimale per svolgere operazioni di lettura e scrittura sequenziali. Dato che le tuple non sono disposte con un ordine prestabilito, il modo tipico di accedere al loro contenuto è tramite scansione (scan) sequenziale. D’altra parte questa organizzazione usa tutti i blocchi a disposizione del file e tutti gli spazi all’interno dei blocchi e, quindi, la scansione risulta particolarmente efficiente. E’ anche possibile accedere ad una tupla specifica, nel caso di tuple a lunghezza fissa, pur di conoscere in che ordine essa è stata inserita.

Per quanto riguarda le operazioni di caricamento iniziale dei dati e di inserimento, esse avvengono alla fine del file ed in modo sequenziale; è sufficiente gestire un puntatore all’ultima tupla per poter eseguire l’operazione. Il principale problema è posto dalle operazioni di modifica e cancellazione: poiché le tuple vengono disposte in sequenza, ogni modifica che comporti un aumento delle dimensioni della tupla non può essere facilmente gestita "in loco", ed ogni cancellazione causa un potenziale spreco di memoria, in quanto viene implementata spesso lasciando inutilizzato dello spazio.

L’organizzazione ISAM dei file (Indexed Sequential Access Method, metodo di accesso sequenziale con indici) assegna a ciascuna tupla una posizione in base al valore del campo chiave. Questa organizzazione è basata sull’idea di dare alle tuple un ordinamento fisico che rifletta l’ordinamento lessicografico dei valori presenti in un campo chiave. In realtà non è necessario che il campo scelto per definire l’ordinamento delle tuple sia un campo chiave, anche se in questo paragrafo supporremo di ordinare i record in base al valore delle loro chiavi che, inoltre, individueranno in maniera univoca un record. Per quanto riguarda i criteri di ordinamento, gli usuali domini di valori, come le stringhe di caratteri, gli interi o i reali, seguono un ordinamento convenzionale: per i numeri interi o reali si considera quello numerico, mentre per le stringhe di caratteri abbiamo l’ordine lessicografico (o dictionary).

Per aumentare la velocità di accesso al file ordinato (che chiamiamo file principale), si definisce un secondo file (chiamato sparse index, indice rado), che consiste nelle coppie:

Per ogni blocco del file principale, nel file indice esiste un record (µ,b): µ è un valore non superiore a quello di tutte le chiavi contenute nel blocco b e maggiore (>) dei valori delle chiavi di ogni blocco che precede b.

Il primo campo di (µ, b) è una chiave e il file indice è ordinato rispetto ad essa.

Se vogliamo trovare il blocco b del file principale che contiene un record con chiave µ dobbiamo ricercare nel file indice il record:

                          (µj, b)             tale che µj <= µ (µ >= µj)

dove il record successivo:

                          (µk, bk)           è tale che µ < µk

in questa situazione si dice che µk copre µ.

La strategia più semplice consiste sicuramente nell’usare una tecnica di ricerca lineare (cioè scandire l’indice dall’inizio controllando ogni record fino a trovare l’indice che copre µ).

Questo metodo non è conveniente se non per gli indici più piccoli, dato che in tal caso si può richiamare in memoria principale l’intero indice e, in media per eseguire una ricerca con successo, si accederà a metà dei blocchi. Comunque fare una ricerca lineare sull’indice è meglio che farla sul file principale; se questo possiede R record per blocco, allora i record dell’indice sono 1/R rispetto a quelli del file principale. Inoltre di solito i record indice sono più corti e possono così essere raggruppati in un numero maggiore per blocco.

Un metodo migliore è rappresentato dall’effettuare una ricerca binaria sulle chiavi del file indice.

Si supponga che B1,… ,Bn siano i blocchi che contengono il file indice (non il file principale) e siano rispettivamente µ1,… µn le prime chiavi di ognuno di tali blocchi.

Per trovare il blocco che contiene il record del file principale con chiave µ, dovremo prima analizzare il blocco indice B[n/2] e confrontare µ con µn/2. Se µ<µn/2, dovremo iterare il processo sui blocchi B1,… ,B[n/2]-1, altrimenti considerare i blocchi Bn/2,… ,Bn. Alla fine rimarrà un solo blocco, in cui potremo effettuare una ricerca lineare per trovare nell’indice il valore chiave che copre µ.

Un metodo ancora più efficiente è noto come ricerca per interpolazione o per calcolo degli indirizzi. Esso si basa sulla nostra conoscenza della statistica della distribuzione attesa per i valori della chiave e sull’affidabilità di tale distribuzione.

Se ad esempio ci si chiede di cercare Giuseppe Rossi sulla guida telefonica, non la apriamo a metà, ma a circa il 75%, "sapendo" che è pressappoco il punto in cui si trova la R. Se ci trovassimo alla S, torniamo circa il 5%, e non a metà dall’inizio, come faremmo invece col secondo passo in una ricerca binaria.

In generale, si supponga di avere un algoritmo che, dato il valore chiave µ1, fornisca il valore della frazione tra altre due chiavi µ2, µ3 in cui ci aspettiamo che si trovi µ1. Chiamiamo questa funzione f(µ1,µ2,µ3). Siano B1,… ,Bn i blocchi in cui si trova l’indice (o parte di esso) ed indichiamo µ2 la prima chiave di B1 e µ3 l’ultima di Bn. Sia i un indice tale che i = [nf(µ1,µ2,µ3)], allora analizzeremo il blocco Bi per definire quale rapporto vi sia tra la prima chiave di tale blocco e µ1. Come in una ricerca binaria, tale processo verrà iterato su B1,… Bi-1 o su Bi,… Bn (sull’insieme di blocchi che contiene la chiave che copre µ1) fino a che non rimarrà un solo blocco.

Una struttura con accesso calcolato garantisce, al pari dell’organizzazione ISAM, un accesso associativo ai dati, in cui, cioè, la locazione fisica dei dati dipende dal valore assunto da un campo particolare ma è preferibile ad essa perché le tuple non devono essere disposte in ordine in memoria di massa.

L’idea che sta alla base dell’organizzazione hashed dei file è quella della suddivisione del file in buckets, a seconda del valore della chiave. Per ogni file memorizzato in tal modo, esiste una funzione hash h che prende come argomento un valore della chiave e fornisce un intero tra 0 e B-1, dove B è il numero dei bucket usati per tale file. L’intero h(v) è il numero di bucket in corrispondenza del valore chiave v.

Ogni baucket è composto da un numero (possibilmente piccolo) di blocchi e questi sono organizzati come raggruppamento. Vi è un array di puntatori, con indice tra 0 e B-1, che chiamiamo indice del bucket. In esso l’elemento i è un puntatore al primo blocco: tale puntatore viene detto testata del bucket. Nel bucket i tutti i blocchi sono collegati in una lista tramite puntatori e, nell’ultimo della lista (o nella testata del bucket, se questo è attualmente vuoto) vi è un puntatore nullo. È normale Progettazione database relazionali che B sia abbastanza piccolo da permettere che l’intero indice del bucket risieda in memoria principale, mentre se così non fosse, l’indice si estenderebbe su tutti i blocchi necessari ed ognuno di questi verrebbe richiamato in memoria quando necessario.

Esistono molti tipi di funzioni utilizzabili come funzioni hash h. È fondamentale che l’intervallo sia 0,… ,B-1 ed è opportuno che h ripartisca le chiavi: ossia che al variare di v su tutti i possibili valori della chiave, h(v) assuma in modo quasi equiprobabile tutti i possibili valori.

Un semplice esempio di funzione hash è quello che trasforma ogni chiave in un intero e poi ne prende il resto modulo B. Se iniziamo con valori interi per la chiave, calcoliamo semplicemente h(v) = v mod B.

Un esempio di file hashed che usa la funzione hash precedente con B=4 è mostrato in figura 4.2.

Le strutture ad albero, denominate B-tree o B+-tree, sono le più frequentemente usate nei DBMS di tipo relazionale. Esse consentono accessi associativi, cioè in base ad un valore di un attributo chiave (key), senza essere necessariamente vincolare la collocazione fisica delle tuple in posizioni specifiche del file. In genere, quando un utente specifica a livello di DDL la definizione di un indice relativo ad un attributo o una lista di attributi di una tabella, ciò corrisponde a definire opportune strutture ad albero.

Come sempre, ogni albero è caratterizzato da un nodo radice, vari nodi intermedi e vari nodi foglia; ogni nodo corrisponde ad un blocco. I legami tra nodi vengono stabiliti da puntatori; in genere, ogni nodo ha un numero di discendenti abbastanza grande (non è raro il caso in cui ogni nodo ha decine o centinaia di successori); questo consente di costruire alberi con un numero limitato di livelli. Un altro requisito importante è che la lunghezza di un cammino che collega il nodo radice da un qualunque nodo foglia sia costante (B-tree, alberi bilanciati). In tal caso, i tempi di accesso alle informazioni contenute nell’albero sono praticamente costanti.

L’organizzazione fisica avviene tramite indici (file), e siccome gli indici non sono altro che file con record non puntati, non vi è motivo per cui non si possa avere un indice di un indice, un indice di quest’ultimo e così via, fino a quando si arriva a un livello di indice che sia contenuto in un solo blocco, come suggerito dalla figura 4.3.

Di fatto una tale struttura potrebbe essere molto più efficiente rispetto a un file con un unico livello di indice. Nella struttura della figura 4.3 il file principale è ordinato per valore di chiave. Il primo livello di indice consiste delle coppie (v, b) in cui b è un puntatore al blocco B del file principale e v è la prima chiave nel blocco B. Naturalmente anche l’indice è ordinato per valore di chiave. Il secondo livello di indice possiede coppie (v, b), in cui b punta al blocco indice di primo livello e v ne è la prima chiave e così via.

La differenza tra un B-tree e un B+-tree è che negli alberi B+, i nodi foglia sono collegati da una catena in base all’ordine imposto dalla chiave. Tale catena consente di svolgere in modo efficiente anche interrogazioni il cui predicato di selezione definisce un intervallo di valori ammissibili. In particolare questa struttura dati consente anche una scansione ordinata in base ai valori di chiave dell’intero file, che risulta abbastanza efficiente.

Negli altri alberi (B-tree) non viene previsto di collegare sequenzialmente i nodi foglia.

Nell’ambito del progetto di una base di dati, la fase finale è costituita dalla progettazione fisica, che, ricevendo in ingresso lo schema logico del DB e le caratteristiche del sistema scelto, produce in uscita lo schema fisico del database, costituito dalle effettive definizioni delle relazioni e soprattutto delle strutture fisiche utilizzate, con i relativi parametri.

L’attività di progettazione fisica di una base di dati relazionale può essere molto complessa, perché oltre alle scelte relative alle strutture fisiche può essere necessario definire molti parametri, che vanno dalle dimensioni iniziali dei file alle possibilità di espansione, dalla contiguità di allocazione alla quantità e alle dimensioni delle aree di transito per scambio di informazioni tra memoria principale e secondaria.

La maggior parte delle scelte da effettuare nel corso della progettazione fisica dipende in effetti dallo specifico sistema di gestione utilizzato, e quindi risulta difficile fornire una panoramica completa. Indicheremo solo le linee principali, che possono però essere considerate sufficienti in presenza di basi di dati di dimensioni non enormi o con carichi di lavoro non particolarmente complessi.

Assumiamo che il DBMS a nostra disposizione preveda solo file non ordinati, con possibilità di definizione di indici. In questo contesto, ignorando gli altri parametri, la progettazione fisica può essere ricondotta ad una attività di individuazione degli indici da definire su ciascuna relazione (a parte l’attività semplice di specifica degli schemi delle relazioni nello specifico DDL del sistema usato, con i tipi di dati ammessi per i vari attributi).

Per orientarci nella scelta degli indici, è opportuno ricordare che le operazioni più delicate in un DB relazionale sono quelle di selezione (che corrisponde all’accesso ad uno o più record sulla base dei valori di uno o più attributi) e di join (che richiede di combinare ennuple di relazioni diverse sulla base dei valori di uno o più attributi di ciascuna di tali relazioni). Ciascuna delle due operazioni può essere eseguita in maniera più efficiente se sui campi interessati è definito un indice, che permette un accesso diretto.

Consideriamo, ad esempio, un DB su due relazioni, la prima, IMPIEGATI, sugli attributi Matricola (che costituisce la chiave), Cognome, Nome e Dipartimento (che indica il codice del dipartimento di afferenza) e la seconda, DIPARTIMENTI, sugli attributi Codice (che costituisce la chiave), Nome e Direttore.

Volendo effettuare sulla relazione IMPIEGATI una selezione sull’attributo Matricola (ricerca di un impiegato dato il numero di matricola), se sulla relazione è presente un indice su tale attributo si può procedere con un accesso diretto, molto efficiente, altrimenti si deve effettuare un accesso sequenziale, con un costo proporzionale alla dimensione del file. Lo stesso vale per una ricerca basata sul cognome dell’impiegato; vale la pena notare che se è definito un indice su un attributo, solo le ricerche basate su tale attributo possono trarne beneficio: se la relazione ha un indice su Matricola e non ha un indice su Cognome, le selezioni su Matricola potranno essere eseguite in modo efficiente mentre quelle su Cognome rimarranno inefficienti.

Un equi-join fra le due relazioni volto a collegare ciascun impiegato con il corrispondente dipartimento, in presenza di un indice sulla chiave Codice della relazione Dipartimenti, può essere effettuato in modo molto efficiente tramite il metodo dei nested-loop; si scandisce sequenzialmente la relazione IMPIEGATI (e questo non è un problema, perché tutte le sue ennuple contribuiscono al risultato) e, per ciascuna di esse, si effettua un accesso diretto alla relazione DIPARTIMENTI sulla base dell’indice. Se l’indice non è definito, l’accesso alla relazione DIPARTIMENTI risulta inefficiente, e tutto il join risulta più costoso.

E’ importante ricordare come molti dei join che si presentano nelle applicazioni sono equi-join e per almeno una delle due relazioni i campi coinvolti formano una chiave, come nell’esempio appena mostrato. Al tempo stesso possiamo notare come quasi sempre la chiave di una relazione sia coinvolta in operazioni di selezione o di join (o entrambe). Pertanto possiamo dire che è ragionevole definire, su ciascuna relazione, un indice in corrispondenza della relativa chiave (indice primario).

Tali indici solitamente vengono creati in automatico dal DBMS. Inoltre possono essere definiti indici (indici secondari) su altri campi su cui vengono effettuate operazioni di selezione oppure su cui è richiesto un ordinamento in uscita (perché un indice ordina logicamente i record di un file, rendendo nullo il costo di un ordinamento). Queste osservazioni costituiscono la base di una semplice strategia di progettazione fisica.

Definiti in questo modo gli indici, si può sperimentare sul campo il comportamento della nostra applicazione: se le prestazioni risultano insoddisfacenti, si possono aggiungere altri indici, procedendo però con grande attenzione, in quanto l’aggiunta di un indice comporta un aggravio del carico per far fronte alle operazioni di modifica. Talvolta, inoltre, il comportamento del sistema è imprevedibile, e l’aggiunta di indici non altera la strategia di ottimizzazione delle interrogazioni principali, risultando del tutto inefficace. É buona norma, dopo l’aggiunta di un indice, verificare che le interrogazioni ne facciano effettivamente uso. Per questo motivo, l’attività di scelta degli indici nell’ambito del progetto fisico delle basi di dati relazionali è svolta spesso in modo empirico, con un approccio per tentativi; più in generale, l’attività di regolazione (tuning) del progetto fisico consente spesso di migliorare le prestazioni della base di dati.