7.32

Consider the schema \(R = (A,B,C,D,E,G)\) and the set \(F\) of functional dependencies: \[ A \rightarrow BC \\ BD \rightarrow E \\ CD \rightarrow AB \\ \]

  1. Find a nontrivial functional dependency containing no extraneous attributes that is logically implied by the above three dependencies and explain how you found it.

  2. Use the BCNF decomposition algorithm to find a BCNF decomposition of \(R\). Start with \(A \rightarrow BC\). Explain your steps.

  3. For your decomposition, state whether it is lossless and explain why.

  4. For your decomposition, state whether it is a dependency preserving and explain why.

  1. Find a nontrivial functional dependency containing no extraneous attributes that is logically implied by the above three dependencies and explain how you found it.

I claim that such a functional dependency does NOT exist. Suppose to the contrary that such a functional dependency exists. Say \(\alpha \rightarrow \beta\). Thus \(\alpha \rightarrow \beta\) is a nontrivial functional dependency containing no extraneous attributes and it is logically implied by \(F\). Define \(F_1 := F \cup \{ \alpha \rightarrow \beta \}\). Now consider an attribute \(X \in \beta\). I am going to prove that \(X\) is extraneous.

Consider the set

\[ F_1' = (F_1 - \{\alpha \rightarrow \beta\}) \cup \{\alpha \rightarrow (\beta - X)\} \]

Since the functional dependency \(\alpha \rightarrow X\) can be inferred from \(F_1'\) (in fact the whole \(\alpha \rightarrow \beta\) can be inferred from \(F \subset F_1'\)) \(X\) is extraneous in \(\beta\).

Thus such a functional dependency does NOT exist.

  1. Use the BCNF decomposition algorithm to find a BCNF decomposition of \(R\). Start with \(A \rightarrow BC\). Explain your steps.

We use the algorithm given on Figure 7.11.

By using the functional dependency \(A \rightarrow BC\) we decompose the schema into

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

Note that \(\{A, B, C\}\) is in BCNF. By applying Augmentation rule followed by Transitivity rule on the functional dependencies given in \(F\), we see that the functional dependency \(AD \rightarrow E\) holds. We use that to decompose the schema \(\{A, D, E, G\}\), into $ {A, D, G} $ and $ {A, D, E} $.

Thus,

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

form a BCNF decomposition of \(R\).

  1. For your decomposition, state whether it is lossless and explain why.

The decomposition that the algorithm given on Figure 7.11 generates is always a lossless decomposition. Thus our decomposition is a lossless decomposition.

  1. For your decomposition, state whether it is a dependency preserving and explain why.

Our decomposition is not dependency preserving. The functional dependency \(BD \rightarrow E\) is not preserved (we used the second test given in section 7.4.4)