La Terza Forma Normale garantisce che uno schema relazionale non presenti ridondanze evitabili mantenendo al tempo stesso tutte le dipendenze funzionali rilevanti. Si basa sull’idea che ogni attributo non banale debba dipendere direttamente da una chiave o essere esso stesso un attributo primo (parte di una chiave candidata). Questa condizione assicura una struttura più pulita e coerente della relazione. La 3NF non è la forma più restrittiva che si può ottenere, ne esistono altre, tra cui la forma normale di Boyce-Codd (BCNF).
DEFINIZIONE
Uno schema di relazione R è in Terza Forma Normale (3NF) rispetto ad un insieme di dipendenze funzionali F se:
Almeno una delle seguenti condizioni è vera: A è un attributo primo (cioè appartiene a una chiave candidata di R). X è una superchiave (contiene una chiave completa).
N.B. Per A ∈ X la dipendenza è banale (cioè per riflessività) e in questo caso lo schema R non può mai violare la 3NF.
Teorema:
Siano R uno schema di relazione e F un insieme di dipendenze funzionali su R. Uno schema R è in 3NF se e solo se non esistono né dipendenze parziali né dipendenze transitive su R.
Dimostrazione:
1. Se R è in 3NF, allora non esistono né DF parziali né transitive su R (⇒):
Assumiamo che R sia in 3NF: Se A è primo (parte di una chiave) allora viene a mancare la prima condizione (A non primo) per avere una dipendenza parziale o transitiva. Proviamo quindi a prendere A non primo, dunque per definizione di 3NF deve valere la condizione: X è superchiave. Dunque per definizione di superchiave:
- Non può verificarsi X ⊂ K, in quanto X non può essere propriamente contenuta in nessuna chiave candidata. Quindi: nessuna dipendenza parziale è possibile.
- Non può verificarsi K - X ≠ Ø ∀ K ∈ R, in quanto se X una superchiave allora esiste almeno una chiave candidata K in R tale che K ⊆ X (ovvero K ⊂ X o K = X) dunque non è possibile che per tutte le chiavi valga la condizione K - X ≠ Ø. Quindi: nessuna dipendenza transitiva è possibile. Teorema (parte solo se) dimostrato.
2. Se non esistono né DF parziali né transitive su R, allora R è in 3NF (⇐):
Assumiamo che non esistono ne dipendenze parziali ne transitive: Supponiamo per assurdo che R non sia in 3NF, in tal caso: ∀ X → A ∈ F+ tale che:
- A non è primo.
- X non è una superchiave. Poiché X non è una superchiave sono possibili due casi mutuamente esclusivi:
- ∀ K ∈ R vale X ⊄ K e K - X ≠ Ø, in tal caso X → A ∈ F+ è transitiva (contraddizione).
- ∃ K ∈ R tale che X ⊂ K, in tal caso X → A ∈ F+ è parziale (contraddizione). In entrambi i casi si giunge ad una contraddizione, dunque il teorema (parte se) è dimostrato.
ESEMPI
Vediamo alcuni esempi di analisi della forma di uno schema R:
Esempio 1:
R = ABCD F = {A → B, B → CD}
Determinazione delle chiavi:
Notiamo subito come A sia una chiave dello schema, in quanto: Per riflessività: A → A ∈ FA (banale). Per transitività: Se A → B e B → CD allora A → CD ∈ FA. Per unione: Se A → A, A → B e A → CD allora A → ABCD ∈ FA. Dunque A → R ∈ FA e, dato che FA = F+: A → R ∈ F+. Quindi A rispetta le condizioni per essere una chiave candidata di R.
Controllo della 3NF:
Valutiamo ora se R è in 3NF rispetto a F+, quindi, per ogni DF in F+, bisogna verificare che almeno una delle due condizioni della definizione sia vera: Iniziamo per comodità con la verifica su F per poi passare a F+:
A → B rispetta la 3NF in quanto A è superchiave.
B → CD non può essere verificata in questo modo in quanto, stando alla definizione, il determinato (CD) deve essere singleton, dunque: Per decomposizione: Se B → CD allora B → C e B → D ∈ FA (e quindi ∈ F+) . Ora verifichiamo B → C e B → D (in F+): In entrambi i casi non viene rispettata la 3NF in quanto B non è superchiave e ne C ne D sono attributi primi (non fanno parte della chiave A).
Conclusione finale:
Concludiamo affermando che lo schema R non è in 3NF rispetto a F.
Esempio 2:
R = ABCD F = {AC → B, B → AD}
Determinazione delle chiavi:
Per riflessività: AC → AC ∈ FA (banale). Per transitività: Se AC → B e B → AD allora AC → AD ∈ FA. Per unione: Se AC → AC, AC → B e AC → AD allora AC → ABCD ∈ FA. Dunque AC → R ∈ FA e, dato che FA = F+: AC → R ∈ F+. Quindi AC rispetta le condizioni per essere una chiave candidata di R.
Per aumento: Se B → AD allora BC → ACD ∈ FA. Per riflessività: BC → B ∈ FA (banale). Per unione: Se BC → ACD e BC → B allora BC → ABCD ∈ FA. Dunque BC → R ∈ FA e, dato che FA = F+: BC → R ∈ F+. Quindi BC rispetta le condizioni per essere una chiave candidata di R.
Aggiungiamo che ABC, che contiene le due chiavi candidate AC e BC, è una superchiave (non è minimale quindi non può essere chiave candidata).
Controllo della 3NF:
Valutiamo ora se R è in 3NF rispetto a F+, quindi, per ogni DF in F+, bisogna verificare che almeno una delle due condizioni della definizione sia vera: Iniziamo per comodità con la verifica su F per poi passare a F+:
AC → B rispetta la 3NF in quanto AC è superchiave.
B → AD non può essere verificata in questo modo in quanto, stando alla definizione, il determinato (AD) deve essere singleton, dunque: Per decomposizione: Se B → AD allora B → A e B → D ∈ FA (e quindi ∈ F+) . Ora verifichiamo B → A e B → D (in F+): B → A rispetta la 3NF in quanto, malgrado B non sia superchiave, A è attributo primo (fa parte della chiave AC). B → D non rispetta la 3NF in quanto, B non è superchiave e D non è attributo primo (non fa parte di nessuna delle due chiavi AC e BC).
Conclusione finale:
Concludiamo affermando che lo schema R non è in 3NF rispetto a F.
Esempio 3:
R = ABCD F = {AB → CD, BC → A, D → AC}
Determinazione delle chiavi:
Per riflessività: AB → A ∈ FA e AB → B ∈ FA (banali). Per unione: Se AB → A, AB → B e AB → CD allora AB → ABCD ∈ FA. Dunque AB → R ∈ FA e, dato che FA = F+: AB → R ∈ F+. Quindi AB rispetta le condizioni per essere una chiave candidata di R.
Per aumento: Se BC → A allora BC → AB ∈ FA. Per transitività: Se BC → AB e AB → CD allora BC → CD ∈ FA. Per unione: Se BC → AB e BC → CD allora BC → ABCD ∈ FA. Dunque BC → R ∈ FA e, dato che FA = F+: BC → R ∈ F+. Quindi BC rispetta le condizioni per essere una chiave candidata di R.
Per aumento: Se D → AC allora BD → ABC ∈ FA. Per riflessività: BD → D ∈ FA (banale). Per unione: Se BD → D e BD → ABC allora BD → ABCD ∈ FA. Dunque BD → R ∈ FA e, dato che FA = F+: BD → R ∈ F+. Quindi BD rispetta le condizioni per essere una chiave candidata di R.
Controllo della 3NF:
Valutiamo ora se R è in 3NF rispetto a F+, quindi, per ogni DF in F+, bisogna verificare che almeno una delle due condizioni della definizione sia vera: Iniziamo per comodità con la verifica su F per poi passare a F+:
AB → CD non può essere verificata in questo modo in quanto, stando alla definizione, il determinato (CD) deve essere singleton, dunque: Per decomposizione: Se AB → CD allora AB → C e AB → D ∈ FA (e quindi ∈ F+) . Ora verifichiamo AB → C e AB → D (in F+): AB → C rispetta la 3NF in quanto AB è superchiave. AB → D rispetta la 3NF in quanto AB è superchiave.
BC → A rispetta la 3NF in quanto BC è superchiave.
D → AC non può essere verificata in questo modo in quanto, stando alla definizione, il determinato (AC) deve essere singleton, dunque: Per decomposizione: Se D → AC allora D → A e D → C ∈ FA (e quindi ∈ F+) . Ora verifichiamo D → A e D → C (in F+): D → A rispetta la 3NF in quanto, malgrado D non sia superchiave, A è attributo primo (fa parte della chiave AB). D → C rispetta la 3NF in quanto, malgrado D non sia superchiave, C è attributo primo (fa parte della chiave BC).
Conclusione finale:
Implicitamente abbiamo verificato tutte le DF in F+ con membro destro (determinato) singleton. Concludiamo affermando che lo schema R è in 3NF rispetto a F.