Quando si parla di normalizzazione di uno schema di relazione \( R \) ci si riferisce, nell'ambito della progettazione dei modelli relazionali, a tutta una serie di procedure che mirano alla rifinitura di un modello ER, sulla base di ulteriori restrizioni che ci aiutano a modellare, senza ambiguità la realtà e la modellizzazione delle informazioni; i cosiddetti vincoli di integraità - abbreviato VI.

In effetti, per una quasi perfetta implementazione di uno schema di relazione \( R \) il solo modello ER concettuale, non è sufficiente. Vi sono almeno due problematiche di cui bisogna tenere conto. La non consistenza dei dati e la ridondanza. In questo paragrafo parlo di uno strumento estremamente importante per la buona progettazione dei database: le Dipendenze Funzionali

Definizione di dipendenza funzionale

Una dipendenza funzionale abbr: d.f. o DF è essenzialmente un VI generico o se vogliamo, e la generalizzazione del concetto di chiave.

Per capire di cosa si tratta, bisogna darne una definizione rigorosa; vediamo perciò di cosa abbiamo bisogno:

• Una relazione \( {\Large R} \) (una tabella che modella un'entità).
• un insieme \( A = \left\{ A_1, A_2, A_3, \ldots ,A_n \right\} \) di attributi di \( R \),
• Due sottoinsiemi di \( A \): \( X \subset A \) ed \( Y \subset A \).
• Un'istanza di relazione \( r \).
• Una coppia di tuple \( (t_1, t_2) \), di \( r \).

Una d.f. e soddisfatta da un'istanza di relazione \( r \) se vale la \( (\clubsuit) \)
$$ (\clubsuit) \hspace{5mm} {\large \forall (t_1, t_2) | t_1 \in r, t_2 \in r, \forall A_i \in X \wedge \forall A_j \in Y }, $$ $$ {\Large t_1[A_i] = t_2[A_i] \Longrightarrow t_1[A_j] = t_2[A_j] } $$ Si dice allora che che \( X \) determina \( Y \) e si scrive \( {\Large X \rightarrow Y } \)

In soldoni: prese due tuple diverse della tabella \( r \) dire che \( X \rightarrow Y \) significa che \( Y \) è funzione degli attributi di \( X \). Ogni qualvolta uno o più attributi di \( X \) sono uguali in tuple diverse, necessariamente i rispettivi attributi in \( Y \) devono anch'essi coincidere nelle medesime tuple. In basso riporto un esempio chiarificatore:

Consideriamo la seguente istanza di relazione \( r \) rappresentata da una tabella

Possiamo dire guardando la figura che vale la seguente d.f. : \( AB \rightarrow C \).
Nell'esempio \( X = AB, Y = C \) e si vede che nella prima e nella seconda riga ogni volta che \( A = a_1 \wedge B = b_1 \Rightarrow C = c_1 \), quindi \( AB \rightarrow C \). Non vale, invece, ad esempio \( A \rightarrow B \) perche se guardiamo la prima e la terza riga o la seconda e la terza ( anche se le prime due vanno bene) accade che \( t_1[A_1] = a_1 \rightarrow t_1[B_1] = b_1 \) ma \( t_3[A_1] = a_1 \rightarrow t_3[B_1] = b_2 \neq b_1 \), quindi \( A \nrightarrow B \).
Un'istanza di relazione che soddisfa tutte le d.f viene detta istanza legale .

---

Chiusura di un insieme di d.f.: Assiomi di Armstrong

In generale ad ogni schema di relazione \( R \) è associato un insieme di d.f. \( \mathcal{F} \). La cosa fondamentale da capire è che su \( R \) oltre alle d.f. di \( \mathcal{F} \), valgono moltre alre d.f. (dipendenti logicamente) da quelle contenute in \( \mathcal{F} \). Diamo quindi la definizione di Chiusura di un insieme di d.f. \( {\large \mathcal{F}^{+} } \)

La chiusura di \( \mathcal{F} \) indicata con \( {\large \mathcal{F}^{+} } \) è l'insieme di tutte le d.f. implicate logicamente dalle dipendenze contenute in \( \mathcal{F} \): in simboli
$$ {\Large \mathcal{F}^{+} \doteq \left\{ X \rightarrow Y \hspace{2mm}|\hspace{2mm} \mathcal{F} \models X \rightarrow Y \right\} } $$

E' possibile dimostrare che attraverso un numero finito di regole fondamentali: gli Assiomi di Armstrong è possibile inferire tutte le d.f. implicate da un insieme \( \mathcal{F} \), determinarne cioè la sua chiusura. Gli assiomi sono 3 e vengono di seguito presentati

Assiomi di Armstrong

• Riflessività : Se \( X \subset Y \Rightarrow X \rightarrow Y\)
• Aumento : Se \( X \rightarrow Y \Rightarrow XZ \rightarrow YZ\)
• Transitività : Se \( X \rightarrow Y \wedge Y \rightarrow Z \Rightarrow X \rightarrow Z\)

Due proprietà fondamentali, conseguenza immediata degli assiomi sono le 2 proprieta qui espresse

• Composizione : Se \( X \rightarrow Y \wedge X \rightarrow Z \Rightarrow X \rightarrow YZ\)
• Decomposizione : Se \(X \rightarrow YZ \Rightarrow X \rightarrow Y \wedge X \rightarrow Z\)

Chiusura degli attributi

Determinare tutte le d.f. a partire da un insieme finito \( \mathcal{F} \) usando i soli assiomi testè enunciati, pur se possibile è molto oneroso. Se vogliamo controllare ad esempio l'appartenenza o no di una d.f. alla chiusura \( {\large \mathcal{F}^{+} } \), possiamo farlo in maniera più efficiente determinando la chiusura sugli attributi \( X \) rispetto ad \( \mathcal{F} \). Per calcolare la chiusura \( X^{+} \) di un insieme di attributi \( X \) rispetto ad un insieme di d.f. \( \mathcal{F} \) bisogna eseguire i seguenti passi:

1. \( X^{+} = X^{(0)} \) (inizializziamo la chiusura con l'insieme di attributi inizialmente contenuti in \( X \).
2. Se \( \exists X \rightarrow Y \in \mathcal{F} : A_i \in Y \wedge X \subseteq X^{i} \Rightarrow X^{i+1} = X^{i} \cup \left\{A_i\right\} \) ( Se esiste una d.f. in \( \mathcal{F} \) i cui attributi dell'insieme \( X \) a sinistra fanno parte della chiusura corrente \( X^{i} \) al passo i-esimo allora aggiungi alla chiusura corrente tutti gli attributi di \( Y \) ottenendo la nuova chiusura \( X^{i+1} \) ).
3. Ripeti (2) fintantochè \( X^{i} \equiv X^{i+1} \).