candidate keys from functional dependencies

ranzy picture ranzy · Apr 27, 2010 · Viewed 57.6k times · Source

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

lbrendanl picture lbrendanl · Jan 30, 2013

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,