## 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 keyStep 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}**, hence a candidate key.

^{+}= {c, e, b, d, a} = R**{d, e}**, hence a candidate key.

^{+}= {d, e, a, c, b} = R

__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

## No comments:

## Post a comment