Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Teoria della Normalizzazione
Raffaella Gentilini
December 13, 2011
Raffaella Gentilini Teoria della Normalizzazione 1 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
IntroduzioneMotivationi
Concetti FondamentaliDipendenze FunzionaliChiusura Insieme Dipendenze FunzionaliCopertura Minimale
Forme Normai basate su Dipendenze FunzionaliForma Normale di Boyce-Codd (BCNF)Terza Forma Normale (3NF)
Raffaella Gentilini Teoria della Normalizzazione 2 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Obbiettivi
Sviluppare una metodologia che permetta di:
1. Decidere se uno schema di relazione e’ uno schema di relazione bendefinito
2. Qualora uno schma di relazione R non soddisfi i criteri di bonta’,decomporlo in {R1, . . . ,Rn}, dove :
• ogni Ri sia uno schema di relazione ben definito• non vi sia perdita di informazione
Il nostro approccio e’ basato sui concetti di:
• dipendenze funzionali
Raffaella Gentilini Teoria della Normalizzazione 3 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Obbiettivi
Sviluppare una metodologia che permetta di:
1. Decidere se uno schema di relazione e’ uno schema di relazione bendefinito
2. Qualora uno schma di relazione R non soddisfi i criteri di bonta’,decomporlo in {R1, . . . ,Rn}, dove :
• ogni Ri sia uno schema di relazione ben definito• non vi sia perdita di informazione
Il nostro approccio e’ basato sui concetti di:
• dipendenze funzionali
Raffaella Gentilini Teoria della Normalizzazione 3 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Obbiettivi
Sviluppare una metodologia che permetta di:
1. Decidere se uno schema di relazione e’ uno schema di relazione bendefinito
2. Qualora uno schma di relazione R non soddisfi i criteri di bonta’,decomporlo in {R1, . . . ,Rn}, dove :
• ogni Ri sia uno schema di relazione ben definito
• non vi sia perdita di informazione
Il nostro approccio e’ basato sui concetti di:
• dipendenze funzionali
Raffaella Gentilini Teoria della Normalizzazione 3 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Obbiettivi
Sviluppare una metodologia che permetta di:
1. Decidere se uno schema di relazione e’ uno schema di relazione bendefinito
2. Qualora uno schma di relazione R non soddisfi i criteri di bonta’,decomporlo in {R1, . . . ,Rn}, dove :
• ogni Ri sia uno schema di relazione ben definito• non vi sia perdita di informazione
Il nostro approccio e’ basato sui concetti di:
• dipendenze funzionali
Raffaella Gentilini Teoria della Normalizzazione 3 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Obbiettivi
Sviluppare una metodologia che permetta di:
1. Decidere se uno schema di relazione e’ uno schema di relazione bendefinito
2. Qualora uno schma di relazione R non soddisfi i criteri di bonta’,decomporlo in {R1, . . . ,Rn}, dove :
• ogni Ri sia uno schema di relazione ben definito• non vi sia perdita di informazione
Il nostro approccio e’ basato sui concetti di:
• dipendenze funzionali
Raffaella Gentilini Teoria della Normalizzazione 3 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Obbiettivi
Sviluppare una metodologia che permetta di:
1. Decidere se uno schema di relazione e’ uno schema di relazione bendefinito
2. Qualora uno schma di relazione R non soddisfi i criteri di bonta’,decomporlo in {R1, . . . ,Rn}, dove :
• ogni Ri sia uno schema di relazione ben definito• non vi sia perdita di informazione
Il nostro approccio e’ basato sui concetti di:
• dipendenze funzionali
Raffaella Gentilini Teoria della Normalizzazione 3 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Dipendenze Funzionali
Dipendenze Funzionali
• Generalizzazione del concetto di chiave
• Esprimono vincoli sulla ammissibilita’ delle istanze di relazione
• Stabiliscono vincoli di dipendenza tra attributi:• I valori di alcuni attributi determinino i valori di altri attributi
nelle tuple
Raffaella Gentilini Teoria della Normalizzazione 4 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Dipendenze Funzionali
Dipendenze Funzionali
• Generalizzazione del concetto di chiave
• Esprimono vincoli sulla ammissibilita’ delle istanze di relazione
• Stabiliscono vincoli di dipendenza tra attributi:• I valori di alcuni attributi determinino i valori di altri attributi
nelle tuple
Raffaella Gentilini Teoria della Normalizzazione 4 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Dipendenze Funzionali
Dipendenze Funzionali
• Generalizzazione del concetto di chiave
• Esprimono vincoli sulla ammissibilita’ delle istanze di relazione
• Stabiliscono vincoli di dipendenza tra attributi:• I valori di alcuni attributi determinino i valori di altri attributi
nelle tuple
Raffaella Gentilini Teoria della Normalizzazione 4 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Dipendenze Funzionali
Definition (Dipendenze Funzionali)
Dato lo schema di relazione R sull’insieme di attributi X , si considerinoα ⊆ X e β ⊆ X .La dipendenza funzionale α→ β vale su R
m
Per ogni istanza di r di R:
• Ogni coppia di ennuple t1, t2 di r avente gli stessi valori per gliattributi in α, ha gli stessi valori per gli attributi in β.
Formalmente:
α→ β vale su Rm
∀r istanza di R,∀t1, t2 ∈ r : t1[α] = t2[α]⇒ t1[β] = t2[β]
Raffaella Gentilini Teoria della Normalizzazione 5 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Dipendenze Funzionali
Definition (Dipendenze Funzionali)
Dato lo schema di relazione R sull’insieme di attributi X , si considerinoα ⊆ X e β ⊆ X .La dipendenza funzionale α→ β vale su R
m
Per ogni istanza di r di R:
• Ogni coppia di ennuple t1, t2 di r avente gli stessi valori per gliattributi in α, ha gli stessi valori per gli attributi in β.
Formalmente:
α→ β vale su Rm
∀r istanza di R,∀t1, t2 ∈ r : t1[α] = t2[α]⇒ t1[β] = t2[β]
Raffaella Gentilini Teoria della Normalizzazione 5 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Example
Si consideri la seguente istanza di R dello schema R(A,B):
A B3 41 53 7
• Si osservi che A→ B non vale
Raffaella Gentilini Teoria della Normalizzazione 6 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Dipendenze Funzionali e Chiavi
• K e’ superchiave per R(X ) sse K → X .
• K e’ chiave candidata per R(X ) sse:
• K → X• non esiste K ′ ⊂ K tale che K ′ → X
• dipendenze funzionali permettono di esprimere vincoli nonesprimibili tramite nozione di chiave:
Vendita(nomeCliente, codiceMerce, nomeProduttore, costo)
Dato lo schema sopra, desideriamo valgano le dipendenze:
• codiceMerce → costo
• codiceMerce → produttore
ma non desideriamo che valga:
• codiceMerce → nomeCliente
Raffaella Gentilini Teoria della Normalizzazione 7 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Dipendenze Funzionali e Chiavi
• K e’ superchiave per R(X ) sse K → X .
• K e’ chiave candidata per R(X ) sse:
• K → X• non esiste K ′ ⊂ K tale che K ′ → X
• dipendenze funzionali permettono di esprimere vincoli nonesprimibili tramite nozione di chiave:
Vendita(nomeCliente, codiceMerce, nomeProduttore, costo)
Dato lo schema sopra, desideriamo valgano le dipendenze:
• codiceMerce → costo
• codiceMerce → produttore
ma non desideriamo che valga:
• codiceMerce → nomeCliente
Raffaella Gentilini Teoria della Normalizzazione 7 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Dipendenze Funzionali e Chiavi
• K e’ superchiave per R(X ) sse K → X .
• K e’ chiave candidata per R(X ) sse:
• K → X
• non esiste K ′ ⊂ K tale che K ′ → X
• dipendenze funzionali permettono di esprimere vincoli nonesprimibili tramite nozione di chiave:
Vendita(nomeCliente, codiceMerce, nomeProduttore, costo)
Dato lo schema sopra, desideriamo valgano le dipendenze:
• codiceMerce → costo
• codiceMerce → produttore
ma non desideriamo che valga:
• codiceMerce → nomeCliente
Raffaella Gentilini Teoria della Normalizzazione 7 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Dipendenze Funzionali e Chiavi
• K e’ superchiave per R(X ) sse K → X .
• K e’ chiave candidata per R(X ) sse:
• K → X• non esiste K ′ ⊂ K tale che K ′ → X
• dipendenze funzionali permettono di esprimere vincoli nonesprimibili tramite nozione di chiave:
Vendita(nomeCliente, codiceMerce, nomeProduttore, costo)
Dato lo schema sopra, desideriamo valgano le dipendenze:
• codiceMerce → costo
• codiceMerce → produttore
ma non desideriamo che valga:
• codiceMerce → nomeCliente
Raffaella Gentilini Teoria della Normalizzazione 7 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Dipendenze Funzionali e Chiavi
• K e’ superchiave per R(X ) sse K → X .
• K e’ chiave candidata per R(X ) sse:
• K → X• non esiste K ′ ⊂ K tale che K ′ → X
• dipendenze funzionali permettono di esprimere vincoli nonesprimibili tramite nozione di chiave:
Vendita(nomeCliente, codiceMerce, nomeProduttore, costo)
Dato lo schema sopra, desideriamo valgano le dipendenze:
• codiceMerce → costo
• codiceMerce → produttore
ma non desideriamo che valga:
• codiceMerce → nomeCliente
Raffaella Gentilini Teoria della Normalizzazione 7 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Dipendenze Funzionali e Chiavi
• K e’ superchiave per R(X ) sse K → X .
• K e’ chiave candidata per R(X ) sse:
• K → X• non esiste K ′ ⊂ K tale che K ′ → X
• dipendenze funzionali permettono di esprimere vincoli nonesprimibili tramite nozione di chiave:
Vendita(nomeCliente, codiceMerce, nomeProduttore, costo)
Dato lo schema sopra, desideriamo valgano le dipendenze:
• codiceMerce → costo
• codiceMerce → produttore
ma non desideriamo che valga:
• codiceMerce → nomeClienteRaffaella Gentilini Teoria della Normalizzazione 7 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Chiusura Insieme Dipendenze Funzionali• Dato un insieme F di dipendenze funzionali, vi possono essere altre
dipendenze funzionali logicamente implicate da F .
• Ad esempio, se valgono A→ B e B → C , possimao infereireche vale A→ C
• L’insieme di dipendenze funzionali logicamente implicate da F ,denotato F+, e’ detto chiusura di F
• Possiamo determinare F+ applicando gli assiomi di Armstrong
• Assiomi Armstrong sono insieme regole inferenza corretto (generanosolo DF valide) e completo (generano tutte le DF in F+)
Assiomi di Armstrong
1. se β ⊆ α, allora α→ β (riflessivita’)
2. se α→ β, allora γα→ γβ (arrichimento)
3. se α→ β e β → γ, allora α→ γ (transitivita’)
Raffaella Gentilini Teoria della Normalizzazione 8 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Chiusura Insieme Dipendenze Funzionali• Dato un insieme F di dipendenze funzionali, vi possono essere altre
dipendenze funzionali logicamente implicate da F .
• Ad esempio, se valgono A→ B e B → C , possimao infereireche vale A→ C
• L’insieme di dipendenze funzionali logicamente implicate da F ,denotato F+, e’ detto chiusura di F
• Possiamo determinare F+ applicando gli assiomi di Armstrong
• Assiomi Armstrong sono insieme regole inferenza corretto (generanosolo DF valide) e completo (generano tutte le DF in F+)
Assiomi di Armstrong
1. se β ⊆ α, allora α→ β (riflessivita’)
2. se α→ β, allora γα→ γβ (arrichimento)
3. se α→ β e β → γ, allora α→ γ (transitivita’)Raffaella Gentilini Teoria della Normalizzazione 8 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Example
• R = (A,B,C ,G ,H, I )F = {A→ B,A→ C ,CG → H,CG → I ,B → H}
• Alcuni membri di F+ sono:
• A→ H
• per transitivita’ da A→ B e B → H
• AG → I
• arricchendo A→ C con G e poi utilizzando la transitivita’ conCG → I
• CG → HI
• arricchimento di CG → I con CG per ottenere CG → CGI ,arricchimento di CG → H con I per ottenere CGI → HI , edinfine applicazione della transitivita’.
Raffaella Gentilini Teoria della Normalizzazione 9 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Example
• R = (A,B,C ,G ,H, I )F = {A→ B,A→ C ,CG → H,CG → I ,B → H}
• Alcuni membri di F+ sono:
• A→ H
• per transitivita’ da A→ B e B → H
• AG → I
• arricchendo A→ C con G e poi utilizzando la transitivita’ conCG → I
• CG → HI
• arricchimento di CG → I con CG per ottenere CG → CGI ,arricchimento di CG → H con I per ottenere CGI → HI , edinfine applicazione della transitivita’.
Raffaella Gentilini Teoria della Normalizzazione 9 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Example
• R = (A,B,C ,G ,H, I )F = {A→ B,A→ C ,CG → H,CG → I ,B → H}
• Alcuni membri di F+ sono:
• A→ H• per transitivita’ da A→ B e B → H
• AG → I
• arricchendo A→ C con G e poi utilizzando la transitivita’ conCG → I
• CG → HI
• arricchimento di CG → I con CG per ottenere CG → CGI ,arricchimento di CG → H con I per ottenere CGI → HI , edinfine applicazione della transitivita’.
Raffaella Gentilini Teoria della Normalizzazione 9 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Example
• R = (A,B,C ,G ,H, I )F = {A→ B,A→ C ,CG → H,CG → I ,B → H}
• Alcuni membri di F+ sono:
• A→ H• per transitivita’ da A→ B e B → H
• AG → I• arricchendo A→ C con G e poi utilizzando la transitivita’ con
CG → I
• CG → HI
• arricchimento di CG → I con CG per ottenere CG → CGI ,arricchimento di CG → H con I per ottenere CGI → HI , edinfine applicazione della transitivita’.
Raffaella Gentilini Teoria della Normalizzazione 9 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Example
• R = (A,B,C ,G ,H, I )F = {A→ B,A→ C ,CG → H,CG → I ,B → H}
• Alcuni membri di F+ sono:
• A→ H• per transitivita’ da A→ B e B → H
• AG → I• arricchendo A→ C con G e poi utilizzando la transitivita’ con
CG → I
• CG → HI• arricchimento di CG → I con CG per ottenere CG → CGI ,
arricchimento di CG → H con I per ottenere CGI → HI , edinfine applicazione della transitivita’.
Raffaella Gentilini Teoria della Normalizzazione 9 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Calcolo di F+
Algoritmo per il calcolo della chiusura di un insieme di dipendenzefunzionali F
F+ ← Frepeat
for each dipendenza funzionale f ∈ F+ doapplica riflessivita’ ed arrichimento ad faggiungi ad F+ le dipendenze ottenute
end forfor each coppia di dipendenze funzionali f1, f2 ∈ F+ do
if f1 ed f2 possono essere combinate usando la transitivita’ thenaggiungi ad F+ le dipendenze ottenute
end ifend for
until F+ non cambia
Raffaella Gentilini Teoria della Normalizzazione 10 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Calcolo di F+
Possiamo velocizzare/semplificare il calcolo della chiusura di F+
utilizzando ulteriori regole di inferenza:
• Unione Se valgono α→ β e α→ γ, allora vale α→ βγ
• Decomposizione Se vale α→ βγ, allora valgono α→ β ed α→ γ
• Pseudotransitivita’ Se valgono α→ γ e γβ → δ, allora vale ancheαβ → δ
Esercizio: Ricavare le precedenti regole a partire dagli assiomi di Arm-strong.
Raffaella Gentilini Teoria della Normalizzazione 11 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Calcolo di F+
Possiamo velocizzare/semplificare il calcolo della chiusura di F+
utilizzando ulteriori regole di inferenza:
• Unione Se valgono α→ β e α→ γ, allora vale α→ βγ
• Decomposizione Se vale α→ βγ, allora valgono α→ β ed α→ γ
• Pseudotransitivita’ Se valgono α→ γ e γβ → δ, allora vale ancheαβ → δ
Esercizio: Ricavare le precedenti regole a partire dagli assiomi di Arm-strong.
Raffaella Gentilini Teoria della Normalizzazione 11 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Calcolo di F+
Possiamo velocizzare/semplificare il calcolo della chiusura di F+
utilizzando ulteriori regole di inferenza:
• Unione Se valgono α→ β e α→ γ, allora vale α→ βγ
• Decomposizione Se vale α→ βγ, allora valgono α→ β ed α→ γ
• Pseudotransitivita’ Se valgono α→ γ e γβ → δ, allora vale ancheαβ → δ
Esercizio: Ricavare le precedenti regole a partire dagli assiomi di Arm-strong.
Raffaella Gentilini Teoria della Normalizzazione 11 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Calcolo di F+
Possiamo velocizzare/semplificare il calcolo della chiusura di F+
utilizzando ulteriori regole di inferenza:
• Unione Se valgono α→ β e α→ γ, allora vale α→ βγ
• Decomposizione Se vale α→ βγ, allora valgono α→ β ed α→ γ
• Pseudotransitivita’ Se valgono α→ γ e γβ → δ, allora vale ancheαβ → δ
Esercizio: Ricavare le precedenti regole a partire dagli assiomi di Arm-strong.
Raffaella Gentilini Teoria della Normalizzazione 11 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Calcolo di F+
Possiamo velocizzare/semplificare il calcolo della chiusura di F+
utilizzando ulteriori regole di inferenza:
• Unione Se valgono α→ β e α→ γ, allora vale α→ βγ
• Decomposizione Se vale α→ βγ, allora valgono α→ β ed α→ γ
• Pseudotransitivita’ Se valgono α→ γ e γβ → δ, allora vale ancheαβ → δ
Esercizio: Ricavare le precedenti regole a partire dagli assiomi di Arm-strong.
Raffaella Gentilini Teoria della Normalizzazione 11 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Chiusura di un Insieme di Attributi
Dato un insieme di attributi α, la chiusura di α rispetto ad F (de-notato α+) e’ l’insieme di attributi determinati funzionalmente daattributi in α utilizzando le dipendenze in F .Avremo che:
• αβ ∈ F sse β ⊆ α+
Calcolo di α+ rispetto ad F
α+ ← αwhile ci sono cambiamenti in α+ do
for each β → γ ∈ F doif β ⊆ α+ then
α+ ← α+ ∪ γend if
end forend while
Raffaella Gentilini Teoria della Normalizzazione 12 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Chiusura di un Insieme di Attributi
Dato un insieme di attributi α, la chiusura di α rispetto ad F (de-notato α+) e’ l’insieme di attributi determinati funzionalmente daattributi in α utilizzando le dipendenze in F .Avremo che:
• αβ ∈ F sse β ⊆ α+
Calcolo di α+ rispetto ad F
α+ ← αwhile ci sono cambiamenti in α+ do
for each β → γ ∈ F doif β ⊆ α+ then
α+ ← α+ ∪ γend if
end forend while
Raffaella Gentilini Teoria della Normalizzazione 12 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Example
• R(X ) = (A,B,C ,G ,H, I ), ovvero X = ABCGHI
• F = {A→ B,A→ C ,CG → H,B → H}• Calcolo di CG+ rispetto ad F :
1. AG+ ← AG2. AG+ ← ABCG (da A→ C e A→ B)3. AG+ ← ABCGH (da CG → H e CG ⊆ ABCG )4. AG+ ← ABCGHI (da CG → I e CG ⊆ ABCGH)
Raffaella Gentilini Teoria della Normalizzazione 13 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Usare la chiusura di attributi . . .
Viene sfruttata in diversi contesti:
• per verificare se un insieme di attributi e’ una superchiave.
• α ⊆ X e’ superchiave per R sse α+ contiene tutti gli attributidi R(X ).
• per verificare se vale una dipendenza funzionale.• per verificare se vale α→ β (ovvero se α→ β appartiene ad
F+) basta verificare se β ⊆ α+.
• calcolo della chiusura di F .• per ogni γ ⊆ X , si calcola la chiusura γ+ e per ogni Y ⊆ γ+ si
genera la DF γ → Y .
Raffaella Gentilini Teoria della Normalizzazione 14 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Usare la chiusura di attributi . . .
Viene sfruttata in diversi contesti:
• per verificare se un insieme di attributi e’ una superchiave.
• α ⊆ X e’ superchiave per R sse α+ contiene tutti gli attributidi R(X ).
• per verificare se vale una dipendenza funzionale.• per verificare se vale α→ β (ovvero se α→ β appartiene ad
F+) basta verificare se β ⊆ α+.
• calcolo della chiusura di F .• per ogni γ ⊆ X , si calcola la chiusura γ+ e per ogni Y ⊆ γ+ si
genera la DF γ → Y .
Raffaella Gentilini Teoria della Normalizzazione 14 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Usare la chiusura di attributi . . .
Viene sfruttata in diversi contesti:
• per verificare se un insieme di attributi e’ una superchiave.
• α ⊆ X e’ superchiave per R sse α+ contiene tutti gli attributidi R(X ).
• per verificare se vale una dipendenza funzionale.• per verificare se vale α→ β (ovvero se α→ β appartiene ad
F+) basta verificare se β ⊆ α+.
• calcolo della chiusura di F .• per ogni γ ⊆ X , si calcola la chiusura γ+ e per ogni Y ⊆ γ+ si
genera la DF γ → Y .
Raffaella Gentilini Teoria della Normalizzazione 14 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Usare la chiusura di attributi . . .
Viene sfruttata in diversi contesti:
• per verificare se un insieme di attributi e’ una superchiave.
• α ⊆ X e’ superchiave per R sse α+ contiene tutti gli attributidi R(X ).
• per verificare se vale una dipendenza funzionale.• per verificare se vale α→ β (ovvero se α→ β appartiene ad
F+) basta verificare se β ⊆ α+.
• calcolo della chiusura di F .• per ogni γ ⊆ X , si calcola la chiusura γ+ e per ogni Y ⊆ γ+ si
genera la DF γ → Y .
Raffaella Gentilini Teoria della Normalizzazione 14 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Copertura Minimale
• Un insieme F di dipendenze funzionale puo’ contenere dipendenzeridondanti, ovvero che possono essere ottenute dalle altredipendenze di F
• Esempio: A→ C e’ ridondante in {A→ B,B → C ,A→ C}
• Anche degliattributi di una dipendenza funzionale potrebbero essereridondanti:
• A destra: {A→ B,B → C ,A→ CD} puo’ essere semplificatain {A→ B,B → C ,A→ D}
• A sinistra: {A→ B,B → C ,AC → D} puo’ esseresemplificata in {A→ B,B → C ,A→ D}
• Intuitivamente, una copertura minimale di F e’ un insieme minimaledi dipendenze funzionali equivalenti ad F, privo di dipendenze eattributi ridondanti.
Raffaella Gentilini Teoria della Normalizzazione 15 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Copertura Minimale
Piu’ formalmente, un insieme F di dipendenze funzionali e’ minimale sse:
1. Ogni dipendenza funzionale in F ha come parte destra un soloattributo
2. Non e’ possibile sostituire una dipendenza funzionale α→ A di Fcon una dipendenza funzionale β → A dove β ⊂ α, ed avere ancoraun insieme di dipendenze funzionali equivalente ad F .
3. Non e’ possibile rimuovere una dipendenza funzionale da F e avereancora un insieme di dipendenze funzionali equivalente ad F .
Una copertura minimale di un insieme di dipendenze funzionali F e’ uninsieme minimale di dipendenze funzionali E equivalente ad F .
Raffaella Gentilini Teoria della Normalizzazione 16 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Copertura Minimale
Calcolo di una copertura minimale E per un insieme di DF F .
1. Si imposti E := F
2. Si sostituisca ogni DF X → A1 . . .An in E con le n DFX → A1, . . . ,X → An.
3. Per ogni DF X → A in E , per ogni attributo B in X :
Se B e’ ridondante nella DF X → A, ovvero se E e’ equivalente a(E \ {X → A}) ∪ {(X \ {B} → A}, allora si sostituisca X → A conX \ {B} → A in E
4. Per ogni DF rimanente X → A: Se E \ {X → A} e’ equivalente adE , allora si rimuova X → A da E .
Raffaella Gentilini Teoria della Normalizzazione 17 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Copertura Minimale
Come verificare ridondanza attributi?
• Sia F un insieme di DF. Consideriamo la DF X → Y in F el’attributo B ∈ X .
• Per verificare se B ∈ X e’ ridondante:
• Calcoliamo la chiusura (X \ {B})+ rispetto ad F• Verifichiamo se (X \ {B})+ contiene Y• Se si’, allora B e’ ridondante (e puo’ essere eliminato).
Raffaella Gentilini Teoria della Normalizzazione 18 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Copertura Minimale
Come verificare ridondanza attributi?
• Sia F un insieme di DF. Consideriamo la DF X → Y in F el’attributo B ∈ X .
• Per verificare se B ∈ X e’ ridondante:
• Calcoliamo la chiusura (X \ {B})+ rispetto ad F
• Verifichiamo se (X \ {B})+ contiene Y• Se si’, allora B e’ ridondante (e puo’ essere eliminato).
Raffaella Gentilini Teoria della Normalizzazione 18 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Copertura Minimale
Come verificare ridondanza attributi?
• Sia F un insieme di DF. Consideriamo la DF X → Y in F el’attributo B ∈ X .
• Per verificare se B ∈ X e’ ridondante:
• Calcoliamo la chiusura (X \ {B})+ rispetto ad F• Verifichiamo se (X \ {B})+ contiene Y
• Se si’, allora B e’ ridondante (e puo’ essere eliminato).
Raffaella Gentilini Teoria della Normalizzazione 18 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Copertura Minimale
Come verificare ridondanza attributi?
• Sia F un insieme di DF. Consideriamo la DF X → Y in F el’attributo B ∈ X .
• Per verificare se B ∈ X e’ ridondante:
• Calcoliamo la chiusura (X \ {B})+ rispetto ad F• Verifichiamo se (X \ {B})+ contiene Y• Se si’, allora B e’ ridondante (e puo’ essere eliminato).
Raffaella Gentilini Teoria della Normalizzazione 18 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Example
• R = (A,B,C )
• F = {A→ BC ,B → C ,A→ B,AB → C}
• Dopo l’esecuzione del passo (2) dell’algoritmo si ha:
E = {A→ B,A→ C ,B → C ,AB → C}• Eseguiamo il passo (3). A e’ ridondante in AB → C ?
• Verifichiamo se la chiusura di B rispetto ad E contiene C
• Si: Infatti B+ = {B,C}. Dunque E diventaE = {A→ B,A→ C ,B → C}
• Eseguiamo il passo (4):
• A→ C e’ implicata logicamente da A→ B,B → C (pertransitivita’). Dunque E diventa E = {A→ B,B → C}.
• Una copertura canonica (o minimale) e’:
E = {A→ B,B → C}
Raffaella Gentilini Teoria della Normalizzazione 19 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Example
• R = (A,B,C )
• F = {A→ BC ,B → C ,A→ B,AB → C}• Dopo l’esecuzione del passo (2) dell’algoritmo si ha:
E = {A→ B,A→ C ,B → C ,AB → C}
• Eseguiamo il passo (3). A e’ ridondante in AB → C ?• Verifichiamo se la chiusura di B rispetto ad E contiene C
• Si: Infatti B+ = {B,C}. Dunque E diventaE = {A→ B,A→ C ,B → C}
• Eseguiamo il passo (4):
• A→ C e’ implicata logicamente da A→ B,B → C (pertransitivita’). Dunque E diventa E = {A→ B,B → C}.
• Una copertura canonica (o minimale) e’:
E = {A→ B,B → C}
Raffaella Gentilini Teoria della Normalizzazione 19 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Example
• R = (A,B,C )
• F = {A→ BC ,B → C ,A→ B,AB → C}• Dopo l’esecuzione del passo (2) dell’algoritmo si ha:
E = {A→ B,A→ C ,B → C ,AB → C}• Eseguiamo il passo (3). A e’ ridondante in AB → C ?
• Verifichiamo se la chiusura di B rispetto ad E contiene C
• Si: Infatti B+ = {B,C}. Dunque E diventaE = {A→ B,A→ C ,B → C}
• Eseguiamo il passo (4):
• A→ C e’ implicata logicamente da A→ B,B → C (pertransitivita’). Dunque E diventa E = {A→ B,B → C}.
• Una copertura canonica (o minimale) e’:
E = {A→ B,B → C}
Raffaella Gentilini Teoria della Normalizzazione 19 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Example
• R = (A,B,C )
• F = {A→ BC ,B → C ,A→ B,AB → C}• Dopo l’esecuzione del passo (2) dell’algoritmo si ha:
E = {A→ B,A→ C ,B → C ,AB → C}• Eseguiamo il passo (3). A e’ ridondante in AB → C ?
• Verifichiamo se la chiusura di B rispetto ad E contiene C• Si: Infatti B+ = {B,C}. Dunque E diventa
E = {A→ B,A→ C ,B → C}• Eseguiamo il passo (4):
• A→ C e’ implicata logicamente da A→ B,B → C (pertransitivita’). Dunque E diventa E = {A→ B,B → C}.
• Una copertura canonica (o minimale) e’:
E = {A→ B,B → C}
Raffaella Gentilini Teoria della Normalizzazione 19 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Example
• R = (A,B,C )
• F = {A→ BC ,B → C ,A→ B,AB → C}• Dopo l’esecuzione del passo (2) dell’algoritmo si ha:
E = {A→ B,A→ C ,B → C ,AB → C}• Eseguiamo il passo (3). A e’ ridondante in AB → C ?
• Verifichiamo se la chiusura di B rispetto ad E contiene C• Si: Infatti B+ = {B,C}. Dunque E diventa
E = {A→ B,A→ C ,B → C}• Eseguiamo il passo (4):
• A→ C e’ implicata logicamente da A→ B,B → C (pertransitivita’). Dunque E diventa E = {A→ B,B → C}.
• Una copertura canonica (o minimale) e’:
E = {A→ B,B → C}
Raffaella Gentilini Teoria della Normalizzazione 19 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Example
• R = (A,B,C )
• F = {A→ BC ,B → C ,A→ B,AB → C}• Dopo l’esecuzione del passo (2) dell’algoritmo si ha:
E = {A→ B,A→ C ,B → C ,AB → C}• Eseguiamo il passo (3). A e’ ridondante in AB → C ?
• Verifichiamo se la chiusura di B rispetto ad E contiene C• Si: Infatti B+ = {B,C}. Dunque E diventa
E = {A→ B,A→ C ,B → C}• Eseguiamo il passo (4):
• A→ C e’ implicata logicamente da A→ B,B → C (pertransitivita’). Dunque E diventa E = {A→ B,B → C}.
• Una copertura canonica (o minimale) e’:
E = {A→ B,B → C}Raffaella Gentilini Teoria della Normalizzazione 19 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Forme Normali basate su Dipendenze Funzionali
• 1NF: Prima Forma Normale
• 2NF: Seconda Forma normale
• 3NF: Terza Forma Normale
• BCNF: Forma Normale di Boyce-Codd
Normalizzare uno schema di relazione R=
Decomporre (opportunamente) R in schemi che siano in forma normale
Raffaella Gentilini Teoria della Normalizzazione 20 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Forme Normali basate su Dipendenze Funzionali
• 1NF: Prima Forma Normale
• 2NF: Seconda Forma normale
• 3NF: Terza Forma Normale
• BCNF: Forma Normale di Boyce-Codd
Normalizzare uno schema di relazione R=
Decomporre (opportunamente) R in schemi che siano in forma normale
Raffaella Gentilini Teoria della Normalizzazione 20 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Normalizzare sfruttando le Dipendenze Funzionali
Decomponendo uno schema di relazione R sfruttando un insieme di dipen-denze funzionali F in un insieme di schemi R1 . . .Rn vogliamo:
• Minimizzare la ridondanza
• Decomposizione Lossless-join: Senza perdita di informazione
• Conservare le dipendenze: Se Fi e’ l’insieme delle dipendenze di F+
che includono solo attributi di Ri , allora:
• La decomposizione dovrebbe essere dependency preserving,cioe’ (F1 ∪ · · · ∪ Fn)+ = F+
• altrimenti il controllo delle violazioni delle dipendenzefunzionali (dello schema originario) comporterebbe lacomputazione esplicita di operazioni di join.
Raffaella Gentilini Teoria della Normalizzazione 21 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Normalizzare sfruttando le Dipendenze Funzionali
Decomponendo uno schema di relazione R sfruttando un insieme di dipen-denze funzionali F in un insieme di schemi R1 . . .Rn vogliamo:
• Minimizzare la ridondanza
• Decomposizione Lossless-join: Senza perdita di informazione
• Conservare le dipendenze: Se Fi e’ l’insieme delle dipendenze di F+
che includono solo attributi di Ri , allora:
• La decomposizione dovrebbe essere dependency preserving,cioe’ (F1 ∪ · · · ∪ Fn)+ = F+
• altrimenti il controllo delle violazioni delle dipendenzefunzionali (dello schema originario) comporterebbe lacomputazione esplicita di operazioni di join.
Raffaella Gentilini Teoria della Normalizzazione 21 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Normalizzare sfruttando le Dipendenze Funzionali
Decomponendo uno schema di relazione R sfruttando un insieme di dipen-denze funzionali F in un insieme di schemi R1 . . .Rn vogliamo:
• Minimizzare la ridondanza
• Decomposizione Lossless-join: Senza perdita di informazione
• Conservare le dipendenze: Se Fi e’ l’insieme delle dipendenze di F+
che includono solo attributi di Ri , allora:
• La decomposizione dovrebbe essere dependency preserving,cioe’ (F1 ∪ · · · ∪ Fn)+ = F+
• altrimenti il controllo delle violazioni delle dipendenzefunzionali (dello schema originario) comporterebbe lacomputazione esplicita di operazioni di join.
Raffaella Gentilini Teoria della Normalizzazione 21 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Normalizzare sfruttando le Dipendenze Funzionali
Decomponendo uno schema di relazione R sfruttando un insieme di dipen-denze funzionali F in un insieme di schemi R1 . . .Rn vogliamo:
• Minimizzare la ridondanza
• Decomposizione Lossless-join: Senza perdita di informazione
• Conservare le dipendenze: Se Fi e’ l’insieme delle dipendenze di F+
che includono solo attributi di Ri , allora:
• La decomposizione dovrebbe essere dependency preserving,cioe’ (F1 ∪ · · · ∪ Fn)+ = F+
• altrimenti il controllo delle violazioni delle dipendenzefunzionali (dello schema originario) comporterebbe lacomputazione esplicita di operazioni di join.
Raffaella Gentilini Teoria della Normalizzazione 21 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Normalizzare sfruttando le Dipendenze Funzionali
Decomponendo uno schema di relazione R sfruttando un insieme di dipen-denze funzionali F in un insieme di schemi R1 . . .Rn vogliamo:
• Minimizzare la ridondanza
• Decomposizione Lossless-join: Senza perdita di informazione
• Conservare le dipendenze: Se Fi e’ l’insieme delle dipendenze di F+
che includono solo attributi di Ri , allora:
• La decomposizione dovrebbe essere dependency preserving,cioe’ (F1 ∪ · · · ∪ Fn)+ = F+
• altrimenti il controllo delle violazioni delle dipendenzefunzionali (dello schema originario) comporterebbe lacomputazione esplicita di operazioni di join.
Raffaella Gentilini Teoria della Normalizzazione 21 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Normalizzare sfruttando le Dipendenze Funzionali
Decomponendo uno schema di relazione R sfruttando un insieme di dipen-denze funzionali F in un insieme di schemi R1 . . .Rn vogliamo:
• Minimizzare la ridondanza
• Decomposizione Lossless-join: Senza perdita di informazione
• Conservare le dipendenze: Se Fi e’ l’insieme delle dipendenze di F+
che includono solo attributi di Ri , allora:
• La decomposizione dovrebbe essere dependency preserving,cioe’ (F1 ∪ · · · ∪ Fn)+ = F+
• altrimenti il controllo delle violazioni delle dipendenzefunzionali (dello schema originario) comporterebbe lacomputazione esplicita di operazioni di join.
Raffaella Gentilini Teoria della Normalizzazione 21 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Example
• R = (A,B,C ), F = {A→ B,B → C}• puo’ essere decomposto in due modi diversi:
1. R1 = (A,B), R2 = (B,C )
• decomposizione senza perdite• conserva le dipendenze
2. R1 = (A,B), R2 = A,C )
• decomposizione senza perdite• non conserva le dipendenze (non posso controllare se viene
violato il vincolo B → C senza calcolare R1 ./ R2)
Raffaella Gentilini Teoria della Normalizzazione 22 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Example
• R = (A,B,C ), F = {A→ B,B → C}• puo’ essere decomposto in due modi diversi:
1. R1 = (A,B), R2 = (B,C )
• decomposizione senza perdite• conserva le dipendenze
2. R1 = (A,B), R2 = A,C )
• decomposizione senza perdite• non conserva le dipendenze (non posso controllare se viene
violato il vincolo B → C senza calcolare R1 ./ R2)
Raffaella Gentilini Teoria della Normalizzazione 22 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Example
• R = (A,B,C ), F = {A→ B,B → C}• puo’ essere decomposto in due modi diversi:
1. R1 = (A,B), R2 = (B,C )• decomposizione senza perdite• conserva le dipendenze
2. R1 = (A,B), R2 = A,C )
• decomposizione senza perdite• non conserva le dipendenze (non posso controllare se viene
violato il vincolo B → C senza calcolare R1 ./ R2)
Raffaella Gentilini Teoria della Normalizzazione 22 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Example
• R = (A,B,C ), F = {A→ B,B → C}• puo’ essere decomposto in due modi diversi:
1. R1 = (A,B), R2 = (B,C )• decomposizione senza perdite• conserva le dipendenze
2. R1 = (A,B), R2 = A,C )• decomposizione senza perdite• non conserva le dipendenze (non posso controllare se viene
violato il vincolo B → C senza calcolare R1 ./ R2)
Raffaella Gentilini Teoria della Normalizzazione 22 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Verificare la Conservazione delle Dipendenze
• Per verificare se la dipendenza α→ β e’ preservata in unadecomposizione di R in R1 . . .Rn, applichiamo il seguente test (lechiusure di attributi sono fatte rispetto ad F ):
result ← αwhile result cambia do
for each Ri nella decomposizione dot = (result ∩ Ri )
+ ∩ Ri
result ← result ∪ tend for
end while
• Se result ⊇ β, allora la DF α→ β e’ preservata.
• Applicheremo il test su tutte le dipendenze di F
• Questa procedura e’ polinomiale, mentre la computazione di F+ e(F1 ∪ · · · ∪ Fn)+ richiede un tempo esponenziale.
Raffaella Gentilini Teoria della Normalizzazione 23 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Boyce-Codd Normal Form (BCNF)
Definizione: Boyce-Codd Normal Form
Uno schema di relazione R(X ) e’ in BCNF rispetto ad un insieme F didipendenze funzionali, se per ogni dipendenza in F+ della forma α → β,α, β ⊆ X , almeno una delle seguenti condizioni e’ soddisfatta:
• α→ β e’ banale (ovvero β ⊆ α)
• α e’ superchiave di R(X )
Raffaella Gentilini Teoria della Normalizzazione 24 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Example
• R(X ) = (A,B,C ), F = {A→ B,B → C}• A e’ chiave
• R non e’ in BCNF
• Decomposizione: R1 = (A,B),R2 = (B,C )• R1 e R2 sono in BCNF• la decomposizione e’ senza perdite• e preserva le dipendenze
Raffaella Gentilini Teoria della Normalizzazione 25 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Example
• R(X ) = (A,B,C ), F = {A→ B,B → C}• A e’ chiave
• R non e’ in BCNF
• Decomposizione: R1 = (A,B),R2 = (B,C )• R1 e R2 sono in BCNF• la decomposizione e’ senza perdite• e preserva le dipendenze
Raffaella Gentilini Teoria della Normalizzazione 25 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Example
• R(X ) = (A,B,C ), F = {A→ B,B → C}• A e’ chiave
• R non e’ in BCNF
• Decomposizione: R1 = (A,B),R2 = (B,C )• R1 e R2 sono in BCNF• la decomposizione e’ senza perdite• e preserva le dipendenze
Raffaella Gentilini Teoria della Normalizzazione 25 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Example
• R(X ) = (A,B,C ), F = {A→ B,B → C}• A e’ chiave
• R non e’ in BCNF
• Decomposizione: R1 = (A,B),R2 = (B,C )• R1 e R2 sono in BCNF• la decomposizione e’ senza perdite• e preserva le dipendenze
Raffaella Gentilini Teoria della Normalizzazione 25 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Algoritmo per la decomposizione in BCNF
result ← {R};done ← falsewhile not done do
if ∃S ∈ result non in BCNF thensi determini una DF α→ β su S che violi BCNFresult ← (result \ S) ∪ {(S \ β)} ∪ {(αβ)}
elsedone ← true
end ifend while
Raffaella Gentilini Teoria della Normalizzazione 26 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Test per BCNF• Per verificare se DF non banaleα→ β causa violazione della BCNF:
• computare α+ (la chiusura di α), e verificare se include tuttigli attributi di R, cioe’ se α+ e’ superchiave di R
• Test semplificato: Per verificare se uno schema R e’ in BCNF, e’sufficiente verificare solo che le DF in F non violano la BCNF(invece di controllare tutte le dipendenze di F+). Infatti:
• se nessuna delle DF in F causa una violazione della BCNF,allora nessuna delle DF in F+ causa una violazione della BCNF
• Tuttavia, utilizzare solo F e’ scorretto quando si effettua il test suuna relazione della decomposizione di R.
• Ad esempio, consideriamo R(A,B,C ,D) edF = {A→ B,B → C}• decomponiamo R in R1(A,B) e R2(A,C ,D)• nessuna delle DF in F contiene solo attributi in (A,C ,D),
tuttavia la DF A→ C ∈ F+ mostra che R2 non e’ in BCNF
Raffaella Gentilini Teoria della Normalizzazione 27 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Test per BCNF• Per verificare se DF non banaleα→ β causa violazione della BCNF:
• computare α+ (la chiusura di α), e verificare se include tuttigli attributi di R, cioe’ se α+ e’ superchiave di R
• Test semplificato: Per verificare se uno schema R e’ in BCNF, e’sufficiente verificare solo che le DF in F non violano la BCNF(invece di controllare tutte le dipendenze di F+). Infatti:
• se nessuna delle DF in F causa una violazione della BCNF,allora nessuna delle DF in F+ causa una violazione della BCNF
• Tuttavia, utilizzare solo F e’ scorretto quando si effettua il test suuna relazione della decomposizione di R.
• Ad esempio, consideriamo R(A,B,C ,D) edF = {A→ B,B → C}• decomponiamo R in R1(A,B) e R2(A,C ,D)• nessuna delle DF in F contiene solo attributi in (A,C ,D),
tuttavia la DF A→ C ∈ F+ mostra che R2 non e’ in BCNF
Raffaella Gentilini Teoria della Normalizzazione 27 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Test per BCNF• Per verificare se DF non banaleα→ β causa violazione della BCNF:
• computare α+ (la chiusura di α), e verificare se include tuttigli attributi di R, cioe’ se α+ e’ superchiave di R
• Test semplificato: Per verificare se uno schema R e’ in BCNF, e’sufficiente verificare solo che le DF in F non violano la BCNF(invece di controllare tutte le dipendenze di F+). Infatti:
• se nessuna delle DF in F causa una violazione della BCNF,allora nessuna delle DF in F+ causa una violazione della BCNF
• Tuttavia, utilizzare solo F e’ scorretto quando si effettua il test suuna relazione della decomposizione di R.
• Ad esempio, consideriamo R(A,B,C ,D) edF = {A→ B,B → C}• decomponiamo R in R1(A,B) e R2(A,C ,D)• nessuna delle DF in F contiene solo attributi in (A,C ,D),
tuttavia la DF A→ C ∈ F+ mostra che R2 non e’ in BCNF
Raffaella Gentilini Teoria della Normalizzazione 27 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Test per BCNF
Per verificare se uno schema Ri di una decomposizione di R e’ in BCNF siopera come segue:
• o verificare se Ri e’ in BCNF rispetto alla restrizione di F+ su Ri
(cioe’ tutte le dipendenze funzionali in R+ che contengono soloattributi di Ri
• oppure effettuare sull’insieme di DF F il seguente test:
• per ogni insieme di attributi α ⊆ Ri , verificare che α+ o nonincluda attributi di Ri \ α, oppure includa tutti gli attributi diRi
• se la condizione sopra e’ violata da qualche α→ β ∈ F , sidimostra che la DF α→ (α+ \ α) ∩ Ri certifica che Ri violaBCNF.
• Le dipendenze di questo tipo saranno usate per decomporreulteriormente Ri
Raffaella Gentilini Teoria della Normalizzazione 28 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Test per BCNF
Per verificare se uno schema Ri di una decomposizione di R e’ in BCNF siopera come segue:
• o verificare se Ri e’ in BCNF rispetto alla restrizione di F+ su Ri
(cioe’ tutte le dipendenze funzionali in R+ che contengono soloattributi di Ri
• oppure effettuare sull’insieme di DF F il seguente test:
• per ogni insieme di attributi α ⊆ Ri , verificare che α+ o nonincluda attributi di Ri \ α, oppure includa tutti gli attributi diRi
• se la condizione sopra e’ violata da qualche α→ β ∈ F , sidimostra che la DF α→ (α+ \ α) ∩ Ri certifica che Ri violaBCNF.
• Le dipendenze di questo tipo saranno usate per decomporreulteriormente Ri
Raffaella Gentilini Teoria della Normalizzazione 28 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Test per BCNF
Per verificare se uno schema Ri di una decomposizione di R e’ in BCNF siopera come segue:
• o verificare se Ri e’ in BCNF rispetto alla restrizione di F+ su Ri
(cioe’ tutte le dipendenze funzionali in R+ che contengono soloattributi di Ri
• oppure effettuare sull’insieme di DF F il seguente test:
• per ogni insieme di attributi α ⊆ Ri , verificare che α+ o nonincluda attributi di Ri \ α, oppure includa tutti gli attributi diRi
• se la condizione sopra e’ violata da qualche α→ β ∈ F , sidimostra che la DF α→ (α+ \ α) ∩ Ri certifica che Ri violaBCNF.
• Le dipendenze di questo tipo saranno usate per decomporreulteriormente Ri
Raffaella Gentilini Teoria della Normalizzazione 28 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Test per BCNF
Per verificare se uno schema Ri di una decomposizione di R e’ in BCNF siopera come segue:
• o verificare se Ri e’ in BCNF rispetto alla restrizione di F+ su Ri
(cioe’ tutte le dipendenze funzionali in R+ che contengono soloattributi di Ri
• oppure effettuare sull’insieme di DF F il seguente test:
• per ogni insieme di attributi α ⊆ Ri , verificare che α+ o nonincluda attributi di Ri \ α, oppure includa tutti gli attributi diRi
• se la condizione sopra e’ violata da qualche α→ β ∈ F , sidimostra che la DF α→ (α+ \ α) ∩ Ri certifica che Ri violaBCNF.
• Le dipendenze di questo tipo saranno usate per decomporreulteriormente Ri
Raffaella Gentilini Teoria della Normalizzazione 28 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Test per BCNF
Per verificare se uno schema Ri di una decomposizione di R e’ in BCNF siopera come segue:
• o verificare se Ri e’ in BCNF rispetto alla restrizione di F+ su Ri
(cioe’ tutte le dipendenze funzionali in R+ che contengono soloattributi di Ri
• oppure effettuare sull’insieme di DF F il seguente test:
• per ogni insieme di attributi α ⊆ Ri , verificare che α+ o nonincluda attributi di Ri \ α, oppure includa tutti gli attributi diRi
• se la condizione sopra e’ violata da qualche α→ β ∈ F , sidimostra che la DF α→ (α+ \ α) ∩ Ri certifica che Ri violaBCNF.
• Le dipendenze di questo tipo saranno usate per decomporreulteriormente Ri
Raffaella Gentilini Teoria della Normalizzazione 28 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
BCNF e conservazione delle dipendenze
Non e’ sempre possibile ottenere una BCNF che conservi le dipendenze:
Example
• R = (J,K , L), F = {JK → L, L→ K}
• due chiavi candidate: JK e JL
• R non e’ in BCNF
• ogni possibile decomposizione di R non preserva JK → L.
Raffaella Gentilini Teoria della Normalizzazione 29 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
BCNF e conservazione delle dipendenze
Non e’ sempre possibile ottenere una BCNF che conservi le dipendenze:
Example
• R = (J,K , L), F = {JK → L, L→ K}
• due chiavi candidate: JK e JL
• R non e’ in BCNF
• ogni possibile decomposizione di R non preserva JK → L.
Raffaella Gentilini Teoria della Normalizzazione 29 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
BCNF e conservazione delle dipendenze
Non e’ sempre possibile ottenere una BCNF che conservi le dipendenze:
Example
• R = (J,K , L), F = {JK → L, L→ K}
• due chiavi candidate: JK e JL
• R non e’ in BCNF
• ogni possibile decomposizione di R non preserva JK → L.
Raffaella Gentilini Teoria della Normalizzazione 29 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
BCNF e conservazione delle dipendenze
Non e’ sempre possibile ottenere una BCNF che conservi le dipendenze:
Example
• R = (J,K , L), F = {JK → L, L→ K}
• due chiavi candidate: JK e JL
• R non e’ in BCNF
• ogni possibile decomposizione di R non preserva JK → L.
Raffaella Gentilini Teoria della Normalizzazione 29 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Terza Forma Normale: Motivazioni
• Ci sono casi in cui:
• BCNF non preserva le dipendenze, mentre e’ necessario avereuna procedura efficiente per mantenere le DF
• Soluzione: Definire una forma normale piu’ debole (vedremo ora laterza forma normale – 3NF).
• ammettere della ridondanza (con i conseguenti svantaggi;vedremo esempio) ma
• garantire che le DF possano essere controllate sulle relazionidecomposte, senza alcun join.
• Proprieta’: Esiste sempre una decomposizione in 3NF che conservale dipendenze.
Raffaella Gentilini Teoria della Normalizzazione 30 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Terza Forma Normale: Motivazioni
• Ci sono casi in cui:
• BCNF non preserva le dipendenze, mentre e’ necessario avereuna procedura efficiente per mantenere le DF
• Soluzione: Definire una forma normale piu’ debole (vedremo ora laterza forma normale – 3NF).
• ammettere della ridondanza (con i conseguenti svantaggi;vedremo esempio) ma
• garantire che le DF possano essere controllate sulle relazionidecomposte, senza alcun join.
• Proprieta’: Esiste sempre una decomposizione in 3NF che conservale dipendenze.
Raffaella Gentilini Teoria della Normalizzazione 30 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Terza Forma Normale: Motivazioni
• Ci sono casi in cui:
• BCNF non preserva le dipendenze, mentre e’ necessario avereuna procedura efficiente per mantenere le DF
• Soluzione: Definire una forma normale piu’ debole (vedremo ora laterza forma normale – 3NF).
• ammettere della ridondanza (con i conseguenti svantaggi;vedremo esempio) ma
• garantire che le DF possano essere controllate sulle relazionidecomposte, senza alcun join.
• Proprieta’: Esiste sempre una decomposizione in 3NF che conservale dipendenze.
Raffaella Gentilini Teoria della Normalizzazione 30 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Terza Forma Normale: Motivazioni
• Ci sono casi in cui:
• BCNF non preserva le dipendenze, mentre e’ necessario avereuna procedura efficiente per mantenere le DF
• Soluzione: Definire una forma normale piu’ debole (vedremo ora laterza forma normale – 3NF).
• ammettere della ridondanza (con i conseguenti svantaggi;vedremo esempio) ma
• garantire che le DF possano essere controllate sulle relazionidecomposte, senza alcun join.
• Proprieta’: Esiste sempre una decomposizione in 3NF che conservale dipendenze.
Raffaella Gentilini Teoria della Normalizzazione 30 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Terza Forma Normale: Motivazioni
• Ci sono casi in cui:
• BCNF non preserva le dipendenze, mentre e’ necessario avereuna procedura efficiente per mantenere le DF
• Soluzione: Definire una forma normale piu’ debole (vedremo ora laterza forma normale – 3NF).
• ammettere della ridondanza (con i conseguenti svantaggi;vedremo esempio) ma
• garantire che le DF possano essere controllate sulle relazionidecomposte, senza alcun join.
• Proprieta’: Esiste sempre una decomposizione in 3NF che conservale dipendenze.
Raffaella Gentilini Teoria della Normalizzazione 30 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Terza Forma Normale: Motivazioni
• Ci sono casi in cui:
• BCNF non preserva le dipendenze, mentre e’ necessario avereuna procedura efficiente per mantenere le DF
• Soluzione: Definire una forma normale piu’ debole (vedremo ora laterza forma normale – 3NF).
• ammettere della ridondanza (con i conseguenti svantaggi;vedremo esempio) ma
• garantire che le DF possano essere controllate sulle relazionidecomposte, senza alcun join.
• Proprieta’: Esiste sempre una decomposizione in 3NF che conservale dipendenze.
Raffaella Gentilini Teoria della Normalizzazione 30 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Terza Forma Normale: Motivazioni
• Ci sono casi in cui:
• BCNF non preserva le dipendenze, mentre e’ necessario avereuna procedura efficiente per mantenere le DF
• Soluzione: Definire una forma normale piu’ debole (vedremo ora laterza forma normale – 3NF).
• ammettere della ridondanza (con i conseguenti svantaggi;vedremo esempio) ma
• garantire che le DF possano essere controllate sulle relazionidecomposte, senza alcun join.
• Proprieta’: Esiste sempre una decomposizione in 3NF che conservale dipendenze.
Raffaella Gentilini Teoria della Normalizzazione 30 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Terza Forma Normale (3NF)
Definizione: Terza Forma Normale
Uno schema di relazione R(X ) e’ in terza forma normale rispetto ad un in-sieme F di dipendenze funzionali, se per ogni dipendenza in F+ della formaα→ β, α, β ⊆ X , almeno una delle seguenti condizioni e’ soddisfatta:
• α→ β e’ banale (ovvero β ⊆ α)
• α e’ superchiave di R(X )
• ogni attributo A in β \ α e’ contenuto in una chiave candidata di R
• Una relazione in BCNF e’ anche in 3NF
• La terza condizione e’ il rilassamento della BCNF che assicura laconservazione delle dipendenze.
Raffaella Gentilini Teoria della Normalizzazione 31 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Terza Forma Normale (3NF)
Definizione: Terza Forma Normale
Uno schema di relazione R(X ) e’ in terza forma normale rispetto ad un in-sieme F di dipendenze funzionali, se per ogni dipendenza in F+ della formaα→ β, α, β ⊆ X , almeno una delle seguenti condizioni e’ soddisfatta:
• α→ β e’ banale (ovvero β ⊆ α)
• α e’ superchiave di R(X )
• ogni attributo A in β \ α e’ contenuto in una chiave candidata di R
• Una relazione in BCNF e’ anche in 3NF
• La terza condizione e’ il rilassamento della BCNF che assicura laconservazione delle dipendenze.
Raffaella Gentilini Teoria della Normalizzazione 31 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Terza Forma Normale (3NF)
Definizione: Terza Forma Normale
Uno schema di relazione R(X ) e’ in terza forma normale rispetto ad un in-sieme F di dipendenze funzionali, se per ogni dipendenza in F+ della formaα→ β, α, β ⊆ X , almeno una delle seguenti condizioni e’ soddisfatta:
• α→ β e’ banale (ovvero β ⊆ α)
• α e’ superchiave di R(X )
• ogni attributo A in β \ α e’ contenuto in una chiave candidata di R
• Una relazione in BCNF e’ anche in 3NF
• La terza condizione e’ il rilassamento della BCNF che assicura laconservazione delle dipendenze.
Raffaella Gentilini Teoria della Normalizzazione 31 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
3NF: Esempio
Example
• R = (J,K , L), F = {JK → L, L→ K}
• due chiavi candidate: JK e JL
• R e’ in 3NF
• JK → L: JK e’ superchiave• L→ K : K e’ contenuta in una chiave candidata
• La decomposizione in BCNF ha i due schemi (JL), (LK )
• verificare il rispetto della DF JK → L richiederebbe un join
• nello schema c’e’ ridondanza
Raffaella Gentilini Teoria della Normalizzazione 32 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
3NF: Esempio
Example
• R = (J,K , L), F = {JK → L, L→ K}
• due chiavi candidate: JK e JL
• R e’ in 3NF
• JK → L: JK e’ superchiave• L→ K : K e’ contenuta in una chiave candidata
• La decomposizione in BCNF ha i due schemi (JL), (LK )
• verificare il rispetto della DF JK → L richiederebbe un join
• nello schema c’e’ ridondanza
Raffaella Gentilini Teoria della Normalizzazione 32 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
3NF: Esempio
Example
• R = (J,K , L), F = {JK → L, L→ K}
• due chiavi candidate: JK e JL
• R e’ in 3NF
• JK → L: JK e’ superchiave• L→ K : K e’ contenuta in una chiave candidata
• La decomposizione in BCNF ha i due schemi (JL), (LK )
• verificare il rispetto della DF JK → L richiederebbe un join
• nello schema c’e’ ridondanza
Raffaella Gentilini Teoria della Normalizzazione 32 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
3NF: Esempio
Example
• R = (J,K , L), F = {JK → L, L→ K}
• due chiavi candidate: JK e JL
• R e’ in 3NF
• JK → L: JK e’ superchiave• L→ K : K e’ contenuta in una chiave candidata
• La decomposizione in BCNF ha i due schemi (JL), (LK )
• verificare il rispetto della DF JK → L richiederebbe un join
• nello schema c’e’ ridondanza
Raffaella Gentilini Teoria della Normalizzazione 32 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
3NF: Esempio
Example
• R = (J,K , L), F = {JK → L, L→ K}
• due chiavi candidate: JK e JL
• R e’ in 3NF
• JK → L: JK e’ superchiave• L→ K : K e’ contenuta in una chiave candidata
• La decomposizione in BCNF ha i due schemi (JL), (LK )
• verificare il rispetto della DF JK → L richiederebbe un join
• nello schema c’e’ ridondanza
Raffaella Gentilini Teoria della Normalizzazione 32 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Algoritmo di Decomposizione in 3NF
1. Sia G una copertura canonica di F
2. Per ogni parte sinistra X in una DF in G :
• si definisca schema D con attributi {X ∪ {A1} ∪ · · · ∪ {Ak}},dove X → A1, . . . , X → Ak sono le sole dipendenze di G conX come parte sinistra
• X sara’ la chiave dello schema
3. Se nessuno degli schemi di relazione in D contiene una chiave di R,si definisca un ulteriore schema di relazione D contenente attributiche formano una chiave di R
4. Si eliminino le relazioni ridondanti (i.e. proiezioni di altre relazioni)
Raffaella Gentilini Teoria della Normalizzazione 33 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Algoritmo di Decomposizione in 3NF
1. Sia G una copertura canonica di F
2. Per ogni parte sinistra X in una DF in G :
• si definisca schema D con attributi {X ∪ {A1} ∪ · · · ∪ {Ak}},dove X → A1, . . . , X → Ak sono le sole dipendenze di G conX come parte sinistra
• X sara’ la chiave dello schema
3. Se nessuno degli schemi di relazione in D contiene una chiave di R,si definisca un ulteriore schema di relazione D contenente attributiche formano una chiave di R
4. Si eliminino le relazioni ridondanti (i.e. proiezioni di altre relazioni)
Raffaella Gentilini Teoria della Normalizzazione 33 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Algoritmo di Decomposizione in 3NF
1. Sia G una copertura canonica di F
2. Per ogni parte sinistra X in una DF in G :
• si definisca schema D con attributi {X ∪ {A1} ∪ · · · ∪ {Ak}},dove X → A1, . . . , X → Ak sono le sole dipendenze di G conX come parte sinistra
• X sara’ la chiave dello schema
3. Se nessuno degli schemi di relazione in D contiene una chiave di R,si definisca un ulteriore schema di relazione D contenente attributiche formano una chiave di R
4. Si eliminino le relazioni ridondanti (i.e. proiezioni di altre relazioni)
Raffaella Gentilini Teoria della Normalizzazione 33 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Algoritmo di Decomposizione in 3NF
1. Sia G una copertura canonica di F
2. Per ogni parte sinistra X in una DF in G :
• si definisca schema D con attributi {X ∪ {A1} ∪ · · · ∪ {Ak}},dove X → A1, . . . , X → Ak sono le sole dipendenze di G conX come parte sinistra
• X sara’ la chiave dello schema
3. Se nessuno degli schemi di relazione in D contiene una chiave di R,si definisca un ulteriore schema di relazione D contenente attributiche formano una chiave di R
4. Si eliminino le relazioni ridondanti (i.e. proiezioni di altre relazioni)
Raffaella Gentilini Teoria della Normalizzazione 33 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Algoritmo di Decomposizione in 3NF
Si dimostra che l’algoritmo visto e’ tale che:
• e’ corretto
• ogni schema Ri e’ in NF
• la decomposizione conserva le dipendenze ed e’ senza perdite.
Raffaella Gentilini Teoria della Normalizzazione 34 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Algoritmo di Decomposizione in 3NF
Si dimostra che l’algoritmo visto e’ tale che:
• e’ corretto
• ogni schema Ri e’ in NF
• la decomposizione conserva le dipendenze ed e’ senza perdite.
Raffaella Gentilini Teoria della Normalizzazione 34 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Algoritmo di Decomposizione in 3NF
Si dimostra che l’algoritmo visto e’ tale che:
• e’ corretto
• ogni schema Ri e’ in NF
• la decomposizione conserva le dipendenze ed e’ senza perdite.
Raffaella Gentilini Teoria della Normalizzazione 34 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Algoritmo di Decomposizione in 3NF
Si dimostra che l’algoritmo visto e’ tale che:
• e’ corretto
• ogni schema Ri e’ in NF
• la decomposizione conserva le dipendenze ed e’ senza perdite.
Raffaella Gentilini Teoria della Normalizzazione 34 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Decomposizione in 3NF: Esempio
Example
• R(nomeDitta, nomeCliente, nomeImp, numUff )
• nomeImp → nomeDitta numUffnomeCliente nomeDitta→ nomeImp
• Il passo 2 inserisce i seguenti schemi nella decomposizione:
• S(nomeimpiegato, nomeDitta, numUff )• T (nomeCliente, nomeDitta, nomeImp)
• Poiche’ T contiene una chiave candidata per R abbiamo finito
Raffaella Gentilini Teoria della Normalizzazione 35 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Decomposizione in 3NF: Esempio
Example
• R(nomeDitta, nomeCliente, nomeImp, numUff )
• nomeImp → nomeDitta numUffnomeCliente nomeDitta→ nomeImp
• Il passo 2 inserisce i seguenti schemi nella decomposizione:
• S(nomeimpiegato, nomeDitta, numUff )• T (nomeCliente, nomeDitta, nomeImp)
• Poiche’ T contiene una chiave candidata per R abbiamo finito
Raffaella Gentilini Teoria della Normalizzazione 35 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Decomposizione in 3NF: Esempio
Example
• R(nomeDitta, nomeCliente, nomeImp, numUff )
• nomeImp → nomeDitta numUffnomeCliente nomeDitta→ nomeImp
• Il passo 2 inserisce i seguenti schemi nella decomposizione:
• S(nomeimpiegato, nomeDitta, numUff )• T (nomeCliente, nomeDitta, nomeImp)
• Poiche’ T contiene una chiave candidata per R abbiamo finito
Raffaella Gentilini Teoria della Normalizzazione 35 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Comparazione di BCNF e 3NF
• Per ogni dato schema e’ sempre possibile calcolare una 3NF:
• senza perdite• che conserva le dipendenze
• Per ogni dato schema e’ sempre possibile calcolare una BCNF
• senza perdite• potrebbe non preservare tutte le dipendenze
Raffaella Gentilini Teoria della Normalizzazione 36 / 37
Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali
Comparazione di BCNF e 3NF
• Esempio di problemi dovuti alla ridondanza ammessa dalla 3NF
• R = (J,K , L)• F = {JK → L, L→ K}
J L Kj1 l1 k1j2 l1 k1j3 l1 k1
null l2 k2
Uno schema in 3NF ma non in BCNF comporta:
• ripetizione di informazione (ad esempio, la coppia di dati l1, k1)
• impiego di valori nulli (ad esempio, per rappresentare la correlazionetra l2 e k2 quando non ci sono corrispondenti valori per J.
Raffaella Gentilini Teoria della Normalizzazione 37 / 37
Top Related