7.34

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

$$\begin{gathered} AB\to CD \\ D\to C \\ DE\to B \\ DEH\to AB \\ AC\to DC \end{gathered}$$

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

a. A list of all candidate keys

b. A canonical cover for $F$

c. The steps of the algorithm, with explanation

d. The final decomposition

---

a. 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?

b. A canonical cover for $F$

Set

$$F_c:=F=\{AB\to CD,D\to C,DE\to B,DEH\to AB,AC\to DC\}$$

$C$ is extraneous in the right hand side of $AC\to DC$

$$F_c=\{AB\to CD,D\to C,DE\to B,DEH\to AB,AC\to D\}$$

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

$$F_c=\{AB\to D,D\to C,DE\to B,DEH\to AB,AC\to D\}$$

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

$$F_c=\{AB\to D,D\to C,DE\to B,DEH\to A,AC\to D\}$$

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

$$F_c=\{AB\to D,D\to C,DE\to B,DEH\to A,AC\to D\}$$

c. The steps of the algorithm, with explanation

Define $F_c:=\{AB\to D,D\to C,DE\to B,DEH\to A,AC\to 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\le i\le 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\}\}$$

d. The final decomposition

$$\{\{A,B,D\},\{B,D,E\},\{A,D,E,H\},\{A,C,D\},\{D,E,G,H\}\}$$