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 Database Closures - Home page

Go to 2NF, 3NF and BCNF

TOPICS (Click to Navigate)

Pages

Saturday, April 11, 2020