Normalizzazione

Premessa

Portale di appartenenza: Basi di dati.

Cosa troverai in questa nota:

• La normalizzazione e del vincolo locale di dipendenza funzionale.
• Gli assiomi di Armstrong con le relative regole di inferenza derivanti.
• I concetti collegati alle dipendenze funzionali come la chiusura di un insieme di dipendenze funzionali e la chiusura di un insieme di attributi e come essi possano essere usati nella progettazione delle relazioni.
• La decomposizione di una relazione, i vari tipi (senza perdita di informazioni e che mantiene le dipendenze) e le relative restrizioni.
• Le forme normali (1NF, 2NF, 3NF e BCNF).

Prerequisiti: per comprendere pienamente il contenuto di questa nota, oltre le conoscenze minime che do per scontato che tu sappia già, ti consiglio di aver letto in precedenza queste altre note:

• Modello relazionale.
• Problemi in una base di dati.
• Operatori derivati.

Buona lettura! ☝️🤓

---

Definizione: normalizzazione

La normalizzazione è il processo di trasformazione di una base di dati relazionale in una equivalente, con l’obiettivo di eliminare ridondanze, minimizzare anomalie di modifica e garantire la consistenza dei dati contenuti al suo interno.

1 - Le dipendenze funzionali

In particolare, alla base del processo di normalizzazione si colloca il processo di rilevamento delle dipendenze funzionali, che permettono di capire i collegamenti tra i vari dati presenti all’interno di un database.

Definizione: vincolo locale di dipendenza funzionale

Data una relazione $R(A)$ e due sottoinsiemi di attributi $X,Y\subseteq A$, il vincolo locale di dipendenza funzionale (o più semplicemente dipendenza funzionale), denotato con $X\to Y$ (si legge $X$ determina $Y$), è soddisfatto se e solo se, per ogni coppia di tuple distinte $t_i,t_j$ in $R$, se vale $t_i[X]=t_j[X]$, allora vale anche $t_i[Y]=t_j[Y]$:

$$X\to Y⟺\forall t_i,t_j\in R(t_i[X]=t_j[X]⟹t_i[Y]=t_j[Y])$$

Esempio di dipendenze funzionali

Consideriamo la relazione $\text{STUDENTI}(\text{Matricola, Corso, Docente})$ con la seguente istanza:

$\text{Matricola}$	$\text{Corso}$	$\text{Docente}$
$1023932$	$\text{Basi di Dati}$	$\text{Prof. Pensa}$
$2019349$	$\text{Sistemi Operativi}$	$\text{Prof. Schifanella}$
$2109322$	$\text{Sistemi Operativi}$	$\text{Prof. Schifanella}$
$2109322$	$\text{Basi di Dati}$	$\text{Prof. Pensa}$

Possiamo per esempio chiederci: vale la dipendenza funzionale $\text{Corso}\to \text{Docente}$? Per verificarlo, applichiamo la definizione e verifichiamo se, per ogni coppia di tuple distinte $t_i,t_j$ in $\text{STUDENTI}$ vale:

$$t_i[\text{Corso}]=t_j[\text{Corso}]⟹t_i[\text{Docente}]=t_j[\text{Docente}]$$

Vediamo che, per esempio, nella prima e nell’ultima tupla il valore di $\text{Corso}$ è $\text{Basi di Dati}$ e in $\text{Docente}$ hanno entrambe valore $\text{Prof. Pensa}$. Allo stesso tempo, le altre due tuple hanno lo stesso valore in $\text{Corso}$ (cioè $\text{Sistemi Operativi}$) e in $\text{Docente}$ corrisponde ($\text{Prof. Schifanella}$). Possiamo quindi confermare che $\text{Corso}\to \text{Docente}$ è una dipendenza funzionale.

Possiamo ora chiederci: vale la dipendenza funzionale $\text{Matricola}\to \text{Corso}$? In questo caso, dobbiamo verificare che:

$$t_i[\text{Matricola}]=t_j[\text{Matricola}]⟹t_i[\text{Corso}]=t_j[\text{Corso}]$$

Possiamo notare che le ultime due tuple hanno lo stesso valore in $\text{Matricola}$ (cioè $2109322$), ma i valori in $\text{Corso}$ non corrispondono: ciò significa che la dipendenza funzionale $\text{Matricola}\to \text{Corso}$ non può essere valida.

Definizione: dipendenza funzionale non banale

Data una relazione $R(A)$ e due sottoinsiemi di attributi $X,Y\subseteq A$, una dipendenza funzionale $X\to Y$ è detta non banale se $Y⊈X$.

2.1 - Assiomi di Armstrong

Il matematico e informatico canadese William W. Armstrong nel 1974 ha proposto un insieme di assiomi che permettono di comprendere le implicazioni logiche che intercorrono tra dipendenze funzionali.

Definizione: assiomi di Armstrong

Gli assiomi di Armstrong (o regole di inferenza di Armstrong) sono un insieme di assiomi utilizzati per dedurre dipendenze funzionali a partire da un insieme dato di dipendenze funzionali in una relazione.

Essi sono tre: assioma di riflessività, assioma di aumento e assioma di transitività.

Assioma di riflessività di Armstrong

Data una relazione $R(A)$ e due sottoinsiemi di attributi $X,Y\subseteq A$, se $Y$ è sottoinsieme di $X$, allora $X$ determina $Y$:

$$\begin{array}{rl}& Y\subseteq X\\ & X\to Y\end{array}$$

Assioma di aumento di Armstrong

Data una relazione $R(A)$ e tre sottoinsiemi di attributi $X,Y,Z\subseteq A$, se $X$ determina $Y$, allora $XZ$¹ determina $YZ$¹:

$$\begin{array}{rl}& X\to Y\\ & XZ\to YZ\end{array}$$

Assioma di transitività di Armstrong

Data una relazione $R(A)$ e tre sottoinsiemi di attributi $X,Y,Z\subseteq A$, se $X$ determina $Y$ e $Y$ determina $Z$, allora $X$ determina $Z$:

$$\begin{array}{rl}& X\to Y\\ & Y\to Z\\ & X\to Z\end{array}$$

2.1.1 - Regole di inferenza addizionali

Dagli assiomi di Armstrong vengono derivate altre regole di inferenza addizionali.

Regola di decomposizione

Data una relazione $R(A)$ e tre sottoinsiemi di attributi $X,Y,Z\subseteq A$, se $X$ determina $YZ$¹, allora $X$ determina $Y$ e $Z$:

$$\begin{array}{rl}& X\to YZ\\ & X\to Y\\ & X\to Z\end{array}$$

Regola di composizione (o del prodotto)

Data una relazione $R(A)$ e quattro sottoinsiemi di attributi $W,X,Y,Z\subseteq A$, se $X$ determina $Y$ e $W$ determina $Z$, allora $XW$¹ determina $YZ$¹:

$$\begin{array}{rl}& X\to Y\\ & W\to Z\\ & XW\to YZ\end{array}$$

Regola di unione

Data una relazione $R(A)$ e tre sottoinsiemi di attributi $X,Y,Z\subseteq A$, se $X$ determina $Y$ e $Z$, allora $X$ determina $YZ$¹:

$$\begin{array}{rl}& X\to Y\\ & X\to Z\\ & X\to YZ\end{array}$$

Regola di pseudo-transitività

Data una relazione $R(A)$ e quattro sottoinsiemi di attributi $W,X,Y,Z\subseteq A$, se $X$ determina $Y$ e $YZ$¹ determina $W$, allora $XZ$¹ determina $W$:

$$\begin{array}{rl}& X\to Y\\ & YZ\to W\\ & XZ\to W\end{array}$$

Regola di estensibilità

Data una relazione $R(A)$ e due sottoinsiemi di attributi $X,Y\subseteq A$, se $X$ determina $Y$, allora $X$ determina $XY$¹:

$$\begin{array}{rl}& X\to Y\\ & X\to XY\end{array}$$

Regola di monotonicità

Data una relazione $R(A)$ e tre sottoinsiemi di attributi $X,Y,Z\subseteq A$ con $X=Z$, se $X$ determina $Y$, allora $XZ$¹ determina $Y$:

$$\begin{array}{rl}& X\to Y\\ & XZ\to Y\end{array}$$

Regola di auto-determinazione

Data una relazione $R(A)$ e un sottoinsieme di attributi $X\subseteq A$, $X$ determina se stesso:

$$\begin{array}{rl}& X\\ & X\to X\end{array}$$

2.2 - Gli attributi estranei

Definizione: attributo estraneo

Data una relazione $R(A)$ con un insieme $F$ di dipendenze funzionali su $R$ e due sottoinsiemi di attributi $X,Y\subseteq A$, un attributo $B\in X$ si dice estraneo nella dipendenza funzionale $(X\to Y)\in F$ se è possibile ottenere $X\to Y$ anche senza il suo uso, utilizzando le restanti dipendenze funzionali in $F$ (cioè $F^{\prime }=F-\{X\to Y\}$) e la dipendenza modificata togliendo $B$ (cioè $f^{\prime }=(X-\{B\})\to Y$):

