Basi dati 2

2019/2020

BASI DI DATI 2 - APPUNTI

C –

ORSO DI LAUREA MAGISTRALE SICUREZZA INFORMATICA

Sommario

Dipendenze funzionali e Normalizzazione di DB Relazionali 1

Dipendenze funzionali 7

Regole di inferenza per dipendenze funzionali 9

Forme Normali 12

Algoritmi per la progettazione di DB Relazionali e ulteriori dipendenze 22

Decomposizione delle relazioni e insufficienza delle forme normali 22

Decomposizione e conservazione delle dipendenze 23

Decomposizione e Join senza perdita (non-additivi) 25

Problemi con valori nulli e tuple dangling 30

Dipendenze multivalore e quarta forma normale 33

Regole di inferenza per FD e MVD 35

Applicazioni di design e Tuning di database 37

Il ciclo di vita di un sistema informativo 38

Le fasi del micro-ciclo di vita 39

Il processo di progettazione di un database 40

La progettazione fisica nei database relazionali 47

Memorizzazione di record ed Organizzazione dei file 49

Gerarchie di memoria e dispositivi di memorizzazione 49

Dispositivi di memoria secondaria 51

Collocazione su disco dei record di un file 54

Ripartizione dei record in blocchi e confronto tra record con spanning e record senza spanning 56

Header dei file 57

File di record non ordinati (file heap) 59

File di record ordinati (file sorted) 60

Tecniche hash 63

Tecnologia RAID 68

Strutture di indici per i file 71

Indici primari 72

Indici di cluster 73

Indici secondari 74

Indice multilivello 77

+

Indici dinamici multilivello implementati da alberi B e alberi B 79

Alberi di ricerca e alberi B 79

+

Alberi B 83

Gestione delle Transazioni 88

Controllo della concorrenza 89

Tecniche di recovery 91

Il System Log 93

Proprietà delle transazioni 93

Gli Schedule 94

Schedule serializzabili 97

Supporto alle transazioni in SQL 99

Tecniche per il Controllo della Concorrenza 101

Lock binari 101

Lock shared/esclusivi 102

Protocollo Two-Phase Locking 105

Tecniche di Recovery 110

Protocollo WAL (Write-Ahead Logging) 112

Tecniche di recovery basate su Deferred Update 113

Tecniche di Recovery basate su Immediate Update 114

Basi di Dati Distribuite ed Architetture Client-Server 117

Architettura di un DDB 118

Funzionalità addizionali caratteristiche dei DDBMS 120

Frammentazione dei dati 121

Replicazione ed allocazione di dati 122

Tipi di DDB 132

Architettura Client-Server 135

XML e basi di dati in Internet 137

XML Schema 139

Attributi 140

Restrizioni 141

Enumerazione 141

Elementi complessi (complex elements) 141

Costrutto sequence 141

Costrutto all 142

Costrutto choice 142

Elementi EMPTY 142

Interrogazioni in XML 143

Database NoSQL 148

Transazioni BASE 149

Vantaggi e svantaggi del NoSQL 149

Classificare i DBMS NoSQL 150

Basi di dati semantiche, SPARQL e Linked Open Data 153

Modello RDF (Resource Description Framework) 153

SPARQL (Simple Protocol and RDF Query Language) 157

SPARQL 1.1 163

Linked e Open Data 165

Data Warehouse 166

Lezione 01 - Dipendenze Funzionali e Normalizzazione di DB Relazionali

Dipendenze funzionali e Normalizzazione di DB Relazionali

Le fasi di progettazione di un di un Database

Ogni schema di relazione è composto da un certo numero di attributi, e lo schema di base di dati relazionale

è composto da un certo numero di schemi di relazione. Non sempre dalla fase di progettazione si ottiene uno

schema privo di difetti, infatti possono sorgere dei problemi nella fase di mapping dal modello ER allo schema

relazionale. Si può ottenere uno schema non ottimale progettando direttamente uno schema logico saltando

la fase di analisi concettuale. Tali difetti possono portare ad anomalie nella base di dati.

Ci sono due livelli ai quali è possibile esaminare la “bontà” di uno schema di relazione; il primo è il livello

logico, come gli utenti interpretano gli schemi di relazione e il significato dei loro attributi. L’avere buoni

schemi di relazione a questo livello consente agli utenti di capire chiaramente il significato dei dati nelle

relazioni, e perciò di formulare correttamente le loro interrogazioni. Il secondo è il livello

d’implementazione, come le tuple in una relazione di base sono memorizzate ed aggiornate. Questo livello

si applica solo a schemi di relazione di base, che saranno memorizzati fisicamente come file, mentre a livello

logico siamo interessati a schemi sia di relazioni di base sia di viste (relazioni virtuali).

