Find all the candidate keys of a relation

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 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;

(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

Find all candidate keys of a relation in RDBMS

How to find candidate keys in a relational database for normalization

steps to find candidate keys

Easy way to find candidate keys

Candidate keys solved exercise

Candidate keys for normalization