Wednesday, 12 July 2017

Calculate the key for relation R in DBMS

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 - 1NF,    2NF,    3NF,    BCNF




 

No comments:

Post a Comment

SQL exercises for beginners one

SQL Exercises for Beginners / Simple SQL Exercises with Answers / Solved SQL exercises / SQL solved exercises with simple conditions / So...