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

# How to find candidate keys in a relational database for normalization

## Featured Content

### Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

data recovery