Forma normale di Boyce e Codd
Definizione
Le DF di Dipartimento
Impiegato
Stipendio
Progetto
Bilancio
Funzione
Rossi
20 Marte
2 tecnico
Verdi
35 Giove
15 progettista
Verdi
35 Venere
15 progettista
Neri
55 Venere
15 direttore
Neri
55 Giove
15 consulente
Neri
55 Marte
2 consulente
Mori
48 Marte
2 direttore
Mori
48 Venere
15 progettista
Bianchi
48 Venere
15 progettista
Bianchi
48 Giove
15 direttore
Impiegato  Stipendio
Progetto  Bilancio
Impiegato Progetto  Funzione
2
Impiegato  Stipendio
La Df riporta che lo stipendio di ciascun
impiegato dipende solo dall’impiegato stesso
indipendentemente dai progetti a cui
partecipa e quindi presenta




Ridondanza
Anomalia di aggiornamento
Anomalia di cancellazione
Anomalia di inserimento
3
Progetto  Bilancio
La DF riporta che il bilancio di ciascun
progetto dipende solo dal progetto stesso
indipendentemente dalla partecipazione degli
impiegati ai progetti e quindi presenta




Ridondanza
Anomalia di aggiornamento
Anomalia di cancellazione
Anomalia di inserimento
4
Impiegato Progetto  Funzione
La DF riporta che in ogni progetto ogni impiegato
svolge una ed una sola funzione.
Si noti che, essendo (Impiegato, Progetto) chiave di
Dipartimento




non esistono due tuple con stessa chiave e Funzione
(non esistono ridondanze)
La modifica interviene su una sola tupla
La cancellazione non comporta perdita di informazioni
che potrebbero essere ancora utili
L’inserimento è possibile anche attribuendo valori nulli
agli attributi diversi da Impiegato e Progetto
5
DF ed anomalie
Le anomalie viste si riconducono alla presenza delle DF:


Impiegato → Stipendio
Progetto → Bilancio
Viceversa la FD

Impiegato, Progetto → Funzione
non causa problemi
Le anomalie sono causate dalla presenza di concetti
eterogenei:



proprietà degli impiegati (lo stipendio)
proprietà dei progetti (il bilancio)
proprietà della chiave Impiegato Progetto
6
La causa delle anomalie
Le prime due FD non corrispondono a chiavi e causano
anomalie
La terza FD corrisponde ad una chiave e non causa
anomalie
Impiegato  Stipendio

Impiegato non è chiave
Progetto  Bilancio

Progetto non è chiave
Impiegato Progetto  Funzione

Impiegato Progetto è chiave
7
Forma Normale di Boyce e Codd
Uno relazione r è in forma normale di Boyce e
Codd se:



per ogni dipendenza funzionale (non banale)
X→Y
definita su R(T),
X contiene una chiave K di r
Ossia X è una superchiave di r
8
Normalizzazione
La normalizzazione è il processo di trasformazione
che


data una relazione che non soddisfa una forma
normale
la scompone in altre relazioni che invece soddisfano la
forma normale
Nel caso della forma normale di Boyce e Codd la
trasformazione si basa su un semplice criterio:


