Appunti di Basi di Dati 2 (corso Informatica UniGe) PDF

Preview

Summary

Dario Olianas A.A 2014/2015 Appunti di Basi di Dati 2 (BD2) 1. Introduzione 1.1 Ruoli di utilizzo delle basi di dati 2 Architettura di un DBMS 3 Organizzazione dei dati su disco 3.1 Organizzazione dei record su disco 3.2 Organizzazione dei blocchi su disco 3.3 Mapping tra relazioni e file 3.4 Cluste...

Description

Dario Olianas

A.A 2014/2015

Appunti di Basi di Dati 2 (BD2)

1. Introduzione 1.1 Ruoli di utilizzo delle basi di dati 2 Architettura di un DBMS 3 Organizzazione dei dati su disco 3.1 Organizzazione dei record su disco 3.2 Organizzazione dei blocchi su disco 3.3 Mapping tra relazioni e file 3.4 Clustering 3.5 Gestione del buffer 4 Strutture ausiliarie di accesso 4.1 Indici 4.1.1 Proprietà degli indici 4.1.2 Struttura degli indici 4.1.2.1 Indici ad albero 4.1.2.1.1 B+ alberi 4.1.2.2 Organizzazioni hash 4.1.2.2.1 Funzioni hash 4.1.2.2.2 Gestione dei trabocchi 4.1.2.2.3 Fattore di caricamento 4.1.3 Definizione di cluster e indici in SQL 5 Esecuzione delle interrogazioni 5.1 Ottimizzazione logica 5.2 Ottimizzazione fisica 5.3 Modalità di esecuzione degli operatori algebrici 5.3.1 Ordinamento 5.3.2 Selezione 5.3.3 Join 5.3.4 Proiezione 5.4 Statistiche 6 Tuning 6.1 Tuning del livello fisico 6.1.1 Criteri di scelta degli indici 6.2 Tuning del livello logico 6.3 Tuning delle interrogazioni 7 Transazioni 7.1 Modelli di transazioni 7.2 Controllo della concorrenza 7.2.1 Protocollo 2 Phase Locking 7.2.2 Protocollo timestamp ordering 7.2.3 Multiversion Concurrency Control 7.2.4 Livelli di isolamento

7.3 Lock tuning 7.4 Gestione del ripristino 7.4.1 Protocolli di ripresa 7.4.2 Recovery tuning 8 Controllo dell’accesso 8.1 Modello discrezionale del System R 8.1.1 Revoca ricorsiva 8.1.2 Autorizzazioni su viste: controllo dell’accesso basato sul contenuto 8.2 Controllo dell’accesso role based 8.3 Controllo dell’accesso dello standard SQL

1. Introduzione

1.1 Ruoli di utilizzo delle basi di dati Gli utenti delle basi di dati si dividono in parametrici e occasionali. Gli utenti parametrici sono quelli che usano sistematicamente determinate procedure messe a disposizione dal sistema, che possono anche essere complesse ma sono note a priori. È possibile sviluppare appositi programmi applicativi che mettono a disposizione le funzioni richieste da questi utenti. Gli utenti occasionali invece fanno richieste non predicibili a priori ma nella maggior parte dei casi molto semplici: solitamente per questi utenti vengono predisposte semplici interfacce interattive. Quando l'interazione con la base di dati richiede lo sviluppo di applicazioni più complesse le estensioni procedurali di SQL non bastano: è necessario sviluppare applicazioni in linguaggi general purpose che interagiscono con la base di dati. I programmatori applicativi si occupano di sviluppo e manutenzione di questi programmi. Il progettista della base di dati è colui che provvede alla progettazione del database attraverso la definizione di schema logico, fisico e di eventuali viste. L'amministratore della base di dati (DBA) stabilisce, in accordo con le politiche dell'organizzazione, le regole per l'utilizzo dei dati e le procedure per la protezione, l'integrità ed il ripristino del database. L'amministratore deve anche migliorare il più possibile l'efficienza e la redditività del sistema. Un altro ruolo nel campo della gestione dati è il progettista di DBMS, che si occupa di progettazione, sviluppo e manutenzione dei DBMS. Dato che sono software molto complessi sono richieste professionalità specifiche. Obiettivo del corso è capire come amministrare un DBMS. Ma per poterlo amministrare con successo bisogna anche sapere come funziona, capire come fa a gestire collezioni di dati grandi, persistenti e condivise in modo efficiente garantendo integrità e protezione dei dati. Non vedremo tutti gli algoritmi ma le idee che stanno alla base. Per l'amministratore è fondamentale il monitoraggio delle prestazioni del DBMS per capire se sta garantendo l'efficienza richiesta o se è necessario del tuning per migliorarne le prestazioni.