Inoltre, come qualsiasi tipo di progettazione, la progettazione di una base di dati può essere eseguita usando

due approcci: bottom-up (dal basso verso l’alto, ossia dai concetti generali a quelli specifici). Tale

metodologia considera come punto di partenza le associazioni di base tra singoli attributi, e le usa per

costruire relazioni. Questo approccio è poco popolare nella pratica e soffre del problema di collezionare un

gran numero di associazioni tra coppie di attributi come punto di partenza. Al contrario, una metodologia di

progettazione top-down comincia con un certo numero di raggruppamenti di attributi in relazioni;

raggruppamenti che sono già stati ottenuti dalle attività di progettazione concettuale e di traduzione. Tale

progettazione viene quindi applicata alle relazioni individualmente e collettivamente, portando a

decomposizioni successive finché non si ottengono tutte le proprietà desiderate.

Esistono delle misure informali di qualità per la progettazione di uno schema di relazione:

1. SEMANTICA DEGLI ATTRIBUTI

2. RIDUZIONE DEI VALORI RIDONDANTI NELLE TUPLE

3. RIDUZIONE DEI VALORI NULL NELLE TUPLE

4. NON CONSENTIRE TUPLE SPURIE

Come si vedrà, queste misure non sono sempre indipendenti tra loro. 1

Lezione 01 - Dipendenze Funzionali e Normalizzazione di DB Relazionali

Semantica degli attributi di una relazione

Ogni volta che si raggruppano degli attributi per formare uno schema di relazione, si suppone che ad essi sia

associato un certo significato. Questo significato, o semantica, specifica come interpretare i valori degli

attributi memorizzati in una tupla della

relazione; in altre parole, come i valori degli

attributi in una tupla sono in relazione tra

loro. Se è stata eseguita correttamente la

progettazione concettuale, seguita da una

traduzione nelle relazioni, la maggior parte

della semantica dovrebbe essere spiegata e

il progetto risultate dovrebbe avere un

significato chiaro. In generale il progetto di

uno schema di relazione sarà tanto migliore

quanto più facile è spiegare la semantica

della relazione. Per illustrare ciò si consideri

la Figura 1, una versione semplificata dello

schema del database Company e la Figura 2,

che presenta un esempio di relazioni

popolate di questo schema. Il significato Figura 1 - Versione semplificata dello schema del database Company

dello schema di relazione IMPIEGATO è

piuttosto semplice: ogni tupla rappresenta

un impiegato, con i valori per il nome dell’impiegato (NOME_I), il numero di previdenza sociale (SSN), la data

di nascita (DATA_N) e l’indirizzo

(INDIRIZZO), nonché il numero del

dipartimento per cui l’impiegato

lavora (NUMERO_D). L’attributo

NUMERO_D è una chiave esterna che

rappresenta un’associazione implicita

tra IMPIEGATO e DIPARTIMENTO.

Anche la semantica degli schemi

DIPARTIMENTO e PROGETTO è chiara;

ogni tupla DIPARTIMENTO

rappresenta un’entità dipartimento, e

ogni tupla PROGETTO rappresenta

un’entità progetto. L’attributo

SSN_DIR_DIP di DIPARTIMENTO

collega un dipartimento all’impiegato

che ne è il direttore, mentre NUM_D di

PROGETTO collega un progetto al

dipartimento che lo controlla;

entrambi gli attributi sono chiavi

esterne. La semantica degli altri due

Figura 2 - Relazioni d’esempio per lo schema di Figura 1 schemi di relazione in Figura 1 è un po'

più complessa. Ogni tupla in SEDI_DIP fornisce un numero di dipartimento (NUMERO_D) e una delle sedi del

dipartimento (SEDE_D). Ogni tupla in LAVORA_SU dà il numero di previdenza sociale di un impiegato (SSN),

2

Lezione 01 - Dipendenze Funzionali e Normalizzazione di DB Relazionali

il numero di progetto di uno dei progetti su cui lavora l’impiegato (NUMERO_P) e il numero di ore settimanali

lavorate dell’impiegato su quel progetto (ORE). Entrambi gli schemi hanno comunque un’interpretazione ben

definita e non ambigua. Lo schema SEDI_DIP rappresenta un attributo multivalore di DIPARTIMENTO, mentre

LAVORA_SU rappresenta un’associazione M:N tra IMPIEGATO e PROGETTO. Tutti gli schemi di relazione in

Figura 1 possono perciò essere considerati “buoni” dal punto di vista di una semantica chiara. La seguente

linea guida informale sviluppa ulteriormente la progettazione di uno schema di relazione.

LINEA GUIDA 1. Si progetti ogni schema di relazione in modo tale che sia semplice spiegarne il significato.

