7.34

Consider the schema \(R = (A,B,C,D,E,G,H)\) and the set \(F\) of functional dependencies:

\[ AB \rightarrow CD \\ D \rightarrow C \\ DE \rightarrow B \\ DEH \rightarrow AB \\ AC \rightarrow DC \\ \]

Use the 3NF decomposition algorithm to generate a 3NF decomposition of \(R\), and show your work. This means:

  1. A list of all candidate keys

  2. A canonical cover for \(F\)

  3. The steps of the algorithm, with explanation

  4. The final decomposition

  1. A list of all candidate keys

Candidate keys that I can come up with:-

\[ \{ \{A, B, E, G, H\}, \{D, E, G, H\} \} \]

TODO: Can we prove that these are the only candidate keys?

  1. A canonical cover for \(F\)

Set \[ F_c := F = \{AB \rightarrow CD, D \rightarrow C, DE \rightarrow B, DEH \rightarrow AB, AC \rightarrow DC\} \]

\(C\) is extraneous in the right hand side of \(AC \rightarrow DC\)

\[ F_c = \{AB \rightarrow CD, D \rightarrow C, DE \rightarrow B, DEH \rightarrow AB, AC \rightarrow D\} \]

\(C\) is extraneous in the right hand side of \(AB \rightarrow CD\). This is because \(AB \rightarrow C\) can be inferred from \(AB \rightarrow D\), \(D \rightarrow C\) and Transitivity rule.

\[ F_c = \{AB \rightarrow D, D \rightarrow C, DE \rightarrow B, DEH \rightarrow AB, AC \rightarrow D\} \]

\(B\) is extraneous in \(DEH \rightarrow AB\). This is because \(DEH \rightarrow B\) can be inferred from \(DE \rightarrow B\) and applying Augmentation rule followed by Decomposition rule.

\[ F_c = \{AB \rightarrow D, D \rightarrow C, DE \rightarrow B, DEH \rightarrow A, AC \rightarrow D\} \]

Since I cannot find any more extraneous attributes, the canonical cover of \(F\) is:-

\[ F_c = \{AB \rightarrow D, D \rightarrow C, DE \rightarrow B, DEH \rightarrow A, AC \rightarrow D\} \]

  1. The steps of the algorithm, with explanation

Define \(F_c := \{AB \rightarrow D, D \rightarrow C, DE \rightarrow B, DEH \rightarrow A, AC \rightarrow D\}\)

Define
\(R_1 := \{A, B, D\}\)
\(R_2 := \{C, D\}\)
\(R_3 := \{B, D, E\}\)
\(R_4 := \{A, D, E, H\}\)
\(R_5 := \{A, C, D\}\)

We see that none of the schemas \(R_i \:\: \forall i, 1 \leq i \leq 5\) contains a candidate key. Thus we define \(R_6\) as:

\(R_6 := \{D, E, G, H\}\)

Then we delete \(R_2\) since \(R_2 \subseteq R_5\).

Thus our result is

\[ \{ R_1, R_3, R_4, R_5, R_6 \} = \{ \{A, B, D\}, \{B, D, E\}, \{A, D, E, H\}, \{A, C, D\}, \{D, E, G, H\} \} \]

  1. The final decomposition

\[ \{ \{A, B, D\}, \{B, D, E\}, \{A, D, E, H\}, \{A, C, D\}, \{D, E, G, H\} \} \]