Esempio 1
Sia assegnata una copertura minima di un insieme di d.f. \( \mathcal{F} \) e le chiavi candidate di \( R \) insieme al grafo delle dipendenze.
Determinare una decomposizione BCNF.
$$
\mathcal{F}_{min} =
\begin{pmatrix}
AB \rightarrow C \\
DE \rightarrow B \\
F \rightarrow ADEG \\
C \rightarrow F \\
G \rightarrow H \\
H \rightarrow G
\end{pmatrix}
$$
$$ Keys(g) = \left\{ DE, I, DF, DG, AF, ABCE \right\} $$
$$ R(ABCDEFGH) $$
$$ \overbrace{
X = AD \\
Y = AD^{+} - AD = FB \\
Z = CEGHI
}
$$
$$ R_1(AB) $$
$$
A \rightarrow B$$
$$ R_2(AECDFGH) $$
$$ \begin{align}
AD \rightarrow E \\
EF \rightarrow G \\
C \rightarrow DF \\
E \rightarrow A \\
F \rightarrow CH\\
G \rightarrow E
\end{align} $$
$$ R_2(AECDFGH) $$
$$ \overbrace{
X = F \\
Y = F^{+} - F = HC \\
Z = AEDG
}
$$
$$ R_3(AECDGF) $$
$$ \begin{align}
EF \rightarrow G \\
F \rightarrow D \\
G \rightarrow E \\
E \rightarrow A \\
AD \rightarrow E
\end{align} $$
$$ R_4(FHC) $$
$$ \begin{align}
F \rightarrow CH \\
C \rightarrow F
\end{align} $$
$$ R_3(ACDEFG) $$
$$ \overbrace{
X = F \\
Y = F^{+} - F = D \\
Z = AEG
}
$$
$$ R_5(FD) $$
$$ F \rightarrow D $$
$$ R_6(FAEG) $$
$$ \begin{align}
AF \rightarrow E \\
EF \rightarrow G \\
G \rightarrow E \\
E \rightarrow A
\end{align} $$
$$ R_6(FAEG) $$
$$ \overbrace{
X = E \\
Y = E^{+} - E = A \\
Z = FG
}
$$
$$ R_7(EA) $$
$$ E \rightarrow A $$
$$ R_8(EFG) $$
$$ \begin{align}
EF \rightarrow G \\
EF \rightarrow E \\
G \rightarrow E
\end{align} $$
$$ R_8(EFG) $$
$$ \overbrace{
X = G \\
Y = G^{+} - G = E \\
Z = F
}
$$
$$ R_9(GE) $$
$$ G \rightarrow E $$
$$ R_{10}(GF) $$
$$ FG \rightarrow G $$
References
[1] - Jeffrey D. Ullman, Basi di dati e basi di conoscenza,
Gruppo Editoriale Jackson S.p.a, Milano 1991, pagg. 430-481
[2] - R. Ramakrishnan - J. Gehrke, Sistemi di basi di dati,
McGraw Hill, Milano 2004, pagg. 157-165, 175.