Individuazione dei diversi concetti riportati insieme
nella relazione
Decomposizione della relazione in relazioni più
semplici, una per ogni concetto.
9
10
Un esempio di normalizzazione
Impiegato
Stipendio
Impiegato
Progetto
Funzione
Rossi
Marte
tecnico
Verdi
Giove
progettista
Rossi
20
Verdi
Venere
progettista
Progetto
Verdi
35
Neri
Venere
direttore
Marte
2
Neri
55
Neri
Giove
consulente
Giove
15
Mori
48
Neri
Marte
consulente
Venere
15
Bianchi
48
Mori
Marte
direttore
Mori
Venere
progettista
Bianchi
Venere
progettista
Bianchi
Giove
direttore
Bilancio
Non sempre così facile
Impiegato
Progetto
Sede
Rossi
Marte
Roma
Verdi
Giove
Milano
Verdi
Venere
Milano
Neri
Saturno
Milano
Neri
Venere
Milano
Impiegato  Sede
Progetto  Sede
Impiegato
Sede
Progetto
Sede
Rossi
Roma
Marte
Roma
Verdi
Milano
Giove
Milano
Neri
Milano
Saturno
Milano
Venere
Milano
11
Proviamo a ricostruire
Impiegato
Sede
Progetto
Sede
Rossi
Roma
Marte
Roma
Verdi
Milano
Giove
Milano
Neri
Milano
Saturno
Milano
Venere
Milano
Impiegato
Progetto
Sede
Rossi
Marte
Roma
Verdi
Giove
Milano
Verdi
Saturno
Milano
Verdi
Venere
Milano
Neri
Giove
Milano
Neri
Saturno
Milano
Neri
Venere
Milano
Diversa dalla
relazione di
partenza!
12
Decomposizione senza perdita
La decomposizione non deve assolutamente alterare il
contenuto informativo del DB
Si introduce pertanto il seguente requisito

Decomposizione senza perdita (lossless)
 Uno schema R(X) si decompone senza perdita
negli schemi R1(X1) e R2(X2) se, per ogni istanza
legale r su R(X), il join naturale delle proiezioni
di r su X1 e X2 è uguale a r stessa
 X (r)  X (r) = r
1
2
13
Decomposizione senza perdita
Una decomposizione con perdita può generare tuple
spurie
Per decomporre senza perdita è necessario e
sufficiente che il join naturale sia eseguito su una
superchiave di uno dei due sottoschemi, ovvero che
valga X1 ∩ X2 → X1 oppure X1 ∩ X2 → X2

La decomposizione senza perdita è garantita se gli
attributi comuni contengono una chiave per almeno una
delle relazioni decomposte
14
Decomposizione senza perdita
Impiegato
Progetto
Sede
Rossi
Marte
Roma
Verdi
Giove
Milano
Verdi
Venere
Milano
Neri
Saturno
Milano
Neri
Venere
Milano
Impiegato
Sede
Impiegato
Progetto
Rossi
Roma
Rossi
Marte
Verdi
Milano
Verdi
Giove
Neri
Milano
Verdi
Venere
Neri
Saturno
Neri
Venere
15
Un altro problema (1/3)
Supponiamo di voler inserire una nuova
ennupla che specifica la partecipazione
dell'impiegato Neri, che opera a Milano, al
progetto Marte
Ricordiamo che le dipendenze sullo schema
originario sono


Impiegato  Sede
Progetto  Sede
Ossia un impiegato deve operare su una sola
sede e anche i progetti devono insistere su
una sola sede
16
Un altro problema (2/3)
Impiegato
Sede
Impiegato
Progetto
Rossi
Roma
Rossi
Marte
Verdi
Milano
Verdi
Giove
Neri
Milano
Verdi
Venere
Neri
Saturno
Neri
Venere
Neri
Marte
17
Un altro problema (3/3)
Proviamo a ricostruire
Impiegato
Progetto
Sede
Rossi
Marte
Roma
Verdi
Giove
Milano
Verdi
Venere
Milano
Neri
Saturno
Milano
Neri
Venere
Milano
Neri
Marte
Milano
La dipendenza Progetto  Sede non è
preservata
18
Conservazione delle dipendenze
Una istanza legale nello schema decomposto genera
sullo schema ricostruito una soluzione non ammissibile
Ogni singola istanza è (“localmente”) legale, ma il DB
(“globalmente”) non lo è
 Infatti il progetto “Marte” risulta essere assegnato
a due sedi, in violazione del vincolo Progetto 
Sede
Problemi di consistenza dei dati si hanno quando la
decomposizione “separa” gli attributi di una FD. Per
verificare che la FD sia rispettata si rende necessario
far riferimento a entrambe le relazioni.
19
Conservazione delle dipendenze
Una decomposizione preserva le dipendenze se
ciascuna delle dipendenze funzionali dello schema
originario coinvolge attributi che compaiono tutti
insieme in uno degli schemi decomposti

