7.33

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

\[ AB \rightarrow CD \\ ADE \rightarrow GDE \\ B \rightarrow GC \\ G \rightarrow DE \\ \]

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\), along with an explanation of the steps you took to generate it.

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

  4. The final decomposition.

  1. A list of all candidate keys.

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

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

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

I think \(AB\) is the only candidate key.

TODO: Prove it!

  1. 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 \rightarrow CD, ADE \rightarrow GDE, B \rightarrow GC, G \rightarrow DE\}\).

Use the union rule to replace any dependencies in \(F_c\) of the form \(\alpha_1 \rightarrow \beta_1\) and \(\alpha_1 \rightarrow \beta_2\) with \(\alpha_1 \rightarrow \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 \rightarrow \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 \rightarrow \beta\) in \(F_c\). We continue this iteration until \(F_c\) does not change.

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

So the current state of \(F_c\) looks like:-

\[ F_c = \{AB \rightarrow D, ADE \rightarrow GDE, B \rightarrow GC, G \rightarrow DE\} \]

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

\[ F_c = \{AB \rightarrow D, ADE \rightarrow GD, B \rightarrow GC, G \rightarrow DE\} \]

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

\[ F_c = \{AB \rightarrow D, ADE \rightarrow G, B \rightarrow GC, G \rightarrow DE\} \]

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

\[ F_c = \{ADE \rightarrow G, B \rightarrow GC, G \rightarrow DE\} \]

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

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

Define \(F_c := \{ADE \rightarrow G, B \rightarrow GC, G \rightarrow 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 \leq i \leq 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\}\} \]

  1. The final decomposition.

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