Normalizzazione
Le forme normali “certificano” che la base di dati soddisfa criteri di
qualità che mirano ad evitare le ridondanze e i conseguenti effetti
collaterali.
La normalizzazione è una procedura che permette di trasformare
schemi non normalizzati in schemi che soddisfano una forma
normale; a utilizzata come tecnica di verifica dei risultati della
progettazione di una base di dati
Non costituisce una metodologia di progettazione
La definizione delle forme normali può essere fatta esaminando
prima i diversi tipi di anomalia che si possono verificare a causa
delle ridondanze.
Una relazione con anomalie
Impiegato Stipendio Progetto
Rossi
20
Marte
Verdi
35
Giove
Verdi
35
Venere
Neri
55
Venere
Neri
55
Giove
Neri
55
Marte
Mori
48
Marte
Mori
48
Venere
Bianchi
48
Venere
Bianchi
48
Giove
Bilancio
2
15
15
15
15
2
2
15
15
15
Funzione
tecnico
progettista
progettista
direttore
consulente
consulente
direttore
progettista
progettista
direttore
Anomalie
Se si utilizza una sola relazione per rappresentare concetti
disomogenei o indipendenti si possono verificare tre tipi di
anomalie, oltre ad avere ridondanza nello schema (un dato è
ripetuto in tutte le tuple relative al concetto cui si riferisce):
• anomalia di aggiornamento: se il dato ridondante varia va
modificato in tutte le tuple
• anomalia di cancellazione: se non ci sono informazioni relative
ad un elemento della chiave si perdono anche tutte le altre
informazioni, anche se disponibili, riguardo ad altri concetti non
inclusi nella chiave (a meno di ammettere valori nulli nella chiave).
• anomalia di inserimento: non è possibile inserire informazioni
su un concetto non incluso nella chiave se manca l’informazione su
un elemento della chiave.
Anomalie
Quindi in presenza di ridondanze:
• alcuni dati possono essere ripetuti, senza aggiunta di informazioni
significative
• gli aggiornamenti (concettualmente atomici) devono essere
ripetuti per ogni occorrenza dei dati relativi.
• La cancellazione di una tupla perché non è più valido l’insieme di
concetti nel suo complesso può comportare l’eliminazione di tutti i
concetti, anche quelli che restano validi
• Non è possibile inserire un solo concetto per una relazione se non
esiste un intero insieme di concetti
Perché questi fenomeni indesiderabili?
• abbiamo usato un'unica relazione per rappresentare informazioni
eterogenee
– gli impiegati con i relativi stipendi
– i progetti con i relativi bilanci
– le partecipazioni degli impiegati ai progetti con le relative funzioni
Dipendenze funzionali
Sono vincoli di integrità di tipo funzionale fra gli attributi di una
relazione.
Formalmente: data una relazione r su uno schema R(X) e due
sottoinsiemi non vuoti Z e Y di X, esiste per r una dipendenza
funzionale tra Y e Z se per ogni coppia di tuple t1 e t2 di r aventi gli
stessi valori su Y, t1 e t2 hanno anche gli stessi valori su Z.
Si indica con Y  Z
(es. Impiegato  Stipendio)
Y  Z è non banale se nessun attributo in Z appartiene a Y
Es.
Impiegato Progetto  Progetto
è banale
Se K è una chiave esiste una dipendenza funzionale da K di tutti gli
altri attributi. Il vincolo di dipendenza funzionale generalizza il
vincolo di chiave.
Y -> Z su R(x) degenera nel vincolo di chiave se Y U Z = X
Tornando all’esempio…..
• gli impiegati hanno un unico stipendio
Impiegato  Stipendio
• i progetti hanno un unico bilancio
Progetto  Bilancio
• In ciascun progetto, un impiegato svolge una sola funzione
Impiegato Progetto  Funzione
Le prime due dipendenze funzionali causano anomalie, la terza no.
Impiegato Stipendio Progetto
Rossi
20
Marte
Verdi
35
Giove
Verdi
35
Venere
Neri
55
Venere
Neri
55
Giove
Neri
55
Marte
Mori
48
Marte
Mori
48
Venere
Bianchi
48
Venere
Bianchi
48
Giove
Bilancio
2
15
15
15
15
2
2
15
15
15
Funzione
tecnico
progettista
progettista
direttore
consulente
consulente
direttore
progettista
progettista
direttore
Impiegato  Stipendio
Progetto  Bilancio
Impiegato Progetto  Funzione
Dipendenze funzionali e anomalie
• La terza dipendenza funzionale corrisponde ad una chiave e non
causa anomalie
• Le prime due non corrispondono a chiavi e causano anomalie
• La relazione contiene alcune informazioni legate alla chiave e altre
ad attributi che non formano una chiave
•
•
•
•
Impiegato Progetto è chiave
Impiegato solo no
Progetto solo no
Le anomalie sono causate dalla presenza di concetti eterogenei:
– proprietà degli impiegati (lo stipendio)
– proprietà di progetti (il bilancio)
– proprietà della chiave Impiegato Progetto
Forma normale di Boyce e Codd
Le dipendenze funzionali X -> Y in cui X sia una superchiave NON
possono creare anomalie o ridondanze, in quanto X di per sé
implica l’unicità di ogni tupla definita su tale insieme.
Se X non è superchiave ciò può non accadere.
Una relazione r si definisce in forma normale di Boyce e Codd se
per ogni dipendenza funzionale X->Y definita su di essa, X
contiene una chiave K di r, cioè X è superchiave di r.
La forma normale di Boyce e Codd richiede che i concetti in una
relazione siano omogenei (solo proprietà direttamente associate
alla chiave)
Decomposizione in forma normale
In generale, se una relazione non è in forma normale, è possibile
portarla in forma normale producendo tante relazioni quante sono
le dipendenze funzionali.
Questo è possibile in molti casi in modo diretto e naturale se le
dipendenze sono indipendenti (es. su insiemi disgiunti di attributi).
In altri casi la cosa può essere più complicata.
Impiegato Stipendio Progetto Bilancio Funzione
Rossi
20
Marte
2
tecnico
Verdi
35Impiegato Giove
15
progettista
Progetto Funzione
Marte
tecnico
Verdi Stipendio 35 Rossi Venere
15
progettista
Impiegato
Giove progettista
Rossi
20
Bilancio
Neri
55 Verdi
Venere
15 Progetto
direttore
Verdi
Venere
progettista
Verdi
35
Marte
2
Neri
55
Giove
15
consulente
Neri
Venere
direttore
Neri
55
Giove
15
Neri
Giove
consulente
Neri
55
Marte
2
consulente
Mori
48
Venere
15
Neri
Marte
consulente
Bianchi
48
Mori
48 Mori Marte
2
direttore
Marte
direttore
Venere progettista
Mori
48 Mori Venere
15
progettista
Bianchi
Venere progettista
Bianchi
48 Bianchi Venere
15
progettista
Giove
direttore
Bianchi
48
Giove
15
direttore
Decomposizione in forma normale
In generale, la progettazione concettuale fatta mediante il modello
E-R tende a garantire che lo schema rappresenti in modo separato
le entità fondamentali e le rispettive associazioni.
Quindi se la progettazione concettuale è stata fatta in modo
corretto, la base di dati risultante dalla sua traduzione dovrebbe
essere in forma normale.
Una buona decomposizione deve soddisfare le proprietà di essere
senza perdita e di conservare le dipendenze.
Non sempre così facile
Impiegato Progetto
Rossi
Marte
Verdi
Giove
Verdi
Venere
Neri
Saturno
Neri
Venere
Sede
Roma
Milano
Milano
Milano
Milano
Impiegato  Sede
Progetto  Sede
Decomponendo in base alle dipendenze:
Impiegato
Rossi
Verdi
Neri
Sede
Roma
Milano
Milano
Progetto
Marte
Giove
Saturno
Venere
Sede
Roma
Milano
Milano
Milano
Ricomposizione della tabella
Impiegato
Rossi
Verdi
Neri
Sede
Roma
Milano
Milano
Impiegato Progetto
Rossi
Marte
Verdi
Giove
Verdi
Venere
Neri
Saturno
Neri
Venere
Verdi
Saturno
Neri
Giove
Progetto
Marte
Giove
Saturno
Venere
Sede
Roma
Milano
Milano
Milano
Sede
Roma
Milano
Milano
Milano
Milano
Milano
Milano
La relazione ottenuta è diversa dalla relazione di partenza
Decomposizione senza perdita
Data una relazione r su X, se X1 e X2 sono due sottoinsiemi di X la
cui unione è X stesso, allora il join delle due relazioni ottenute per
proiezione di r su X1 e X2 è una relazione che contiene tutte le
tuple di r più eventualmente alcune altre che si possono definire
“spurie”.
La decomposizione di r su X1 e X2 è senza perdita se il join delle
due proiezioni è uguale ad r stessa, cioè non contiene tuple spurie.
Se si deve fare una decomposizione ai fini della normalizzazione,è
essenziale che sia senza perdita.
Sia r una relazione su X e X1 e X2 tali che X1 U X2 = X e
X0 = X1  X2 . Se r soddisfa la dipendenza funzionale X0->X1
oppure X0 -> X2 allora la decomposizione è senza perdita.
Cioè la decomposizione è senza perdita se gli attributi comuni sono
superchiave per una delle relazioni decomposte.
Conservazione delle dipendenze
La decomposizione in più relazioni può creare casi in cui un
inserimento di dati illecito per la relazione originaria (per la
violazione di una dipendenza funzionale) possa non essere rilevato
nel caso della relazione decomposta.
Una proprietà fondamentale delle decomposizioni deve essere
quella di conservare le dipendenze.
Questo può essere garantito se ciascuna delle dipendenze
funzionali dello schema originario coinvolge attributi che
compaiono tutti insieme in uno degli schemi decomposti.
Conservazione delle dipendenze
Impiegato Progetto
Rossi
Marte
Verdi
Giove
Verdi
Venere
Neri
Saturno
Neri
Venere
Impiegato
Rossi
Verdi
Neri
Sede
Roma
Milano
Milano
Sede
Roma
Milano
Milano
Milano
Milano
Impiegato  Sede
Progetto  Sede
Impiegato Progetto
Rossi
Marte
Verdi
Giove
Verdi
Venere
Neri
Saturno
Neri
Venere
Supponiamo di voler inserire una nuova tupla che specifica la
partecipazione dell'impiegato Neri, che opera a Milano, al progetto
Marte
Conservazione delle dipendenze
Impiegato
Rossi
Verdi
Neri
Neri
Impiegato Progetto
Rossi
Marte
Verdi
Giove
Verdi
Venere
Neri
Saturno
Neri
Venere
Sede
Roma
Milano
Milano
Milano
Neri
Impiegato Progetto
Rossi
Marte
Verdi
Giove
Verdi
Venere
Neri
Saturno
Neri
Venere
Neri
Marte
Progetto  Sede non è conservata
Marte
Sede
Roma
Milano
Milano
Milano
Milano
Milano
Qualità di una decomposizione
Quindi, una decomposizione deve soddisfare le proprietà di
decomposizione senza perdita e di conservazione delle
dipendenze.
• La decomposizione senza perdita garantisce che le informazioni
nella relazione originaria siano ricostruibili con precisione a partire
da quelle decomposte. In questo caso la stessa interrogazione dà
gli stessi risultati sulla relazione originaria e su quelle decomposte.
• La conservazione delle dipendenze garantisce che le relazioni
decomposte rappresentano i vincoli di integrità quelle originarie.
Ogni aggiornamento (non) valido su quella originaria corrisponde a
un aggiornamento (non) valido su quelle decomposte. Queste
possono accettare anche aggiornamenti leciti impossibili su quella
originaria, a causa delle anomalie rimosse con la decomposizione.
Una relazione non-normalizzata
Dirigente Progetto
Rossi
Marte
Verdi
Giove
Verdi
Marte
Neri
Saturno
Neri
Venere
Sede
Roma
Milano
Milano
Milano
Milano
Progetto Sede  Dirigente
Dirigente  Sede
La decomposizione è problematica
Progetto Sede  Dirigente coinvolge tutti gli attributi e quindi
nessuna decomposizione può preservare tale dipendenza
Quindi in alcuni casi la forma normale di Boyce & Codd “non è
raggiungibile”
Terza forma normale
Esistono schemi che violano la forma normale di Boyce e Codd
che non sono decomponibili ai fini della normalizzazione.
Es. se è presente una dipendenza funzionale in cui un membro
sinistro non è superchiave o se una dipendenza funzionale
coinvolge già tutti gli attributi e quindi non è decomponibile
conservando le dipendenze.
In questi casi si ammette una condizione meno restrittiva, che a
sua volta non ammette ridondanze o anomalie pur ammettendo
situazioni come quelle viste sopra.
Tale condizione si chiama terza forma normale.
Terza forma normale
Si dice che una relazione r è in terza forma normale se, per ogni
dipendenza funzionale X -> Y definita su di essa è verificata
almeno una delle seguenti condizioni:
• X contiene una chiave K di r
• ogni attributo in Y è contenuto in almeno una chiave di r
La terza forma normale è meno forte della forma normale di Boyce
e Codd ma è sempre ottenibile.
Uno schema non decomponibile in BCNF
Dirigente Progetto
Rossi
Marte
Verdi
Giove
Verdi
Marte
Neri
Saturno
Neri
Venere
Sede
Roma
Milano
Milano
Milano
Milano
Dirigente  Sede
Progetto Sede  Dirigente
Una possibile riorganizzazione
Dirigente Progetto
Rossi
Marte
Verdi
Giove
Verdi
Marte
Neri
Saturno
Neri
Venere
Sede
Roma
Milano
Milano
Milano
Milano
Reparto
1
1
1
2
2
Dirigente  Sede Reparto
Sede Reparto  Dirigente
Progetto Sede  Reparto
Decomposizione in BCNF
Dirigente
Rossi
Verdi
Neri
Sede Reparto
Roma
1
Milano
1
Milano
2
Progetto
Marte
Giove
Marte
Saturno
Venere
Sede Reparto
Roma
1
Milano
1
Milano
1
Milano
2
Milano
2
Progettazione e normalizzazione
• la teoria della normalizzazione può essere usata
nella progettazione logica per verificare lo schema
relazionale finale
• si può usare anche durante la progettazione
concettuale per verificare la qualità dello schema
concettuale
Nome
fornitore
Codice
Nome
prodotto
Indirizzo
Prodotto
Partita
IVA
Prezzo
PartitaIVA  NomeFornitore Indirizzo
Analisi dell’entità
– L’entità viola la terza forma normale a causa
della dipendenza:
PartitaIVA  NomeFornitore Indirizzo
– Possiamo decomporre sulla base di questa
dipendenza
Nome
prodotto
Partita Nome
IVA fornitore
Codice
(1,1)
Prodotto
Prezzo
(0,N)
Fornitura
Fornitore
Indirizzo
Dipartimento
(0,N)
(0,N)
Professore
(0,1)
Studente
Tesi
(0,N)
Corso di
laurea
Studente  Corso di laurea
Studente  Professore
Professore  Dipartimento
Analisi della relationship
• La relationship viola la terza forma normale a
causa della dipendenza:
Professore  Dipartimento
• Possiamo decomporre sulla base di questa
dipendenza
(0,N)
Afferenza
(1,1)
Professore
Dipartimento
(0,N)
(0,1)
Tesi
(0,N)
Corso di
laurea
Studente
Ulteriore analisi sulla base delle
dipendenze
• La relationship Tesi è in BCNF sulla base delle
dipendenze
Studente  CorsoDiLaurea
Studente  Professore
• le due proprietà sono indipendenti
• questo suggerisce una ulteriore decomposizione
(0,N)
Professore
(0,1)
Tesi
Studente
(1,1)
(1,1)
(0,N)
Afferenza
(0,N)
Dipartimento
Corso di
laurea
Iscrizione
(0,N)
Corso di
laurea