Teoria della Normalizzazione...Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze...

Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze Funzionali

Teoria della Normalizzazione

Raffaella Gentilini

December 13, 2011

Raffaella Gentilini Teoria della Normalizzazione 1 / 37

IntroduzioneMotivationi

Concetti FondamentaliDipendenze FunzionaliChiusura Insieme Dipendenze FunzionaliCopertura Minimale

Forme Normai basate su Dipendenze FunzionaliForma Normale di Boyce-Codd (BCNF)Terza Forma Normale (3NF)

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

Obbiettivi

• ogni Ri sia uno schema di relazione ben definito

• non vi sia perdita di informazione

Obbiettivi

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

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

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[β]

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

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[β]

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

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

• K → X

• non esiste K ′ ⊂ K tale che K ′ → X

• codiceMerce → nomeClienteRaffaella Gentilini Teoria della Normalizzazione 7 / 37

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’)

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

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’.

Example

• A→ H

• per transitivita’ da A→ B e B → H

• AG → I

• CG → HI

Example

• A→ H• per transitivita’ da A→ B e B → H

• AG → I

• CG → HI

Example

• AG → I• arricchendo A→ C con G e poi utilizzando la transitivita’ con

CG → I

• CG → HI

Example

• 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’.

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

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.

Calcolo di F+

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

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

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)

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 .

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.

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 .

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 .

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).

Copertura Minimale

• Calcoliamo la chiusura (X \ {B})+ rispetto ad F

• Verifichiamo se (X \ {B})+ contiene Y• Se si’, allora B e’ ridondante (e puo’ essere eliminato).

Copertura Minimale

• Calcoliamo la chiusura (X \ {B})+ rispetto ad F• Verifichiamo se (X \ {B})+ contiene Y

• Se si’, allora B e’ ridondante (e puo’ essere eliminato).

Copertura Minimale

• Calcoliamo la chiusura (X \ {B})+ rispetto ad F• Verifichiamo se (X \ {B})+ contiene Y• Se si’, allora B e’ ridondante (e puo’ essere eliminato).

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}

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

E = {A→ B,B → C}

Example

• R = (A,B,C )

• Verifichiamo se la chiusura di B rispetto ad E contiene C

E = {A→ B,B → C}

Example

• R = (A,B,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):

E = {A→ B,B → C}

Example

• R = (A,B,C )

E = {A→ B,B → C}

Example

• R = (A,B,C )

E = {A→ B,B → C}Raffaella Gentilini Teoria della Normalizzazione 19 / 37

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

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

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.

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)

Example

1. R1 = (A,B), R2 = (B,C )

• decomposizione senza perdite• conserva le dipendenze

2. R1 = (A,B), R2 = A,C )

Example

1. R1 = (A,B), R2 = (B,C )• decomposizione senza perdite• conserva le dipendenze

2. R1 = (A,B), R2 = A,C )

Example

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

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.

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 )

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

Example

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

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

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

Test per BCNF

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

• ogni possibile decomposizione di R non preserva JK → L.

Example

• R = (J,K , L), F = {JK → L, L→ K}

Example

• R = (J,K , L), F = {JK → L, L→ K}

Example

• R = (J,K , L), F = {JK → L, L→ K}

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.

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:

• 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.

3NF: Esempio

Example

• R = (J,K , L), F = {JK → L, L→ K}

• 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

3NF: Esempio

Example

• R = (J,K , L), F = {JK → L, L→ K}

• R e’ in 3NF

3NF: Esempio

Example

• R = (J,K , L), F = {JK → L, L→ K}

• R e’ in 3NF

3NF: Esempio

Example

• R = (J,K , L), F = {JK → L, L→ K}

• R e’ in 3NF

3NF: Esempio

Example

• R = (J,K , L), F = {JK → L, L→ K}

• R e’ in 3NF

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)

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.

• e’ corretto

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

Example

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

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.

Teoria della Normalizzazione...Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze...

Documents

Transcript of Teoria della Normalizzazione...Introduzione Concetti Fondamentali Forme Normai basate su Dipendenze...