$$(\underset{F^{\prime }}{\underbrace{F-\{X\to Y\}}})\cup \{\underset{f^{\prime }}{\underbrace{(X-\{B\})\to Y}}\}\models X\to Y$$

Esempio di attributo estraneo

Consideriamo la relazione $R(A_1,A_2,A_3,A_4)$ con l’insieme di dipendenze funzionali

$$F=\{A_1{A}_2\to A_3,A_1\to A_3,A_3\to A_4\}$$

Esaminiamo la dipendenza $A_1{A}_2\to A_3$ per verificare se $A_2$ è un attributo estraneo attraverso la sua definizione:

$$(\underset{F^{\prime }}{\underbrace{F-\{A_1{A}_2\to A_3\}}})\cup \{\underset{f^{\prime }}{\underbrace{(A_1{A}_2-\{A_2\})\to A_3}}\}\models A_1{A}_2\to A_3$$

Calcoliamo prima $F^{\prime }$, cioè l’insieme di dipendenze funzionali $F$ privato della dipendenza che stiamo esaminando:

$$\begin{array}{rl}{F}^{\prime }& =F-\{A_1{A}_2\to A_3\}\\ & =\{A_1{A}_2\to A_3,A_1\to A_3,A_3\to A_4\}-\{A_1{A}_2\to A_3\}\\ & =\{A_1\to A_3,A_3\to A_4\}\end{array}$$

Ora calcoliamo $f^{\prime }$, cioè la dipendenza modificata togliendo quello che vogliamo provare essere un attributo estraneo:

$$\begin{array}{rl}{f}^{\prime }& =(A_1{A}_2-\{A_2\})\to A_3\\ & =A_1\to A_3\end{array}$$

Ora chiediamoci: è possibile dedurre $A_1{A}_2\to A_3$ dall’unione di $F^{\prime }$ e $f^{\prime }$?

$$F^{\prime }\cup \{f^{\prime }\}=\{A_1\to A_3,A_3\to A_4\}\cup \{A_1\to A_3\}=\{A_1\to A_3,A_3\to A_4\}\models A_1{A}_2\to A_3$$

Questo è vero, perché $A_1\to A_3$ implica $A_1{A}_2\to A_3$ per la regola di monotonicità, quindi possiamo concludere che $A_2$ è estraneo nella dipendenza funzionale $A_1{A}_2\to A_3$.

2.3 - Chiusura di un insieme di dipendenze funzionali

Definizione: chiusura di un insieme di dipendenze funzionali

Data una relazione $R(A)$ con un insieme $F$ di dipendenze funzionali su $R$, una chiusura $F^{+}$ è un insieme di dipendenze funzionali su $R$ tali che ogni $f^{+}\in F^{+}$ è derivabile da $F$:

$$F^{+}=\{f^{+}=X\to Y\mid X,Y\subseteq R\wedge F\models X\to Y\}$$

Esempio di chiusura di un insieme di dipendenze funzionali

Consideriamo una relazione $R(A,B,C)$ con l’insieme di dipendenze funzionali

$$F=\{A\to B,B\to C\}$$

Un esempio di una sua chiusura $F^{+}$, ovvero di un insieme di tutte le dipendenze funzionali che si possono derivare logicamente da $F$, può essere la seguente:

$$F^{+}=\{A\to C,B\to BC,AB\to AC\}$$

Possiamo notare infatti come ogni $f^{+}\in F^{+}$ è derivabile da $F$:

• $A\to C$: derivabile secondo l’assioma di transitività:

$$\begin{array}{rl}& A\to B\\ & B\to C\\ & A\to C\end{array}$$

• $B\to BC$: derivabile secondo la regola di estensibilità:

$$\begin{array}{rl}& B\to C\\ & B\to BC\end{array}$$

• $AB\to AC$: derivabile secondo l’assioma di aumento:

$$\begin{array}{rl}& B\to C\\ & AB\to AC\end{array}$$

Osservazione: utilità della chiusura di un insieme di dipendenze funzionali

Conoscere la chiusura $F^{+}$ di un insieme $F$ di dipendenze funzionali significa conoscere tutte le dipendenze funzionali valide in $F$ perché sono deducibili a partire da quelle contenute in $F$ stesso.

Osservazione: crescita esponenziale della cardinalità di una chiusura

Una chiusura $F^{+}$ di un insieme di dipendenze funzionali $F$ può includere dipendenze del tipo $X\to Y$ su ogni possibile coppia di sottoinsiemi di attributi $X,Y\subseteq A$. Sappiamo che il numero di sottoinsiemi di $A$ possibili è $2^{|A|}$ e, avendo questa possibilità sia per $X$ che per $Y$, abbiamo che il numero potenziale di dipendenze è $2^{|A|}\cdot 2^{|A|}=4^{|A|}$, che è esponenziale nella dimensione dello schema $A$.

Dunque, elencare o costruire tutte le dipendenze funzionali di $F^{+}$ è computazionalmente impraticabile anche per schemi moderatamente grandi (per esempio, se $|A|=10$, ci sono fino a $4^{10}=\mathrm{1.048.576}$ possibili dipendenze funzionali).

2.4 - Equivalenza di insiemi di dipendenze funzionali

Osservazione: le dipendenze funzionali non sono uniche

In una relazione, non c’è unicità nelle dipendenze funzionali che possono essere soddisfatte in essa.

Esempio di non-unicità delle dipendenze funzionali

Consideriamo la relazione $\text{BIBLIOTECA}(\text{Libro, Autore, CasaEditrice})$ con la seguente istanza:

$\text{Libro}$	$\text{Autore}$	$\text{CasaEditrice}$	$\text{AnnoDiPubblicazione}$
$\text{Divina Commedia}$	$\text{Dante Alighieri}$	$\text{Adelphi}$	$2017$
$\text{I Promessi Sposi}$	$\text{Alessandro Manzoni}$	$\text{Adelphi}$	$2017$
$\text{Lezioni Americane}$	$\text{Italo Calvino}$	$\text{Laterza}$	$2023$
$\text{Vita Nova}$	$\text{Dante Alighieri}$	$\text{Adelphi}$	$2017$
$\text{Se una notte...}$	$\text{Italo Calvino}$	$\text{Laterza}$	$2023$

Posso considerare due insiemi diversi di dipendenze funzionali che agiscono su questa relazione:

• L’insieme $F=\{\text{Autore}\to \text{CasaEditrice},\text{Autore}\to \text{AnnoDiPubblicazione}\}$.
• L’insieme $G=\{\text{CasaEditrice}\to \text{AnnoDiPubblicazione}\}$.

Questi due insiemi sono ugualmente validi e dipendono solamente dal punto di vista del progettista che sceglie come descrivere le dipendenze funzionali che insistono su questa relazione.

Questo concetto potrebbe sembrare molto banale, ma in realtà, grazie anche alla definizione formale di chiusura, ora possiamo caratterizzare dal punto di vista teorico il concetto di equivalenza tra insiemi di dipendenze funzionali.

Definizione: equivalenza di insiemi di dipendenze funzionali

Data una relazione $R(A)$ con due insiemi $F$ e $G$ di dipendenze funzionali su $R$, $F$ si dice equivalente a $G$ (e si denota "$F\equiv G$") se le loro chiusure $F^{+}$ e $G^{+}$ sono uguali:

$$F\equiv G⟺F^{+}=G^{+}$$

Abbiamo ricondotto l’equivalenza ad un’uguaglianza insiemistica: se tutte le dipendenze derivate dall’insieme $F$ sono uguali a tutte le dipendenze derivate da $G$, le due basi di dati evolvono allo stesso modo.

Tuttavia, come già detto, risulta però complesso costruire per intero le chiusure $F^{+}$ e $G^{+}$ per verificare l’equivalenza. Fortunatamente, esiste una proprietà che porta al medesimo risultato.

Proprietà dell'equivalenza di insiemi di dipendenze funzionali

Data una relazione $R(A)$ con due insiemi $F$ e $G$ di dipendenze funzionali su $R$, $F$ è equivalente a $G$ se e solo se $G$ è deducibile da $F$ e $F$ è deducibile da $G$:

$$F\equiv G⟺F\models G\wedge G\models F$$

Esempio di equivalenza di insiemi di dipendenze funzionali

Consideriamo una relazione $R(A,B,C)$ con due insiemi di dipendenze funzionali:

• $F=\{A\to BC\}$.
• $G=\{A\to B,A\to C\}$.

Per verificare l’equivalenza $F\equiv G$, dobbiamo verificare se ogni $f\in F$ è deducibile da $G$ e, viceversa, se ogni $g\in G$ è deducibile da $F$.

Verifichiamo il primo caso ($G\models F$):

• $G=\{A\to B,A\to C\}\models A\to BC$: deducibile per la regola di unione.

Ora verifichiamo il secondo caso ($F\models G$):

