# Finding the Candidate Keys of a Relation Using the FD's

I have definitely checked out many different related posts. I have also done different sample problems from online sources as well from a similar problem. However, I am stuck on the problem below specifically.

Given the following relation $R$ and the set of functional dependencies $S$ that hold on $R$, find all candidate keys for $R$. Show your work.

$R(A, B, C, D, E, F)$

$S:$

$AB \rightarrow C$

$AC \rightarrow B$

$AD \rightarrow E$

$BC \rightarrow A$

$E \rightarrow F$

Initially, I broke the attributes into groups: attributes found only on the left, only on the right, and on both sides (they are $D$, $ABCE$, and $F$ respectively). I also know that I should try to compute the closure of $D$. This is where I get stuck. At first glance, this seems like I am unable to solve this problem, which isn't true. I also tried computing the closures of $(AD)$, $(BD)$, $(CD)$, and $(ED)$ because I thought that the closure of $D = D$. Any thoughts?

## 2 Answers

You are right to start with the closures of the attributes. Finding the closures will help with finding the candidate keys.

There might be more efficient ways to go about this. What works for me at least is to look at the given functional dependencies. If none of them have single attributes on the left-hand side, then don't bother with finding the closures of the individual attributes-- they will just be themselves. I.e. given R(A,B,C) and FDs A,B->C and B,C->A, the closures of each individual attribute {A}+, {B}+, and {C}+, will be, respectively, {A}, {B}, {C}.

Here, though, you have one FD that has a single-attribute on its left-hand side: E->F. The closure of {E}+ is E itself plus whatever E can determine, which is F, thus {E}+ = {E,F}.

Now, you have figured out the closures of the individual attributes. But that doesn't go far since the rest of the FDs have two attributes on their left-hand sides. You can then calculate the closure of, say, {A,B}+. Automatically you can add A and B into that closure since each attribute determines itself. Now look to the set of given FDs and you see that there is one that goes A,B->C. Since you already have A and B inside the closure (you have all of the attributes on the FD's left-hand side in your closure) then you can add whatever attributes are on the right-hand side into your closure. So now the closure of {A,B}+ = {A,B,C}.

Essentially you keep building larger closures with the ultimate goal of finding closures that encompass the entire set of attributes.

In this case, the candidate keys (there are three) all have three-attributes each. Try calculating the closure of {A,B,D}+. You know automatically that A,B,D should go inside it. You can also add whatever attributes are in closures that are subsets of {A,B,D}+, such as {A,B}+ from before. Thus, you can add C to the closure which now looks like {A,B,C,D}. Now check the list of given FDs again and you will see that A,D->E can now be added, since A and D are inside the closure. Thus, the closure is now {A,B,C,D,E}. Finally, you can add in the FD of E->F. And that completes the set of attributes of the relation.

Here is a useful tool for checking your work: http://raymondcho.net/RelationalDatabaseTools/RelationalDatabaseTools.html

You can use it to check your work on calculating closures and candidate keys.

Follow the following steps :

1> Check which attributes are not present in RHS of the Functional Dependencies (FDs).These attributes cannot be derived and have to present in all the candidate keys. {D in this case}

2> Check closure of D. D- {D} D cannot derive all other attributes => not candidate key

3> Start checking closure of pairs of 2 attributes that include D. (AD,BD,CD) Closure(AD)-{A,D,E,F} cannot derive all other attributes=> not candidate key Closure(BD)-{B,D} not candidate key Closure(CD)-{C,D} not candidate key

4> Start checking closure of chunk of 3 attributes that include D. (ABD,BCD,ACD) Closure(ABD)-{A,B,D,C,E,F} all attributes covered => Candidate key Closure (BCD)-{B,C,D,A,E,F} all attributes covered => Candidate key Closure(ACD)- {A,C,D,E,F,B} all attributes covered => Candidate Key

5> Start checking closure of chunk of 4 attributes that include D. (ABCD) But ABCD is a super key of ABD (OR BCD OR ACD) and cannot be a candidate key.

Thus the candidate keys here are ABD,BCD and ACD.