Basi di dati - modello fisico e algebra relazionale

C C

w w

m m

w w

w w

o o

.c .c

.d .d

k k

o o

c c

c c

a a

-tr -tr

u u

MODELLO FISICO –INTRODUZIONE

RAM: memoria di I livello, in linea, volatile e ad accesso diretto

Disco magnetico: memoria di II livello, persistente, ad accesso diretto

Unita a nastro: memoria di III livello, fuori linea, persistente, acc sequenziale

Disco magnetico: superfici magnetiche impressionabili in modo persistente, piatti rotanti attorno ad un

asse, letti da testine e fissate attorno ad un braccio mobile; In particolare la tecnologia del disco magnetico

influenza le prestazioni del DBMS e presenta due particolarità:

- Organizzazione in blocchi dei dati: Per leggere un bit nel blocco è necessario leggere tutto il blocco

in cui è contenuto;Si ha un accesso casuale al blocco, specificando l’id de blocco(indirizzo hardware

del blocco sul disco);

o Un parametro importante per le prestazioni è la località dei blocchi;

o Clustering: tecnica di raggruppamento dei dati perché siano fisicamente vicini su disco.

o RAID: tecnologia concepita per consentire la lettura e la scrittura in parallelo su dischi

magnetici e utilizza vari dischi contemporaneamente.

 RAID LIVELLO 0: usa piu dischi per scrivere/leggere in parallelo e migliorare le

prestazioni;

 RAID LIVELLO 1: usa dischi a coppie per fornire funzionalità di mirroring (resistenza

ai guasti);

 RAID LIVELLO 0+1: effettua mirroring di un intero array di livello 0 e attraverso la

tecnica del livello 1;

 LIVELLI SUPERIORI: forniscono inoltre funzionalità di codica ridondante e

correzione d’errore, e questo determina complessità e costo crescente.

- Tempi di trasferimento e località;

MODELLO FISICO- CONCETTI FONDAMENTALI

Modello fisico: insieme delle regole e delle tecniche per la memorizzazione della base di dati su disco.

- Gestire la paginazione: ovvero accedere efficientemente ai blocchi su disco per portarli nella RAM;

- Memorizzare i dati nei file: ovvero rappresentare efficientemente le tabelle nei file;

- Eseguire le operazioni sui file: ovvero effettuare efficientemente le interrogazioni e gli

aggiornamenti;

Il modello fisico si compone quindi di:

- Strategia della paginazione: servizio fornito ai livelli superiori e utilizza un buffer di blocchi in

memoria RAM per limitare l’accesso al disco.

o Buffer manager: modulo che gestisce l’accesso al disco e si occupa della lettura e scrittura

dei blocchi; Obiettivo del buffer manager è massimizzare l’hit ratio, ovvero le percentuali di

blocchi richiesti dai livelli superiori e prelevati dal buffer e i parametri su cui intervenire

sono:

 Dimensione del buffer;

n n

g g

a a

e e

h h

Vi Vi

XC XC

e e

F- F-

w w

PD PD

er er

! !

W W

O O

N N

y y

bu bu

to to

k k

lic lic

C C

w w

m m

w w

w w

o o

.c .c

.d .d

k k

o o

c c

c c

a a

-tr -tr

u u

 Algoritmo di paginazione (come fare spazio ad una nuova pagina quando il buffer è

esaurito)

o Algoritmo di paginazione: si tratta di un tipico problema di gestione di memoria virtuale

Il buffer è organizzato in pagine che hanno dimensioni pari a un numero intero di blocchi. Il gestore del

buffer si occupa del caricamento e dello scaricamento delle pagine dalla memoria centrale alla memoria di

massa. Si noti che la tempistica delle operazioni non necessariamente coincide con quella delle richieste

ricevute:

- Lettura: se la pagina è presente nel buffer allora non è necessario la lettura fisica;

- Scrittura: il gestore del buffer può decidere di differire la scrittura fisica.

Entrambi i casi esposti consentono di ridurre il tempo di risposta di un applicazione.

Ogni DBMS ha il suo buffer manager e il suo sistema di paginazione.

- Strategia di memorizzazione: consiste nello scegliere la dimensione dei blocchi e l’organizzazione

dei file per le tabelle. I dati sono generalmente memorizzati in forma di record e ogni record è una

collezione di valori di dati, e ogni valore è formato da uno o più byte e corrisponde a un particolare

campo del record.

o Record: unità di registrazione nel file e consiste nella registrazione di una codifica binaria di

una ennupla;

 Record di lunghezza fissa: quando è possibile, viene stabilità una lunghezza unica

in bit per tutti i record di una tabella; In questo caso si ha spreco di spazio e

semplice localizzazione dei record nel blocco(la posizione di ciascun record è nota);

 Record di lunghezza variabile: esistono attributi di lunghezza variabile che rendono

impossibile stabilire la lunghezza fissa(null,varchar). In questo caso si ha un

risparmio di spazio e una localizzazione complessa dei record.

 File = sequenza di blocchi;

 Blocco = sequenza di record;

o Fattore di blocco: numero di record contenuti in un blocco = floor(dim blocco/dim record)

o Struttura dipica del file: struttura doppiamente collegata di blocchi con una directory

iniziale(struttura di dati contenuta nell’intestazione del file e lista di puntatori ai blocchi del

file)

o File heap: organizzazione disordinata e i record vengono inseriti in coda;

o File ordinato: viene mantenuto l’ordine secondo un campo di ordinamento e i record

