ME test

Question

Relational Schema R with 'n' attributes(A₁, A₂, A₃, A₄.........A_n). and 'm' simple Candidate Keys in R where m<n . How many Super Keys are possible in relation R? 

A) 2^n-m -1

B) (2^m-1)2^n-m 

C) (2ⁿ-1)(2^n-m)

D) (2^m-1)(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≤nm≤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}

Answer 2

Solve by example or venn- diagram | Option b is correct.