Find the candidate keys from the given relation for normalization
Question:
Consider
a relation with schema R(A,B,C,D) with functional dependencies (FD’s):
BC
→ A,
AD → B, CD → B, AC → D.
Find
all the candidate keys of R.
Solution:
Let us find the closure
for the left hand side (LHS) attributes of given set of functional
dependencies.
Let us take the FD BC → A to check whether
the LHS BC forms a candidate key or not.
We know
|
Result =
|
How?
|
Description
|
BC
|
BC
|
Given
|
|
BC
|
BCA
|
BC → A
|
If we know BC, then we can derive A uniquely as
per the reflexivity rule, hence result = BCA
|
BCA
|
BCAD
|
AC → D
|
From the previous step we know attribute A, and
by the FD AC → D the result
becomes ABCD which is equal to R. Hence, BC is a candidate key
|
We derived all the other candidate
keys in the same way as stated above and given in the table below;
LHS
Closure
|
Due to the FDs
|
Result becomes
|
Description
|
(BC)+
|
BC → A
AC → D
|
=
ABC (Reflexive)
=
ABCD (Pseudo-transitive)
|
The
result of (BC)+ is equivalent to R.
Hence
BC is a candidate key.
|
(AD)+
|
AD → B
|
=
ABD (Reflexive)
|
(AD)+
≠ R.
Hence
AD does not form
candidate key.
|
(CD)+
|
CD → B
BC → A
|
= BCD (Reflexive)
=
ABCD (Pseudo-transitive)
|
(CD)+
is equivalent to R.
Hence
CD forms a candidate key.
|
(AC)+
|
AC → D
AD → B
or
CD → B
|
=
ACD (Reflexive)
=
ABCD (Pseudo-transitive)
|
(AC)+
= R hence is
a candidate key.
|
BC,
AC, and CD are the candidate keys for the given relation.
********
Go to Normalization - Solved Exercises page
Go to How to find closure? page
No comments:
Post a Comment