• $F=\{A\to BC\}\models A\to B$: deducibile per la regola di decomposizione.
• $F=\{A\to BC\}\models A\to C$: deducibile per la regola di decomposizione.

Abbiamo concluso che $F\models G$ e $G\models F$ e, per la proprietà dell’equivalenza di insiemi di dipendenze funzionali, possiamo confermare che vale l’equivalenza $F\equiv G$.

2.5 - Chiusura di un insieme di attributi

Definizione: chiusura di un insieme di attributi

Data una relazione $R(A)$ con un sottoinsieme di attributi $X\subseteq A$ su cui è definito un insieme $F$ di dipendenze funzionali, una chiusura $X_F^{+}$ è un insieme di attributi $A_i\in A$ tali che la dipendenza funzionale $X\to A_i$ è deducibile da $F$:

$$X_F^{+}=\{A_i\in A\mid F\models X\to A_i\}$$

Esempio di chiusura di un insieme di attributi

Consideriamo una relazione $R(A,B,C,D)$ con l’insieme di dipendenze funzionali

$$F=\{A\to B,A\to D,C\to D\}$$

e considero $X=\{A\}$.

Una possibile chiusura $X_F^{+}$ di $X$ è:

$$X_F^{+}=\{B,D\}$$

Infatti, per ogni attributo $x$ in $X_F^{+}$, la dipendenza funzionale $X=\{A\}\to x$ è deducibile da $F$:

• $X=\{A\}\to B$: è deducibile perché $A\to B$ è già un elemento di $F$.
• $X=\{A\}\to D$: è deducibile perché $A\to D$ è già un elemento di $F$.

Possiamo confermare che la chiusura $X_F^{+}=\{B,D\}$ è valida.

Algoritmo per il calcolo della chiusura di un insieme di attributi

Data una relazione $R(A)$ con due sottoinsieme di attributi $X,Z\subseteq A$ su cui è definito un insieme $F$ di dipendenze funzionali, la chiusura $X_F^{+}$ è calcolata nel seguente modo:

1. Assegna $X$ a $X_F^{+}$ e $F$ a $F^{\prime }$.
2. Esiste in $F^{\prime }$ una dipendenza funzionale $Y\to Z$ tale che $Y\subseteq X_F^{+}$?
3. Se sì, unisci $Z$ a $X_F^{+}$ e rimuovi $Y\to Z$ da $F^{\prime }$.
4. Se no, stop.

Esempio di uso dell'algoritmo per il calcolo della chiusura di un insieme di attributi

Consideriamo una relazione $R(A,B,C,D,E,G)$ con l’insieme di dipendenze funzionali

$$F=\{AD\to B,D\to AC,D\to G,E\to G\}$$

e considero $X=\{A,D\}$. Proviamo a calcolare la chiusura $X_F^{+}$ usando l’algoritmo per il calcolo della chiusura di un insieme di attributi:

• Passo 1: $X_F^{+}=\{A,D\}$ e $F^{\prime }=\{AD\to B,D\to AC,D\to G,E\to G\}$.
• Passo 2: in $F^{\prime }$ c’è la dipendenza funzionale $AD\to B$ (dove $Y=AD\subseteq X_F^{+}$ e $Z=B$).
• Passo 3: $X_F^{+}=\{A,D\}\cup \{B\}=\{A,B,D\}$ e $F^{\prime }=\{AD\to B,D\to AC,D\to G,E\to G\}-\{AD\to B\}=\{D\to AC,D\to G,E\to G\}$.
• Passo 2: in $F^{\prime }$ c’è la dipendenza funzionale $D\to AC$ (dove $Y=D\subseteq X_F^{+}$ e $Z=AC$).
• Passo 3: $X_F^{+}=\{A,B,D\}\cup \{A,C\}=\{A,B,C,D\}$ e $F^{\prime }=\{D\to AC,D\to G,E\to G\}-\{D\to AC\}=\{D\to G,E\to G\}$.
• Passo 2: in $F^{\prime }$ c’è la dipendenza funzionale $D\to G$ (dove $Y=D\subseteq X_F^{+}$ e $Z=G$).
• Passo 3: $X_F^{+}=\{A,B,C,D\}\cup \{G\}=\{A,B,C,D,G\}$ e $F^{\prime }=\{D\to G,E\to G\}-\{D\to G\}=\{E\to G\}$.
• Passo 2: in $F^{\prime }$ non ci sono più dipendenze funzionali valide.

Dopo aver eseguito l’algoritmo, abbiamo trovato che la chiusura $X_F^{+}$ contiene i seguenti attributi:

$$X_F^{+}=\{A,B,C,D,G\}$$

Proprietà 1 sulla chiusura di un insieme di attributi

Data una relazione $R(A)$ con due sottoinsiemi di attributi $X,Y\subseteq A$ su cui è definito un insieme $F$ di dipendenze funzionali, la dipendenza funzionale $X\to Y$ è deducibile da $F$ se e solo se $Y$ è un sottoinsieme di $X_F^{+}$:

$$F⊢X\to Y⟺Y\subseteq X_F^{+}$$

Osservazione: usare la proprietà 1 per verificare la validità delle dipendenze funzionali

Possiamo notare come, se una dipendenza funzionale è deducibile da un insieme di dipendenze, allora è valida. Ciò significa che è possibile usare la proprietà 1 per verificare la validità di una dipendenza funzionale.

Esempio di uso della proprietà 1 per verificare la validità delle dipendenze funzionali

Consideriamo una relazione $R(A,B,C,D,E,G)$ con l’insieme di dipendenze funzionali

$$F=\{AD\to B,D\to AC,D\to G,E\to G\}$$

Vogliamo verificare la validità della dipendenza $AD\to G$ (quindi $X=AD$ e $Y=G$). Per fare ciò, dobbiamo calcolare la chiusura $X_F^{+}$ e verificare se in essa è presente $G$. Nell’esempio precedente avevamo già calcolato questa chiusura e abbiamo ottenuto:

$$X_F^{+}=\{A,B,C,D,G\}$$

Dal momento che $\{G\}\subseteq X_F^{+}$, possiamo confermare che la dipendenza $AD\to G$ è valida.

Vogliamo ora verificare la validità della dipendenza $A\to G$ (quindi $X=A$ e $Y=G$). Per fare ciò, dobbiamo calcolare la chiusura $X_F^{+}$ e verificare se in essa è presente $G$. Applicando l’algoritmo, notiamo subito che stavolta la chiusura $X_F^{+}$ contiene solo $A$ (perché non ci sono dipendenze con attributi deducibili unicamente da $A$).

Dal momento che $\{G\}⊈X_F^{+}=\{A\}$, la dipendenza $A\to G$ NON è valida.

Una riformulazione che si trova spesso in giro della proprietà 1 è quella che viene detta proprietà di membership.

Proprietà di membership sulla chiusura di un insieme di attributi

Data una relazione $R(A)$ con due sottoinsiemi di attributi $X,Y\subseteq A$ su cui è definito un insieme $F$ di dipendenze funzionali, la dipendenza funzionale $X\to Y$ è contenuta nella chiusura $F^{+}$ se e solo se $Y$ è un sottoinsieme di $X_F^{+}$:

$$(X\to Y)\in F^{+}⟺Y\subseteq X_F^{+}$$

Osservazione: usare la proprietà di membership per verificare la validità delle dipendenze funzionali

Similmente a quanto avviene per la proprietà 1, possiamo usare anche la proprietà di membership, collegandoci a quanto detto sopra, per chiarire subito se una dipendenza è valida o no semplicemente controllando se è presente nella chiusura dell’insieme di dipendenze a cui si riferisce.

Proprietà 2 sulla chiusura di un insieme di attributi

Data una relazione $R(A)$ con un sottoinsieme di attributi $X\subseteq A$ su cui sono definiti due insiemi $F$ e $G$ di dipendenze funzionali, le chiusure $X_F^{+}$ e $X_G^{+}$ sono uguali.

2.6 - Uso della dipendenza funzionale nelle superchiavi

Il concetto di dipendenza funzionale può essere usato per dare una nuova definizione di superchiave.

Definizione: superchiave

Data una relazione $R(A)$, un sottoinsieme di attributi $sk\subseteq A$ è una superchiave se e solo se determina $A$ (cioè vale la dipendenza funzionale $sk\to A$).

Osservazione: verificare una superchiave con la sua chiusura

Data una relazione $R(A)$ su cui è definito un insieme $F$ di dipendenze funzionali, per verificare se un sottoinsieme di attributi $sk\subseteq A$ è una superchiave basterà calcolare la sua chiusura $s{k}_F^{+}$ e vedere se questa coincide con lo schema $A$.

Esempio di verifica di una superchiave con la sua chiusura

Consideriamo una relazione $R(A,B,C,D,E)$ con l’insieme di dipendenze funzionali

$$F=\{A\to B,B\to C,AC\to D\}$$

