no of superkeys

Question

Comments

Number of simple candidate keys are = m 
So how many possible super keys with only m candidate keys = (2^m-1)

Now number of left attribute can be added are = n-m 

so total keys = (2^m-1)$\times$ 2^n-m 

Answer 1

Here simple candidate keys mean candidate keys having only one attribute.

So for m simple candidate keys, we will have 2^m - 1  super keys(as each candidate key will either be included or not, so 2 choices for each simple candidate key and -1 when neither of candidate keys is selected)

Now, we're left with (n - m) (given that $m\leq n$) attributes and we know that superset of super keys is also a super key. So, we either include them or don't include them. So, (n - m) elements have 2 choices each.

So, total super keys possible = (2^m - 1) * 2^{n - m}

Let's verify with an example. A relation R(A, B, C) with candidate keys as A and B.

So here, m = 2

Super keys possible with m candidate keys should be 2^m - 1 = 3 which are {A, B, AB}

And now we're left with n - m = 3 - 2 = 1 element i.e. C which may be included or not to form super keys.

So total super keys possible = 3 * 2¹ = 6 {A, AB, AC, ABC, B, BC}

P.S : Such questions can also be solved using Venn Diagrams.

Comments

@just_bhavana How the Venn Diagram for this can be drawn?