La Normalizzazione di Schemi Relazionali

La Normalizzazione di Schemi
Relazionali
Normalizzazione di schemi
relazionali
1
Introduzione
 La teoria della normalizzazione si occupa dei
seguenti problemi su schemi relazionali:



Definire quando due schemi sono equivalenti (pb. della
rappresentazione)
Definire criteri di bontà per schemi (=>forme normali)
Determinare metodi algoritmici per ottenere uno
schema “migliore” ed equivalente a partire da uno
schema non in forma normale (=> normalizzazione)
Normalizzazione di schemi relazionali
2
TEORIA RELAZIONALE:
INTRODUZIONE
 Tre metodi per produrre uno schema
relazionale:
a) Partire da un buon schema E-R e tradurlo
b) Costruire direttamente le relazioni e poi
correggere quelle che presentano “anomalie”
c) Partire da uno schema relazionale fatto da altri e
modificarlo o completarlo
Normalizzazione di schemi relazionali
3
Teoria della progettazione
relazionale
 Studia cosa sono le “anomalie” e come eliminarle.
 È particolarmente utile se si usano i metodi (c) o (b).
È moderatamente utile anche quando si usa il
metodo (a).
 Una forma normale è una proprietà di uno
schema relazionale che ne garantisce la
“qualità”, cioè l’assenza di determinati difetti
Normalizzazione di schemi relazionali
4
 L’attività che permette di trasformare schemi
non normalizzati in schemi che soddisfano
una forma normale è detta normalizzazione
 La normalizzazione va utilizzata come
tecnica di verifica dei risultati della
progettazione di una base di dati
 Non costituisce quindi una metodologia di
progettazione
Normalizzazione di schemi relazionali
5
ANOMALIE
Normalizzazione di schemi relazionali
6
OSSERVAZIONI
1.Lo stipendio di ciascun impiegato è unico ed è
funzione del solo impiegato, indipendentemente
dai progetti cui partecipa
Impiegato  Stipendio
2.Il bilancio di ciascun progetto è unico e dipende
solo dal progetto, indipendentemente dagli
impiegati che vi partecipano
Progetto  Bilancio
Normalizzazione di schemi relazionali
7
ANOMALIE NELLA BASE DI
DATI (1)
Il valore dello stipendio di ciascun impiegato è ripetuto
in tutte le n-uple relative a esso: si ha quindi
ridondanza
Normalizzazione di schemi relazionali
8
ANOMALIE NELLA BASE DI
DATI (2)
Se lo stipendio di un impiegato varia, si deve andare
a modificarne il contenuto in tutte le n-uple
corrispondenti affinchè la dipendenza continui a
valere: anomalia di aggiornamento
Normalizzazione di schemi relazionali
9
ANOMALIE NELLA BASE DI
DATI (3)
Se un impiegato interrompe la partecipazione a tutti i
progetti senza lasciare l’azienda, si eliminano tutte le nuple corrispondenti, e quindi ogni traccia del suo nome
e del suo stipendio, dati che potrebbero essere di
interesse: anomalia di cancellazione
Normalizzazione di schemi relazionali
10
ANOMALIE NELLA BASE DI
DATI (4)
Se si hanno informazioni su un nuovo impiegato, non
è possibile inserirle fino a che a questi non viene
assegnato un progetto: anomalia di inserimento
Normalizzazione di schemi relazionali
11
Analizziamo la relazione…
 Ogni impiegato ha un solo stipendio (anche se
partecipa a più progetti)
 Ogni progetto ha un (solo) bilancio
 Ogni impiegato in ciascun progetto ha una sola
funzione (anche se può avere funzioni diverse in
progetti diversi)
 Ma abbiamo usato un’unica relazione per rappresentare
tutte queste informazioni eterogenee:



gli impiegati con i relativi stipendi
i progetti con i relativi bilanci
le partecipazioni degli impiegati ai progetti con le relative
Normalizzazione di schemi relazionali
12
funzioni
Schemi con anomalie
Normalizzazione di schemi relazionali
13
 Quali sono le differenze tra il primo e il
secondo schema di base di dati?
 Certe relazioni presentano difetti dovuti al
fatto che riuniscono concetti tra loro
disomogenei
Normalizzazione di schemi relazionali
14
Una inutile decomposizione
Normalizzazione di schemi relazionali
15
Ipotesi dello schema di relazione
universale
 Le informazioni da memorizzare in una base di dati sono
descrivibili per mezzo di attributi di un’unica relazione
(relazione universale), cioè
Gli attributi con lo stesso nome in relazioni diverse
hanno lo stesso significato e sono definiti sullo
stesso dominio
 Es. Per riferirci alle date di nascita e di assunzione degli
impiegati di una ditta, non possiamo usare due attributi Data
anche in relazioni diverse, dobbiamo usare due nomi diversi
(es. DataNascita e DataAssunzione)
Normalizzazione di schemi relazionali
16
DIPENDENZE FUNZIONALI
 Per formalizzare la nozione di schema senza
anomalie, occorre una descrizione formale della
semantica dei fatti rappresentati in uno schema
relazionale.
 Istanza valida di R: è una nozione semantica, che
dipende da ciò che sappiamo del dominio del
discorso
Normalizzazione di schemi relazionali
17
DIPENDENZE FUNZIONALI
Dato uno schema R(T) e X, Y T, una dipendenza
funzionale (DF) è un vincolo su R del tipo X Y,
i.e. X determina funzionalmente Y o Y è determinato
da X, se
per ogni istanza valida di R un valore di X determina
in modo univoco un valore di Y, ovvero
r istanza valida di R, t1, t2 r
t1[X] = t2[X]
t1[Y] = t2[Y]
Normalizzazione di schemi relazionali
18
ESEMPIO
 Librerie(CodiceLibro, NomeNegozio,
IndNegozio, Titolo, Autore, Quantità)
 DF:
{ CodiceLibro Titolo, Autore
NomeNegozio IndNegozio
CodiceLibro, NomeNegozio
Titolo, Quantità, Autore }
Normalizzazione di schemi relazionali
IndNegozio,
19
Una istanza r0 di R soddisfa la DF X
r0  X Y
t1, t2
Y
sse
r0 se t1[X] = t2[X] allora t1[Y] = t2[Y]
Una istanza r0 di R soddisfa un insieme F di DF se
X Y F, vale r0  X Y
Normalizzazione di schemi relazionali
20
Osservazioni
 Le dipendenze funzionali sono definite all'interno di uno