Nell’esempio la dipendenza Progetto  Sede non è
conservata
Se una FD non si preserva diventa più complicato
capire quali sono le modifiche del DB che non
violano la DF stessa
20
Alcune definizioni: attributo primo
Un attributo di uno schema di relazione R è
detto attributo primo di R se esso è membro
di una qualche chiave candidata di R.
Un attributo è detto non primo se non è un
attributo primo, cioè se non è membro di
nessuna chiave candidata.
21
1 Forma Normale
La 1FN è parte integrante della definizione
formale di relazione nel modello relazionale di
base.
La 1FN impone che il dominio di un attributo
comprenda solo valori atomici.
La 1FN non consente quindi di usare attributi
multivalore, composti o una loro qualsiasi
combinazione.
22
2 Forma normale
La 2FN si basa sul concetto di dipendenza funzionale
completa.
Una dipendenza funzionale X->Y è una dipendenza
funzionale completa se la rimozione di un qualsiasi
attributo A da X fa decadere la DF.
Una DF è parziale se è possibile rimuovere da X
attributi senza che essa venga meno.
Uno schema di relazione R è in 2FN se ogni attributo
non primo A di R dipende funzionalmente in modo
completo dalla chiave primaria di R
23
2 Forma normale: considerazioni
Uno schema di relazione è in 2FN se ogni
attributo non primo A di R non è parzialmente
dipendente da nessuna chiave di R.
La verifica comporta l’esame delle DF i cui
attributi della parte sinistra fanno parte
della chiave primaria.
Se la chiave primaria è fatta da un sol
attributo (il che stabilisce che le DF sulla
chiave sono complete) allora lo schema di
relazione è già in 2FN.
24
3 Forma Normale
La 3FN si basa sul concetto di DF transitiva.
Una DF X->Y definita sullo schema di
relazione R è transitiva se esiste un insieme
Z, che non è né chiave candidata né
appartiene ad una chiave di R, per cui valgono
contemporaneamente X->Z e Z->Y
Uno schema di relazione R è in 3FN se
soddisfa la 2FN e nessun attributo non primo
di R dipende in modo transitivo dalla chiave
primaria (definizione originaria di Codd).
25
3 Forma Normale: generalizzazione
Uno schema di relazione R è in 3FN se ogni volta che
sussiste in R una DF non banale
X->A
o X è una superchiave di R
o A è un attributo primo di R
Quindi uno schema di relazione R non è in 3FN quando
viola entrambe le condizioni. Da cui si ricava:
Uno schema di relazione R è in 3FN se ogni
attributo non primo di R è funzionalmente
dipendente in modo completo da ogni chiave
di R e non è dipendente in modo transitivo da
alcuna chiave di R.
26
3FN e BCNF
La forma normale di Boyce e Codd è stata
proposta come una forma più semplice di 3FN
ma difatti è più restrettiva.
Ogni relazione in BCNF è anche in 3FN.
Le relazioni in 3FN non necessariamente sono
in BCFN
27
Ancora anomalie
Lo schema TEL(Prefisso,Numero,Località,Abbonato,Indirizzo)
ha vincoli


Prefisso,Numero → Località,Abbonato, Indirizzo
Località → Prefisso
Lo schema è in 3NF, in quanto Prefisso è primo (non c’è
dipendenza transitiva)
Nella seguente istanza legale l’informazione sul prefisso viene
replicata per ogni abbonato
Prefisso
051
059
051
051
059
Numero
457856
452332
987856
552346
387654
Località
Bologna
Modena
Bologna
Castenaso
Vignola
Abbonato
Rossi
Verdi
Bianchi
Neri
Mori
Indirizzo
Via Roma 8
Via Bari 16
Via Napoli 77
Piazza Borsa 12
Via Piave 65
28
29
Decomposizione in BCNF
Una soluzione consiste nel decomporre lo schema in


