Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

candidate keys from functional dependencies

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.

like image 632
ranzy Avatar asked Apr 27 '10 02:04

ranzy


People also ask

How do I find candidate keys in a table?

Candidate Key is minimal set of attributes of a relation which can be used to identify a tuple uniquely. For Example, each tuple of EMPLOYEE relation given in Table 1 can be uniquely identified by E-ID and it is minimal as well. So it will be Candidate key of the relation.

How are primary keys related to functional dependencies?

The functional dependency is a relationship that exists between two attributes. It typically exists between the primary key and non-key attribute within a table. The left side of FD is known as a determinant, the right side of the production is known as a dependent.


2 Answers

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,

like image 154
lbrendanl Avatar answered Sep 23 '22 13:09

lbrendanl


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)

like image 24
Agustin Avatar answered Sep 19 '22 13:09

Agustin