##### Super Keys

For given relation R(ABCDE), candidate keys are AB, BC, CD. What are the no. of super keys ?
Plz someone explain, how to find it ?

##### 1Comment
6 Sep 2016 12:58 am

We use the inclusion exclusion principle.Before that,we calculate the following:

a) Superkeys due to 1 candidate key at a time:

Superkeys due to AB = 23(since these 2 attributes will be there + each of C,D and E may or may not be included,so 2 ways for each of C,D and E) = 8

Similarly , keys due to BC = 23(due to 2 ways each for A,D and E) = 8

Keys due to CD = 23 = 8

Now , taking 2 candidate keys intersection at a time:

Due to AB and BC i.e. ABC = 22(choice is remaining for D and E only) = 4

Similarly,due to BC and CD i.e. BCD = 22 = 4(choice remains for A and E)

Due to AB and CD i.e. ABCD = 2(choice remains for E only)

Now,taking all 3 candidate keys intersection:

Due to AB,BC and CD i.e. ABCD = 2 ways(choice only for E attribute)

Now,we apply inclusion exclusion principle.

We know ,if n(A) , n(B) and n(C) are cardinalities of set A,B and C respectively, then

n(A ∪ B ∪ C) = n(A) + n(B) + n(C) - n(A∩B) - n(B∩C) - n(A∩C) + n(A∩B∩C)

So,in this case, set A,B and C are the superkeys due to candidate keys AB,BC and CD respectively.

So, total no. of superkeys = 8 + 8 + 8 - 4 - 4 - 2 + 2 = 16 superkeys

Hence,16 superkeys possible for the given candidate keys.