BTREE | Stima livelli di Giuseppe Sottile

Esempio 3

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 \\ C \rightarrow D \\ F \rightarrow B \\ AC \rightarrow E \\ G \rightarrow H \\ D \rightarrow G \\ E \rightarrow AF \\ C \rightarrow F \\ H \rightarrow G \end{pmatrix}$

$Keys(g) = \left\{ AB, E, AF, AC \right\}$

$R(ABCDEFGH)$

$\overbrace{ X = F \\ Y = F^{+} - F = B \\ Z = AECDGH }$

$R_1(FB)$

$F \rightarrow B$

$R_2(FAECDGH)$

$\begin{align} AF \rightarrow C \\ AC \rightarrow E \\ E \rightarrow AF \\ C \rightarrow D \\ H \rightarrow G\\ G \rightarrow H \\ C \rightarrow F \end{align}$

$R_2(FAECDGH)$

$\overbrace{ X = D \\ Y = D^{+} - D = GH \\ Z = AECF }$

$R_3(DAECF)$

$\begin{align} AF \rightarrow C \\ C \rightarrow D \\ AC \rightarrow E\\ E \rightarrow AF \end{align}$

$R_4(DGH)$

$\begin{align} D \rightarrow G \\ G \rightarrow H \\ H \rightarrow G \end{align}$

$R_3(DAECF)$

$\overbrace{ X = C \\ Y = C^{+} - C = DF \\ Z = AE }$

$R_5(CDF)$

$C \rightarrow DF$

$R_6(CAE)$

$\begin{align} AC \rightarrow E \end{align}$

$R_4(DGH)$

$\overbrace{ X = G \\ Y = G^{+} - G = H \\ Z = D }$

$R_7(GH)$

$G \rightarrow H \\ H \rightarrow G$

$R_8(GD)$

$\begin{align} D \rightarrow G \end{align}$

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.