Question

Let a relation in DBMS is given as R(A, B, C, D, E) and candidate keys are {A} and {BC}. Total number of possible super keys are:

Comments

To create super keys we can combine the candidate key with the sets formed with the remaining attributes.

So the number of superkeys we can form with candidate key {A}$= A = 2^{n-1} = 2^{5-1} = 16$

Number of superkeys we can form with candidate key {BC} $= B = 2^{n-2} (here n=5) = 2^{5-2} = 8$

Now there are several key sets that we have counted twice when calculating both separately, like {A,B.C} , {B,C,A} &  {A,B.C,D} , {B.C,D,A} etc.

So as per set theory 

If A ∩ B ≠ φ, then

n (A ∪ B) = n (A) + n (B) – n (A ∩ B)

$superkeys = 16 + 8 - 2^{5-3} = 24-4 = 20$

Hence 20 super-keys are possible.

Answer 1

Simply apply inclusion exclusion rule ATQ.

Given that, CKs are {A} and {BC}.

So, Total no. of SKs = 2^(n-1) + 2^(n-2) – 2^(n-3)     [ {inclusion of 1^st CK + inclusion of 2^nd CK } – {exclusion of {CK1 & CK2}}]

  = 2^(5-1) + 2^(5-2) – 2^(5-3)

  = 2^4 + 2^3 – 2^2

  = 16 + 8 – 4

  = 20   (Ans)

Comments

Can you explain the counting methodology, I am sort of confused. I understand its why there is 2pow(n-1) possibilities for a superkey is from either you have to take it or leave the key out, is my understanding right ? how can I take this further.