2. Architettura di un DBMS Un DBMS è un software che deve garantire la gestione di grandi collezioni di dati persistenti e condivise in modo efficiente, affidabile, integro e sicuro. Ciascuno di questi aspetti (grandi dimensioni, persistenza, condivisione, integrità e sicurezza) è supportato dal sistema attraverso specifiche componenti. Il concetto di "grande" dipende dalla quantità di spazio a disposizione: per grande intendiamo abbastanza dati da non riuscire a stare in memoria centrale. Sistemi di data warehousing e i big data utilizzano diversi ordini di grandezza in più. Memoria primaria: più piccola e veloce, volatile, manipolata direttamente dalla CPU.

Memoria secondaria: capacità di memorizzazione più elevata, persistente ma decisamente più lenta. I dati che contiene devono essere copiati in memoria primaria per poter essere elaborati dalla CPU. Le basi di dati solitamente sono memorizzate su memoria secondaria, per motivi di dimensioni, persistenza e costi inferiori. In alcune aree si utilizzano DBMS che memorizzano i dati in memoria primaria, ma noi non li vedremo.

In giallo le componenti legate all'efficienza, in verde alla concorrenza, in blu all'integrità e in rosa alla sicurezza. Al livello più basso abbiamo i dischi su cui vengono memorizzati i dati, composti da dati utente, dati di sistema (metadati, cataloghi e statistiche) che servono al sistema per la gestione del DB e gli indici: strutture ausiliarie di accesso che permettono al DBMS di eseguire più efficientemente alcune operazioni. Il sistema potrebbe funzionare anche senza, ma se ci sono le prestazioni migliorano: l'amministratore può intervenire nella fase di definizione degli indici. Dati utente, di sistema e indici essendo memorizzati su disco non potranno essere altro che file: ci sarà quindi un gestore dei file a gestirli. Sopra il gestore dei file abbiamo il gestore del buffer. Avere un buffer serve al DBMS per poter gestire il buffering con politiche diverse da quelle del sistema operativo che lo ospita. L'esecutore delle interrogazioni permette, sfruttando il gestore del buffer ed il gestore dei file, di restituire all'utente i risultati delle query. E’ composto da un parser, dall’ottimizzatore delle interrogazioni e dall’esecutore propriamente detto. L’ottimizzatore delle interrogazioni è

