Esempio 1
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(ABCDEFGH), \mathcal{F} = \begin{pmatrix} AB \rightarrow CE \\ DE \rightarrow B \\ F \rightarrow ADE \\ C \rightarrow F \\ BF \rightarrow G \\ G \rightarrow H \\ H \rightarrow G \end{pmatrix} \right\rangle $$
\(
\mathcal{F} =
\begin{pmatrix}
AB \rightarrow CE \\
DE \rightarrow B \\
F \rightarrow ADE \\
C \rightarrow F \\
BF \rightarrow G \\
G \rightarrow H \\
H \rightarrow G
\end{pmatrix} \underset { \underset{{\Huge f.s.}}{\uparrow} }{\longrightarrow}
\)
\(
\mathcal{\hat{F}} =
\begin{pmatrix}
AB \rightarrow C \\
AB \rightarrow E \\
DE \rightarrow B \\
F \rightarrow A \\
F \rightarrow D \\
F \rightarrow E \\
C \rightarrow F \\
BF \rightarrow G \\
G \rightarrow H \\
H \rightarrow G
\end{pmatrix} \underset { \underset{{\Huge r. SX, e.rid}}{\uparrow} }{\longrightarrow}
\)
\(
\require{cancel}
\mathcal{\hat{F}'} =
\begin{pmatrix}\\
AB \rightarrow C \\
\bcancel{AB \rightarrow E }\\
DE \rightarrow B \\
F \rightarrow A \\
F \rightarrow D \\
F \rightarrow E \\
C \rightarrow F \\
\bcancel{B}F \rightarrow G \\
G \rightarrow H \\
H \rightarrow G
\end{pmatrix}
\)
$$ {\large F \rightarrow B?: \hspace{1cm} F^{+} = FADE\underset{\uparrow}{B} } $$ $$ {\large {\Large AB}^{+}_{\mathcal{\hat{F}'} - \left\{ AB \rightarrow E \right\} } {\large = ABCF\underset{\uparrow}{E}} \hspace{1cm} {\Large F}^{+}_{\mathcal{\hat{F}'} - \left\{ AB \rightarrow E, F \rightarrow G \right\} } {\large = FADEBCF} }$$
Copertura minima
\(
\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}
\)
Chiavi
$$ Keys(g) = \left\{ DE, I, DF, DG, AF, ABCE \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.
