Database Normalization--Part 2 (Closure Set of Attributes)

Till now, we have covered up to the Closure Set of Attributes method of finding candidate keys. Before reading this post, please read the following post on Normalization:-

• Part 1: Introduction to Database Normalization

In this post, we will see how to find the candidate keys of a relation using the Closure Set of Attributes Method. We must note that candidate keys can also be found out using the axioms of Functional Dependencies mentioned. But during the GATE examination, an attempt to save time is a must.

Closure Set of Attributes Method

This method is very useful in finding out the keys of a relation which is needed for Normalization procedure. Let us go through a couple of examples to understand the procedure.

Suppose we consider the following relation R with 4 attributes (A,B,C,D) and are also given a functional dependency set (Functional dependencies are arrived at during the Requirements Analysis Phase, when the problem is being analyzed and client specifications are being noted).

R(A,B,C,D) = { AàB , BàC , CàD , DàA } -----------> given FD set

So, here we have 4 functional dependencies. Now, we will find out the entire attribute set which each attribute derives. It is a repetitive approach.

(A)⁺ = { A,B,C,D}

Closure set of A contains A by default as AàA always holds. 
As we have the functional dependency AàB, so the closure set of A will contain B (A derives B)

Closure set of A contains B and B->C therefore using transitivity axiom,  we can say that AàC, so   the closure set of A will contain C. 
 Similarly, we arrive at the following conclusions:-

·         (B)⁺={A,B,C,D}

·         (C)⁺={A,B,C,D}

·         (D)⁺={A,B,C,D}

In this example, we find that each of the attributes A,B,C and D are the candidate keys as each of them individually derives all the attributes of this relation. A candidate key is a minimal superkey. There cannot exist any other candidate key for this relation because any superset (other than itself) of a candidate key is a superkey but not a candidate key. Please read the previous sentence again if you find the language confusing. Let us take another example.

Let us consider another relation R(A,B,C,D,E,F,G,H) along with its functional dependency set as
{ABàCD,DàE,EàF,BàA,FàG,GàH}. 

We are required to find out the Candidate Keys for this

relation R.

In the 1st step, we find the closure sets of the single attributes A,B,C and D to obtain:-

·         (A)⁺={A}

·         (B)⁺={A,B,C,D,E,F,G,H}

·         (C)⁺={C}

·         (D)⁺={D,E,F,G,H}

Now, at the conclusion of this 1st step, we are sure that B is a candidate key as it derives all the attributes. Also, we can conclude at this point that if any other candidate key exists for this relation, it will not have B in it (as any superset of a candidate key is a superkey but not a candidate key).

      Now, we must find the closure sets of AC, CD, AD (2-attribute closures). We note here that

(AC)⁺ denotes the set that A and C can derive together, repetitively. Here,

(AC)⁺ ={A,C}
(AD)⁺={A,D,E,F,G,H}
(CD)⁺={C,D,E,F,G,H}

So none of the 2-attribute sets are candidate keys. But we still should check for the 3-attribute set
ACD. Note that B shouldn't be part of this check as it itself is a candidate key and cannot be part

of any superset of itself.

(ACD)⁺={A,C,D,E,F,G,H}

So, ACD is not a candidate key as well as it cannot derive the attribute B.

Important Note

If we look carefully at the Functional Dependencies, we will find that B is not present in Right Hand Side of any of the Functional Dependencies. This indicates that B should be a part of any candidate key (otherwise B won't be derived).

Now, if B is a part of any candidate key of this relation, there cannot be any other candidate key as B is a single attribute candidate key. So, we could have directly stated that B is the only candidate key for this relation which would have saved a lot of time. This trick comes in very handy in GATE. Any attrribute which is not present in Right Hand Side of any of the Functional Dependencies of a given relation, has to be part of any candidate key of that relation.

At this point, we know how to find the candidate keys of any given relation provided we know the Functional Dependencies which exist for that relation. In the next post, we will look at the types of functional Dependencies that exist and subsequently move on to Normal Forms. 

Was it a nice read? Please subscribe to the blog by clicking on the 'Follow' button on the right hand side of this page. You can also subscribe by email by entering your email id in the box provided. In that case, you will be updated via email as and when new posts are published. Please share the post if you find it useful. Cheers!

Click here to read Part 3