Normalizzazione

Premessa

Portale di appartenenza: Basi di dati.

Cosa troverai in questa nota:

• Un’introduzione al concetto di normalizzazione e del vincolo locale di dipendenza funzionale.
• Una presentazione degli assiomi di Armstrong con le relative regole di inferenza derivanti.

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, denotato con $X\to 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.

2 - 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 - 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 $X_1\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_1\})\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 algoritmi

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

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.

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={\pi }_X(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, per ogni istanza $r$ di $R(A)$ che soddisfa le dipendenze funzionali contenute in $F$, 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 $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{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 $r$ di partenza, 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, per ogni istanza $r$ di $R(A)$ che soddisfa le dipendenze funzionali contenute in $F$, 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, per ogni istanza $r$ di $R(A)$ che soddisfa le dipendenze funzionali contenute in $F$, 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\}$$

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.

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

4.1 - 1ª Forma Normale (1NF)

4.2 - 2ª Forma Normale (2NF)

4.3 - 3ª Forma Normale (3NF)

4.4 - Forma Normale di Boyce-Codd (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)

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. Si legge ”$X$ determina $Y$“. ↩

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

3. Qua è stato usato l’abuso di notazione sulle istanze, per cui è stato dato come argomento all’operatore di proiezione l’istanza $r$ e non la relazione $R(A)$ a cui si riferisce, così come viene considerato come risultato del natural-join un’istanza e non una relazione. ↩

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