vengono inseriti secondo l’ordine.

- Strategia di accesso: Le operazioni principali sui file corrispondono alle operazioni effettuate nel

linguaggio di interrogazione sulle tabelle (aggiornamenti, interrogazioni).

o Stutture di accesso: insieme di strutture ausiliarie di accesso al file utilizzate per migliorare

le prestazioni delle operazioni, tipicamente indici.

- Indici: file associato al file di record di una tabella, e contiene un insieme di riferimenti al file

primario sottoforma di coppie (chiave di ricerca, riferimento al blocco).

o Indice primario: indice su campo chiave primaria. File ordinato secondo il campo e uno solo

per tabella, viene creato automaticamente alla definizione della chiave primaria e serve a

verificare il vincolo di chiave.

o Indice secondario: indice su un campo non chiave primaria, file non ordinato secondo il

campo. Possono essercene vari per tabella.

n n

g g

a a

e e

h h

Vi Vi

XC XC

e e

F- F-

w w

PD PD

er er

! !

W W

O O

N N

y y

bu bu

to to

k k

lic lic

C C

w w

m m

w w

w w

o o

.c .c

.d .d

k k

o o

c c

c c

a a

-tr -tr

u u

o Indice denso : 1 voce per ogni record del file;

o Indice sparso: 1 voce per ogni blocco del file;

o Indice su singolo attributo o piu attributi: nel secondo caso la dimensione dell’indice tende

ad aumentare.

o Indice di raggruppamento e non: l’indice di raggruppamento implica una organizzazione

del file, mentre un indice che non è di raggruppamento non implica una organizzazione del

file.

La creazione di indici aggiuntivi è giustificata solo nel caso di basi di dati di grandi dimensioni e requisiti

stringenti di operazioni. MODELLO FISICO – CONCETTI AVANZATI

Indici Multilivello: per migliorare i tempi di ricerca, utilizzo gli indici multilivello. Per costruire una struttura

multilivello di indici primari tutti i valori devono essere distinti.

- Indice secondario multilivello:

o Normalmente i valori dell’attributo da indicizzare non sono distinti;

o Possono pensare che per ciascuna chiave nell’indice ci sia un blocco di puntatori e non un

puntatore singolo;

o Da quel momento in poi la struttura multilivello è identica;

Struttura multilivello:Il costo degli inserimenti è relativamente alto e bisogna gestire i trabocchi, e per

questo vengono usate diverse strutture multilivello.

- Strutture ordinate statiche: tabelle ISAM. In queste lo spazio per i blocchi di tutti i livelli è allocato

staticamente alla creazione del file e i blocchi sono contigui e il file viene mantenuto ordinato

rispetto alla chiave.

o L’inserimento viene effettuato ordinatamente finchè ce spazio nei blocchi e quando i

blocchi si saturano viene usato un file disordinato di trabocco(overflow).Sono necessarie

periodiche riorganizzazioni globali con fusione del file primairo e del file di trabocco.

o Vantaggi: allocazione contigua dei blocchi e la struttura non viene toccata;

o Svantaggi: possono essere necessarie ristrutturazioni frequenti.

- Strutture ordinate dinamiche: B Tree e B+Tree, strutture ad albero speciali. In queste il file viene

ordinato con rappresentazione collegata. I blocchi sono allocati dinamicamente e vengono utilizzati

algoritmi ottimizzati per l’inserimento che minimizzano le riorganizzazioni.

o si tratta di alberi di ricerca di apertura n>2;

o i blocchi sono sempre parzialmente pieni (non vengono mai riempiti completamente)

o gli algoritmi di inserimento prevedono riorganizzazioni locali per mantenere una

distribuzione di occupazione ottimale.

o Vincoli aggiuntivi: l’albero deve essere bilanciato (tutte le foglie sono alla stessa distanza

dalla radice) e l’occupazione dei blocchi deve essere almeno il 50%.

o I livelli più alti sono relativamente piccoli e possono essere tenuti permanentemente nel

buffer per velocizzare le ricerche.

o Vantaggi: inserimenti con ricerca logaritmica, ricerche rapide e accesso ordinato secondo la

chiave di ordinamento.In generale ha prestazioni migliore della struttura ISAM.

- Hascing:ricerche in tempo lineare nella lunghezza della chiave ed è possibile costruire file di hash

oppure indice di hash.

n n

g g

a a

e e

h h

Vi Vi

XC XC

e e

F- F-

w w

PD PD

er er

! !

W W

O O

N N

y y

bu bu

to to

k k

lic lic

C C

w w

m m

w w

w w

o o

.c .c

.d .d

k k

o o

c c

c c

a a

-tr -tr

u u

o Funzione Hash: funzione che trasforma un valore (chiave) di lunghezza variabile in uno di

lunghezza fissa (hash della chiave). Una caratteristica tipica di una funzione hash è che

l’hash deve essere calcolabile rapidamente. Le funzioni hasch sono cosi classificabili:

 Funzione priva di collisione: non ci sono due valori per cui l’hash è uguale ed è

possibile solo se i valori sono finiti;

 Funzione con collisione: più valori possono avere lo stesso valore di hash e ad ogni

chiave un bucket (gruppo di valori tutti con lo stesso hash),

o File hash: è possibile utilizzare una funzione hash per inserire i record nel file e poterli

recuperare in tempo praticamente costante.Si parla di:

 Hascing statico: in cui il numero di bucket è uguale a un numero fissato a priori e

dove viene