Esempio 5
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 C \\ CB \rightarrow D \\ F \rightarrow B \\ AC \rightarrow E \\ G \rightarrow H \\ D \rightarrow G \\ E \rightarrow ABF \\ C \rightarrow F \\ H \rightarrow G \end{pmatrix} \right\rangle $$
\(
\mathcal{F} =
\begin{pmatrix}
AB \rightarrow C \\
CB \rightarrow D \\
F \rightarrow B \\
AC \rightarrow E \\
G \rightarrow H \\
D \rightarrow G \\
E \rightarrow ABF \\
C \rightarrow F \\
H \rightarrow G
\end{pmatrix} \underset { \underset{{\Huge f.s.}}{\uparrow} }{\longrightarrow}
\)
\(
\mathcal{\hat{F}} =
\begin{pmatrix} \\
AB \rightarrow C \\
CB \rightarrow D \\
F \rightarrow B \\
AC \rightarrow E \\
G \rightarrow H \\
D \rightarrow G \\
E \rightarrow A \\
E \rightarrow B \\
E \rightarrow F \\
C \rightarrow F \\
H \rightarrow G
\end{pmatrix} \underset { \underset{{\Huge r. SX, e.rid}}{\uparrow} }{\longrightarrow}
\)
\(
\require{cancel}
\mathcal{\hat{F}'} =
\begin{pmatrix} \\
AB \rightarrow C \\
C\bcancel{B} \rightarrow D \\
F \rightarrow B \\
AC \rightarrow E \\
G \rightarrow H \\
D \rightarrow G \\
E \rightarrow A \\
\bcancel{E \rightarrow B }\\
E \rightarrow F \\
C \rightarrow F \\
H \rightarrow G
\end{pmatrix}
\)
$$ {\large C \rightarrow B?: \hspace{1cm} C^{+} = CF\underset{\uparrow}{B} } $$ $$ {\Large E}^{+}_{\mathcal{\hat{F}'} - \left\{ E \rightarrow B \right\} } {\large = EAF\underset{\uparrow}{B}} $$ $${\Large E}^{+}_{\mathcal{\hat{F}'} - \left\{ E \rightarrow B, E \rightarrow F \right\} } {\large = EA} $$ $$ {\Large E}^{+}_{\mathcal{\hat{F}'} - \left\{ E \rightarrow B, C \rightarrow F \right\} } {\large = CDGH} $$
Copertura minima
\(
\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}
\)
Chiavi
$$ Keys(g) = \left\{ AB, E, AF, AC \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.
