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