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

## Search Engine

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

# Find the candidate keys of a relation in RDBMS

## Find all the candidate keys of relation R - solved exercise

Question:
Find all the candidate keys of R given R and the set F of functional dependencies (FDs) as follows;
R = (a, b, c, d, e) and F = {a → c, c → bd, d → a}

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

Given,
R = (a, b, c, d, e) and F = {a → c, c → bd, d → a}

Step 1: Out of all attributes of R, only {e} is not present in the RHS of any FD. So, A = {e}. And, every candidate key of R must have the attribute e in it.

Step 2: Set of attributes appear on RHS of any FD are a, b, c, and d. Out of them the attributes not appear on the LHS of FDs is b. So, B = {b}. And, the attribute b cannot be part of any candidate key

Step 3: A+ = {e}+ ≠ R. So, let us move on to step 4.

Step 4: Since A+ ≠ R is not a candidate key, then for each attribute x in (R – B) check whether A U {x} is a candidate key or not.
R – B = {a, b, c, d, e} – {b} = {a, c, d, e}
Now, let us combine attributes of A with each attribute of (R-B) and check whether they form a candidate key or not. That is, check whether {a, e}, {c, e} and {d, e} forms candidate key or not using closure of these attribute sets. [Refer how to find closure here, one more solved exercise]
{a, e}+         = {a, e}
= {a, e, c} from FD a → c
= {a, e, c, b, d} from FD c → b d
= R
Hence, {a, e} is a super key and also a candidate key.
{c, e}+ = {c, e, b, d, a} = R, hence a candidate key.
{d, e}+ = {d, e, a, c, b} = R, hence a candidate key.

Result:
The candidate key of R are {a, e}, {c, e} and {d, e}.

**********

Go back to Normalization – solved exercises page.

Go to How to find closure page

Go to 2NF, 3NF and BCNF