NUM_TEL(Numero,Località,Abbonato,Indirizzo)
PREF_TEL(Località, Prefisso)
La decomposizione è lossless perché

(NUM_TEL

PREF_TEL) = TEL
Numero
Località
Abbonato
Indirizzo
Prefisso
Località
457856
Bologna
Rossi
Via Roma 8
051
Bologna
452332
Modena
Verdi
Via Bari 16
059
Modena
987856
Bologna
Bianchi
Via Napoli 77
051
Castenaso
552346
Castenaso
Neri
Piazza Borsa 12
059
Vignola
387654
Vignola
Mori
Via Piave 65
Osservazioni
Benché gli schemi in 3NF non siano esenti da
problemi, tale livello di normalizzazione è
comunemente accettato nella pratica
Nel caso generale, problemi di complessità
computazionale rendono improponibile affrontare
l’attività di normalizzazione mediante tecniche di
“analisi”. Tutti i seguenti problemi sono NPcompleti:



Determinare se un attributo è primo
Verificare se esiste una chiave di grado minore di k
Verificare se uno schema è in 3NF
30
Osservazioni
L’approccio adottato è di tipo costruttivo,
ovvero anziché verificare se uno schema è
al livello di normalizzazione richiesto, si
progettano schemi che siano a tale livello di
normalizzazione.
Qualità di una decomposizione (ottenibile con
algoritmi di normalizzazione):


deve essere senza perdita, per garantire la
ricostruzione delle informazioni originarie
dovrebbe conservare le dipendenze, per
semplificare il mantenimento dei vincoli di
integrità originari
31
Decomposizione in 3NF
L’idea alla base dell’algoritmo che produce una
decomposizione in 3NF è creare una relazione per
ogni gruppo di FD che hanno lo stesso lato sinistro
(determinante) e inserire nello schema
corrispondente gli attributi coinvolti in almeno una
FD del gruppo


Esempio: Se le FD individuate sullo schema
R(ABCDEFG) sono:
 AB→ CD, AB →E, C → F, F → G
si generano gli schemi:
 R1(ABCDE), R2(CF), R3(FG)
32
Decomposizione in 3NF
Se 2 o più determinanti si determinano
reciprocamente, si fondono gli schemi (più
chiavi alternate per lo stesso schema)

Esempio: Se le FD su R(ABCD) sono:
A

→BC, B → A, C →D
si generano gli schemi
 R1(ABC),
R2(CD)
33
Decomposizione in 3NF
Alla fine si verifica che esista uno schema la
cui chiave è anche chiave dello schema
originario (se non esiste lo si crea)

Esempio: Se le FD su R(ABCD) sono:
A

→C, B →D
si generano gli schemi
 R1(AC),
R2(BD), R3(AB)
34
Una limitazione non superabile
Dirigente
Progetto
Sede
Rossi
Marte
Roma
Verdi
Giove
Milano
Verdi
Marte
Milano
Neri
Saturno
Milano
Neri
Venere
Milano
Progetto Sede  Dirigente
Dirigente  Sede
35
Una limitazione non superabile
Nell’esempio la dipendenza
Progetto,SedeDirigente coinvolge tutti gli
attributi e quindi nessuna decomposizione può
preservare tale dipendenza
Quindi, in funzione del pattern di FD,
potrebbe non essere possibile decomporre in
BCNF e preservare le FD
36
In pratica…
Se la relazione non è normalizzata si decompone in
terza forma normale
Si verifica se lo schema ottenuto è anche in BCNF

Si noti che se una relazione ha una sola chiave allora
le due forme normali coincidono
Se uno schema non è in BCNF si hanno 3 alternative:



