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 as follows;
F = { AB → C,
BD → EF, AD → GH, A → I, H → J}.
Find the key of relation R.
Solution:
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^{+}

= AI from the
functional dependency A → I
(By
reflexivity rule)
No
more functional dependencies that has either of the attributes AI in LHS. Hence,
A^{+} = AI.

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

H^{+}

= HJ from H
→ J (By
reflexivity rule)
No
more functional dependencies that has either of the attributes HJ in LHS.
Hence, H^{+} = HJ.
Note:
We need not find H+ since H is available on RHS in AD
→ GH.

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

(AB)^{+}

= ABC from
AB → C
= ABCI
from A → I
No
more functional dependencies that has either of the attributes ABCI in LHS.
Hence, (AB)^{+} = ABCI.

(AB)^{+} ≠ R.
So, (AB) is not a candidate key.

(AD)^{+}

= ADGH
from AD →
GH (By reflexivity rule)
= ADGHI
from A → I (By union rule. AD → GH and A → I, so AD → GHI)
= ADGHIJ
from H → J
No
more functional dependencies that has either of the attributes ADGHIJ in LHS.
Hence, (AD)^{+} = ADGHIJ.

(AD)^{+} ≠ R.
So, (AD) is not a candidate key.

(BD)^{+}

= BDEF
from BD →
EF
No
more functional dependencies that has either of the attributes BDEF in LHS.
Hence, (BD)^{+} = BDEF.

(BD)^{+} ≠ R.
So, (BD) is not a candidate key.

(ABD)+

= ABDGH (By reflexivity and augmentation. That is, AD → GH and if we augment
B on both sides we get ABD → BGH. Hence, ABDGH.)
= ABDGHIJ from (AD)^{+}  refer above.
= ABCDGHIJ
from AB →
C
= ABCDEFGHIJ
from BD
→ EF.

(ABD)^{+} = R.
Hence, (ABD) is the candidate key.

Hint: The
left hand side only attribute will definitely be the key or part of the key.
***************
Go to Normalization  Solved Exercises page
Go to How to find closure? page
No comments:
Post a Comment