algoritmo di decomposizione in 3NF

Dato uno schema di relazione e un insieme di dipendenze funzionali $G$ su $R$ esiste sempre una decomposizione $\rho =\{R_1,\dots ,R_k\}$ di $R$ che rispetta i criteri di una buona decomposizione in 3NF, cioè:

• ogni $R_i$ è in 3NF,
• $\rho$ preserva $F$,
• $\rho$ ha un join naturale senza perdita.

Tale decomposizione può essere calcolata in tempo polinomiale con un algoritmo che riceve in input una qualunque copertura minimale di $G$, che definiamo $F$.

Input: $R$, $F$.

Output: $\rho$.

1. $S:=\varnothing$
2. for $A$ in $R$: (questa parte serve a selezionare nell‘“accumulatore” $S$ tutte le dipendenze funzionali non coinvolte in nessuna dipendenza funzionale in $F$)
   1. if $A$ non è coinvolto in nessuna dipendenza funzionale in $F$:
      1. $S:=S\cup \{A\}$
3. if $S\ne \varnothing$: (questa parte rimuove tutti gli attributi di $S$ da $R$, inizializzando la decomposizione $\rho$ a $S$)
   1. $R:=R-S$
   2. $\rho :=\rho \cup \{S\}$
4. if esiste $f\in F$ che coinvolge tutti gli attributi in $R$:
   1. $\rho :=\rho \cap \{R\}$
5. else:
   1. for $X\to A$ in $F$:
      1. $\rho :=\rho \cup \{XA\}$

Esempio

Dato $R=\{A,B,C,D,E,H\}$ e $F=\{AB\to CD,C\to E,AB\to E,ABC\to D\}$

Verifica che $ABH$ è una chiave per $R$.

• $ABH$ deve determinare funzionalmente tutto lo schema: vero, perché la chiusura di $ABH$ coincide con $R$.
• Nessun sottoinsieme di $ABH$ deve determinare funzionalmente l’intero schema: vero, perché considerando che la chiave deve avere sicuramente $H$, $A{H}^{+}$ e $B{H}^{+}$ non coincidono con $R$.

Sapendo che $ABH$ è l’unica chiave per $R$, verifica che $R$ non è in 3NF.

Esistono le dipendenze parziali $AB\to CD$ e $AB\to E$, quindi $R$ non può essere in 3NF.

Trova una copertura minimale $G$ di $F$.

Primo passo: decomporre i determinati in singleton

$$G=\{AB\to C,AB\to D,C\to E,AB\to E,ABC\to D\}$$

Secondo passo: rimuovere gli attributi superflui dei determinanti:

• $AB\to C$: $A_F^{+}=\{A\},B_F^{+}=\{B\}$, quindi $C\notin A_F^{+},B_F^{+}$. Nessun attributo è ridondante.
• $AB\to D$: $A_F^{+}=\{A\},B_F^{+}=\{B\}$, quindi $D\notin D_F^{+},B_F^{+}$. Nessun attributo è ridondante.
• $C\to E$: È atomica, quindi nessun attributo può essere rimosso.
• $AB\to E$: $A_F^{+}=\{A\},B_F^{+}=\{B\}$, quindi $E\notin D_F^{+},B_F^{+}$. Nessun attributo è ridondante.
• $ABC\to D$: $A{B}_F^{+}=\{AB,C,D,E\},C_F^{+}=\{C,E\}$, quindi $D\in A{B}_F^{+}$ (perché esiste $AB\to D$ in $F$). $C$ è ridondante, quindi possiamo ridurre la dipendenza a $AB\to D$, che esiste già in $F$.

$$G=\{AB\to C,AB\to D,C\to E,AB\to E\}$$

Terzo passo: rimuovere le dipendenze ridondanti:

• Rimuovendo $AB\to C$ si altererebbe $A{B}^{+}=\{AB,C,D,E\}$, quindi la dipendenza non è ridondante.
• Rimuovendo $AB\to D$ si altererebbe $A{B}^{+}=\{AB,C,D,E\}$, quindi la dipendenza non è ridondante.
• Rimuovendo $C\to E$ si altererebbe $C^{+}=\{C,E\}$, quindi la dipendenza non è ridondante.
• Rimuovendo $AB\to E$ non si altererebbe $A{B}^{+}=\{AB,C,D,E\}$, quindi la dipendenza $AB\to E$ è ridondante (tra l’altro è ottenuta per transitività da $AB\to C\wedge C\to E$)

$$G=\{AB\to C,AB\to D,C\to E\}$$

Trova una decomposizione $\rho$ di $R$ tale che preserva $G$ e ogni schema in $\rho$ è in 3NF.

Iniziamo l’algoritmo: per prima cosa $H\notin G⟹\rho =\{H\},R=\{A,B,C,D,E\}$. Non ci sono dipendenze che coinvolgono tutti gli attributi dello schema, quindi eseguiamo l’istruzione 5. dell’algoritmo, ottenendo $\rho =\{H,ABC,ABD,CE\}$.

Trova una decomposizione $\sigma$ di $R$ tale che preserva $G$ e ogni schema in $\sigma$ è in 3NF.

per avere una decomposizione con join senza perdita, aggiungiamo alla decomposizione precedente un sottoschema che contenga la chiave $ABH$ (che non è già contenuta in alcuno degli schemi ottenuti)

Dimostrazione della correttezza dell’algoritmo

todo pag. 5 pdf 19