An algorithm to find all possible candidate keys of relation.

The utmost headache for a database designer is to find the all possible key(s) or candidate key(s) of a relation. Here is the solution of that headache.
I am going to give you a very efficient algorithm to find all possible key(s) of a relation. The algorithm is as follows-
For a given set of functional dependencies (F) on a relation, the algorithm can be described as-


  1. Find the minimal cover of F and say it Fc.
  2. Use Fc to divide the attributes of relation R into 3 groups, namely essential attributes(L), useless attributes(R) and common attributes(M). Essential attributes are the attributes which are essentially the part of all key(s) of the relation. Useless attributes are the attributes which are not the part of the key. Common attributes are the attributes which may or may not be the part of the key.
  3. After grouping so, find all possible combination of the attributes to find the key(s).
I guess your agenda is still not solved. So, in order to completely make this algorithm clear, let us take an example.
Let us consider a relation R with attributes A,B,C,D and E.
      So,             R(A,B,C,D,E)
      and             F={CE -> D,D -> B,C -> A}

Step 1:

Find the minimal cover of F and say it Fc
hence, Fc={CE -> D,D -> B,C -> A}

Note:
In this example F and Fc are same. But, this is not true for all relation.

Step 2:

Dividing the attribute in L, M and R
Computing L, means finding those attributes which can not be derived from any functional dependencies. To do so, list all attributes of R into L which are either only on the left side of the FD or are not present in FD.

In this case,
the attributes which are only present on the left side of the FD or are not present in FD are-
                                            L= {C,E}
Similary, M contains those attributes which are present on both sides of the FD.
Hence,
                                            M={D}
And R contains those attributes which are present only on the right side of the FD
Hence,
                                            R={A,B}

Note:
In order to check whether you have distributed the attributes correctly or not, perform
              L (intersection) M, L (intersection) R and R (intersection) M.
The result of all three operations are essentially phi. If it is so, the you have grouped the attributes correctly else not.

Step 3:

Now, compute closure of L,
here,
                             L+={A,B,C,D,E}
If closure of L gives all the attributes of relation R, L is the key and stop.
If closure of L doesn't gives all the attributes of relation R, then find all possible combination of L and M, and compute the closure of each. The collection of attributes whose closure contains all the attributes of R is our key(s).

In this example CE is our only key.

NOTE:
To know how to compute minimal cover of the FD, visit my blog.

Comments