particolarmente importante perché SQL è un linguaggio dichiarativo: dice cosa fare, non come. Il sistema deve quindi sapere come vanno eseguite le query, che all'esecutore arrivano già ottimizzate: al livello superiore vi è infatti l'ottimizzatore delle interrogazioni, che ricevuta una query sceglie l'algoritmo più efficiente per eseguirla e lo invia all'esecutore. La scelta dell'algoritmo viene fatta in base a tutti i dati disponibili: statistiche riguardo ai dati più utilizzati, indici ecc. permettono al sistema di scegliere ogni volta la strategia più efficiente per una certa interrogazione. Il gestore del ripristino si occupa di mantenere la consistenza in caso di malfunzionamento. Il gestore dell'integrità si occupa di verificare se le modifiche richieste mantengono la base di dati in uno stato integro: se tutti i vincoli di integrità continuerebbero ad essere rispettati dopo l'esecuzione delle modifiche. I dati di sistema vengono memorizzati anch'essi in tabelle relazionali: in particolare i metadati come nomi delle tabelle, tipo degli attributi ecc. sono memorizzati in tabelle dette cataloghi di sistema: memorizzano informazioni sullo schema della base di dati (relazioni viste ecc.), strutture ausiliarie di accesso (indici), autorizzazioni e statistiche sul contenuto delle relazioni. In questo corso ci concentriamo su efficienza, concorrenza e sicurezza Efficienza Abbiamo visto in BD il concetto di indipendenza fisica: modifiche al livello fisico non devono influenzare ciò che avviene al livello logico. Questo ci permette di scegliere le strutture dati più efficienti per la memorizzazione e scegliere le strategie più efficienti di implementazione di un modello di dati. Il DBA può intervenire sulle scelte fatte dal sistema a livello fisico. Ci sono diverse scelte per mappare le tuple delle relazioni su file, e scelte differenti portano a costi di accesso differenti: potremmo ad esempio mettere tutto in un solo file, o fare un file per ogni tabella, all'interno del file mantenere o no ordinate le tuple, e se si come ordinarle (chiave primaria, frequenza di accesso ecc.). L'uso di strutture ausiliarie di accesso come indici e tabelle hash permette di ritrovare più efficientemente le tuple che soddisfano una certa condizione. Questa scelte vengono fatte tenendo conto di informazioni sui profili delle relazioni, sulle interrogazioni che saranno svolte più di frequente e sul carico di lavoro a cui sarà sottoposta la base di dati. Le prestazioni non dipendono solo dal livello fisico, ma anche dal livello logico: la presenza di viste e il fatto che le tabelle siano normalizzate o no influenzano le prestazioni del sistema. Seguendo le metodologie di progettazione viste a BD lo schema logico prodotto dovrebbe essere ottimale, ma non sempre è così: potremmo trovarci a dover amministrare database con schemi ridondanti. L'utilizzo di determinate forme normali e la creazione di opportune viste (che possono essere materializzate o no) permette di migliorare l'efficienza del sistema. Abbiamo detto che in seguito ad una query il sistema sceglie l'algoritmo più efficiente per eseguirla: ma anche questa scelta ha un costo: però il vantaggio che si ricava dall'utilizzo della strategia migliore bilancia largamente il costo della scelta. Non sempre questo è vero: a causa di diversi fattori (statistiche non aggiornate e altro) la strategia scelta in automatico dal sistema potrebbe non essere abbastanza efficiente e portare a prestazioni non ottimali: il DBA deve accorgersene attraverso il monitoraggio e intervenire con opportuni interventi di tuning a livello fisico.

Anche con un livello fisico perfettamente ottimizzato, a volte il DBMS sceglie una strategia diversa a seconda di come è scritta l'interrogazione: in questi casi l'unico intervento possibile è riformulare la query in modo che abbia la stessa semantica ma un'esecuzione più efficiente. Gestione delle transazioni Le transazioni sono sequenze di operazioni realizzate in modo atomico: o hanno successo tutte (commit) o non viene eseguito niente (abort). I DBMS mettono a disposizione diversi livelli di isolamento delle transazioni: quanto vogliamo che le transazioni siano consapevoli di altre transazioni eseguite concorrentemente. La scelta del livello di isolamento adeguato velocizza l'approccio concorrente minimizzando il numero di blocchi, deadlock e rollback. Controllo dell'accesso I dati sono la risorsa da proteggere per impedirne la corruzione e garantirne la confidenzialità, utilizzando meccanismi a granularità più fine di quella offerta dal sistema operativo: il controllo dell'accesso sarà basato sul contenuto dei file. Dall'analisi dei requisiti è necessario individuare una politica di gestione degli accessi adeguata.