Vogliamo verificare se il sottoinsieme di attributi $sk=\{A,E\}$ è una superchiave di $R$. Per fare ciò, dobbiamo calcolare la chiusura $s{k}_F^{+}$ e verificare se essa è uguale allo schema $\{A,B,C,D,E\}$. Usando l’algoritmo, possiamo calcolare subito la chiusura che risulta essere:

$$s{k}_F^{+}=\{A,B,C,D,E\}$$

Dal momento che $s{k}_F^{+}=\{A,B,C,D,E\}$ è proprio lo schema della relazione $R$, possiamo confermare che il sottoinsieme di attributi $sk=\{A,E\}$ è una superchiave di $R$.

Osservazione: attributi fuori dall'insieme di dipendenze funzionali fanno parte della superchiave

Data una relazione $R(A)$ su cui è definito un insieme $F$ di dipendenze funzionali, se un attributo $A_i\in A$ non è determinato da nessuna dipendenza funzionale presente in $F$, allora questo dovrà necessariamente far parte della superchiave che si sta cercando.

Esempio di attributo fuori dall'insieme di dipendenze funzionali che fa parte della superchiave

Consideriamo una relazione $R(A,B,C,D,E)$ con l’insieme di dipendenze funzionali

$$F=\{A\to B,B\to C,AC\to D\}$$

Vogliamo verificare se il sottoinsieme di attributi $sk=\{A\}$ è una superchiave di $R$. Per fare ciò, dobbiamo calcolare la chiusura $s{k}_F^{+}$ e verificare se essa è uguale allo schema $\{A,B,C,D,E\}$. Usando l’algoritmo, possiamo calcolare subito la chiusura che risulta essere:

$$s{k}_F^{+}=\{A,B,C,D\}$$

Possiamo notare che in $F$ non è presente alcuna dipendenza funzionale che determina $E$ e, per questo, $E$ non fa parte della chiusura $s{k}_F^{+}$.

Per rendere la chiusura $s{k}_F^{+}$ una superchiave, bisogna includere anche $E$ in $sk$: infatti, se $sk=\{A,E\}$, allora $s{k}_F^{+}=\{A,B,C,D,E\}$ che corrisponde allo schema di $R$ e rende $sk$ una superchiave.

2.7 - Le dipendenze ridondanti

Definizione: dipendenza ridondante

Data una relazione $R(A)$ su cui è definito un insieme $F$ di dipendenze funzionali, una dipendenza funzionale $f=X\to Y\in F$ si dice che è una dipendenza ridondante se, rimuovendola da $F$, rimane comunque derivabile dalla chiusura $F^{+}$ delle altre dipendenze presenti:

$$f\in F^{+}=(F\setminus \{f\}{)}^{+}$$

Insieme in forma canonica

Definizione: insieme di dipendenze funzionali in forma canonica

Data una relazione $R(A)$ su cui è definito un insieme $F$ di dipendenze funzionali, $F$ si dice che è in forma canonica se, per ogni dipendenza funzionale non banale $(X\to Y)\in F$ (con $X,Y\subseteq A$), $Y$ è un singoletto, cioè un singolo attributo.

2.8 - Insieme di copertura minimale

Definizione: insieme di copertura minimale

Data una relazione $R(A)$ su cui è definito un insieme $F$ di dipendenze funzionali in forma canonica, un sottoinsieme $F^{\prime }\subseteq F$ si dice che è un insieme di copertura minimale se, per ogni dipendenza funzionale non banale $(X\to Y)\in F^{\prime }$ (con $X,Y\subseteq A$):

1. $X$ non contiene attributi estranei.
2. $X\to Y$ non è una dipendenza ridondante.

Algoritmo per il calcolo di un insieme di copertura minimale

Data una relazione $R(A)$ su cui è definito un insieme $F$ di dipendenze funzionali in forma canonica, questo algoritmo calcola l’insieme di copertura minimale $F^{\prime }\subseteq F$.

I passi da seguire sono i seguenti:

1. Assegna $F$ a $F^{\prime }$:

$$F^{\prime }:=F$$

2. Per ogni dipendenza funzionale $X\to A_i$ in $F^{\prime }$ e per ogni $B\in X$, se $A_i$ è nella chiusura di $X$ tolto $B$, allora cancella $B$ da $X$:

$$\forall X\to A_i\in F,\forall B\in X(A_i\in (X\setminus \{B\}{)}_{F^{\prime }}^{+}⟹X:=X\setminus \{B\})$$

3. Per ogni dipendenza funzionale $X\to A_i$ in $F^{\prime }$, se $A_i$ è nella chiusura di $X$ rispetto all’insieme $F^{\star }=F^{\prime }\setminus \{X\to A_i\}$ di dipendenze funzionali, allora assegna $F^{\star }$ a $F^{\prime }$:

$$\forall X\to A_i\in F,\forall B\in X(A_i\in X_{F^{\star }}^{+}⟹F^{\prime }:=F^{\star })$$

3 - Decomposizione di relazioni

Ora introduciamo un altro concetto alla base della normalizzazione: la decomposizione di una relazione.

Definizione: decomposizione

Data una relazione $R(A)$ e un ricoprimento $\{X,Y\}$ dello schema $A$ (cioè $X,Y\subseteq A$ e $X\cup Y=A$), l’insieme di relazioni $\{R_1(X),R_2(Y)\}$ (dove $R_i(S)={\pi }_S(R)$) è una decomposizione di $R(A)$ e ogni $R_i$ viene detto sottoschema di $R$.

Esempio di decomposizione

Consideriamo una relazione $R(A,B,C,D,E)$. Una sua decomposizione potrebbe essere:

$$\{R_1(A,C,D),R_2(B,C,E)\}$$

Infatti, $\{A,C,D\}\cup \{B,C,E\}=\{A,B,C,D,E\}$ che corrisponde proprio allo schema della relazione. In particolare:

• Il sottoschema $R_1(A,C,D)$ corrisponde alla proiezione ${\pi }_{A,C,D}(R)$.
• Il sottoschema $R_2(B,C,E)$ corrisponde alla proiezione ${\pi }_{B,C,E}(R)$.

3.1 - Decomposizione senza perdita di informazioni

Definizione: decomposizione senza perdita di informazioni

Data una relazione $R(A)$ su cui è definito un insieme $F$ di dipendenze funzionali, una decomposizione $\{R_1(X),R_2(Y)\}$ di $R$ è detta senza perdita di informazioni se si ha che:

$${\pi }_X(R)\bowtie {\pi }_Y(R)=R$$

Esempio di decomposizione senza perdita di informazioni

Consideriamo una relazione $\text{STUDENTE}(\text{Matricola, Nome, Corso})$ con l’insieme di dipendenze funzionali

$$F=\{\text{Matricola}\to \text{Nome}\}$$

e consideriamo la sua istanza che soddisfa le dipendenze funzionali contenute in $F$ (infatti a ogni matricola corrisponde sempre lo stesso nome):

$\text{Matricola}$	$\text{Nome}$	$\text{Corso}$
$1213812$	$\text{Rossi Mario}$	$\text{Basi di Dati}$
$2813923$	$\text{Bianchi Gaia}$	$\text{Sistemi Operativi}$
$2813923$	$\text{Bianchi Gaia}$	$\text{Basi di Dati}$
$1213812$	$\text{Rossi Mario}$	$\text{Sistemi Operativi}$

Consideriamo la decomposizione

$$\{R_1(\text{Matricola,Nome}),R_2(\text{Corso})\}$$

dove il sottoschema $R_1(\text{Matricola,Nome})$ rappresenta la proiezione ${\pi }_{\text{Matricola,Nome}}(\text{STUDENTE})$²:

$\text{Matricola}$	$\text{Nome}$
$1213812$	$\text{Rossi Mario}$
$2813923$	$\text{Bianchi Gaia}$

e il sottoschema $R_2(\text{Corso})$ rappresenta la proiezione ${\pi }_{\text{Corso}}(\text{STUDENTE})$²:

$\text{Corso}$
$\text{Basi di Dati}$
$\text{Sistemi Operativi}$

Se effettuiamo il natural-join tra il due sottoschemi $R_1$ ed $R_2$ otteniamo:

$\text{Matricola}$	$\text{Nome}$	$\text{Corso}$
$1213812$	$\text{Rossi Mario}$	$\text{Basi di Dati}$
$2813923$	$\text{Bianchi Gaia}$	$\text{Sistemi Operativi}$
$2813923$	$\text{Bianchi Gaia}$	$\text{Basi di Dati}$
$1213812$	$\text{Rossi Mario}$	$\text{Sistemi Operativi}$

Questa istanza corrisponde proprio all’istanza della relazione $\text{STUDENTE}$ da cui siamo partiti, quindi si può concludere che la decomposizione $\{R_1(\text{Matricola,Nome}),R_2(\text{Corso})\}$ è senza perdita di informazioni.

A partire dalla nozione di decomposizione senza perdita di informazioni, possiamo ricavarci un importante teorema.

Teorema sulla decomposizione senza perdita di informazioni