schema di relazione, e non possono esistere tra attributi
appartenenti a relazioni diverse
 Le DF sono una proprietà:


semantica, cioè dipendono dai fatti rappresentati e
non da come gli attributi sono combinati in schemi di
relazione
intensionale, cioè sono legate al significato dei fatti
che rappresentano, e non alle istanze
Normalizzazione di schemi relazionali
21
DIPENDENZE FUNZIONALI
 Notazione:
 R <T, F> denota uno schema con
T
insieme di attributi
F insieme di dipendenze funzionali
Normalizzazione di schemi relazionali
22
PROPRIETA’
 Se X è una superchiave, allora X determina ogni
altro attributo della relazione:

Per ogni istanza valida r0 di R, YT
 r0  X
Y
 r0  X
T
 Se X è un insieme di attributi di R tale che per ogni
istanza valida r0 di R, r0  X T allora X è
superchiave
Normalizzazione di schemi relazionali
23
PROPRIETÀ DELLE DF
Da un insieme F di DF, in generale altre DF sono
„implicate‟ da F.
 Definizione: Sia F un insieme di DF sullo schema R,
diremo che F implica logicamente X Y
FX
Y
se ogni istanza r di R che soddisfa F soddisfa anche
X Y.
Normalizzazione di schemi relazionali
24
ESEMPIO

Sia R<T, F>,
F = {X
 X, Y, Z


Y, X
T.
Z}
Altre DF sono soddisfatte da R, ad es.
Per ogni X’ X, F  X X’ ( DF banale)
 FX
YZ, infatti sia r un’istanza valida di R, t1,t2
t1[X] = t2[X] t1[Y] = t2[Y]
t1[X] = t2[X] t1[Z] = t2[Z]
t1[X] = t2[X] t1[YZ] = t2[YZ]
{X Y, X Z}  X YZ

Normalizzazione di schemi relazionali
r
25
REGOLE DI INFERENZA
 Altro esempio: {X Y, Y Z}  X Z
 Alcune regole di inferenza valgono:
{X Y, X Z}  X YZ
{}X X
 Come derivare tutte le DF implicate
logicamente da un insieme F, usando un
insieme di regole di inferenza?
Normalizzazione di schemi relazionali
26
ASSIOMI DI ARMSTRONG
 “Assiomi” di Armstrong (sono in realtà regole di
inferenza):
Se Y X, allora X Y (Riflessività R )
 Se X
Y, Z T, allora XZ YZ
(Arricchimento A)
 Se X
Y, Y Z, allora X Z
(Transitività T)

Normalizzazione di schemi relazionali
27
DERIVABILITA’
Sia RI un insieme di regole di inferenza:
FXY
X  Y è derivabile da F usando le regole di RI, se:
esiste una sequenza finita f1, …, fmdi dipendenze,con
XY
 ogni fi è un elemento di F oppure è ottenuto dalle
precedenti dipendenze f1, …, fi-1 usando una regola di
inferenza
 f m=
Normalizzazione di schemi relazionali
28
 Ogni sottosequenza f1, …, fk-1 è una derivazione,
F  fk
k=1,… ,m
 RI è COMPLETO se
F  X  Y implica che F  X  Y
 RI è CORRETTO se
F  X  Y implica che F  X  Y
Normalizzazione di schemi relazionali
29
DERIVAZIONE
 Si dimostra che a partire dagli assiomi di
Armstrong si derivano altre regole:
{X Y, X Z}  X
Z
Y {X Y}  X
 {X
Y}  XZ Y
{ }  X
X

YZ (unione U)
Z (decomposizione D)
(indebolimento I)
(identità ID)
Normalizzazione di schemi relazionali
30
 Unione U:
1. X
Y
2. X
XY
3. X
Z
4. XY
YZ
5. X
YZ
(per ipotesi)
(per arricchimento da 1.)
(per ipotesi)
(per arricchimento da 3.)
(per transitività da 2.,4.)
 Per esercizio dimostrare le altre proprietà
Normalizzazione di schemi relazionali
31
CHIUSURA DI UN INSIEME
 Definizione. Dato R<T, F>, e X T, la
chiusura X, denotata con X+, è
X+ = {Ai T | F  X Ai}
 Proposizione. Siano X ,Y T,
F  X Y se e solo se Y
Normalizzazione di schemi relazionali
X+
32
 Es. R(A B C D), F = {A




B, BC
D}
(A)+= {A,B}
(BC)+= {B,C,D}
(AD)+= {A,B,D}
(AC)+= {A,B,C,D}
Normalizzazione di schemi relazionali
33
CORRETTEZZA E COMPLETEZZA
DEGLI ASSIOMI DI ARMSTRONG
Teorema. Gli assiomi di Armstrong sono corretti e
completi.
 Correttezza degli assiomi:
X Y,
F X
Y
FX
Y
 Corretto: usando gli assiomi non si possono dedurre da F
dipendenze che non sono in implicate logicamente da F
Normalizzazione di schemi relazionali
34
Dimostrazione della correttezza
Per induzione sulla lunghezza della derivazione di
X Y da F,
f1, …, fm,
fm= X  Y
m=1 vale banalmente
m>1 per ipotesi induttiva il teorema vale per ogni
derivazione di lunghezza minore di m
Normalizzazione di schemi relazionali
35
 CASO 1: fm= X  Y F; in questo caso F  X Y;
 CASO 2: X  Y è stato derivato usando un assioma:
 Riflessività: YX, allora F  X
Y;
 Arricchimento: esistono X’, Y’ tali che X= X’Z, Y= Y’Z
e per un certo i < m si ha F  X’ Y’.
Sia r una istanza valida di R, e t, t’  r tali che:
t[X]=t’[X]
allora t[X’]=t’[X’], t[Y’]=t’[Y’], e t[Y’Z]=t’[Y’Z].
 Transitività: esiste W, esistono i,j < m t. c. fi=X
