GATE Overflow Test Series | Databases | Test 1 | Question: 17

Question

The maximum number of super keys for the relation schema $R(A_{1},A_{2},A_{3},A_{4},\dots, A_{n})$ with $A_{1}A_{2}$ and $A_{1}A_{3}$ as the candidate key is _________

• A. $2^{n-1} + 2^{n-1} - 2^{n-2}$
• B. $2^{n-1} - 2^{n-3}$
• C. $2^{n-2} - 2^{n-2} - 2^{n-3}$
• D. $2^{n-1} + 2^{n-2} - 2^{n-3}$

Answer 1

With $A_{1}A_{2}$ as candidate key, the number of super keys, $SK(A_{1}A_{2})  = 2^{n-2}$ (any subset of the remaining $n-2$ attributes including the empty set form a super key.

Similarly with $A_{1}A_{3}$ as candidate key, the number of super keys, $SK(A_{1}A_{3})  = 2^{n-2}$
    
And with $\{A_{1}A_{2}A_{3}\}$ as candidate key
the number of super keys, $SK(A_{1}A_{2}A_{3})  = 2^{n-3}.$  

Now, the total number of distinct super keys $SK(A_{1}A_{2},A_{1}A_{3}) = SK(A_{1}A_{2}) + SK(A_{1}A_{3}) - SK(A_{1}A_{2}A_{3})$

$\qquad = 2^{n-2} + 2^{n-2} - 2^{n-3}=2^{n-1} - 2^{n-3}.$

So, the correct answer is $(B).$