Data una relazione $R(A)$ su cui è definito un insieme $F$ di dipendenze funzionali, una decomposizione $\{R_1(X),R_2(Y)\}$ di $R$ è senza perdita di informazioni se si ha che l’intersezione $X\cap Y$ determina o $X$ o $Y$:

$$(X\cap Y)\to X\vee (X\cap Y)\to Y$$

Esempio di uso del teorema sulla decomposizione senza perdita di informazioni

Consideriamo una relazione $\text{STUDENTE}(\text{Matricola, Nome, Corso})$ con l’insieme di dipendenze funzionali

$$F=\{\text{Matricola}\to \text{Nome}\}$$

e consideriamo la sua istanza $r$ che soddisfa le dipendenze funzionali contenute in $F$ (infatti a ogni matricola corrisponde sempre lo stesso nome):

$\text{Matricola}$	$\text{Nome}$	$\text{Corso}$
$1213812$	$\text{Rossi Mario}$	$\text{Basi di Dati}$
$2813923$	$\text{Bianchi Gaia}$	$\text{Sistemi Operativi}$
$2813923$	$\text{Bianchi Gaia}$	$\text{Basi di Dati}$
$1213812$	$\text{Rossi Mario}$	$\text{Sistemi Operativi}$

Consideriamo la decomposizione

$$\{R_1(\text{Matricola,Nome}),R_2(\text{Matricola, Corso})\}$$

dove il sottoschema $R_1(\text{Matricola,Nome})$ rappresenta la proiezione ${\pi }_{\text{Matricola,Nome}}(\text{STUDENTE})$²:

$\text{Matricola}$	$\text{Nome}$
$1213812$	$\text{Rossi Mario}$
$2813923$	$\text{Bianchi Gaia}$

e il sottoschema $R_2(\text{Matricola, Corso})$ rappresenta la proiezione ${\pi }_{\text{Matricola, Corso}}(\text{STUDENTE})$²:

$\text{Matricola}$	$\text{Corso}$
$1213812$	$\text{Basi di Dati}$
$2813923$	$\text{Sistemi Operativi}$
$2813923$	$\text{Basi di Dati}$
$1213812$	$\text{Sistemi Operativi}$

Secondo il teorema, se l’intersezione $\{\text{Matricola, Nome}\}\cap \{\text{Matricola, Corso}\}=\{\text{Matricola}\}$ può determinare $\{\text{Matricola, Nome}\}$ o $\{\text{Matricola, Corso}\}$ a partire da $F$, allora questa decomposizione è senza perdita di informazioni.

Verifichiamo prima $\{\text{Matricola}\}\to \{\text{Matricola, Nome}\}$:

• Abbiamo la dipendenza $\{\text{Matricola}\}\to \{\text{Nome}\}$ già presente in $F$.
• Avendo $\{\text{Matricola, Nome}\}$ dal passaggio precedente, ricaviamo $\{\text{Matricola}\}\to \{\text{Matricola, Nome}\}$ per la regola di estensibilità.

Abbiamo verificato, quindi, che $\{\text{Matricola}\}\to \{\text{Matricola, Nome}\}$ (cioè che $X\cap Y\to X$): possiamo quindi confermare che la decomposizione $\{R_1(\text{Matricola,Nome}),R_2(\text{Matricola, Corso})\}$ è senza perdita di informazioni.

Ovviamente, il teorema può facilmente essere riformulato sulla base della definizione di superchiave.

Corollario sulla decomposizione senza perdita di informazioni

Data una relazione $R(A)$ su cui è definito un insieme $F$ di dipendenze funzionali, una decomposizione $\{R_1(X),R_2(Y)\}$ di $R$ è senza perdita di informazioni se si ha che l’intersezione $X\cap Y$ è superchiave o di $X$ o di $Y$.

3.2 - Restrizione di un insieme di dipendenze funzionali

Immaginiamo di avere una relazione su cui è definito un insieme di dipendenze funzionali. Dopo aver decomposto questa relazione, vogliamo “decomporre” anche l’insieme delle dipendenze funzionali sulle due decomposizioni: ecco il concetto di restrizione.

Definizione: restrizione di un insieme di dipendenze funzionali

Data una decomposizione $\{R_i(A_i)\}$ di una relazione $R(A)$ su cui è definito un insieme $F$ di dipendenze funzionali, una restrizione $F_i$ di un sottoschema $R_i$ è l’insieme di dipendenze funzionali contenute nella chiusura $F^{+}$ di $F$ che riguardano solo gli attributi $A_i$:

$$F_i=\{X\to Y\in F^{+}\mid X,Y\subseteq A_i\}$$

Esempio di restrizione di un insieme di dipendenze funzionali

Consideriamo una relazione $R(A,B,C)$ con l’insieme di dipendenze funzionali

$$F=\{A\to B,B\to C\}$$

Gli elementi della chiusura $F^{+}$ di $F$ sono:

$$F^{+}=\{A\to B,B\to C,A\to C\}$$

Ora decomponiamo $R$ in

$$\{R_1(A,B),R_2(B,C)\}$$

Calcoliamo la restrizione $F_1$ sul sottoschema $R_1(A,B)$ a partire dagli elementi della chiusura $F^{+}$:

• $A\to B$: ✅ può essere un elemento di $F_1$ perché $\{A,B\}\subseteq \{A,B\}$.
• $B\to C$: ❌ non può essere un elemento di $F_1$ perché $\{B,C\}⊈\{A,B\}$.
• $A\to C$: ❌ non può essere un elemento di $F_1$ perché $\{A,C\}⊈\{A,B\}$.
• E così via per tutti gli altri elementi non elencati della chiusura $F^{+}$.

Quindi possiamo concludere che la restrizione $F_1$ sul sottoschema $R_1(A,B)$ è:

$$F_1=\{A\to B\}$$

Ora calcoliamo la restrizione $F_2$ sul sottoschema $R_2(B,C)$ a partire dagli elementi della chiusura $F^{+}$:

• $A\to B$: ❌ non può essere un elemento di $F_2$ perché $\{A,B\}⊈\{B,C\}$.
• $B\to C$: ✅ può essere un elemento di $F_2$ perché $\{B,C\}\subseteq \{B,C\}$.
• $A\to C$: : ❌ non può essere un elemento di $F_2$ perché $\{A,C\}⊈\{B,C\}$.

Quindi possiamo concludere che la restrizione $F_2$ sul sottoschema $R_2(B,C)$ è:

$$F_2=\{B\to C\}$$

3.3 - Decomposizione che mantiene le dipendenze

Dal concetto di restrizione si può ricavare quello di una decomposizione che “mantiene” le dipendenze.

Definizione: decomposizione che mantiene le dipendenze

Data una relazione $R(A)$ su cui è definito un insieme $F$ di dipendenze funzionali, una decomposizione $\{R_1(X),R_2(Y)\}$ di $R$ si dice che mantiene le dipendenze se $F$ è deducibile dall’unione delle restrizioni $F_1$ ed $F_2$ (rispettivamente dei sottoschemi $R_1$ ed $R_2$):

$$F_1\cup F_2\models F$$

Esempio di decomposizione che mantiene le dipendenze

Consideriamo una relazione $R(A,B,C)$ con l’insieme di dipendenze funzionali

$$F=\{A\to B,B\to C\}$$

Gli elementi della chiusura $F^{+}$ di $F$ sono:

$$F^{+}=\{A\to B,B\to C,A\to C\}$$

Ora decomponiamo $R$ in

$$\{R_1(A,B),R_2(B,C)\}$$

Troviamo che la restrizione $F_1$ sul sottoschema $R_1(A,B)$ è:

$$F_1=\{A\to B\}$$

Mentre, la restrizione $F_2$ sul sottoschema $R_2(B,C)$ è:

$$F_2=\{B\to C\}$$

Facendo l’unione delle due restrizioni $F_1$ ed $F_2$, abbiamo:

$$F_1\cup F_2=\{A\to B\}\cup \{B\to C\}=\{A\to B,B\to C\}$$

Possiamo facilmente verificare che da $F_1\cup F_2$ è deducibile l’insieme di dipendenze funzionali $F$ perché l’unico elemento mancante, $A\to C$, è deducibile dall’assioma di transitività:

$$\begin{array}{rl}& A\to B\\ & B\to C\\ & A\to C\end{array}$$

Si può quindi dire che la decomposizione $\{R_1(A,B),R_2(B,C)\}$ di $R$ mantiene le dipendenze.

3.4 - Decomposizione che mantiene la località delle dipendenze

Possiamo ulteriormente approfondire il concetto di decomposizione che mantiene le dipendenze se teniamo conto del fatto che queste dipendenze funzionali possono essere verificate guardando solo una singola relazione della decomposizione, cioè non è necessario combinare tra loro più relazioni per controllarla.

Definizione: decomposizione che mantiene la località delle dipendenze

