7.33

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

$$\begin{gathered} AB\to CD \\ ADE\to GDE \\ B\to GC \\ G\to DE \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$, along with an explanation of the steps you took to generate it.

c. The remaining steps of the algorithm, with explanation.

d. The final decomposition.

---

a. A list of all candidate keys.

$$\begin{gathered} (AB{)}^{+}=\{A,B,C,D,E,G\}=R \\ (A{)}^{+}=\{A\}\ne R \\ (B{)}^{+}=\{B,C,D,E,G\}\ne R \end{gathered}$$

Therefore, $AB$ is a candidate key (minimal superkey).

$$\begin{gathered} (ADE{)}^{+}=\{A,D,E,G\}\ne R \\ (G{)}^{+}=\{D,E,G\}\ne R \end{gathered}$$

I think $AB$ is the only candidate key.

TODO: Prove it!

b. A canonical cover for $F$, along with an explanation of the steps you took to generate it.

We use the algorithm given on Figure 7.9.

Set $F_c=F=\{AB\to CD,ADE\to GDE,B\to GC,G\to DE\}$.

Use the union rule to replace any dependencies in $F_c$ of the form ${\alpha }_1\to {\beta }_1$ and ${\alpha }_1\to {\beta }_2$ with ${\alpha }_1\to {\beta }_1{\beta }_2$.

But looking at the functional dependencies given in $F_c$ we see that there are no such dependencies.

Now, we find a functional dependency $\alpha \to \beta$ in $F_c$ with an extraneous attribute either in $\alpha$ or in $\beta$. If an extraneous attribute is found, we delete it from $\alpha \to \beta$ in $F_c$. We continue this iteration until $F_c$ does not change.

Looking at the functional dependency $AB\to CD$ we see that $C$ is extraneous. Since the functional dependency $B\to C$ can be inferred from the functional dependency $(B\to GC)\in F_c$ by the Decomposition rule.

So the current state of $F_c$ looks like:-

$$F_c=\{AB\to D,ADE\to GDE,B\to GC,G\to DE\}$$

We see that $E$ on the right hand side of the functional dependency $ADE\to GDE$ is extraneous. So let’s delete that one. Then $F_c$ becomes:-

$$F_c=\{AB\to D,ADE\to GD,B\to GC,G\to DE\}$$

Attribute $D$ on the right hand side of the functional dependency $ADE\to GD$ is also extraneous. So $F_c$ becomes:-

$$F_c=\{AB\to D,ADE\to G,B\to GC,G\to DE\}$$

By using the functional dependencies $B\to GC,G\to DE$ and Decomposition rule followed by Transitivity rule, it can be shown that $B\to D$ holds. Thus we can delete the functional dependency $AB\to D$.

$$F_c=\{ADE\to G,B\to GC,G\to DE\}$$

Since we can not find any other extraneous attributes, we claim that $F_c$ is a canonical cover for $F$.

c. The remaining steps of the algorithm, with explanation.

Define $F_c:=\{ADE\to G,B\to GC,G\to DE\}$

Define
$R_1:=\{A,D,E,G\}$
$R_2:=\{B,C,G\}$
$R_3:=\{D,E,G\}$

We see that none of the schemas $R_i\forall i,1\le i\le 3$ contains a candidate key. Thus we define $R_4$ as:

$R_4:=\{A,B\}$

Then we delete $R_3$ since $R_3\subseteq R_1$.

Thus the follwing is a 3NF decomposition of our schema $R$.

$$\{R_1,R_2,R_4\}=\{\{A,D,E,G\},\{B,C,G\},\{A,B\}\}$$

d. The final decomposition.

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