Esempio 3
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(ABCDEFG), \mathcal{F} = \begin{pmatrix} AB \rightarrow CG \\ C \rightarrow E \\ D \rightarrow B \\ F \rightarrow G \\ E \rightarrow AF \\ ABF \rightarrow D \end{pmatrix} \right\rangle $$
\(
\mathcal{F} =
\begin{pmatrix}
AB \rightarrow CG \\
C \rightarrow E \\
D \rightarrow B \\
F \rightarrow G \\
E \rightarrow AF \\
ABF \rightarrow D
\end{pmatrix} \underset { \underset{{\Huge f.s.}}{\uparrow} }{\longrightarrow}
\)
\(
\mathcal{\hat{F}} =
\begin{pmatrix} \\
AB \rightarrow C \\
AB \rightarrow G \\
C \rightarrow E \\
D \rightarrow B \\
F \rightarrow G \\
E \rightarrow A \\
E \rightarrow F \\
ABF \rightarrow D
\end{pmatrix} \underset { \underset{{\Huge r. SX, e.rid}}{\uparrow} }{\longrightarrow}
\)
\(
\require{cancel}
\mathcal{\hat{F}'} =
\begin{pmatrix} \\
AB \rightarrow C \\
\bcancel{AB \rightarrow G }\\
C \rightarrow E \\
D \rightarrow B \\
F \rightarrow G \\
E \rightarrow A \\
E \rightarrow F \\
AB\bcancel{F} \rightarrow D
\end{pmatrix}
\)
$$ {\large AB \rightarrow F?: \hspace{1cm} AB^{+} = CGE\underset{\uparrow}{F} } $$ $$ {\Large AB}^{+}_{\mathcal{\hat{F}'} - \left\{ AB \rightarrow G \right\} } {\large = ABCDEF\underset{\uparrow}{G}} $$
Copertura minima
\(
\mathcal{F}_{min} =
\begin{pmatrix}
AB \rightarrow CD \\
C \rightarrow E \\
D \rightarrow B \\
F \rightarrow G \\
E \rightarrow AF \\
\end{pmatrix}
\)
Chiavi
$$ Keys(g) = \left\{ AB, AD, BE, BC, ED, CD \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.
