Forme normali

Le forme normali si possono ottenere attraverso il processo di normalizzazione, che coinvolge la decomposizione, e che garantisce la qualità dello schema risultante.

Forma normale di Boyce-Codd

Uno schema $R (T, F)$ è in BCNF sse per ogni $X \to Y \in F$ tale che $Y ⊈ X$ si ha che $X$ è una superchiave.

Questa forma preserva i dati, garantisce l'assenza di anomalie ma non preserva le dipendenze.

Algoritmo di analisi

La conversione in BCNF consiste nel decomporre ricorsivamente lo schema $R (T, F)$ :

Per il caso base, se $R (T, F)$ è in BCNF restituire ${R (T, F)}$
Altrimenti trovare una $X \to Y \in F$ che viola la BCNF
Calcolare gli attributi $T_{1} = X_{F}^{+}$ e $T_{2} = X \cup (T ∖ T_{1})$
Calcolare le proiezioni $F_{1} = π_{T_{1}} (F)$ e $F_{2} = π_{T_{2}} (F)$
Trovare la decomposizione ricorsiva $ρ_{1}$ di $R_{1} (T_{1}, F_{1})$ e $ρ_{2}$ di $R_{2} (T_{2}, F_{2})$
Restituire $ρ_{1} \cup ρ_{2}$

Esempio

Per esempio con $R (A BC, {A B \to C, C \to A})$ la conversione sarebbe:

La BCNF è violata da $C \to A$ perchè $C$ non è superchiave, infatti $C_{F}^{+} \neq = A BC$
Si calcolano $T_{1} = C_{F}^{+} = A C$ e $T_{2} = BC$
Si calcolano $F_{1} = {C \to A}$ e $F_{2} = \emptyset$
Si trovano le decomposizioni $ρ_{1} = {R_{1} (A C, {C \to A})}$ e $ρ_{2} = {R_{2} (BC, \emptyset)}$

Terza forma normale

Uno schema $R (T, F)$ è detto in 3NF sse per ogni $X \to Y \in F$ tale che $Y ⊈ X$ si ha che $X$ è una superchiave oppure tutti gli attributi $Y ∖ X$ sono attributi primi.

Conviene quindi prima trovare le chiavi di $R$ e poi verificarne la proprietà.

Questa forma preserva i dati e le dipendenze, ma può comunque possedere anomalie.

Algoritmo di sintesi

La conversione in 3NF consiste nel:

Iniziare con la copertura canonica $G$ di $F$
Rimpiazzare da $G$ le $X \to A_{1}, ..., X \to A_{n}$ con una singola $X \to A_{1}, ..., A_{n}$
Creare un $R_{i} (X Y)$ per ogni $X \to Y \in G$
Rimuovere gli schemi i cui attributi fanno parte di un altro schema più grande
Se nessun $R_{i}$ ha attributi superchiave per $R$ , aggiungere un $R_{n + 1} (Z)$ , dove $Z$ è una chiave di $R$