3. Organizzazione dei dati su disco Tra i compiti di un DBMS c’è quello di gestire l’organizzazione dei dati sul disco in maniera ottimale, per ridurre al minimo il numero di trasferimenti dal disco alla memoria principale, dato che sono molto costosi in termini di tempo. Vedremo l'aspetto dell'efficienza partendo dal basso dell'architettura: gestore dei file, gestori del buffer, dati utente e indici. Più avanti ci occuperemo anche di dati di sistema e statistiche. Sul disco le informazioni sono memorizzate in cerchi concentrici chiamati tracce. Le tracce con lo stesso diametro sui vari piatti sono dette cilindro. La testina dovrà muoversi su un braccio per posizionarsi sulla traccia richiesta. Il concetto di cilindro è importante perché le tracce che fanno parte di uno stesso cilindro possono essere accedute nello stesso momento, con un unico movimento del braccio. Questo aspetto è preso in considerazione dai DBMS, che cercherà di mettere sullo stesso cilindro gli elementi che di solito vengono richiesti insieme. Il tempo di latenza di un disco è il tempo necessario affinché un'intera traccia passi sotto il braccio, e solitamente è molto breve; il tempo di seek invece è il tempo necessario per posizionare il braccio sul cilindro richiesto, e solitamente è molto lungo. Per migliorare l'efficienza riducendo il tempo di seek, il sistema cercherà di mettere su uno stesso cilindro informazioni che solitamente vengono accedute contemporaneamente. L'unità di trasferimento dal disco alla memoria principale è il blocco, una sequenza di byte contigui (la cui dimensione dipende dal SO) memorizzati su una stessa traccia di uno stesso cilindro. Il tempo del trasferimento vero e proprio dal disco alla memoria centrale è molto breve, non ci interessa ottimizzarlo: obiettivo delle ottimizzazioni dei DBMS è ridurre il tempo di seek.

I dati generalmente sono memorizzati sotto forma di record: un insieme di valori collegati, dove i valori sono i campi del record. Nella base di dati di esempio (videoteca) la relazione Film(titolo,regista,anno,genere,valutaz) potrebbe essere memorizzata con un record di tipo struct C come questa: struct film { char titolo; char regista; int anno etc }

Ciascuno record deve avere un identificatore univoco chiamato record ID o RID, che solitamente ha la forma . Un file è composto da una sequenza di record, che possono essere a lunghezza fissa o variabile. I record a lunghezza variabile permettono di risparmiare spazio in caso di valori nulli, di varchar (di cui non conosco a priori la dimensione precisa) o, se stiamo usando estensioni object relational, per tipi complessi. Con i record a lunghezza fissa invece ogni record ha gli stessi campi e la lunghezza dei campi è fissa. L'accesso è semplificato perché ne conosco a priori la dimensione.

Tracciato di un record della relazione Film. I record a lunghezza variabile portano un'altra ottimizzazione: immaginiamo di avere una relazione con record a lunghezza fissa. Se voglio aggiungere un campo (nullabile) ad una relazione, e se questo campo avesse inizialmente valore non nullo in una sola tupla, se sto usando file con record a lunghezza fissa dovrò modificare tutti i record, se sto usando file con record a lunghezza variabile modificherò solo il record interessato. Una soluzione intermedia è di usare una cella puntatore all'informazione che mi interessa. A livello fisico non esistono mai soluzioni ottime, ma solo soluzioni ottimali per un certo contesto.

3.1 Organizzazione dei record su disco Abbiamo detto che un file può essere visto come una collezione di record, e che i dati su disco vengono trasferiti in memoria principale come blocchi. I record dei file saranno quindi mappati sui blocchi. Se a livello di sistema operativo l'unità minima a cui vogliamo accedere solitamente è un file intero (e quindi il mapping dei singoli record ci interessa poco), un DBMS vuole poter accedere anche ai singoli record, e per questo sarebbe opportuno che i blocchi contenessero record correlati tra loro, che vengono spesso acceduti insieme. L'organizzazione dipende dalle operazioni che farò più di frequente: se ad esempio faccio quasi solo selezioni semplici (senza join) sarà opportuno che ogni blocco contenga solo tuple di una

stessa relazione. Se invece faccio frequenti join sarà meglio che i record delle relazioni joinate più di frequente condividano gli stessi blocchi. Non sempre è possibile organizzare i record in modo che un blocco sia completamente occupato da record: ci sarà sempre un po' di spazio inutilizzato. Se un record può essere memorizzato su più blocchi stiamo usando un'organizzazione spanned, se ogni record deve essere memorizzato su un singolo blocco stiamo usando un'organizzazione unspanned. L'organizzazione spanned è obbligatoria quando le dimensioni dei record superano le dimensioni del blocco (ad esempio in caso di immagini, testi lunghi o oggetti binari molto grandi [BLOB]), l'organizzazione unspanned invece è preferibile quando stiamo usando record a lungezza fissa. In generale, se la dimensione del record non supera quella del blocco è preferibile evitare di memorizzare un solo record su più blocchi, perché così dovrò fare più accessi per caricare un solo record: piuttosto è meglio sprecare un po' di spazio.

