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
No comments:
Post a Comment