Non si uniscano attributi provenienti da più tipi di entità e tipi di associazione in un’unica relazione.

Intuitivamente, se uno schema di relazione corrisponde a un solo tipo di entità o a un tipo di associazione, il

suo significato tende a essere chiaro. Altrimenti la relazione corrisponde a un miscuglio di più entità e

associazioni e perciò diviene semanticamente oscura. Anche gli schemi di relazione

nella Figura 3 (a) e (b)

presentano una semantica

chiara. Una tupla nello schema di

relazione IMP_DIP rappresenta

un singolo impiegato ma

comprende informazioni

aggiuntive, vale a dire il nome

(NOME_D) del dipartimento per

cui l’impiegato lavora e il

Figura 3 - Due schemi di relazione e le rispettive dipendenze funzionali numero di previdenza sociale

(SSN_DIR_DIP) del direttore del dipartimento. Per la relazione IMP_PROG, ogni tupla collega un impiegato a

un progetto, ma comprende anche il nome dell’impiegato (NOME_I), il nome del progetto (NOME_P) e la

sede del progetto (SEDE_P). Anche se non c’è alcunché di sbagliato dal punto di vista logico in queste due

relazioni, esse violano la linea guida 1, mischiando attributi proveniente da distinte entità del mondo reale;

IMP_DIP mescola attributi impiegati e dipartimenti, e IMP_PROG mescola attributi di impiegati e progetti.

Queste relazioni possono essere usate come viste, ma causano problemi quando vengono usate come

relazioni di base.

Riduzione dei valori ridondanti nelle tuple

Uno scopo della progettazione di schemi è quello di ridurre al minimo lo spazio di memoria occupato dalle

relazioni di base (file). Il raggruppamento di attributi in schemi di relazione ha un effetto significativo sullo

spazio di memoria. Ad esempio, si confronti lo spazio occupato dalle due relazioni di base IMPIEGATO e

DIPARTIMENTO in Figura 2 con lo spazio della relazione di base IMP_DIP in Figura 4, che è il risultato

dell’applicazione dell’operazione di JOIN NATURALE a IMPIEGATO e DIPARTIMENTO. In IMP_DIP, i valori degli

attributi che riguardano uno specifico dipartimento (NUMERO_D, NOME_D, SSN_DIR_DIP) sono ripetuti per

ogni impiegato che lavora per quel dipartimento. Al contrario, l’informazione su ogni dipartimento appare

solo una volta nella relazione DIPARTIMENTO di Figura 2. Solo il numero di dipartimento (NUMERO_D) è

ripetuto nella relazione IMPIEGATO per ogni impiegato che lavora in quel dipartimento. Considerazioni simili

si applicano alla relazione IMP_PROG (Figura 4), che aumenta la relazione LAVORA_SU con ulteriori attributi

di IMPIEGATO e PROGETTO. 3

Lezione 01 - Dipendenze Funzionali e Normalizzazione di DB Relazionali

Un altro grave problema che si presenta usando le relazioni in Figura 4 come relazioni di base è il problema

delle anomalie di aggiornamento. Esse possono essere classificate in anomalie di inserimento, anomalie di

cancellazione e anomalie di modifica.

Figura 4 - Relazioni esemplificative per gli schemi in Figura 3, ottenute

applicando il JOIN NATURALE alle relazioni in Figura 2.

Anomalie di inserimento. Possono essere distinte in due tipi, illustrati dai seguenti esempi basati sulla

relazione IMP_DIP.

• Per inserire una nuova tupla impiegato in IMP_DIP occorre inserire i valori degli attributi del

dipartimento per cui l’impiegato lavora, o valori nulli (se l’impiegato ancora non lavora per un

dipartimento). Ad esempio, per inserire una nuova tupla per un impiegato che lavora nel

dipartimento numero 5, bisogna inserire correttamente i valori degli attributi del dipartimento 5 in

modo tale che siano consistenti con i valori del dipartimento 5 in altre tuple di IMP_DIP. Nel progetto

di Figura 2 non ci si deve preoccupare di questo problema di consistenza, dato che nella tupla

impiegata viene inserito solo il numero del dipartimento; tutti gli altri valori di attributi di

dipartimento 5 sono registrati solo una volta nella base di dati, come tupla singola nella relazione

DIPARTIMENTO.

• È difficile inserire nella relazione IMP_DIP un nuovo dipartimento che non ha ancora impiegati. Il solo

modo per farlo è quello di porre valori nulli negli attributi relativi a impiegato. Ciò causa un problema

perché SSN è la chiave primaria di IMP_DIP, e si suppone che ogni tupla rappresenti un’entità

impiegato, non un’entità dipartimento. Inoltre, quando viene assegnato il primo impiegato a quel

