Advanced Database Management System - Tutorials and Notes: Find all the candidate keys of a relation

## Search Engine

Please visit, subscribe and share 10 Minutes Lectures in Computer Science

## 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 key Step 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;
= 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 2NF, 3NF and BCNF