Proiezione

Dato un insieme di dipendenze $F$ in $R$, la proiezione $\Pi_{R_i} (F)$ di $F$ su $R_i$ (sottoinsieme di $R$) è l’insieme di dipendenze $X \to Y$ in $F^+$ tale che gli attributi in $X \cup Y$ sono tutti contenuti in $R_i$

Dependency preserving

<aside> <img src="/icons/exclamation-mark_purple.svg" alt="/icons/exclamation-mark_purple.svg" width="40px" />

Una decomposizione $D= \{R_1,..,R_m\}$ di $R$ è dependency preserving rispetto a $F$ se l’unione delle proiezioni di $F$ su ciascun $R_i$ in $D$ è equivalente a $F$, cioè $((\Pi {R_1}(F) \cup ..\cup (\Pi{R_m}(F)))^+ = F^+$

</aside>

Proposizione 1

È sempre possibile trovare una decomposizione dependency preserving $D$ rispetto a $F$ tale che ogni $R_i$ in $D$ è in 3NF

Copertura minimale

Un insieme di dipendenze funzionali $F$ è minimale se:

• ogni dipendenza in $F$ ha un singolo attributo sul lato destro
• non è possibile rimpiazzare una dipendenza $X \to A$ con una dipendenza $Y \to A$ dove $Y$ è un sottoinsieme proprio di $X$ ed avere ancora un insieme di dipendenze che è equivalente ad $F$
• non possiamo rimuovere una dipendenza da $F$ ed ottenere un insieme di dipendenze equivalente ad $F$

<aside> <img src="/icons/exclamation-mark_purple.svg" alt="/icons/exclamation-mark_purple.svg" width="40px" />

Una copertura minimale di un insieme $E$ di dipendenze funzionali è un insieme minimale $F$ di dipendenze che è equivalente ad $E$

</aside>

Algoritmo di decomposizione dependency preserving in 3NF

<aside> <img src="/icons/thought-alert_purple.svg" alt="/icons/thought-alert_purple.svg" width="40px" />

1. trovare una copertura minimale $G$ di $F$
2. per ogni parte sinistra $X$ di una dipendenza funzionale che appare in $G$, creare uno schema di relazione $\{X \cup A_1\cup .. \cup A_m\}$ in $D$ dove $X \to A_1,.., X \to A_m$ sono le sole dipendenze in $G$ aventi $X$ come parte sinistra
3. mettere in uno schema di relazione singolo tutti gli attributi rimanenti, per garantire la proprietà di attribute preservation </aside>

Algoritmo di copertura minimale

<aside> <img src="/icons/thought-alert_purple.svg" alt="/icons/thought-alert_purple.svg" width="40px" />

1. porre $G := F$

2. rimpiazzare ogni dipendenza funzionale $X \to \{A_1,..,A_n\}$ in $G$ con $n$ dipendenze funzionali $X \to A_1,..,X\to A_n$

3. per ogni dipendenza funzionale $X\to A$ in $G$

     per ogni attributo $B$ che è un elemento di $X$
   

   {

   se $\{\{G \backslash\{X \to A\}\} \cup \{(X \backslash \{B\}) \to A\}\}$ è equivalente a $G$

   allora sostituire $X \to A$ con $(X \backslash\{B\}) \to A$ in $G$

   }

4. per ogni dipendenza funzionale rimanente $X \to A$ in $G$

   {

   se $\{G \backslash\{X\to A\}\}$ è equivalente a $G$

   allora rimuovere $X\to A$ da $G$

   }

</aside>