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 a relation R with attributes
ABCDEFGH and functional dependencies S as follows:
S = {A →
CD, ACF → G,
AD →
BEF, BCG → D, CF → AH, CH → G,
D → B,
H →
DEG}
Find all keys for 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.
 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

Decision

A^{+}

= ACD from A → CD
= ACDBEF from AD → BEF
= ACDBEFG from
ACF → G
= ACDBEFGH from CF → AH

Result includes all the
attributes of relation R. That is, if we know A, then all the attributes of R
could be uniquely determined. Hence, A is one candidate key.

ACF^{+}

No need to find
the closure of (ACF) because the subset A is already a candidate key.

ACF is a super
key but not candidate key.

AD^{+}

No need to find
the closure of (AD) because the subset A is already a candidate key.

AD is a super key
but not candidate key.

BCG^{+}

= BCGD from BCG → D

Result does not include
all the attribute of relation R. Hence, (BCG) cannot be a candidate key.

CF^{+}

= CFAH from CF → AH
Further, as we
know A now, then we can conclude that CF will uniquely determine all the other
attributes of A.

Result includes all the
attributes of relation R. Hence, (CF) is one candidate key.

D+

= DB from D → B

Result
does
not include all R. Hence, D cannot be a key.

H+

= HDEG from H → DEG
= HDEGB from D → B

Result
does
not include all R. Hence, H cannot be a key.

From the above table, it is clear that
only A and
CF are the candidate keys.
Go to Normalization  Solved Exercises page
Go to How to find closure? page
No comments:
Post a Comment