dipartimento, non si ha più bisogno della tupla con valori nulli. Questo problema non si presenta nel

progetto di Figura 2, perché un dipartimento viene inserito nella relazione DIPARTIMENTO che in

esso lavorino impiegato o non lavorino, e ogni volta che un impiegato è assegnato a quel

dipartimento una tupla corrispondente è inserita in IMPIEGATO.

Anomalie di cancellazione. Questo problema è legato alla seconda situazione di anomalia di inserimento

discussa sopra. Se si cancella da IMP_DIP una tupla impiegato che è quella che rappresenta l’ultimo impiegato

che lavora per un particolare dipartimento, l’informazione riguardante quel dipartimento non è più presente

nella base di dati. Il problema non si presenta nella base di dati di Figura 2 perché le tuple di DIPARTIMENTO

sono memorizzate separatamente. 4

Lezione 01 - Dipendenze Funzionali e Normalizzazione di DB Relazionali

Anomalie di modifica. In IMP_DIP, se si cambia il valore di uno degli attributi di un particolare dipartimento,

ad esempio il direttore del dipartimento 5, occorre aggiornare le tuple di tutti gli impiegati che lavorano in

quel dipartimento, altrimenti la base di dati diverrà inconsistente. Se ci si dimentica di aggiornare alcune

tuple, per lo stesso dipartimento verranno mostrati due diversi valori di direttore in diverse tuple impiegato,

il che non dovrebbe verificarsi.

Basandosi sulle tre anomalie precedenti, è possibile fornire la seguente linea guida.

LINEA GUIDA 2. Si progettino gli schemi di relazione di base in modo che nelle relazioni non siano presenti

anomalie di inserimento, cancellazione o modifica, Se sono presenti delle anomalie, le si rilevi chiaramente

e ci si assicuri che i programmi che aggiornano la base di dati operino correttamente.

La seconda linea guida è consistente con la prima e, in un certo senso, ne è una riaffermazione. È importante

notare che queste linee guida possono talora dover esser violate al fine di incrementare le prestazioni di certe

interrogazioni. Ad esempio, se un’interrogazione importante recupera informazioni riguardanti il

dipartimento di un impiegato, insieme con gli attributi di impiegato, lo schema IMP_DIP può essere usato

come relazione di base. Le anomalie in IMP_DIP devono però essere notate e ben comprese, in modo tale

che non si finisca col produrre inconsistenze ogni volta che viene aggiornata la relazione di base. In generale

è consigliabile usare relazioni di base prive di anomalie, e specificare viste che utilizzino i JOIN per

raggruppare gli attributi frequentemente richiamati in interrogazioni importanti. Ciò riduce il numero di

termini JOIN specificati nell’interrogazione, rendendo più semplice scrivere l’interrogazione correttamente,

e in molti casi migliora le prestazioni.

Riduzione dei valori null nelle tuple

È possibile che nei progetti di alcuni schemi vengano raggruppati numerosi attributi a formare una “grossa”

relazione. Se molti di questi attributi non riguardano tutte le tuple della relazione, quelle tuple finiscono con

l’avere molti valori nulli. Ciò può dar luogo a uno spreco di spazio di memoria e può anche portare a problemi

di comprensione del significato degli attributi e di specificazione delle operazioni di JOIN a livello logico. Un

altro problema con i valori null è come rispondere della loro presenza quando vengono applicate operazioni

aggregate come COUNT o SUM. Inoltre, i valori null possono avere più interpretazioni, tra cui le seguenti:

• L’attributo non è pertinente per questa tupla;

• Il valore dell’attributo per questa tupla è sconosciuto;

• Il valore è noto ma assente, cioè non è ancora stato memorizzato;

L’uso della stessa rappresentazione per tutti i valori null non consente di cogliere i diversi significati che essi

possono assumere. Si può pertanto enunciare un’altra linea guida.

LINEA GUIDA 3. Per quanto possibile, si eviti di porre in una relazione di base attributi i cui valori possono

essere frequentemente null. Se i valori null sono inevitabili, ci si assicuri che essi si presentino solo in casi

eccezionali e che non riguardino una maggioranza di tuple nella relazione.

Ad esempio, se solo il 10% degli impiegati ha un ufficio personale, non c’è ragione di includere un attributo

NUMERO_UFFICIO nella relazione IMPIEGATO; piuttosto può essere progettata una relazione IMP_UFFICI

(SSN_I, NUMERO_UFFICIO) che comprenda tuple solo per impiegati che hanno uffici privati.

Non consentire tuple spurie

Si considerino i due schemi di relazione IMP_SEDI e IMP_PROG1 di Figura 5, che possono essere usati al posto

de