Esempio 2
Copertura minima
Sia assegnato uno schema di relazione \( R \) ed un insieme \( \mathcal{F} \) di d.f.\( \rightarrow \) Determinare una copertura minima di \( \mathcal{F} \) e le chiavi candidate di \( R \) $$ \left\langle R(ABCDEFGHI), \mathcal{F} = \begin{pmatrix}\\ BG \rightarrow C \\ CF \rightarrow I \\ C \rightarrow ABE \\ AD \rightarrow F \\ E \rightarrow DG \\ D \rightarrow H \\ F \rightarrow B \\ GF \rightarrow H \end{pmatrix} \right\rangle $$
\(
\mathcal{F} =
\begin{pmatrix}\\
BG \rightarrow C \\
CF \rightarrow I \\
C \rightarrow ABE \\
AD \rightarrow F \\
E \rightarrow DG \\
D \rightarrow H \\
F \rightarrow B \\
GF \rightarrow H
\end{pmatrix} \underset { \underset{{\Huge f.s.}}{\uparrow} }{\longrightarrow}
\)
\(
\mathcal{\hat{F}} =
\begin{pmatrix}
BG \rightarrow C \\
CF \rightarrow I \\
C \rightarrow A \\
C \rightarrow B\\
C \rightarrow E \\
AD \rightarrow F \\
E \rightarrow D \\
E \rightarrow G\\
D \rightarrow H \\
F \rightarrow B \\
GF \rightarrow H
\end{pmatrix} \underset { \underset{{\Huge r. SX, e.rid}}{\uparrow} }{\longrightarrow}
\)
\(
\require{cancel}
\mathcal{\hat{F}'} =
\begin{pmatrix}\\
BG \rightarrow C \\
C\bcancel{F} \rightarrow I \\
C \rightarrow A \\
\bcancel{C \rightarrow B}\\
C \rightarrow E \\
AD \rightarrow F \\
E \rightarrow D \\
E \rightarrow G\\
D \rightarrow H \\
F \rightarrow B \\
\bcancel{GF \rightarrow H}
\end{pmatrix}
\)
$$ {\large F \rightarrow C?: \hspace{1cm} F^{+} = ABEDGH\underset{\uparrow}{F} } $$ $$ {\large D \rightarrow A?: \hspace{1cm} D^{+} = DH } $$ $$ {\large {\Large C}^{+}_{\mathcal{\hat{F}'} - \left\{ C \rightarrow B \right\} } {\large = CAEDGF\underset{\uparrow}{B}} \hspace{1cm} {\Large GF}^{+}_{\mathcal{\hat{F}'} - \left\{ GF \rightarrow H, C \rightarrow B \right\} } {\large = GFBCIAED\underset{\uparrow}{H}} }$$
Copertura minima
\(
\mathcal{F}_{min} =
\begin{pmatrix}
BG \rightarrow C \\
C \rightarrow IAE \\
AD \rightarrow F \\
E \rightarrow DG \\
D \rightarrow H \\
F \rightarrow B \\
\end{pmatrix}
\)
Chiavi
$$ Keys(g) = \left\{ BG, C, FG, ADG, AE, BE \right\} $$
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.
