7.6

Compute the closure of the following set \(F\) of functional dependencies for relation schema \(R = (A, B, C, D, E)\). \[ A \rightarrow BC \\ CD \rightarrow E \\ B \rightarrow D \\ E \rightarrow A \]

List the candidate keys for \(R\).


Note: It is not reasonable to expect students to enumerate all of \(F^+\). Some shorthand representation of the result should be acceptable as long as the nontrivial members of \(F^+\) are found.

Starting with \(A \rightarrow BC\), we can conclude that: \(A \rightarrow B\) and \(A \rightarrow C\).

Since \(A \rightarrow B\) and \(B \rightarrow D\), \(A \rightarrow D\) (decomposition, transitive)

Since \(A \rightarrow CD\) and \(CD \rightarrow E\), \(A \rightarrow E\) (union, decomposition, transitive)

Since \(A \rightarrow A\), we have \(A \rightarrow ABCDE\) from the above steps (reflexive, union)

Since \(E \rightarrow A\), \(E \rightarrow ABCDE\) (transitive)

Since \(CD \rightarrow E\), \(CD \rightarrow ABCDE\) (transitive)

Since \(B \rightarrow D\) and \(BC \rightarrow CD\), \(BC \rightarrow ABCDE\) (augmentative, transitive)

Also, \(C \rightarrow C\), \(D \rightarrow D\), \(BD \rightarrow D\), etc.

Therefore, any functional dependency with \(A, E, BC\) or \(CD\) on the left-hand side of the arrow is in \(F^+\), no matter which other attributes appear in the functional dependency. Allow \(*\) to represent any set of attributes in \(R\), the \(F^+\) is \(BD \rightarrow B\), \(BD \rightarrow D\) , \(C \rightarrow C\), \(D \rightarrow D\), \(BD \rightarrow BD\), \(B \rightarrow D\), \(B \rightarrow B\), \(B \rightarrow BD\), and all functional dependencies of the form \(A* \rightarrow \alpha\), \(BC* \rightarrow \alpha\), \(CD * \rightarrow \alpha\), \(E * \rightarrow \alpha\) where \(\alpha\) is any subset of \(\{A, B, C, D, E\}\). The candidate keys are \(A\), \(BC\), \(CD\), and \(E\).