W,
fj=W Y, con F  X W e F  W Y;
per ogni r istanza valida r di R, per ogni t, t’  r,
t[X]=t’[X] implica t[W]=t’[W],
t[W]=t’[W] implica t[Y]=t’[Y],
cioè F  X
Y.
 Completezza degli assiomi:
X
Y,
FX
Y
FX
Y
 completo se dato un insieme F di
dipendenze le regole di inferenza permettono
di dedurre tutte le dipendenze in che sono
implicate logicamente da F.
Normalizzazione di schemi relazionali
37
Un lemma ausiliario

Lemma: sia r una istanza di R su T, r={t,t’}
 t[X+]=t’[X+]
 t[A] t’[A] se AX+
Allora r soddisfa F.
Dim. Sia V
W una dipendenza di F.
 se V X+ allora t[V] t’[V] allora r soddisfa a vuoto la
dipendenza V
W
Normalizzazione di schemi relazionali
38


se V X+ allora F  X V, e F  V
per transitività F  X
W;
allora W X+ e t[W]=t’[W].
Sia F  X Y; l’istanza r  X
precedente.
W per Hp., e
Y per lemma
Dato che XX+,
 allora t[X]=t’[X],
+
 allora t[Y]=t’[Y], dunque Y X
FX
Y
Normalizzazione di schemi relazionali
39
 Conseguenze: Dato X T,
X+ = {Ai T | F  X
Ai}.
Per determinare la chiusura di X basta
applicare in maniera esaustiva le regole di
inferenza alle dipendenze di F
Normalizzazione di schemi relazionali
40
ESEMPIO
 R(A B C D), F = {A B, BC D}
 AC è una superchiave? Cioè F  AC ABCD?
1. A B data
2. AC BC
3. BC D data
4. BC BCD
5. AC BCD
6. AC ABCD
da 1. e A
da 3. e A
da 2., 4. e T
da 5. e A
Normalizzazione di schemi relazionali
41
Chiusura di un insieme di
dipendenze
 F+ indica l’insieme di tutte le dipendenze
funzionali derivabili da F
 Definizione Dato un insieme F di DF, la
chiusura di F, denotata con F+, è:
F+ = { X
Y |FX
Normalizzazione di schemi relazionali
Y}
42
Problema dell’implicazione
 Problema dell’implicazione: controllare se una DF
V W F+.
 Soluzione banale: generare F+: applicare ad F
ricorsivamente tutti gli assiomi di Armstrong.

Questo algoritmo ha complessità esponenziale negli attributi
dello schema:
Se |T| =a, allora F+ contiene almeno le 2a-1 dipendenze
banali del tipo TX, con X T, X non vuoto.
Normalizzazione di schemi relazionali
43
CHIUSURA LENTA
 Chiusura lenta: Un algoritmo efficiente per
risolvere il problema dell’implicazione senza
calcolare la chiusura di F.
 Per decidere se X Y F+ basta controllare se Y
X+ e si ha un semplice algoritmo per calcolare X+.
Normalizzazione di schemi relazionali
44
ALGORITMO DI CHIUSURA
LENTA
 Algoritmo CHIUSURA LENTA
input
R<T, F> X T
output XPIU
begin
XPIU := X
while (XPIU cambia) do
for W V in F with W XPIU and V
do XPIU = XPIU V
end
Normalizzazione di schemi relazionali
XPIU
45
CORRETTEZZA DI
CHIUSURA LENTA
 Teorema: L’algoritmo CHIUSURA LENTA
è corretto, ovvero:
XPIU = X+
(dimostrazione omessa)
Normalizzazione di schemi relazionali
46
ESEMPIO
F = {DB
E, B
C, A
B}, trovare (AD)+
XPIU = AD
XPIU = AD B =ADB
XPIU = ADB E = ABDE
XPIU = ADBE C = ABCDE = (AD)+ = T
(AD) è una superchiave
Normalizzazione di schemi relazionali
47
ESERCIZIO
T={A, B, C, D, E, G, H, I}
F={ADG GI, ACH ADG, BC
AD, CE ACH}
Trovare (BC)+, (BCG)+, (BCE)+
Normalizzazione di schemi relazionali
48
COMPLESSITA’ DI CHIUSURA
LENTA
 Sia a il numero degli attributi di T e p il numero
delle dipendenze funzionali in F.
- il ciclo while viene eseguito p volte e al più a
volte;
- il test di contenuto tra due insiemi ordinati di
a elementi costa a;
- il ciclo interno di for viene eseguito al più
p volte;
Normalizzazione di schemi relazionali
49
 Il costo in tempo dell’Algoritmo CHIUSURA
LENTA è allora nel caso peggiore:
O(ap mina,p)
 CHIUSURA LENTA è semplice ma non efficiente
 Esiste un algoritmo più complesso ma più
efficiente:
O(ap)
Normalizzazione di schemi relazionali
50
CHIAVI E ATTRIBUTI PRIMI
 Definizione Dato lo schema R<T, F>, diremo
che W T è una chiave di R se
1. W
T F+
(W superchiave)
V W, V T F+
(V non superchiave)
 Attributo primo: attributo che appartiene ad
almeno una chiave (altrimenti è non primo)
Normalizzazione di schemi relazionali
51
COMPLESSITA’
Il problema di trovare tutte le chiavi di una
relazione richiede un algoritmo di
complessità esponenziale nel caso peggiore
 Il problema di controllare se un attributo è
primo è NP-completo

Normalizzazione di schemi relazionali
52
ESERCIZIO
 R(A,B,C,D,E). F = {EC D, AB E, E AB}.
 Trovare tutte le chiavi di R.
Osservazione: ogni attributo che non compare nella
parte destra di alcuna dipendenza non banale fa
parte di tutte le chiavi di R.



Allora fa C parte di ogni chiave
C non è chiave
Si considerano AC, CB, CD, CE
Normalizzazione di schemi relazionali
53
 (AC)+= {A,C}
 (BC)+= {B,C}
 (CD)+= {C,D}
 (CE)+= {C,E,D,A,B}=T è chiave
 Ci sono altre chiavi?
 Quali sono gli attributi primi?
Normalizzazione di schemi relazionali
54
COPERTURA DI INSIEMI DI DF
 Definizione: Due insiemi di DF, F e G, sullo schema
