Basics of Candidate Key and counting

We already know the formal definition of candidate key let's talk some more.


1. Given that a set  S =  {{A_{1,}A_{2},A_{3}, .......... A_{n}}}

Then the maximum number of candidate key possible is : 2^{n}-1


Example 1:-

R=\left \{ A,B,C,D,E,H \right \}

FD's= \left \{ A\rightarrow B,BC\rightarrow D,E\rightarrow C, D\rightarrow A\right \}

find the Candidate Keys.


First, find out which of the  attributes are not derived by any other attributes

So EH are the one. So they must be present in CK.


(AEH)^{^{+}}= A,B,,C,D,E,H

(BEH)^{^{+}}= A,B,,C,D,E,H

(DEH)^{^{+}}= A,B,,C,D,E,H

(CEH)^{^{+}}= C,E,H

So only AEH, BEH,DEH are the candidate keys because they are deriving all the attributes.


Finding the number of Super keys:-


If a set has n elements and one of the element is already known to be a candidate key then any superset of the candidate key is Superkey. We know this stuff. Remaining n-1 keys have two choices either they can be the part of superkey or not.


1. let  R=\left \{ E,F,G,H,I,J,K,L,M,N, \right \}

and it is already known that GHI  is  then the number of superkeys is:-

the total number of attributes is 10 and out of which 3 attributes formed candidate key then the remaining 7, has two choices: either they want to be the part of superkey or not.

So 2 choices ................7 times

So total number of superkeys = 2^{7}=128


2.  R=\left \{ A,B,C,D \right \} 

      FD= \left \{ AB\rightarrow CD,D\rightarrow A \right \}

find the number of super keys.


First, find the number of candidate keys:-

 B is not derived by anyone So it must be the part of a candidate key.

(AB)^{+}=\left \{ A,B,C,D \right \}

(BD)^{+}=\left \{ A,B,C,D \right \}

(BC)^{+}=\left \{ B,C\right \}

So only two candidate keys: AB,BD

Number of superkeys =

number of superkeys when AB is taken as candidate key number of superkeys when BD is taken as the candidate key  number of superkeys when BOTH are   taken as the candidate key

2^{2}+2^{2} -2 =6



Contributor's Info