candidate keys from functional dependencies

Given the Relation R with attributes ABCDE. You are given the follow开发者_如何学编程ing 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.

---

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.

---

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)

---

Use an algorithm;

1.Take any attribute or set of attributes

eg: ACD

2.Take the first mentioned functional dependency

eg: A -> B

3.Is the L.H.S of the dependency a subset of the attribute/s you chose in step 1?

If yes add the R.H.S of the functional dependency to the attribute. If no,ignore this functional dependency.

eg: A is a subset of ACD. So add B to ACD. ACD is now ABCD

4.Now go to the next functional dependency.Repeat step 3.

eg: BC -> E BC is a subset of ABCD. So ABCD is now ABCDE

5.If you have all the attributes now, you can stop.

If you don't have all the attributes, keep going to the next functional dependency and repeat step 3. If you have reached the last functional dependency and do not have all attributes, go back to the first functional dependency and repeat steps 3 and 4. Keep cycling in this loop until the set of attributes you have don't change no matter the functional dependency you repeat step 3 with.

eg: As I have ABCDE for attribute set ACD, I can stop.

If you have all attributes you have a superkey. eg: ACD is a superkey because I have ABCDE.

---

CD is the candidate key, so ACD, BCD, CDE all can be candidate key. C,D do not appear in the right side of any functional dependencies which is why CD is candidate key.

This will help you to understand.