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, How many candidate keys are there for a table
Question:
Given
a schema R( A, B, C, D, E), and the following set of FDs: {A→ E, E → CD, BC → A, D → B}
Solution:
To find the key of a
relation, we need to find the closure of
attributes. If any attribute’s or set of attributes’ closure gives all the
attributes of the relation, then we would say that attribute/set of attributes
as the key for that relation.
To simplify this task or
to avoid wasting time on finding closure of all attributes, let us do find the
closure for left hand side (LHS) attributes of the given functional
dependencies.
In the given exercise, all
the attributes of R are present in the LHS of some functional dependencies. Hence,
we need to try for all LHS attributes.
LHS
|
Due to the FDs
|
Result becomes
|
Description
|
A+
|
A→ E
E→ CD
D→ B
|
=
AE (Reflexive)
=
AECD (Transitive)
=
AECDB (Transitive)
=
ABCDE
|
The
result of A+ is equivalent to R.
A
is a candidate key.
|
E+
|
E→
CD
D→
B
BC→ A
|
=
ECD (Reflexive)
=
ECDB (Transitive)
=
ECDBA (Transitive)
=
ABCDE
|
E+
gives R.
E
is a candidate key.
|
D+
|
=
DB
|
D→
B (Reflexive)
|
D+
is not equivalent to R.
D
is not a candidate key.
|
B+
or C+
|
Neither
B nor C alone form the LHS of any FDs. Hence, they individually cannot form a
candidate key.
|
||
So
far we have tried individual (singleton) attributes. We can now try the combination
of different attributes. We do not need
to test the combination of attributes that have either A or E. The superset
of either A or E cannot be a candidate key.
|
|||
(BC)+
|
BC→ A
A→
E
E→
CD
|
=
BCA (Reflexive)
=
BCAE (Transitive)
=
BCAED (Transitive)
=
ABCDE
|
(BC)+
is equivalent to R.
(BC)
is a candidate key.
|
(CD)+
|
D→
B
BC→ A
A→
E
|
=
CDB (Reflexive)
=
CDBA (Augment)
=
CDBAE (Transitive)
=
ABCDE
|
(CD)
is a candidate key.
|
A, E, BC, and CD are the candidate
keys of the relation R.
*******************
Go to Normalization - Solved Exercises page
Go to How to find closure? page