R sono equivalenti, F G, sse F+ = G+.
 Se F G, allora F è una copertura di G (e G una
copertura di F).
 Nell’esempio R(A,B,C,D,E):
F = {A B, B C, ED AB}
G = {A C, A B, B C, ED A}
sono
equivalenti
Normalizzazione di schemi relazionali
55
 Definizione Sia F un insieme di DF:
1. Data una X
Y F, si dice che X contiene un
attributo estraneo Ai se:
(X – {Ai}) Y F+, cioè F  (X – {Ai}) Y
2. X
Y è una dipendenza ridondante se:
(F – {X Y})+ = F+,
cioè F – {X Y}  X Y
Normalizzazione di schemi relazionali
56
ESEMPIO
 R(A,B,C), F = {AB C, A B, B A }
 B è attributo estraneo in AB C, perchè
C (A)+
 R(A,B,C), F = {A B, B C, A
 A C è dipendenza ridondante
Normalizzazione di schemi relazionali
C}
57
Copertura canonica
F è detta una copertura canonica se:
 la parte destra di ogni DF in F è un unico
attributo;
 non esistono attributi estranei in nessuna
dipendenza di F;
 nessuna dipendenza in F è ridondante.
Normalizzazione di schemi relazionali
58
ESISTENZA DELLA
COPERTURA CANONICA
 Teorema. Per ogni insieme di dipendenze F esiste
una copertura canonica.
 Algoritmo per calcolare una copertura canonica:
1.
2.
3.
Trasformare le dipendenze nella forma X
assumere senza perdita di generalità)
Eliminare gli attributi estranei
Eliminare le dipendenze ridondanti
Normalizzazione di schemi relazionali
A (si può
59
 Input: F
 Output: G copertura canonica di F
begin
G:=F
for each X Y in G with |X|>1 do
Z:=X
for each A in X do
if Y [Z- A ]+ then Z:=Z- A ;
G=(G- X Y )
Z Y
for each f in G do
if f (G- f )+ then G= G- f
end
 Complessità O(a2p2)
 Esempio: F = {AB
copertura canonica.

C, A
B, B
Infatti B è attributo estraneo in AB
{A
C, A
B, B
A}, {B
A}, non è una
C.
C, A
B, B
A}
sono canoniche.
Normalizzazione di schemi relazionali
61
Osservazione
Normalizzazione di schemi relazionali
62
SCHEMI EQUIVALENTI
 Se uno schema presenta anomalie può essere
trasformato in uno schema equivalente “ben fatto”?
 L’approccio da seguire è quello di decomporre lo
schema in schemi più piccoli "equivalenti"
 “equivalente”:(informale) che descrive la medesima
realtà di interesse
 Si deve formalizzare il concetto di equivalenza di
schemi!
Normalizzazione di schemi relazionali
63
DECOMPOSIZIONE DI
SCHEMI
 Definizione Dato uno schema R(T),
= {R1(T1), …, Rk(Tk)}
è una decomposizione di R sse Ti = T.
ES. {Studenti(Matr,Nome), Esami(Matr,Voto)}
decomposizione di:
Esami(Matr,Nome,Voto)
 Non è necessario che gli schemi siano disgiunti
Normalizzazione di schemi relazionali
64
EQUIVALENZA DI SCHEMI
 L'equivalenza tra lo schema originario e
una sua decomposizione è formalizzata in
termini di soddisfacimento di due proprietà,
indipendenti tra loro:
 conservazione dei dati
 conservazione delle dipendenze
Normalizzazione di schemi relazionali
65
CONSERVAZIONE DEI DATI
BIBLIOTECA
NomeUtente
Residenza
RossiCarlo
Carrara
Paoli Luca
Tel
NLibro
Autore
Titolo
Data
75444 XY188A
Boccaccio
Decameron
07-07
Avenza
59729 XY256B
Verga
Novelle
07-08
PaoliMauro
Dogana
66133 XY090C
Petrarca
Canzoniere
01-08
PaoliLaura
Avenza
59729 XY101A
Dante
Vita Nova
05-08
PaoliLuca
Avenza
59729 XY701B
Manzoni
Adelchi
14-01
PaoliLuca
Avenza
59729 XY008C
Moravia
La noia
17-08
NomeUtente Residenza,Tel
NLibro Autore,Titolo
Normalizzazione di schemi relazionali
66
UTENTI=
NomeUtente,Residenza,Tel(BIBLIOTECA)
PRESTITI =
Tel,Nlibro,Autore,Titolo,Data(BIBLIOTECA)
NomeUtente
Residenza
Tel
RossiCarlo
Carrara
75444
Paoli Luca
Avenza
59729
PaoliMauro
Dogana
66133
PaoliLaura
Avenza
59729
Tel
NLibro
Autore
Titolo
Data
75444
XY188A
Boccaccio
Decameron
07-07
59729
XY256B
Verga
Novelle
07-08
66133
XY090C
Petrarca
Canzoniere
01-08
59729
XY101A
Dante
Vita Nova
05-08
59729
XY701B
Manzoni
Adelchi
14-01
59729
XY008C
Moravia
La noia
17-08
Utenti che hanno preso libri in prestito nel mese di gennaio
NomeUtente,Residenza,(UTENTI

NomeUtente
Residenza
Paoli Luca
Avenza
PaoliLaura
Avenza
Data[01-01,31-01]
(PRESTITI))
Questa relazione è errata !
Nella decomposizione si può perdere parte dell'informazione
Normalizzazione di schemi relazionali
68
DECOMPOSIZIONI CHE
PRESERVANO I DATI
 Definizione = {R1(T1), …, Rk(Tk)} è una decomposizione di
R(T) che preserva i dati sse per ogni istanza valida r di R:
r=(
T1
r)  (
T2
r)  … (
Tk r)
 Teorema Se = {R1(T1), …, Rk(Tk)} è una decomposizione di
R(T), allora per ogni istanza r di R:
r
(
T1
r)  (
T2
r)  …  (
Normalizzazione di schemi relazionali
Tk r)
69
DECOMPOSIZIONI CHE
PRESERVANO I DATI
 Definizione = {R1(T1), …, Rk(Tk)} è una decomposizione di
R(T) che preserva i dati sse per ogni istanza valida r di R:
r=(
T1
r)  (
T2
r)  … (
Tk r)
 Teorema Se = {R1(T1), …, Rk(Tk)} è una decomposizione di
R(T), allora per ogni istanza r di R:
 La perdita di informazioni consiste nel fatto che si ottengono
più ennuple di quante ce ne fossero nella relazione originale
r
(
T1
r)  (
T2
r)  …  (
Normalizzazione di schemi relazionali
Tk r)
70
ESEMPIO DI DECOMPOSIZIONE

Sia r qui sotto un’istanza valida di R(ABC):
r=
A
B
C
a1
a2
b
b
c1
c2
Allora la decomposizione {R(AB), R(BC)}
T1
r=
A
a1
B
b
a2
b
T2
non preserva i dati, infatti
r=
T1
r
Normalizzazione di schemi relazionali
B
b
C
c1
b
c2
T2
r r
71
DECOMPOSIZIONI BINARIE
 Teorema Sia R<T, F> uno schema di relazione,
la decomposizione = {R1(T1), R2(T2)} preserva i
dati sse:
T1 T2 T1 F+ oppure T1 T2 T2 F+.
Siano:
T1 T2
T1 F+,
r una istanza valida in R<T, F>
s = ( T1 r)  ( T2 r)
r  s per il teorema precedente;
72
si dimostra che s  r
sia t  s = ( T1 r)  ( T2 r)
u,v r t.c. u[T1 ]= t[T1 ] e v[T2 ]= t[T2 ],
u[T1 T2]=v[T1 T2 ]=t[T1 T2 ]
per Hp. T1 T2 T1 F+,
allora t[T1 ] = u[T1 ] = v[T1 ] e t=v  r.
Normalizzazione di schemi relazionali
73
Per contronominale:
F non implica nè T1 T2
T2.
T1 nè T1
T2
Esiste una istanza r di R(T,F) tale che
r
(
T1
r)  (
T2
r)
Normalizzazione di schemi relazionali
74
Per contronominale:
F non implica nè T1 T2
T2. Siano:
T1 nè T1
T2
T2 )+

