Find the key of relation R

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 = {AB → C, A → DE, B → F, F → GH, D → IJ}. Find the key of relation R.

Solution: [One more simple solution - Click here]

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+	= ADE from the functional dependency A → DE (By reflexivity rule) = ADEIJ from D → IJ (By transitivity rule. A → D and D → IJ hence A → IJ) No more functional dependencies that has either of the attributes ADEIJ in LHS. Hence, A+ = ADEIJ.	A+ ≠ R. So, A is not a candidate key.
B+	= BF from B → F (By reflexivity rule) = BFGH from F → GH (By transitivity rule) No more functional dependencies that has either of the attributes BFGH in LHS. Hence, B+ = BFGH.	B+ ≠ R. So, B cannot be a candidate key.
(AB)+	= ABC from AB → C = ABCDE from the functional dependency A → DE = ABCDEIJ from D → IJ = ABCDEFIJ from B → F = ABCDEFGHIJ from F → GH	(AB)+ = R. So, (AB) is the candidate key.

One more simple solution - Click here.

**************

Go to Normalization - Solved Exercises page

Go to - 1NF,    2NF,    3NF,    BCNF

Go to How to find closure? page

 

Find the keys of a relational table in dbms solved problem

Correct functional dependencies for bcnf relation

Which of the FDs are correct for R to be in BCNF?, Boyce-Codd Normal Form

Question:

13. Let us consider a relation R with the schema R (A, B, C, D). If we expect R to be in BCNF, then which of the following sets of functional dependencies must hold in R?

(a) A → C, A → D, AD → C, B → A

(b) C → B, C → D, A → C, D → A

(c) C → D, CD → A, BD → A, AB → C

(d) A → D, C → A, AC → B, D → B

Answer:

(b) C → B, C → D, A → C, D → A

Discussion/Reason:

For a relation to be in BCNF, then all the FDs must have candidate keys on their left hand side.

Let us find the closure (refer here for attribute closure) for LHS of each FD of option (b).

Closure of C (C+)	FD causes the result
result = CB	C → B
result = CBD	C → D
result = CBDA	D → A

From the above table, the result of closure of C = ABCD = R. Hence, C is one of the candidate keys.

Closure of A (A+)	FD causes the result
result = AC	A → C
result = ACB	C → B
result = ACBD	C → D

From the above table, the result of closure of A = ABCD = R. Hence, A is one of the candidate keys.

Closure of D (D+)	FD causes the result
result = DA	D → A
result = DAC	A → C
result = DACB	C → B

From the above table, the result of closure of D = ABCD = R. Hence, D is one of the candidate keys.

For option (b), all the FDs left hand sides are candidate keys. So, R should hold these FDs to be in Boyce Codd Normal Form.

You try for other FDs given in other options. The LHS will not form a key.

         Previous Question                                                                                Next Question

Go to Multiple choices questions page