Find the candidate keys of a relation, How to find the candidate keys, Which is the key for the given table, concept of candidate key in dbms, candidate key examples
Question:
Consider the relation R = {A, B, C, D, E, F, G, H, I,
J} and the set of functional dependencies F = {AB → C, A → DE, B → F, F → GH, D → IJ}. Find the key
of relation R.
We can find keys (candidate keys) for a relation by
finding the closure
of an/set of attributes. Checking each attribute or all subsets of the given
set of attributes for a key is time consuming job. Hence, we may employ some of
the following heuristics/assumptions in identifying the keys;
 We may start checking all the left hand side attributes of any/all of the given set of functional dependencies. We can start with single LHS attributes.
 If we find the closure of an attribute and that attribute is the candidate key then any superset cannot be the candidate key. For example, if A is a candidate key, then AB is not a candidate key but a super key.
LHS

Result

Description

A^{+}

= ADE from
the functional dependency A → DE
(By
reflexivity rule)
= ADEIJ
from D → IJ (By transitivity rule.
A → D and D → IJ hence A → IJ)
No
more functional dependencies that has either of the attributes ADEIJ in LHS. Hence,
A+ = ADEIJ.

A^{+} ≠ R.
So, A is not a candidate key.

B^{+}

= BF from
B → F (By
reflexivity rule)
= BFGH
from F → GH (By transitivity rule)
No
more functional dependencies that has either of the attributes BFGH in LHS. Hence,
B+ = BFGH.

B^{+} ≠ R.
So, B cannot be a candidate key.

(AB)^{+}

= ABC from
AB → C
= ABCDE
from the functional dependency A → DE
= ABCDEIJ
from D → IJ
= ABCDEFIJ from
B → F
= ABCDEFGHIJ
from F → GH

(AB)^{+} = R.
So, (AB) is the candidate key.

**************
Go to Normalization  Solved Exercises page
Go to How to find closure? page
No comments:
Post a Comment