Si lascia così com’è, gestendo le anomalie residue (se
l’applicazione lo consente)
Si decompone in BCNF, predisponendo opportune
query di verifica (per verificare le dipendenze
originarie vengano violate)
Si cerca di rimodellare la situazione iniziale, al fine di
permettere di ottenere schemi BCNF
37
BCNF e 3a Forma Normale
La terza forma normale è meno restrittiva
della forma normale di Boyce e Codd (e
ammette relazioni con alcune anomalie)
Ha il vantaggio però di essere sempre
“raggiungibile”
38
Uno schema non in BCNF
Dirigente
Progetto
Sede
Rossi
Marte
Roma
Verdi
Giove
Milano
Verdi
Marte
Milano
Neri
Saturno
Milano
Neri
Venere
Milano
Progetto Sede  Dirigente
Dirigente  Sede
39
Una possibile riorganizzazione
Dirigente
Progetto
Sede
Reparto
Rossi
Marte
Roma
1
Verdi
Giove
Milano
1
Verdi
Marte
Milano
1
Neri
Saturno
Milano
2
Neri
Venere
Milano
2
Dirigente  Sede Reparto
Sede Reparto  Dirigente
Progetto Sede  Reparto
40
41
Decomposizione in BCNF
Progetto
Sede
Reparto
Dirigente
Sede
Reparto
Marte
Roma
1
Rossi
Roma
1
Giove
Milano
1
Verdi
Milano
1
Marte
Milano
1
Neri
Milano
2
Saturno
Milano
2
Venere
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
42
Es.: entità non normalizzata
Nome
fornitore
Codice
Nome
prodotto
Indirizzo
Partita
IVA
Prodotto
Prezzo
PartitaIVA  NomeFornitore Indirizzo
43
Analisi dell’entità
L’entità viola la terza forma normale a causa
della dipendenza:

PartitaIVA  NomeFornitore Indirizzo
Possiamo decomporre sulla base di questa
dipendenza
44
45
Decomposizione
Nome
prodotto
Partita
IVA
Codice
(1,1)
Prodotto
Prezzo
Nome
fornitore
(0,N)
Fornitura
Fornitore
Indirizzo
Es.: associazione non normalizzata
Dipartimento
(0,N)
Professore
(0,N)
Tesi
(0,1)
Studente
(0,N)
Corso di
laurea
Studente  Corso di laurea
Studente  Professore
Professore  Dipartimento
46
Analisi dell’associazione
L’ associazione viola la terza forma normale a
causa della dipendenza:

Professore  Dipartimento
Possiamo decomporre sulla base di questa
dipendenza
47
48
Decomposizione
(0,N)
Afferenza
Dipartimento
(1,1)
Professore
(0,N)
Tesi
(0,N)
Corso di
laurea
(0,1)
Studente
Ulteriore analisi sulla base delle
dipendenze
L’associazione Tesi in BCNF sulla base delle
dipendenze


Studente  CorsoDiLaurea
Studente  Professore
Le due proprietà sono indipendenti
Questo suggerisce una ulteriore
decomposizione
49
Ulteriore decomposizione
Professore
(0,N)
Tesi
(0,1)
Studente
(1,1)
(1,1)
Afferenza
Iscrizione
(0,N)
(0,N)
Dipartimento
Corso di
laurea
50
Normalizzazione vs. performances
Potremmo voler utilizzare schemi non
normalizzati per aumentare la performances
Ad es. collegare e mostrare informazioni
memorizzate in due tabelle differenti
richiede il join delle tabelle
51
Normalizzazione vs. performances

Alternativa 1: usare schemi denormalizzati
che contengono gli attributi di entrambe le
relazioni
 accesso
più veloce
 spazio e tempo di esecuzione superiore per
gestire le modifiche
 maggiore sforzo di programmazione per gestire
la ridondanza, con conseguente maggiore
incidenza degli errori di programmazione

Alternativa 2: usare una vista materializzata
 stessi
vantaggi e svantaggi della alternativa 1,
eccetto il maggiore sforzo di programmazione
52
Riferimenti
Atzeni, Ceri, Paraboschi, Torlone – Basi di dati – McGraw-Hill,
1999
Cabibbo, Torlone, Batini – Basi di dati: progetti ed esercizi
svolti – Pitagora editrice, Bologna, 1995
Atzeni, Batini, De Antonellis – Teoria relazionale dei dati –
Boringhieri, Torino, 1985
53