candidate keys from functional dependencies

Question

Given the Relation R with attributes ABCDE. You are given the following dependencies: A -> B, BC -> E, and ED -> A. I already have the answer which is CDE, ACD, and BCD. I just need to know how to do it. Thanks.

Answer 1

A candidate key is a minimal superkey. In other words, there are no superflous attributes in the key. The first step to finding a candidate key, is to find all the superkeys. For those unfamiliar, a super key is a set of attributes whose closure is the set of all atributes. In other words, a super key is a set of attributes you can start from, and following functional dependencies, will lead you to a set containing each and every attribute.

Since we have the functional dependencies: A -> B, BC -> E, and ED -> A, we have the following superkeys:

• ABCDE (All attributes is always a super key)
• BCED (We can get attribute A through ED -> A)
• ACDE (Just add B through A -> B)
• ABCD (Just add E through BC -> E)
• ACD (We can get B through A -> B, and then we can get E through BC -> E)
• BCD (We can get E through BC -> E, and then A from ED -> A)
• CDE (We can get A through ED -> A and then B from A -> B)

(One trick here to realize, is that since C and D never appear on the right side of a functional dependency, every key must include both C and D)

Now that we have all our super keys, we can see that only the last three are candidate keys. Since the first four can all be trimmed down. But we cannot take any attributes away from the last three superkeys and still have them remain a superkey.

Thus the candidate keys are: ACD, BCD, and CDE.

Hope that helps,

Answer 2

To find the candidate key you need to split the FD's into attributes into Left, Middle, Right - The Left includes attributes that only show up in the left hand side (CD) - The Middle includes attributes that show up in both left and right (ABE) - The Right includes attribues that only show up in the right hand side (none)

Now find the closure of attributes from the Left: * CD+ -> CD Since we do not get all the attributes of the relation we need to add the Middle attributes (ABE) one at a time and try to find the closure again.

So: * CDA+ -> CDABE (CDA is a candidate key) * CDB+ -> CDBEA (CDB is a candidate key) * CDE+ -> CDEAB (CDE is a candidate key)