Normalizzazione

uni
Una forma normale è una proprietà di un Database relazionale (Modello Logico Relazionale) che ne garantisce la qualità, ovvero l’assenza di determinati difetti, tra cui le anomalie.
Una relazione non normalizzata:

• presenta ridondanze
• durante gli aggiornamenti incontra errori
  Le forme normali sono di solito definite sul Modello Logico Relazionale ma hanno senso anche in altri contesti, per esempio nel Modello Entity-Relationship.
  La normalizzazione è una procedura che permette di trasformare schemi non normalizzati in schemi che soddisfano una determinata forma normale. Questa procedura viene utilizzata come tecnica di verifica dei risultati della progettazione di una base di dati, non è una metodologia di progettazione.

Decomposizione di Schemi

Teorema:
Dato uno schema $R(T)$, l’insieme di schemi $\rho =\{R_1(T_1),...,R_k(T_k)\}$ è una decomposizione di $R$ se e solo se ${\cup }_i{T}_i=T$
Nota bene: la precedente definizione non richiede che gli schemi $R_i$ siano disgiunti.
Affinché uno schema e la sua decomposizione siano equivalenti quest’ultima deve preservare i dati e preservare le dipendenze.

Teorema della perdita dei dati

Se $\rho =\{R_1(T_1),...,R_k(T_k)\}$ è una decomposizione di $R(T,F)$, allora per ogni istanza di $r$ di $R(T)$ si ha

$$r\in {\pi }_{T_1}(r)\bowtie ...\bowtie {\pi }_{T_k}$$

Questo teorema ci dice che perdiamo informazione quando, ricostruendo una relazione, otteniamo più tuple che nella relazione originaria.

Decomposizione che preserva dati

Se $\rho =\{R_1(T_1),...,R_k(T_k)\}$ è una decomposizione di $R(T,F)$, $\rho$ è una decomposizione che preserva i dati se e solo se, per ogni relazione $r$ che soddisfa $R(T,F)$, si ha:

$$r={\pi }_{T_1}(r)\bowtie ...\bowtie {\pi }_{T_k}$$

Questa definizione ci dice che in una decomposizione che preserva dati, ogni istanza valida $r$ della relazione di partenza deve essere uguale al join naturale delle sue proiezioni sui vari $T_i$.

Teorema di preservazione dei dati

Sia $\rho =\{R_1(T_1),R_2(T_2)\}$ una decomposizione di $R(T,F)$, essa preserva i dati se e solo se $T_1\cap T_2\to T_1\in F^{+}$ oppure $T_1\cap T_2\to T_2\in F^{+}$.
In altre parole gli attributi comuni alle due relazioni devono essere chiave in una delle due tabelle.

Decomposizione che preserva le dipendenze

Dato uno schema $R(T,F)$ e una decomposizione $\rho =\{R_1(T_1),...,R_k(T_k)\}$, $\rho$ è una decomposizione di $R(T,F)$ che preserva le FD se e solo se: ${\cup }_i{\pi }_{T_i}(F)\equiv F$, cioè se $({\cup }_i{\pi }_{T_i}(F){)}^{+}=F^{+}$

Verificare una decomposizione che preserva le FD

Per verificare se una decomposizione di $R(T,F)$ in due relazioni con attributi $X,Y$ preserva le dipendenze bisogna verificare che $({\pi }_X(F)\cup {\pi }_Y(F){)}^{+}=F^{+}$
Per fare ciò è necessario:

• saper calcolare la proiezione di un insieme di FD su un insieme di attributi: algoritmo con complessità esponenziale
• saper determinare l’equivalenza di due insiemi di FD: algoritmo con complessità polinomiale:
  • per ogni $X\to Y\in F$ calcoliamo $X_G^{+}$ e verifichiamo se $Y\in X_F^{+}$
  • di nuovo invertendo $F$ e $G$.

Proiezione di un insieme di dipendenze

Dato $R(T,F)$ e $T_i\in T$, la proiezione dell’insieme di FD $F$ sull’insieme di attributi $T_i$ è

$${\pi }_{T_i}(F)=\{X\to Y\in F^{+}|X,Y\in T_i\}$$

Algoritmo per il calcolo di ${\pi }_{T_i}(F)$

Input: $R(T,F)$ e $T_i\in T$
Output: ${\pi }_{T_I}(F)$
$Z\leftarrow \{\}$
for each $Y\in T_i$ do
$W\leftarrow Y^{+}-Y$
$Z\leftarrow Z\cup \{Y\to (W\cap T_i)\}$
return $Z$
Complessità Esponenziale nel caso peggiore.

