## Finding all candidate keys of a relation, Steps to find the candidate keys of a relational table

##
__Finding candidate keys in a relational table - Solved exercise__

__Question:__
Given the following
relation R and the set of functional dependencies F that hold on R, find all
candidate keys for R.

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

F = {AB → C, AC → B,
AD → E, BC → A, E → F}

__Solution:__
Let us follow the steps
given in the box below to find all the candidate keys of R.

Step 1: Let γ = set of attributes not present in the RHS of
any FD. The
set of attributes in γ must be a part of any candidate key of R.Step 2: Let β = set of attributes appear on RHS but not on
LHS of any FD. The set of attributes in β cannot be a part of any candidate key of R.Step 3: Find closure γ^{+}. if γ^{+} = R,
then γ is the only candidate keyStep 4: If γ^{+} ≠ R, then for each attribute x in
R- β,
·
Test whether γ U {x} is a
candidate key.
·
If not, add
another attribute from R- β to γ and test whether it is a candidate key
·
Repeat this step
until all candidate keys found |

Given,

R
(A, B, C, D, E, F) and F = {AB → C, AC → B, AD → E, BC → A, E → F}

Step 1: Find the
set

*γ*of attributes that are not present in the RHS of any functional dependency.
D is the only
attribute that is not present in RHS of any of the functional dependencies.
Hence, the candidate key(s) must have the attribute D.

*γ*= {D}

Step 2: Find the
attributes that appear on RHS but not on LHS of any FD.

F is the only
attribute that appear on RHS but not on LHS. Hence, F cannot be part of any candidate
keys of R.

β
= {F}

Step 3: Find
closure of γ, ie., γ

^{+}
γ

^{+}= D^{+}= ∅
γ

^{+}≠ R, hence we move on to step 4.
Step 4: Find R- β
and combine each attribute from this set with D and find the closures.

R-
β = {A, B, C, D, E, F} – {F} = { A, B, C, D, E}

Let’s combine D
with each of the element from the above set to test for candidate keys.

**Keep in mind that our candidate keys must consist of D in it but not F**. Let us do one by one as follows;
(AD)

^{+}= AD
= ADE from FD AD → E

= ADEF from FD E → F

≠ R.

Hence, AD is not a
candidate key. We try the others the same way.

(BD)

^{+}= BD ≠ R.
(CD)

^{+}= CD ≠ R.
(DE)

^{+}= DEF ≠ R.
Now let us add one
more attribute to check for candidate keys;

(ABD)

^{+}= ABDCEF = R. Hence, (ABD) is a candidate key.
(ACD)

^{+}= ACDBEF = R. Hence, (ACD) is a candidate key.
(AED)

^{+}= AEDF ≠ R.
(BCD)

^{+}= BCDAEF = R. Hence, (BCD) is a candidate key.
(BED)

^{+}= BEDF ≠ R.
(CED)

^{+}= CEDF ≠ R.

*(ABCD)*^{+}= ABCDEF = R. But (ABCD) is not a candidate key. It is a super key, because its subset consists of keys.

__Result:__
ABD, ACD, and BCD
are the candidate keys of R.

**********

Go back to Normalization – solved exercises page.

Go to How to find closure page

Go to Database Closures - Home page

Go to 2NF, 3NF and BCNF