MadeEasy Test Series: Databases - Candidate Keys

Question

Relation R(A1, A2, A3 ..... An) n attributes. On this relation m simple candidate key (m ≤ n). How many super keys possible in this relation?

A. 2m – 1

B. (2n – 1) ⋅ 2n-m

C. 2n – 1

D. (2m – 1) 2n-m

One way is by taking instances and solve it, but plz without it what's the logic behind the answer?

Comments

option D . is correct

Explanation :

    There are m simple candidate keys 

    So every candidate have 2 chance : they can Present in super key  OR Absent , But at least one of in 'm'             should  present .

                      No. of chance to appear m candidate key in Superset is = 2^m-1

                   and  all remaining  attribute 'n-m' have to chance they can present Or absent in Super key.

                   No .of chance all remaining attributes to appear in Super Key =2^(n-m)

                                         So ,     Total no of Super Key Possible=(2^m-1)2^(n-m)

---

check it

https://gateoverflow.in/170757/madeeasy-subject-test-databases-candidate-keys

Answer 1

Since all the Candidate keys here are Simple (Single attribute), We can do it by Complement method.

For a Group of attributes to be called a Super key, It must contain at least One Candidate key. Thus, Some Group of attributes can never be a Super key if it does not contain any candidate key. There are $n-m$ Non-prime attributes. If we make any subset from these $n-m$ attributes, that can never be a Super key. Else if we include at least One of the $m$ attributes, that would be called Super key. So..

Number of Super Keys possible = All Possible Subsets of $n$ attributes -  All Possible subsets of $n-m$ attributes.

$2^n - 2^{n-m}$

Comments

According to you also Option D is correct.