3.2 Organizzazione dei blocchi su disco Tre possibili strategie sono allocazione continua, allocazione concatenata e utilizzo di bucket. Nell'allocazione continua tutti i blocchi che costituiscono un file sono memorizzati in maniera contigua, quindi tutti su stessa traccia e stesso cilindro (se ci stanno). Questo approccio migliora le prestazioni in lettura perché una volta trovato l'inizio del file non avrò bisogna di altri seek, i blocchi sono tutti contigui. In scrittura può causare problemi quando le dimensioni di un file superano quelle che erano state allocate inizialmente: non ci sono abbastanza blocchi contigui per memorizzarlo. In questo caso dovrò spostare i blocchi di altri file per liberare spazio contiguo. L'allocazione continua è un approccio conveniente in caso di letture frequenti e scritture rare: se parliamo di basi di dati un esempio può essere un DB che contiene dati storici, che saranno quindi più letti che modificati. Nell'allocazione concatenata i blocchi non sono necessariamente contigui, ma ogni blocco di un file contiene un puntatore al blocco successivo. L'espansione delle dimensioni di un file è più efficiente, le prestazioni in lettura invece peggiorano perché ogni volta che ho finito un blocco dovrò cercare il successivo. Un approccio che tenta prendere pro e contro delle due strategie precedenti è l'utilizzo di bucket: utilizzo un insieme di blocchi non necessariamente continui ma comunque vicini per gruppi di record tra loro correlati, che saranno spesso acceduti insieme. I blocchi di un bucket sono collegati tra di loro come nell'allocazione concatenata: se un bucket aumenta di dimensione i nuovi blocchi verranno cercati il più vicino possibile. In caso di cancellazioni è meglio non riusare i blocchi liberi di un bucket per memorizzare record di un altro bucket: è più convieniente lasciarli liberi (almeno per un po') nel caso arrivassero nuovi record da memorizzare in quel bucket. Come fa il sistema a decidere in quale bucket va messo un certo record? Una possibile soluzione è una funzione hash che associa ogni dato al blocco di un bucket.

3.3 Mapping tra relazioni e file I DBMS possono utilizzare diverse strategie per determinare quanti e quali file creare e mantenere aggiornati su disco. DBMS di piccole dimensioni (cioè sistemi atti a gestire database medio piccoli) solitamente creano un file per ogni relazione presente nello schema logico. Per DBMS large scale questa strategia non è efficace: dato che il DBMS ha più informazioni del SO sui dati a cui vuole accedere, vorrà che durante l’accesso la parte demandata al sistema operativo sia più piccola possibile, in modo da poter gestire in maniera opportuna le allocazioni di record e blocchi. Una strategia adottata di frequente è di utilizzare un unico grosso file in cui il DBMS memorizzerà tutti i

dati. Qualunque sia la strategia adottata, i file che contengono i record dei dati costituiscono l'organizzazione primaria dei dati. Nel modello relazionale una relazione è un insieme di tuple. Nelle implementazioni di SQL questo non è sempre vero, le relazioni sono multiinsiemi di tuple: quando eseguo un'interrogazione, nella relazione risultato le tuple ripetute ci sono (a meno che non dica esplicitamente di escluderle). In ogni caso, sia insiemi che multiinsiemi non tengono conto dell'ordinamento. Un file invece è una lista di record, e le liste hanno un ordine. A seconda dell'organizzazione primaria dei dati scelta cambierà anche il modo in cui i record vengono organizzati nel file che li contiene: in un file heap i record vengono memorizzati in ordine di inserimento, non mi interessa memorizzarli in un ordine particolare. In un file ordinato (o sequenziale) invece i record sono memorizzati mantenendo l'ordinamento su uno o più campi, ed al file viene associato un indice (ad albero) sui campi coinvolti nell'ordinamento. In un file hash infine i record sono memorizzati in una struttura hash in cui la posizione del record nel file dipende dal valore ottenuto dall'applicazione di una funzione hash a uno o più campi. Scegliere se utilizzare o no un file ordinato è fondamentale per un DBA.