Data una relazione $R(A)$ su cui è definito un insieme $F$ di dipendenze funzionali e un insieme di copertura minimale $F^{\prime }\subseteq F$, una decomposizione che mantiene le dipendenze $\{R_i(X_i){\}}_{i\in I}$ di $R$ si dice che mantiene la località delle dipendenze se, per ogni dipendenza funzionale $(X\to Y)\in F^{\prime }$, esiste una relazione nella decomposizione $\{R_i(X_i){\}}_{i\in I}$ che contiene gli attributi $X$ e $Y$:

$$\forall (X\to Y)\in F^{\prime },\exists i\in I(X\cup Y\subseteq R_i)$$

4 - Forme normali

Esistono delle “ricette” per la buona progettazione di una base di dati per limitare l’ammissibilità di dipendenze funzionali tra gli attributi, con l’obiettivo di eliminare o ridurre ridondanze e anomalie di modifica: le forme normali.

Definizione: forma normale

Una relazione $R(A)$ su cui è definito un insieme $F$ di dipendenze funzionali si dice essere in una forma normale $FN$ se soddisfa i vincoli specifici di quella forma normale rispetto a $F$. ^definizione-forma-normale

4.1 - 1ª Forma Normale (1NF)

La 1ª Forma Normale (1NF) si basa sull’uso di attributi con valori indivisibli, detti atomici.

Definizione: attributo atomico

Un attributo atomico è un attributo di una relazione il cui dominio è composto unicamente da valori indivisibili.

Esempi di attributi atomici

Consideriamo una relazione $\text{STUDENTE}(\text{Matricola, Nome, Corso})$. Supponiamo che i domini dei suoi attributi siano i seguenti:

• $\text{Matricola}$ di tipo intero (numero identificativo univoco).
• $\text{Nome}$ di tipo stringa (stringa che rappresenta nome e cognome).
• $\text{Corso}$ di tipo stringa (nome di un singolo insegnamento).

Se ogni attributo assume un solo valore indivisibile per ogni tupla, allora tali attributi sono atomici.

Ad esempio, l’istanza:

$\text{Matricola}$	$\text{Nome}$	$\text{Corso}$
$12345$	$\text{Mario Rossi}$	$\text{Basi di Dati}$
$67890$	$\text{Anna Verdi}$	$\text{Sistemi Operativi}$

contiene solo attributi atomici, in quanto:

• $12345$ è un singolo numero (intero).
• $\text{Mario Rossi}$ è una stringa indivisibile nel contesto.
• $\text{Basi di Dati}$ è una singola unità di informazione.

Se invece $\text{Corso}$ contenesse un insieme di valori, come $\{\text{Basi di Dati, Reti}\}$, oppure $\text{Nome}$ fosse codificato come una struttura {"nome": "Mario", "cognome": "Rossi"}, gli attributi non sarebbero più atomici.

Definizione: 1ª Forma Normale (1NF)

Una relazione $R(A)$ si dice in 1ª Forma Normale (1NF, 1ˢᵗ Normal Form) se tutti i suoi attributi sono atomici.

4.2 - 2ª Forma Normale (2NF)

Definizione: 2ª Forma Normale (2NF)

Una relazione $R(A)$ su cui è definito un insieme $F$ di dipendenze funzionali si dice in 2ª Forma Normale (2NF, 2ⁿᵈ Normal Form) se è in 1ª Forma Normale e ogni attributo non chiave $A_i\in A$ non dipende da un sottoinsieme proprio $X$ di una chiave candidata $k\subseteq A$:

$$\forall A_i\in A,\nexists X⊊k\subseteq A(X\to A_i)$$

Esempio di relazione in 2ª Forma Normale (2NF)

Consideriamo la seguente relazione:

$$\text{ISCRIZIONE}(\text{Matricola},\text{CodCorso},\text{NomeStudente},\text{NomeCorso})$$

e l’insieme $F$ di dipendenze funzionali:

$$\begin{array}{rl}F=\{& (\text{Matricola},\text{CodCorso})\to \text{NomeStudente},\\ & (\text{Matricola},\text{CodCorso})\to \text{NomeCorso},\\ & \text{Matricola}\to \text{NomeStudente},\\ & \text{CodCorso}\to \text{NomeCorso}\}\end{array}$$

Possiamo considerare la chiave candidata $\{\text{Matricola},\text{CodCorso}\}$. In questo caso, le dipendenze $\text{Matricola}\to \text{NomeStudente}$ e $\text{CodCorso}\to \text{NomeCorso}$ indicano che gli attributi non chiave $\text{NomeStudente}$ e $\text{NomeCorso}$ dipendono solo da una parte della chiave (cioè rispettivamente solo da $\text{Matricola}$ e da $\text{CodCorso}$), quindi questa relazione viola la 2NF.

Si può però decomporre $\text{ISCRIZIONE}(\text{Matricola},\text{CodCorso},\text{NomeStudente},\text{NomeCorso})$ nelle seguenti tre relazioni:

1. $\text{ISCRIZIONE2}(\text{Matricola},\text{CodCorso})$ con la restrizione $F_1=\varnothing$ e chiave candidata $\{\text{Matricola, CodCorso}\}$.
2. $\text{STUDENTE}(\text{Matricola},\text{NomeStudente})$ con la restrizione $F_2=\{\text{Matricola}\to \text{NomeStudente}\}$ e chiave candidata $\{\text{Matricola}\}$.
3. $\text{CORSO}(\text{CodCorso},\text{NomeCorso})$ con la restrizione $F_3=\{\text{CodCorso}\to \text{NomeCorso}\}$ e chiave candidata $\{\text{CodCorso}\}$.

In questa nuova decomposizione, ogni attributo non chiave dipende interamente dalla chiave candidata e, quindi, ognuna di queste tre nuove relazioni è in 2NF.

4.3 - 3ª Forma Normale (3NF)

Definizione: 3ª Forma Normale (3NF)

Una relazione $R(A)$ su cui è definito un insieme $F$ di dipendenze funzionali si dice in 3ª Forma Normale (3NF, 3ʳᵈ Normal Form) se è in 2ª Forma Normale e, per ogni dipendenza funzionale non banale $X\to A_i$ (con $X\subseteq A$ e $A_i\in A$) contenuta nella chiusura $F^{+}$ di $F$, si verifica almeno una delle seguenti condizioni:

1. $X$ è una superchiave di $R$.
2. $A_i$ è parte di almeno una chiave candidata.

Esempio di relazione in 3ª Forma Normale (3NF)

Consideriamo la relazione:

$$\text{IMPIEGATO}(\text{CF},\text{Nome},\text{Dipartimento},\text{Responsabile})$$

su cui è definito il seguente insieme di dipendenze funzionali:

$$F=\{\text{CF}\to \text{(Nome, Dipartimento)},\text{Dipartimento}\to \text{Responsabile}\}$$

Considerando come chiave candidata $\text{CF}$, la relazione è in 2NF perché ogni attributo non chiave dipende interamente dalla chiave candidata.

Tuttavia, la relazione $\text{IMPIEGATO}$ viola la 3NF perché (considerando solo le dipendenze funzionali di $F$ e tralasciando quelle della sua chiusura $F^{+}$ per questioni pratiche):

• L’attributo $\text{Dipartimento}$ non è una superchiave (perché non determina l’intero schema della relazione), violando così la condizione 1 della definiizone della 3NF.
• Gli attributi $\text{Nome}$, $\text{Dipartimento}$ e $\text{Responsabile}$ non fanno parte di almeno una chiave candidata, essendo questa composta unicamente da $\text{CF}$ e violando così la condizione 2 della definiizone della 3NF.

Si può però decomporre $\text{IMPIEGATO}(\text{CF},\text{Nome},\text{Dipartimento},\text{Responsabile})$ nelle seguenti due relazioni:

1. $R_1(\text{CF},\text{Nome},\text{Dipartimento})$ con la restrizione $F_1=\{\text{CF}\to \text{(Nome, Dipartimento)}\}$ e chiave candidata $\text{CF}$.
2. $R_2(\text{Dipartimento},\text{Responsabile})$ con la restrizione $F_2=\{\text{Dipartimento}\to \text{Responsabile}\}$ e chiave candidata $\text{Dipartimento}$.

In questa nuova decomposizione, per ogni dipendenza funzionale non banale $X\to A_i$ contenuta nella chiusura $F^{+}$ di $F$, viene rispettata la condizione 1 della definizione secondo cui $X$ è una superchiave di $R$ (infatti, $\text{CF}$ e $\text{Dipartimento}$ sono anche chiavi candidate dei rispettivi sottoschemi e per definizione di chiave candidata sono anche superchiavi).

Quindi, possiamo concludere che ognuna di queste due nuove relazioni è in 3NF.

4.3.1 - Algoritmo di normalizzazione in 3NF

Possiamo costruire un algoritmo che ci permette di normalizzare una relazione in 3NF attraverso dei passaggi ben definiti.

Algoritmo di normalizzazione di una relazione in 3NF