W=(T1

Y1 = T1 - W

Y2 = T2 - W
T1
Normalizzazione di schemi relazionali
T1
T2
T2
75
Per contronominale:
F non implica nè T1 T2
T2. Siano:
T1 nè T1
T2
T2 )+
(T1
T2 )+

W=(T1

Y1 = T1 - W

Y2 = T2 - W
Y1
Normalizzazione di schemi relazionali
T1
T2
Y2
76
per ogni Ai
consideriamo
ai,ai' dom(Ai), ai  ai'
costruiamo una istanza r di R<T,F> sugli attributi W Y1
Y2 con due ennuple:
e1[Ai] = ai
ai
se Ai
W
ai '
altrimenti
e2[Ai] =
Normalizzazione di schemi relazionali
77
 r soddisfa ogni dipendenza V Z F
 se V  W allora e1[V]  e2[V] : la dipendenza
è soddisfatta a vuoto;
 se V  W allora e1[V] = e2[V], e V
Z F,
 Z  W, perchè W è chiuso, allora
 e1[Z] = e2[Z].
Normalizzazione di schemi relazionali
78
 Y1 e Y2 sono non vuoti, altrimenti:
Y1 = (T1 T2 )+ - T1 =
(T1 T2 )+ = T1
 dunque T1 r , T2 r hanno 2 ennuple e
( T1 r)  ( T2 r)
contiene 4 ennuple, allora
( T1 r)  ( T2 r)  r
contro l’ipotesi che r preserva i dati
Normalizzazione di schemi relazionali
79
DECOMPOSIZIONE CON
PERDITA
UTENTI(NomeUtente,Residenza,Tel)
PRESTITI(NLibro,Autore,Titolo,Data,Tel)
NomeUtente
NLibro
Residenza,Tel
Autore,Titolo, Data
T1 T2=Tel Non è chiave né per T1 né per T2
Normalizzazione di schemi relazionali
80
DECOMPOSIZIONE
SENZA PERDITA
UTENTI(NomeUtente,Residenza,Tel)
PRESTITI(NLibro,Autore,Titolo,Data,NomeUtente)
NomeUtente
NLibro
Residenza,Tel
Autore,Titolo, Data
T1 T2=NomeUtente
Normalizzazione di schemi relazionali
E'chiave per T1
81
CONSEGUENZE
 se gli attributi comuni della decomposizione sono
chiave per almeno una delle relazioni decomposte,
allora la decomposizione preserva i dati
 se gli attributi comuni della decomposizione
contengono una chiave per almeno una delle
relazioni decomposte (dunque sono superchiave),
allora la decomposizione preserva i dati
Normalizzazione di schemi relazionali
82
PRESERVAZIONE DELLE
DIPENDENZE
Sia R(P,T,C) uno schema di relazione con dipendenze
T
C, C
P: persona
T: telefono
C: casa
P:
r
=
P
p1
p1
p1
T
t1
t2
t3
C
c1
c2
c3
83
PRESERVAZIONE DELLE
DIPENDENZE
Sia R(P,T,C) uno schema di relazione con dipendenze
T
C, C
P: persona
T: telefono
C: casa
P, decomposto come segue
P
p1
p1
p1
T
t1
t2
t3
T
r2 = T2 r = t1
t2
t3
C
c1
c2
c3
r1 =
T1
r=
84
La decomposizione preserva i dati,
T1
T2=T
E'chiave per r2
Non sono preservate le dipendenze, ad esempio C
P,
perchè gli attributi sono finiti in relazioni diverse.
Può causare problemi? Se si vuole inserire il fatto che
la casa c1 ha un nuovo telefono t4 intestato alla
persona p2.
•
Nella R(P,T,C) non si può perchè viola il vincolo C
•
Nella decomposizione si può
Normalizzazione di schemi relazionali
P
85
PROIEZIONE DELLE
DIPENDENZE
 Definizione Dato lo schema R<T, F>, e
T1 T, la proiezione di F su T1 è
+ | X, Y
(F)
=
{X
Y
F
T1}
T1
 Esempio
Sia R(A, B, C) e F={A B, B
{A B, B A}
AB (F)
{A C, C A}
AC (F)
Normalizzazione di schemi relazionali
C, C
A}.
86
Algoritmo per il calcolo di
T1
(F)
INPUT: R(T,F), T1
OUTPUT: Una copertura di T1 (F)
begin
for each Y T1 do
Z:= Y+
output Y
Z T1
end
end
Normalizzazione di schemi relazionali
87
PRESERVAZIONE DELLE
DIPENDENZE
 La nozione di proiezione di un insieme di
dipendenze ci permette di formalizzare
l'equivalenza tra le dipendenze dello schema
originale e quelle degli schemi decomposti
 Definizione Dato lo schema R<T, F>, la
decomposizione = {R1, ..., Rn} preserva le
dipendenze sse l’unione delle dipendenze in
è una copertura di F.
Normalizzazione di schemi relazionali
Ti(F)
88
ESEMPIO
Esempio




R<T, F>,
T= {A, B, C},
F={A B, B C, C
A}.
= {R1(A,B), R2(B,C)} preserva le dipendenze?
(F) = {A B, B

C, C
BC (F) = {B
 AB (F)  BC (F) = {A

AB
}
}
B, B
,B
C, C
}
E' una copertura per F
Normalizzazione di schemi relazionali
89
PRESERVAZIONE DELLE
DIPENDENZE
Teorema Sia = {Ri<Ti, Fi>} una
decomposizione di R<T, F> che preservi le
dipendenze e tale che un Tj sia una
superchiave per R.
Allora la decomposizione preserva i dati.
Normalizzazione di schemi relazionali
90
ESEMPIO
 Telefoni(Prefisso, Numero, Località,
Abbonato, Via),
F = {PN LAV, L P}
 Chiavi: {P,N}, {L,N}
 Si consideri la decomposizione:
= { Telefoni <{N, L, A, V}, {LN A V}>,
Prefisso <{L, P}, {L P}> }
Normalizzazione di schemi relazionali
91
 Preserva dati, perchè
{N, L, A, V}  {L, P} = {L}
chiave per Prefisso
 {N, L, A, V} è superchiave
 Non preserva le dipendenze: PN L non è
deducibile da F1 e F2
 Dunque il viceversa del teorema non vale.
Normalizzazione di schemi relazionali
92
ESEMPIO
 R<T, F>, T= {A, B, C}, F={A B, B C, C A}.
 = {R1(A,B), R2(B,C)} preserva le dipendenze
 (AB)+ = (BC)+ = {A, B, C}, è chiave
 Per il Teorema precedente la decomposizione
preserva i dati
 Evidente dal fatto che {A, B} {B, C} = {B} è
chiave per R2(B,C)
Normalizzazione di schemi relazionali
93
FORME NORMALI
 Se uno schema presenta delle anomalie
esistono algoritmi per trasformare lo schema
in schemi equivalenti senza anomalie:
 Forme normali: proprietà che devono essere
soddisfatte dalle dipendenze fra attributi di
schemi "ben fatti"
Normalizzazione di schemi relazionali
94
Prima forma normale
 Ha un interesse puramente storico
 Richiede che i valori di tutti i domini di una relazione
siano atomici
 E' un vincolo implicito del modello relazionale dei
dati
 Recentemente sono stati introdotti nuovi modelli
relazionali dei dati (modello relazionale esteso,
modelli relazionali a oggetti), che non soddisfano il
vincolo: il valore di un attributo può essere anche un
ennupla o una relazione
Normalizzazione di schemi relazionali
95
Forme normali
 BCNF (Boyce-Codd normal form): La
decomposizione preserva i dati ma non le
dipendenze

L’algoritmo è esponenziale
Elimina
tutte le
anomalie
Mantiene
certe
anomalie
 3NF (terza forma normale): La
decomposizione preserva i dati e le dipendenze

L’algoritmo è polinomiale
Normalizzazione di schemi relazionali
96
Boyce-Codd normal form
Biblioteca(Utente, Residenza, Tel, N_libro,
Autore, Titolo, Data)
Schema con anomalie:
Utente Residenza, Tel
N_libro Autore, Titolo, Data
Ci sono due diverse realtà nel dominio che si
modella
Normalizzazione di schemi relazionali
97
IDEA INFORMALE
 L’idea base della BCNF è che una dipendenza funzionale
A
B su uno schema, in cui A non contiene attributi
estranei, indica che, nel dominio che si modella, esiste una
collezione C di oggetti che sono univocamente identificati
da A.
 Se una relazione ben disegnata contiene A, ci sono 2
possibilità:
1. se la relazione modella la collezione C, allora A deve
essere chiave per la relazione;
2. altrimenti A deve apparire solo come chiave esterna;
Normalizzazione di schemi relazionali
98
BCFN
 Definizione R<T, F> è in BCNF se per ogni X A
F+, con A X (non banale), X è una superchiave.
In realtà non è necessario controllare la chiusura di F.
 Teorema R<T, F> è in BCNF se e solo se per ogni
X A F non banale, X è una superchiave.
Normalizzazione di schemi relazionali
99
BCFN
 Definizione R<T, F> è in BCNF se per ogni X A
F+, con A X (non banale), X è una superchiave.
In realtà non è necessario controllare la chiusura di F.
 Teorema R<T, F>, con F copertura canonica, è in
BCNF se e solo se per ogni dipendenza elementare
X A F, X è una superchiave (e dunque chiave).
Normalizzazione di schemi relazionali
100
ESEMPI
 Docenti(CodiceFiscale, Nome, Dipartimento,
IndirizzoDip)
 Impiegati(Codice, Qualifica, NomeFiglio,
Indirizzo)
 Librerie(CodiceLibro, NomeNegozio, IndNegozio,
Titolo, Quantità)
 Telefoni(Prefisso, Numero, Località, Abbonato,
Via), F = {P N
L A V, L P}
Normalizzazione di schemi relazionali
101
ESEMPIO
studenti(Matricola, Cognome, Nome,Data di
nascita)
esami(Studente, Voto, Corso, Data)
E’ in BCNF
Matricola
Cognome Nome, Data di Nascita
Studente, Corso
Voto
Normalizzazione di schemi relazionali
102
ESEMPIO
docente(Matricola, Cognome, Nome, Corso)
corsi(Codice, Titolo, Docente)
E’ in BCNF
Matricola
Codice
Cognome Nome, Corso
Titolo, Docente
Normalizzazione di schemi relazionali
103
ESEMPIO
 Magazzini(Articolo,Magazzino,Quantità,
Indirizzo) con le dipendenze
Articolo,Magazzino Quantità,
Magazzino Indirizzo
Non è in BCNF
La relazione Magazzini mescola informazioni
relative alle entità che sono identificate dal
campo Magazzino con le informazioni relative
all’entità Articolo
Normalizzazione di schemi relazionali
104
Problemi causati dalla violazione
della BCNF
1. ridondanza:
 per inserire un nuovo articolo in un magazzino già
presente occorre replicare l’indirizzo del magazzino
 se si modifica l’indirizzo di un magazzino questa
modifica va riportata in tutte le ennuple dove è
presente quel magazzino
2. altre anomalie: difficoltà a gestire l’esistenza di
magazzini senza merce
 per inserire un nuovo magazzino è necessario che ci
sia almeno un articolo
Normalizzazione di schemi relazionali
105
NORMALIZZAZIONE
IN SCHEMI BCNF
 Esistono algoritmi (di normalizzazione) per
trasformare schemi relazionali in BCNF
 Sono algoritmi di analisi: si parte da uno schema
R<T,F> contenente tutti gli attributi



si decompone R in R1(X, Y) e R2(W, Z), con XW=T;
si calcolano le proiezioni delle dipend. di R su R1 e R2
su di essi si ripete il procedimento fino a che non si
ottiene uno schema in BCNF.
Normalizzazione di schemi relazionali
106
L’ALGORITMO DI ANALISI
input R<T, F> con F copertura canonica
output = {R1, ..., Rm} decomposizione di R in BCNF e preserva i dati
= {R<T, F>}
begin
while esiste in una Ri<Ti, Fi> non in BCNF per la dipendenza X A
do
Ta = X+
Fa = Ta (Fi)
Tb = Ti – X+ + X
Fb = Tb (Fi)
= – Ri + {Ra<Ta, Fa>, Rb< Tb, Fb >} (Ra, Rb sono nomi nuovi)
end
PROPRIETA’
DELL’ALGORITMO
 L’algoritmo ha complessità esponenziale, a causa
del calcolo delle proiezioni delle dipendenze
funzionali
 Preserva i dati (non si dimostra)
 Non necessariamente preserva le dipendenze
Normalizzazione di schemi relazionali
108
Esempi di decomposizioni
senza perdita di dipendenze
Docenti(CodiceFiscale, Nome, Dipartimento,
IndirizzoDip), {D I ; C
ND}
 R1(Dipartimento,
IndirizzoDip), {D I}
 R2(CodiceFiscale, Nome, Dipartimento), {C
ND}
 Preserva i dati perchè Dipartimento è chiave per
R1
 Preserva le dipendenze
Normalizzazione di schemi relazionali
109
ESEMPIO
Impiegati(Codice, Qualifica, NomeFiglio)
 {C
Q}
 R1(Codice, Qualifica), {C
Q}
 R2(Codice, NomeFiglio)

Normalizzazione di schemi relazionali
110
Deccomposizione che non
preserva le dipendenze
 Telefoni(Prefisso, Numero, Località, Abbonato,Via),
 {Località Prefisso, Prefisso Numero
Località
Abbonato Via}



R1(Località, Prefisso); F1= {Località Prefisso}
R2(Numero, Località, Abbonato, Via); F2= {Numero,
Località Abbonato,Via}
Preserva dati ma non le dipendenze:
Prefisso,Numero Località non è deducibile dalle
dipendenze di F1 e F2.
Normalizzazione di schemi relazionali
111
 Cosa vuole dire “non preserva le dipendenze”?
Non viene impedito di assegnare a due utenti di
due località diverse lo stesso numero e prefisso

R1 = {(Siena, 0577); (Monteriggioni, 0577)}

R2 = {(Siena, 506070, Rossi, Piave),
(Monteriggioni,506070, Bianchi, Isonzo)}
 Le ennuple R1 e R2 non violano nessuno dei
vincoli relativi allo schema decomposto
Normalizzazione di schemi relazionali
112
TERZA FORMA NORMALE
 Vantaggi:


È sempre possibile decomporre un qualsiasi schema in
schemi in 3NF che preservino dati e dipendenze
Tempo polinomiale
 Svantaggi:

E’ meno restrittiva della BCNF: accetta anche schemi
che presentano anomalie
Normalizzazione di schemi relazionali
113
TERZA FORMA NORMALE
 Definizione: R<T, F> è in 3NF se
per ogni X A F+, con A X,
X è una superchiave o A è primo
 La 3FN ammette una dipendenza non banale e nonda-chiave se gli attributi a destra sono primi;
 la BCNF non ammette mai nessuna dipendenza non
banale e non-da-chiave.
Normalizzazione di schemi relazionali
114
 Teorema: R<T, F> è in 3FN se per ogni X
A F non banale, allora X è una superchiave
oppure A è primo.
 Evidentemente se uno schema è in BCNF è
anche in 3NF
Normalizzazione di schemi relazionali
115
ESEMPIO
 Non sono in 3FN (e nemmeno in BCNF)
 Docenti(CodiceFiscale, Nome,
Dipartimento, IndirizzoDip),
C NDI, D
 Impiegati(Codice, Qualifica, NomeFiglio),
C Q
Normalizzazione di schemi relazionali
116
ESEMPIO DI SCHEMI IN 3NF
MA NON BCNF



Telefoni(Prefisso, Numero, Località, Abbonato, Via)
 F = {Prefisso Numero
Località Abbonato Via,
Località Prefisso}
 Chiavi = {PN, LN} P è attributo primo
 P è attributo primo
Ci sono ridondanze?
Esami(Matricola, Telefono, Materia, Voto)
 Matricola Materia
Voto
 Matricola
Telefono
 Telefono
Matricola
 Chiavi: Matricola Materia, Telefono Materia
Normalizzazione di schemi relazionali
117
DEFINIZIONE EQUIVALENTE
 Teorema: R<T, F>, con F copertura canonica è in
3FN se per ogni dipendenza funzionale X A F,
1.X è una superchiave (cioè chiave), oppure
2.A è primo
Normalizzazione di schemi relazionali
118
 Il problema di decidere se uno schema di
relazione è in 3NF è NP-completo (richiede la
conoscenza degli attributi primi)
 Esiste un algoritmo semplice e polinomiale che
permette di decomporre un qualunque schema in
3NF preservando dati e dipendenze
Normalizzazione di schemi relazionali
119
L’ALGORITMO DI SINTESI
Input: R<T, F>, con F copertura canonica
Output: decomposizione = {S1, ..., Sm} di R in 3NF che
preserva i dati e le dipendenze
1. sostituisci in F ogni insieme X
A1,..., X Ah di dipendenze
aventi lo stesso determinante con la dipendenza X A1,...,Ah;
2. per ogni X
Y in F:
1.
2.
metti uno schema con attributi XY in :
le chiavi sono gli attributi di X;
elimina da ogni schema contenuto in un altro schema di ;
4. se la decomposizione non contiene uno schema i cui attributi
sono una superchiave di R, aggiungi un nuovo schema, con
attributi W, con W una chiave di R.
3.
ESEMPIO
Esempio: R A,B,C,D , F= AB C, C D, D B
• le dipendenze sono una copertura canonica;
• Passo 1: le dipendenze sono già in gruppi con lo stesso
determinante;
• Passo 2: produce la decomposizione:
• R1= ABC , con chiave sintetizzata AB, F1= AB
• R2= CD , con chiave sintetizzata C , F2= C D
• R3= DB , con chiave sintetizzata D , F3= D B
C
• Passo 3: non ci sono inclusioni di schemi
• Passo 4: lo schema R1 contiene AC che sono chiave per R
Normalizzazione di schemi relazionali
121
ESEMPIO
Esempio: R A,B,C,D , F= A B, C D
• le dipendenze sono una copertura canonica;
• Passo 1: le dipendenze sono già in gruppi con lo stesso
determinante;
• Passo 2: produce la decomposizione:
• R1= AB , con chiave sintetizzata A,
• R2= CD , con chiave sintetizzata C
• Passo 3: non ci sono inclusioni di schemi
• Passo 4: si aggiunge lo schema R3(AC)
NB. Senza il Passo 4 la decomposizione preserverebbe le
dipendenze ma non
i dati
Normalizzazione di schemi relazionali
122
PRESERVAZIONE DATI E
DIPENDENZE
Teorema 1: Dato uno schema R<T, F>, con F copertura
canonica l’Algoritmo Elementare produce una decomposizione
= {S1, ..., Sm} di R che preserva dati e dipendenze.



L’algoritmo produce una decomposizione: tutti gli attributi di T
appartengono allo schema generato; se ci sono attributi di T che non
partecipano ad alcuna dipendenza, allora fanno parte di ogni chiave di
R, dunque vengono aggiunte nel passo 4.
La decomposizione prodotta preserva le dipendenze perchè per ogni
dipendenza X A esiste uno schema che contiene XA
La decomposizione preserva i dati per un Teorema noto: preserva le
dipendenze e una componente è superchiave (per il passo 4).
Normalizzazione di schemi relazionali
123
• La complessità dell’algoritmo è O(a2p2)
 Teorema 2: Dato uno schema R<T, F>, con F
copertura canonica l’Algoritmo elementare produce
una decomposizione = {S1, ..., Sm} di R in schemi
3NF.
Normalizzazione di schemi relazionali
124
OSSERVAZIONE
 L’algoritmo di decomposizione produce una
decomposizione = {S1, ..., Sm} di R tale che:


preserva dati e dipendenze
ogni Si è in 3NF rispetto alle proiezioni di F su Si,
 ma non fornisce per ogni Si una copertura delle
proiezioni di F su Si, ovvero in genere
+ F+
(F)
Si
i
Normalizzazione di schemi relazionali
125
Esempio
R A,B,C,D , F= AB C, C D, D B
le dipendenze sono una copertura canonica e
l’algoritmo produce una decomposizione con schemi
• R1= ABC , con chiave sintetizzata AB, F1= AB
• R2= CD , con chiave sintetizzata C, F2= C D
• R3= DB , con chiave sintetizzata D, F3= D B
La proiezione delle dipendenze su R1 è AB
B e non AB C
Normalizzazione di schemi relazionali
C
C, C
126
LE DF NON BASTANO
Nome
Bragazzi
Bragazzi
Bragazzi
Bragazzi
Bragazzi
Bragazzi
Fantini
Fantini
Fantini
Figlio
Maurizio
Maurizio
Maurizio
Marcello
Marcello
Marcello
Maria
Maria
Maria
Stipendi
100
120
140
100
120
140
160
180
190
In una base di dati
relazionale ci possono
essere altre anomalie
non imputabili alle
dipendenze funzionali
 la relazione è in BCNF (infatti non ci sono
dipendenze non banali)
 questa anomalia (ridondanza) è dovuta al fatto che
nella relazione si rappresentano proprietà
multivalore indipendenti (Figlio e Stipendio)
 Una ridondanza del genere può essere eliminata
decomponendo la tabella
Normalizzazione di schemi relazionali
128
Stip_Imp
Figli_Imp
Nome
Stipendio
Bragazzi
Bragazzi
100
120
Bragazzi
Fantini
Fantini
140
160
180
Fantini
190
Nome
Figlio
Bragazzi
Maurizio
Bragazzi
Marcello
Fantini
Maria
DIPENDENZE MULTIVALORE
Per eliminare anomalie dovute alla coesistenza di
proprietà multivalore indipendenti:
E’ stata definita una nuova dipendenza tra i dati, dipendenza
multivalore
 E’ stato dato un nuovo insieme di regole di inferenza corretto e
completo per dipendenze funzionali e multivalore
 E’ stata estesa la nozione di decomposizione che preserva i dati e le
dipendenze
 E’ stata definita la quarta forma normale che generalizza la BCNF
 E’ stato dato un algoritmo di normalizzazione di schemi non in
quarta forma normale che generalizza quello visto per BCNF, e ha
le stesse proprietà di conservare i dati ma non le dipendenze

Normalizzazione di schemi relazionali
130