Esempio 4
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} ABE \rightarrow C \\ C \rightarrow D \\ DE \rightarrow CF \\ A \rightarrow E \\ D \rightarrow B \\ F \rightarrow ABG \\ G \rightarrow H \\ H \rightarrow G \end{pmatrix} \right\rangle $$
\(
\mathcal{F} =
\begin{pmatrix}
ABE \rightarrow C \\
C \rightarrow D \\
DE \rightarrow CF \\
A \rightarrow E \\
D \rightarrow B \\
F \rightarrow ABG \\
G \rightarrow H \\
H \rightarrow G
\end{pmatrix} \underset { \underset{{\Huge f.s.}}{\uparrow} }{\longrightarrow}
\)
\(
\mathcal{\hat{F}} =
\begin{pmatrix} \\
ABE \rightarrow C \\
C \rightarrow D \\
DE \rightarrow C \\
DE \rightarrow F \\
A \rightarrow E \\
D \rightarrow B \\
F \rightarrow A \\
F \rightarrow B \\
F \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\bcancel{E} \rightarrow C \\
C \rightarrow D \\
\bcancel{DE \rightarrow C }\\
DE \rightarrow F \\
A \rightarrow E \\
D \rightarrow B \\
F \rightarrow A \\
F \rightarrow B \\
F \rightarrow G \\
G \rightarrow H \\
H \rightarrow G
\end{pmatrix}
\)
$$ {\large AB \rightarrow E?: \hspace{1cm} AB^{+} = AB\underset{\uparrow}{E} } $$ $$ {\large D \rightarrow E?: \hspace{1cm} D^{+} = DB } $$ $$ {\Large AB}^{+}_{\mathcal{\hat{F}'} - \left\{ AB \rightarrow C \right\} } {\large = ABE} $$ $${\Large DE}^{+}_{\mathcal{\hat{F}'} - \left\{ DE \rightarrow C \right\} } {\large = DEFAB\underset{\uparrow}{C}} $$ $$ {\Large F}^{+}_{\mathcal{\hat{F}'} - \left\{ F \rightarrow B, DE \rightarrow C \right\} } {\large = FAGHE} $$ $${\Large F}^{+}_{\mathcal{\hat{F}'} - \left\{ F \rightarrow G, DE \rightarrow C \right\} } {\large = FABCDE} $$
Copertura minima
\(
\mathcal{F}_{min} =
\begin{pmatrix}
AB\rightarrow C \\
C \rightarrow D \\
DE \rightarrow F \\
A \rightarrow E \\
D \rightarrow B \\
F \rightarrow ABG \\
G \rightarrow H \\
H \rightarrow G
\end{pmatrix}
\)
Chiavi
$$ Keys(g) = \left\{ AB, AD, F, DE, CE, 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.