• Input: una relazione $R(A)$ su cui è definito l’insieme $F$ di dipendenze funzionali.
• Output: una base di dati $DB$ con relazioni in 3NF che corrisponde a una decomposizione senza perdita di informazioni di $R(A)$.
• Procedimento:
  1. Calcolo l’insieme di copertura minimale $F^{\prime }$ di $F$: $$F^{\prime }=\{X_1\to A_1,X_2\to A_2,\dots ,X_n\to A_n\}=\{X_i\to A_i{\}}_{i\in I}$$
  2. Costruisco una base di dati $DB$ con $$DB=\{R_1(X_1{A}_1),R_2(X_2{A}_2),\dots ,R_n(X_n{A}_n)\}=\{R_i(X_i{A}_i){\}}_{i\in I}$$
  3. Se nessuna relazione $R_i\in DB$ contiene una chiave candidata $k$ qualsiasi di $R(A)$, aggiungo a $DB$ una nuova relazione $R_{n+1}(k)$: $$DB:=DB\cup \{R_{n+1}(k)\}$$

Durante l’esecuzione dell’algoritmo di normalizzazione di una relazione in 3NF, consideriamo una qualsiasi relazione $R_i(X_i{A}_i)$ risultante dal passo 2 del procedimento: questa relazione è stata generata dalla dipendenza funzionale $X_i\to A_i$, quindi $X_i$ è una superchiave di $R_i$ per la nuova definizione di superchiave, ma possiamo dimostrare che $X_i$ è anche una chiave candidata di $R_i$ perché è minimale.

Proprietà di generazione di chiavi candidate dell'algoritmo di normalizzazione di una relazione in 3NF

Durante l’esecuzione dell’algoritmo di normalizzazione di una relazione in 3NF, per una qualsiasi relazione $R_i(X_i{A}_i)$ risultante dal passo 2 del procedimento, $X_i$ è una chiave candidata di $R_i$.

Dimostrazione della proprietà di generazione di chiavi candidate dell'algoritmo di normalizzazione di una relazione in 3NF

Facciamo una dimostrazione per assurdo.

Supponiamo che $X_i$ sia solo superchiave di $R_i$ (e che quindi non sia minimale), ciò vuol dire che esiste un sottoinsieme proprio $W⊊X_i$ tale che $F^{\prime }⊢W\to A_i$. Allora, per l’assioma di riflessività, abbiamo che $X_i\to W$ e, per l’assioma di transitività, se $X_i\to W$ e $W\to A_i$, allora $X_i\to A_i$.

Ciò implica che quindi $X_i\to A_i$ sia una dipendenza ridondante perché è derivabile da queste altre dipendenze funzionali, ma ciò non è possibile perché dal passo 1 dell’algoritmo di normalizzazione in 3NF otteniamo un insieme di copertura minimale in cui non sono presenti dipendenze funzionali.

Di conseguenza, $W\to A_i$ non può esistere e $X_i$ deve essere per forza minimale, quindi è una chiave candidata.

Proprietà di mantenimento della località delle dipendenze dell'algoritmo di normalizzazione di una relazione in 3NF

Durante l’esecuzione dell’algoritmo di normalizzazione di una relazione in 3NF, ogni dipendenza funzionale $(X_i\to A_i)\in F^{\prime }$ risultante dal passo 1 del procedimento si trova nella restrizione della corrispondente relazione $R_i(X_i{A}_i)$ per costruzione, quindi la decomposizione $DB=\{R_i(X_i{A}_i){\}}_{i\in I}$ è una decomposizione che mantiene la località delle dipendenze.

Proprietà di mantenimento di informazioni dell'algoritmo di normalizzazione di una relazione in 3NF

L’esecuzione dell’algoritmo di normalizzazione di una relazione in 3NF su una relazione $R(A)$ genera una decomposizione $DB=\{R_i(X_i{A}_i){\}}_{i\in I}$ che è senza perdite di informazioni, ossia:

$$R(A)=\underset{i\in I}{\bowtie }{R}_i(X_i{A}_i)=R_1(X_1{A}_1)\bowtie R_2(X_2{A}_2)\bowtie \dots \bowtie R_n(X_n{A}_n)$$

4.4 - Forma Normale di Boyce-Codd (BCNF)

Definizione: Forma Normale di Boyce-Codd (BCNF)

Una relazione $R(A)$ su cui è definito un insieme $F$ di dipendenze funzionali si dice in Forma Normale di Boyce-Codd (BCNF, Boyce-Codd Normal Form) se è in 3ª Forma Normale e, per ogni dipendenza funzionale non banale $X\to Y$ (con $X,Y\subseteq A$) contenuta nella chiusura $F^{+}$ di $F$, $X$ è una superchiave.

Esempio di relazione in Forma Normale di Boyce-Codd (BCNF)

Consideriamo la relazione:

$$R(\text{Studente, Corso, Docente})$$

su cui è definito il seguente insieme di dipendenze funzionali:

$$F=\{\text{(Studente, Corso)}\to \text{Docente},\text{Docente}\to \text{Corso}\}$$

Considerando come chiave candidata $(\text{Studente, Corso})$, la relazione è in 3NF perché ogni attributo non chiave (in questo caso solo $\text{Docente}$) dipende interamente dalla chiave candidata.

Tuttavia, la relazione $R$ viola la BCNF perché l’attributo $\text{Docente}$ non è una superchiave (perché non determina l’intero schema della relazione).

Si può però decomporre $R(\text{Studente, Corso, Docente})$ nelle seguenti due relazioni:

1. $R_1(\text{Studente, Docente})$ con la restrizione $F_1=\varnothing$ e chiave candidata $\text{Studente}$.
2. $R_2(\text{Corso},\text{Docente})$ con la restrizione $F_2=\{\text{Docente}\to \text{Corso}\}$ e chiave candidata $\text{Docente}$.

In questa nuova decomposizione, per ogni dipendenza funzionale non banale $X\to Y$ contenuta nella chiusura $F^{+}$ di $F$, $X$ è una superchiave di $R$ (infatti, $\text{Docente}$ è chiave candidata del sottoschema $R_2$ e, per definizione di chiave candidata, è anche una superchiave).

Quindi, possiamo concludere che ognuna di queste due nuove relazioni è in BCNF.

Osservazione: la BCNF è una restrizione sulla condizione 1 della 3NF

Osservando la definizione della BCNF, si può osservare come questa sia una “restrizione” sulla condizione 1 della 3NF, nel senso che, mentre nella 3NF viene richiesto che la relazione rispetti almeno una delle due condizioni, nella BCNF si chiede che la condizione 1 venga necessariamente rispettata.

Osservazione: la BCNF impedisce le anomalie di modifica

La normalizzazione di una relazione in BCNF elimina la possibilità di avere anomalie di modifica di qualsiasi tipo: questo accade perché, in ogni dipendenza funzionale non banale $X\to Y$, si ha che $X$ è una superchiave che, per definizione, impedisce la ridondanza e assicura che ogni dato sia rappresentato una sola volta.

Bisogna sottolineare però che, ovviamente, ciò vale solo all’interno delle singole relazioni, non globalmente all’interno dell’intera base di dati.

4.4.1 - Algoritmo di normalizzazione in BCNF

Algoritmo di normalizzazione di una base di dati in BCNF

Input: base di dati $DB(SC)$ composto dalle relazioni $R_i(A_i)$ su ognuna delle quali è definito l’insieme di dipendenze funzionali $F_i$.

Output: $DB(SC)$ con le relazioni tutte in BCNF.

1. Cercare all’interno di $DB$ una relazione $R_i(A_i)$ non in BCNF, ossia cercare nel corrispondente insieme di dipendenze funzionali $F_i$ una dipendenza funzionale non banale $X\to Y$ (con $X,Y\subseteq A_i$) tale che $X$ non è superchiave di $R_i(A_i)$.
2. Se non esiste una $X\to Y$ del genere, allora l’algoritmo termina (perché $DB$ sarà già in BCNF).
3. Se esiste, modificare $DB$:
4. Eliminare la relazione $R_i(A_i)$ da $DB$:

$$DB:=DB\setminus R_i(A_i)$$

2. Aggiungere a $DB$ due nuove relazioni:
   • La relazione $R_1(A_i\setminus Y)$ (dal cui schema $A_i$ rimuovere $Y$) su cui è definita la restrizione $F_1$ di $F_i$ in $A_i\setminus Y$:
   $$DB:=DB\cup R_1(A_i\setminus Y)$$
   • La relazione $R_2(X\cup Y)$ (con schema l’unione di $X$ e $Y$) su cui è definita la restrizione $F_2$ di $F_i$ in $X\cup Y$:
   $$DB:=DB\cup R_2(X\cup Y)$$
3. Ricominciare dal passo 1.

Osservazione: l'algoritmo produce una decomposizione senza perdita di informazioni

L’algoritmo di normalizzazione di una base di dati in BCNF produce una decomposizione senza perdita di informazioni, dimostrabile tramite il teorema: infatti, $R_i(A_i)$ viene decomposto in $\{R_1(A_i\setminus Y),R_2(X\cup Y)\}$ e, dato che $A_i\setminus Y=X$ (proprio perché $X\subseteq A_i$), l’intersezione $(A_i\setminus Y)\cap (X\cup Y)=X\cap (X\cup Y)=X$ determina $A_i\setminus Y=X$ (cioè vale $X\to X$).