Forma Normale di Boyce-Codd (BCNF)

Teorema:
Uno schema $R(T,F)$ è in forma normale Boyce-Codd (BCNF) se e solo se per ogni dipendenza funzionale non banale $X\to Y\in F^{+}$, $X$ è una superchiave di $R$.
Corollario:
Uno schema $R(T,F)$ con $F$ copertura minimale è in BCNF se e solo se per ogni FD elementare $X\to A\in F$, $X$ è una superchiave.
Questa forma normale si basa sull’idea che una dipendenza funzionale $X\to A$, in cui $X$ non contiene attributi estranei (Ridondanza), indica che nella realtà che modella esiste una collezione di entità omogenee univocamente identificate da $X$.
Da questa definizione, il fatto che uno schema sia in BCNF dipende dalla chiusura $F^{+}$ e non dalla copertura $F$, purtroppo per calcolare $F^{+}$ abbiamo solo algoritmi esponenziali. Possiamo però facilmente stabilire se uno schema è in BCNF con un algoritmo di complessità polinomiale.

Algoritmo di verifica BCNF

Input: schema $R(T,F)$
Output: true se $R$ è in BCNF, false altrimenti
for each $X\to Y\in F$ do
if $Y\notin X$ and $T\notin X^{+}$ then
return false
return true

Normalizzazione in BCNF in casi semplici

Per ogni dipendenza $X\to Y$ che viola la BCNF, definiamo una nuova relazione su $XY$ ed eliminiamo $Y$ dalla relazione originaria.

Algoritmo per decomposizione in BNCF che preserva i dati

Input: $R(T,F)$ (per semplicità gli elementi di $F$ sono nella forma $X\to A$)
Output: $\rho$ in BNCF che preserva i dati
$\rho \leftarrow \{R(T,F)\}$
while esiste $R_i(T_i,F_i)\in \rho$ che non è in BCNF do
for each $X\to A\in F_i$ do
if $A\notin X$ and $T_i⊈X^{+}$ then
$R_1\leftarrow R_i\left(T_i-A,{\pi }_{T_i-A}(F_i)\right)$
$R_2\leftarrow R_i\left(X+A,{\pi }_{X+A}(F_i)\right)$
$\rho \leftarrow \rho -\{R_i\}\cup \{R_1,R_2\}$
break
return $\rho$
Non è garantita la preservazione delle dipendenze.

Terza Forma Normale (3NF)

Teorema:
Una relazione è in 3NF se e solo se per ogni FD non banale $X\to A\in F^{+}$, è verificata almeno una delle seguenti condizioni:
- $X$ è una superchiave di $R$
- $A$ è contenuto in almeno una chiave di $R$ (in questo caso si dice che $A$ è un attributo primo)
Quindi se $R$ è in BCNF allora è anche in 3NF: $BCNF⟹3NF$
La verifica di 3NF è un problema NP-completo e il miglior algoritmo deterministico noto ja complessità esponenziale nel caso peggiore. Occorre sapere le chiavi e l’algoritmo per farlo ha complessità esponenziale.
Si può però sempre ottenere una decomposizione in 3NF che preserva dati e FD.

Algoritmo per decomposizione in 3NF

Dividiamo una copertura minimale $G$ in gruppi $G_i$ tale che tutte le le FD in un gruppo abbiano la stessa parte sinistra. Da ogni gruppo $G_i$ si definisce uno schema di relazione composto da tutti gli attributi che appaiono in $G_i$, la cui chiave, detta chiave sintetizzata, è la parte sinistra comune:
Input: $R(T,F)$
Output: $\rho$ che preserva i dati e le dipendenze e con ogni elemento in 3NF

1. Trovare una copertura minimale $G$ di $F$ e porre $\rho \leftarrow \{\}$
2. Sostituire in $G$ ogni insieme di dipendenze $\{X\to A_1,\dots ,X\to A_h\}$ con la dipendenza $X\to A_1\cdots A_h$
3. Per ogni dipendenza $X\to Y\in G$ creare uno schema con attributi $XY$ in $\rho$
4. Eliminare da $\rho$ ogni schema che sia contenuto in un altro schema di $\rho$
5. Se $\rho$ non contiene nessuno schema i cui attributi costituiscono una superchiave di $R$, aggiungere a $\rho$ uno schema con attributi $W$, dove $W$ è una chiave di $R$
   Complessità polinomiale, sempre possibile e conserva dati e FD.