Una base di dati è semplicemente una collezione di dati collegati, tipicamente memorizzati in un disco, organizzati in modo da facilitare l’accesso e il mantenimento dei dati stessi e renderli disponibili a più utenti. Un DBMS è un sistema che mantiene una o più base di dati, ne permette la consultazione e si adopera affinché essa permanga in uno stato consistente.
Un Database Management System (DBMS) deve:
Database Relazionale
Database Gerarchico
Database Reticolare
Database ad Oggetti
Per quel che riguarda la progettazione di database il modello cui si fa riferimento per i primi tre database è il diagramma entità/relazioni che permette di rappresentare la struttura dei dati in un metalinguaggio da cui è poi possibile ricavare la struttura del database a seconda dei vari casi applicando procedimenti particolari per ogni modello specifico.
Il database ad oggetti, a differenza dei tre precedenti, si basa sul modello delle classi che è una rappresentazione degli elementi che compongono il sistema; questo tipo di DBMS è relativamente recente e solo da poco sono disponibili DBMS ad oggetti con prestazioni paragonabili agli altri. Esistono DBMS ad oggetti statici o dinamici, i due tipi si differenziano per la possibilità di far eseguire i metodi degli oggetti che contengono direttamente nel DBMS senza portarli in memoria.
2.1 Rappresentazione logica di un database
Nel 1972 un gruppo di studio, su commissione dell’American National Standards Institute (ANSI), stabilì un modello per l’amministrazione di un DBMS. Questo gruppo di studio venne chiamato Standard and Planning Architecture Requirements Committe (SPARC) [bib.1,3].
Come risultato lo SPARC definì un’architettura che rappresenta oggi lo standard de facto per quel che riguarda la rappresentazione concettuale di DBMS.
Nel rapporto finale del 1978 l’architettura di un database è composta di tre livelli:
External view layer
Conceptual view layer
Internal view layer
Il primo livello rappresenta la vista di come utenti e/o applicazione vedono il database, per esempio un pannello di inserimento dati.
Il secondo livello rappresenta la vista concettuale, cioè come l’amministratore del sistema vede il database.
L’ultimo livello rappresenta la vista del programmatore; a questo livello é specificato il modo in cui i record e i campi sono fisicamente memorizzati.
2.2 Modello di rappresentazione di un DBMS
Il DBMS risulta costituito da varie componenti software, che collaborano tra loro per garantire l’efficienza, la sicurezza e l’elaborazione parallela delle transazioni [FIG. 2.2.1]:
Il modulo successivo, l’analizzatore semantico, preleva dalla lista la prima transazione valida e ne verifica la correttezza; fa riferimento al catalogo del database che contiene una descrizione di tutti gli oggetti contenuti nel database e controlla che i vari riferimenti siano corretti. Se la query fallisce viene rigettata e ne viene data comunicazione all’utente/applicazione attraverso un codice che rappresenta l’errore verificatosi.
Il modulo seguente si occupa dell’ottimizzazione della query in modo da incrementare le performance del sistema, esso si serve di un catalogo di statistiche che consente di migliorare l’ordine di esecuzione del predicato WHERE.
Una volta ottimizzata la query viene passata al modulo di scheduling che, dopo essersi assicurato che non vi siano conflitti con il piano di transazioni concorrenti, la invia al modulo che si occupa del locking dei vari oggetti del database.
Quando gli oggetti richiesti sono bloccati la transazione viene passata al database manager che la processa; questo agisce assieme al sort manager e al buffer manager: il primo è un modulo che si occupa di ordinare temporaneamente i risultati, mentre il secondo alloca la memoria interna necessaria all’operazione.
Il database manager effettua un log delle operazioni svolte e procede al ripristino della base dati nel caso in cui si verifichi un errore, questo avviene mediante l’operazione di ROLLBACK che riporta il database in uno stato consistente.
La gestione delle transazioni concorrenti pone, dal punto di vista di un DBMS, la condizione di dover risolvere due problemi:
Consideriamo ora il caso in cui due transazioni, T1 e T2, debbano modificare lo stesso record R1, potrebbe verificarsi la seguente situazione:
T2 legge R1
T2 scrive su R1
Questi problemi sono risolvibili ordinando le operazioni che le transazioni andranno a eseguire in modo che non interferiscano tra loro. Ci sono due soluzioni per implementare detto tipo di strategia:
Tecniche di serializzazione
Algoritmi del controllo della concorrenza
Una qualsiasi transazione può essere scomposta in una serie di azioni elementari, serializzare due o più transazioni significa ordinare in modo coerente l’insieme delle azioni di tutte le transazioni coinvolte [fig. 2.3.1]. Essenzialmente si tratta di verificare che le azioni che si susseguono non interferiscano tra loro.
Una transazione è definita matematicamente come un particolare ordine di esecuzione di una serie di azioni che operano sul database e viene espressa nella forma seguente:
T = { E , < }
dove E è il dominio delle azioni che vengono compiute e < rappresenta il set di operazioni binarie nella successione richiesta. Nel nostro caso il dominio delle azioni è costituito da tutte le operazioni di read, write, COMMIT e ROLLBACK che vengono fatte sul database, mentre il set di operazioni binarie rappresenta l’ordine di esecuzione di tali operazioni.
A questo punto è necessario definire le proprietà di una transazione:
T = { (R) U(W) U[COMMIT o ROLLBACK] }
dove
R = tutte le operazioni di lettura dal database
W= tutte le operazioni di scrittura sul database
COMMIT= rappresenta l’operazione di convalida
ROLLBACK= rappresenta l’operazione di ripristino che si compie quando una transazione fallisce
Una transazione deve terminare con COMMIT o ROLLBACK, ma non con entrambe.
Tutte le operazioni sul database devono terminare con COMMIT o ABORT
Date due operazioni OP1(X) e OP2(X), dove X è l’oggetto che viene indirizzato e le operazioni siano una write e una read, allora o OP1(X) precede OP2(X) o OP2(X) preceda OP1(X).
Applicando questo set di regole alle tre transazioni seguenti:
T1= r1(x), r1(y), w1(z), c1
T2= r2(x), w2(x), c2
T3= r3(x), r3(y), w3(x), c3
Ne segue:
T1= { E1, <1 }
T2= {E2, <2 }
T3= {E3, <3 }
dove
E1= [r1(x), r1(y), w1(z), c1]
<1= [(r1(x), r1(y), w1(z)), (r1(x), c1) , (r1(y), c1), (w1(z), c1)]
…
ecc.
Lo scheduler accetta in ingresso l’insieme delle operazioni delle tre transazioni e genera una lista di esecuzione definita history che passa al database manager. Lo scheduler ordina le operazioni in modo che non vi siano interferenze tra esse e che sia rispettata l’integrità dei dati processati, in modo cioè che le tre transazioni appaiano eseguite in modo seriale. Il modo in cui lo scheduler ordina le operazioni da eseguire dipende dall’algoritmo di gestione della concorrenza che esso implementa: per esempio lo scheduler potrebbe impiegare il lock dei record oppure il time stamps.
Perché le transazioni appaiano eseguite in successione si dovrebbe avere:
T1 r1(y) r1(x) w1(y) c1
T3= r3(x) w3(y) w3(x) c3
T2= r2(x) w2(x) c2
Una possibile lista di esecuzione potrebbe essere la seguente:
SH (Serial History)= r2(x), w2(x), r3(x), c2, w3(y), r1(y), w3(x), r1(x), c3, w1(y), c1
2.3.2 Algoritmi per il controllo della concorrenza
Gli algoritmi per il controllo della concorrenza si dividono in due categorie: pessimistici e ottimistici [bib. 1,2,5].
Gli scheduler che implementano algoritmi che fanno parte della prima categoria verificano che l’operazione successiva a quella in esecuzione non crei conflitti con la stessa, se non viene rilevata nessuna interferenza l’operazione viene processata, altrimenti l’operazione viene memorizzata in una coda di ritardo e viene eseguita solo quando l’operazione precedente termina la sua esecuzione. Con questo tipo di strategia le operazioni che vengono ritardate possono incorrere in un ritardo ulteriore determinato dall’esecuzione di un’altra operazione prima di venire prelevate dalla coda di ritardo; questo problema può però essere risolto adottando un sistema a priorità che tenga conto del tempo che una transazione viene ritardata.
Nel secondo tipo di algoritmi la strategia è opposta: ad ogni richiesta di modifica il gestore di database risponde sempre affermativamente, permettendo a qualsiasi operazione di accedere ai dati. Quando però avviene un’operazione di scrittura sul database, si va a verificare che nel frattempo qualche altra operazione non abbia modificato il record, in questo caso il database manager da comunicazione all’utente/applicazione dell’avvenuta collisione.
Da un esame delle due strategie risulta evidente che la prima è indicata in un ambiente ad alto tasso di collisioni mentre la seconda presuppone un ambiente con un basso tasso di collisioni per mostrare risultati migliori; infatti gli algoritmi pessimistici vengono di solito utilizzati in database locali, mentre quelli ottimistici vengono utilizzati in ambienti client/server.
2.4 Protocollo di locking a due fasi
Una soluzione che permette di mantenere il controllo dell’esecuzione concorrente di più transazioni è il così detto two-phase locking protocols. Essenzialmente vengono assegnati due diversi tipi di locking agli oggetti del database che vengono indirizzati dalle varie transazioni, il lock in scrittura e quello in lettura [bib 1, 2, 5].
I due tipi di lock differiscono sostanzialmente in un aspetto: mentre un oggetto può essere bloccato in lettura da più di una transazione, l’operazione di lock in scrittura deve coinvolgere una sola transazione [fig. 2.4.1]. Questo significa che solo un lock in lettura può essere compatibile con un altro lock in lettura, mentre il lock in scrittura deve essere univoco. Se ad esempio abbiamo due transazioni, T1 e T2, che richiedo di bloccare l’oggetto X in lettura, tutte e due le operazioni andranno in porto; se una delle due transazioni richiede un lock in scrittura dell’oggetto X, allora una sola transazione può bloccare l’oggetto.
L’algoritmo appena descritto è implicitamente diviso in due fasi: la fase di locking e quella di unlocking. Nella prima fase una transazione ottiene il blocco di tutti i record che richiede; nella seconda la transazione sblocca tutti gli oggetti ha ottenuto. Questo algoritmo impone che una transazione che abbia rilasciato gli oggetti bloccati non possa richiederne altri, il risultato è un’esecuzione delle transazioni sequenziale.
|
|
R | W |
| R | Si | No |
| W | No | No |
Il lato negativo di questa tecnica è l’eventualità che si verifichino delle situazioni di deadlock in quanto è possibile che due transazioni, T1 e T2, debbano accedere per operazioni scrittura a due oggetti X1 e X2; può capitare che T1 richieda e ottenga il lock di X1, e T2 quello di X2. Ora per poter essere eseguite le transazioni devono entrambe possedere gli oggetti e ciascuna attende che l’altra rilasci l’oggetto in suo possesso.
Questa situazione di stallo può essere risolta ricorrendo ad un processo in background che verifichi e risolva le situazioni di deadlock secondo una delle tre seguenti strategie:
1) Timeout intervals
Se una transazione sta aspettando da un certo tempo senza eseguire nessuna operazione, allora lo scheduler assume che vi sia una situazione di deadlock e la termina. Con questo metodo si corre il rischio che una transazione che sta aspettando un oggetto posseduto da un’altra venga terminata.
2) Wait-For-Graph
Questo metodo ha uno scheduler che mantiene una struttura denominata grafico delle attese (wait-for-graph); questa struttura dati tiene conto delle transazioni che stanno aspettando un oggetto posseduto da un’altra applicazione. I deadlock vengono individuati verificando che non vi siano cicli nel grafico delle attese; nel caso una situazione di deadlock venga verificata, lo scheduler procede terminando l’applicazione che soddisfa certe regole.
3) Protocollo di ordinamento Time Stamp
Questa strategia mantiene la concorrenza delle transazioni assegnando un certo tempo a tutte le operazioni della transazione (time stamp); le operazioni vengono così marcate secondo la successione temporale in cui arrivano al T.M. In questo modo l’esecuzione delle operazioni viene ordinata secondo una modalità di accodamento FIFO.
L’uso di questo algoritmo previene il verificarsi di situazioni di deadlock: infatti operazioni appartenenti a transazioni diverse hanno priorità diverse. Il lato negativo di questa strategia è che se una singola operazione di una transazione ha un conflitto tutta la transazione viene rigettata.
Un DBMS deve avere la capacità di riportare la base dati in uno stato consistente dopo un crash di sistema o il fallimento di una applicazione; questo compito è affidato al Recovery Manager (R.M.) [fig 2.5.1].
Per migliorare le prestazioni, parte dei dati di un database vengono mantenuti in memoria consentendo così di ridurre il numero e la frequenza degli accessi al disco; per vedere se i dati presenti nella cache memory sono stati modificati si utilizza un bit di flag che è impostato ad uno (1) se vi sono state delle modifiche.
Un altro elemento che viene utilizzati dal R.M. è il log delle operazioni eseguite sulla base di dati; di solito detto oggetto è rappresentato da tre tabelle:
1) Una lista di COMMIT
Contiene una registrazione di ogni transazione che è terminata con successo. È necessaria in quanto i dati non vengono memorizzati subito sul disco, ma vengono mantenuti nella cache ed andrebbero persi in un ipotetico crash del sistema. Le transazioni vengono così memorizzate prima nel log e poi vengono eseguite sulla base di dati.
2) Una lista di ROLLBACK
Contiene la lista delle transazioni che non sono terminate con successo. Questa lista viene utilizzata per riportare il database in uno stato consistente dopo che una transazione fallisce, ed è molto utile per trovare quelle transazioni che possono aver corrotto la base di dati.
3) Una lista di Dati
Contiene un’immagine dei dati della cache prima e dopo le modifiche apportate. È necessaria per operazioni di ripristino dei valori precedenti a delle modifiche e/o per effettuare le operazioni di ROLLBACK.
Un esempio di funzionamento del sistema R.M. può essere il seguente:
Una transazione viene processata dal T.M.
Un record richiesto dalla transazione viene caricato in memoria attraverso la cache manager
L’immagine del record viene salvata nella lista dati del log
Vengono fatti gli opportuni cambiamenti al record in memoria
Il R.M. memorizza l’immagine del record modificato e il messaggio di COMMIT sul log
Nel momento in cui il sistema deve scrivere i cambiamenti sul disco il sistema va in crash
A questo punto, quando il sistema viene riattivato e si richiama la funzione di recovery, il R.M. verifica se nella COMMIT list è presente una transazione terminata con un COMMIT che deve essere rieseguita. Una volta trovata la transazione il R.M. procede ripristinando la situazione precedente al crash di sistema, questa operazione è detta " redo ". Effettuato questo riallineamento il R.M. procede applicando l’operazione memorizzata nel log. e il database è riportato in uno stato coerente.
Lo stesso principio si applica nel momento in cui il sistema dovesse andare in crash dopo un’operazione che generi un ROLLBACK.