Esempio di uso dell'algoritmo di normalizzazione di una base di dati in BCNF

Consideriamo la base di dati $DB$ composta dalle seguenti relazioni:

• La relazione $R_1(A_1,A_2,A_3)$ con chiave candidata $(A_1,A_2)$ su cui è definito il seguente insieme di dipendenze funzionali: $$F_1=\{(A_1,A_2)\to A_3,A_3\to A_1\}$$ Possiamo confermare che è in 3NF perché ogni attributo non chiave (in questo caso solo $A_3$) dipende interamente dalla chiave candidata, ma non è in BCNF perché non tutte le dipendenze funzionali non banali $X\to Y\in F_1$ (con $X,Y\subseteq \{A_1,A_2,A_3\}$) sono tali che $X$ è superchiave (in questo caso, per la dipendenza $A_3\to A_1$, $A_3$ non è superchiave).
• La relazione $R_2(B_1,B_2,B_3,B_4)$ con chiave candidata $B_1$ su cui è definito il seguente insieme di dipendenze funzionali: $$F_2=\{B_4\to B_1,B_1\to B_3,(B_2,B_3)\to B_1,B_1\to (B_2,B_4)\}$$ Possiamo confermare che è in 3NF perché ogni attributo non chiave (in questo caso $B_2,B_3,B_4$) dipende interamente dalla chiave candidata, ma non è in BCNF perché non tutte le dipendenze funzionali non banali $X\to Y\in F_2$ (con $X,Y\subseteq \{B_1,B_2,B_3,B_4\}$) sono tali che $X$ è superchiave (in questo caso, per le dipendenze $B_4\to B_1$ e $(B_2,B_3)\to B_1$, $B_4$ e $(B_2,B_3)$ non sono superchiavi).
• La relazione $R_3(C_1,C_2)$ con chiave candidata $C_2$ su cui è definito il seguente insieme di dipendenze funzionali: $$F_3=\{C_2\to C_1\}$$ Possiamo confermare che è in 3NF perché ogni attributo non chiave (in questo caso $C_1$) dipende interamente dalla chiave candidata, ed è anche in BCNF perché tutte le dipendenze funzionali non banali $X\to Y\in F_3$ (con $X,Y\subseteq \{C_1,C_2\}$) sono tali che $X$ è superchiave (infatti $C_2$ è superchiave).

Possiamo quindi usare l’algoritmo per normalizzare la base di dati $DB$ in BCNF:

• Passo 1: all’interno di $DB$ possiamo prendere la relazione $R_1$ che non è in BCNF, in particolare prendendo la dipendenza funzionale non banale $A_3\to A_1\in F_1$ in cui $A_3$ non è superchiave.
• Passo 3: elimino la relazione $R_1$ da $DB$ e ci aggiungo la decomposizione $\{R_4(A_2,A_3),R_5(A_1,A_3)\}$ in cui i due sottoschemi hanno rispettivamente come restrizioni $F_4=\varnothing$ e $F_5=\{A_3\to A_1\}$, quindi ora $DB$ conterrà le seguenti relazioni con i rispettivi insiemi di dipendenze funzionali:

$$\begin{array}{rl}{R}_2(B_1,B_2,B_3,B_4)& F_2=\{B_4\to B_1,B_1\to B_3,(B_2,B_3)\to B_1,B_1\to (B_2,B_4)\}\\ R_3(C_1,C_2)& F_3=\{C_2\to C_1\}\\ R_4(A_2,A_3)& F_4=\varnothing \\ R_5(A_1,A_3)& F_5=\{A_3\to A_1\}\end{array}$$

• Passo 1: all’interno di $DB$ possiamo prendere la relazione $R_2$ che non è in BCNF, in particolare prendendo la dipendenza funzionale non banale $B_4\to B_1\in F_2$ in cui $B_4$ non è superchiave.
• Passo 3: elimino la relazione $R_2$ da $DB$ e ci aggiungo la decomposizione $\{R_6(B_2,B_3,B_4),R_7(B_1,B_4)\}$ in cui i due sottoschemi hanno rispettivamente come restrizioni $F_6=\varnothing$ e $F_7=\{B_4\to B_1\}$, quindi ora $DB$ conterrà le seguenti relazioni con i rispettivi insiemi di dipendenze funzionali:

$$\begin{array}{rl}{R}_3(C_1,C_2)& F_3=\{C_2\to C_1\}\\ R_4(A_2,A_3)& F_4=\varnothing \\ R_5(A_1,A_3)& F_5=\{A_3\to A_1\}\\ R_6(B_2,B_3,B_4)& F_6=\varnothing \\ R_7(B_1,B_4)& F_7=\{B_4\to B_1\}\end{array}$$

• Passo 2: non ci sono più relazioni nella base di dati $DB$ che non siano in BCNF.

Osservazione: la terminazione dell'algoritmo è garantita

Ci sono condizioni per cui, usando l’algoritmo di normalizzazione di una base di dati in BCNF, si entra in un loop senza fine? No, la terminazione è garantita dal passo di decomposizione, infatti:

1. Consideriamo la relazione $R_i(A_i)$ in 3NF ma non in BCNF su cui è definito un insieme $F$ di dipendenze funzionali.
2. Eseguendo l’algoritmo, prendiamo in considerazione la dipendenza funzionale non banale $X\to Y$ (con $X,Y\subseteq A_i$) su cui effettuiamo la decomposizione $\{R_1(A_i\setminus Y),R_2(X\cup Y)\}$.
3. Consideriamo il grado delle relazioni $R_i,R_1,R_2$: abbiamo banalmente che $|A_i\setminus Y|<|A_i|$, cioè $R_1$ ha sicuramente meno attributi di $R_i$. Possiamo confermare però che anche $R_2$ ha meno attributi di$R_i$ (cioè $|X\cup Y|<|A_i|$)?
4. Partiamo dall’ipotesi che $|X\cup Y|=|A_i|$ e, dato che $(X\cup Y)\subseteq A_i$ allora $X\cup Y=A_i$.
5. Abbiamo però che la dipendenza funzionale non banale $X\to Y$ per la regola di estensibilità implica $X\to XY$ e, avendo $X\cup Y=XY=A_i$, abbiamo che $X\to A_i$.
6. Con $X\to A_i$ possiamo dire che, per definizione, $X$ è una superchiave perché determina l’intero schema, ma abbiamo una contraddizione perché siamo partiti dal presupposto che $R_i(A_i)$ non fosse in BCNF perché, nella dipendenza funzionale non banale $X\to Y$, $X$ non è una superchiave.
7. Abbiamo quindi che i gradi di $R_1$ ed $R_2$ sono strettamente minori di quello di $R_i$ (cioè $|A_i\setminus Y|<|A_i|$ e $|X\cup Y|<|A_i|$), quindi dopo ripetute iterazioni dell’algoritmo di normalizzazione ci ritroveremo man mano con relazioni con sempre meno attributi, fino ad arrivare una relazione del tipo $R_n(\{A,B\})$ (dove $A$ e $B$ sono due singoli attributi).
8. Le dipendenze funzionali di $R_n$ dovranno essere necessariamente della forma $A\to B$ o $B\to A$, analizziamo entrambi i casi:

• Se abbiamo la dipendenza $A\to B$, per la regola di estensibilità abbiamo $A\to AB$ e, dato che $A$ determina l’intero schema, per definizione avremo che $A$ sarà una superchiave.
• Viceversa, se abbiamo la dipendenza $B\to A$, per la regola di estensibilità abbiamo $B\to AB$ e, dato che $B$ determina l’intero schema, per definizione avremo che $B$ sarà una superchiave.

9. In entrambi i casi, l’unica dipendenza funzionale di $R_n$ avrà come determinante una superchiave, rispettando così le condizioni della BCNF.

Abbiamo visto quindi come, iterando l’algoritmo di normalizzazione, arriveremo necessariamente prima o poi a una relazione in BCNF.

4.5 - 4ª Forma Normale (4NF)

4.6 - 5ª Forma Normale o Forma Normale di Proiezione-Join (5NF o PJNF)

4.7 - 6ª Forma Normale o Forma Normale di Dominio-Chiave (6NF o DKNF)

---

Approfondimento

Fonti:

• 🏫 Lezioni e slide del Prof. Pensa Ruggero Gaetano del corso di Basi di Dati (canale B), Corso di Laurea in Informatica presso l’Università di Torino, A.A. 2024-25:
  • 8. La normalizzazione.
  • 9. La normalizzazione, seconda parte.

Footnotes

1. Questa è la notazione per l’unione di attributi. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸ ↩⁹ ↩¹⁰

2. Ricordiamo che, nel caso della proiezione, può esserci un collasso delle tuple duplicate. ↩ ↩² ↩³ ↩⁴