Database normalization - solved exercise to find keys

Set of solved exercises in Normalization / Normalization Solved Examples / How to find candidate keys, and primary keys in database? / Sets of examples to find the keys of a tables / Process of Key finding in a database – Examples

Question:

Relation R has eight attributes ABCDEFGH. Fields of R contain only atomic values. F = {CH → G, A → BC, B → CFH, E → A, F → EG} is a set of functional dependencies (FDs) so that F⁺ is exactly the set of FDs that hold for R. Find the candidate keys of relation R. (GATE 2013 question)

Solution:

Which attribute (or set of attributes) is the key? – We know that, if the closure of an attribute (or set of attributes) includes all the attributes of the relation, then that attribute (or set of attributes) is one of the candidate keys of the relation (table).

To simplify, we would find the closure for left hand side attributes of all the functional dependencies (we can skip redundant attributes).

Closure of A (A⁺):

Result = A

Result = ABC from A → BC

Result = ABCFH from B → CFH

Result = ABCEFGH from F → EG

Final result = ABCEFGH which is not ABCDEFGH i.e., result ≠ R. hence, A is not a candidate key.

Closure of E (E⁺):

Result = E

Result = EA from E → A

If we know A, from the above derivation, final result would be ABCEFGH. And this is not equal to R, hence E is not a candidate key.

At this stage, we need to observe one thing from the set of functional dependencies given. The thing is, attribute D is not part of any functional dependencies. Hence, we need to include D with other attributes. That means, whatever key we find, D should be a part of it.

Hence, we would try with D as a component attribute; if we follow the steps applied above; we would get the following;

Closure of AD (AD⁺) = R. Hence, AD is one of the candidate keys.

Closure of BD (BD⁺) = R. So BD is one of the candidate keys.

Closure of ED (ED⁺) = R. So, ED is one of the candidate keys.

Closure of FD (FD⁺) = R. Hence, FD is one of the candidate keys.

AD, BD, ED, and FD are the candidate keys of R.

What about other set of attributes?

The other attributes other than AD, BD, ED, and FD cannot be the keys (refer definition for candidate keys). Why?

We know that the closure of ABD, ADE, ADF, BED, etc. would form the keys. According to the definition (candidate key is a minimal key for which the proper subset must not contain a key), for example, the subset of ABD contains the keys AD, and BD which are keys. This holds for all the other combinations. Hence, they cannot form the candidate keys. (they are all super keys).

Another try: Let us try to find the closure of CH.

Closure of CH (CH⁺):

Result = CH

Result = CHG from CH → G.

We cannot move further because C, H and G are not (individually or collectively) uniquely determine any other attributes. Hence, CH⁺ = CHG.

As a result, we would conclude that AD, BD, ED, and FD are the qualified candidate keys for R.

Go back to Normalization – solved exercises page.

Related Posts:

Various uses of attribute closure

How to find Closure?