GATE 2026 CS (CS1) – Question 65
Consider a relational database schema with a relation $R(A, B, C, D)$. If $\{A, B\}$ and $\{A, C\}$ are the only two candidate keys of the relation $R$, then the number of superkeys of relation $R$ is ______. (answer in integer)
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 6
Explanation
A superkey is any superset of a candidate key.
The set of all attributes is $\{A, B, C, D\}$, which has $2^4 = 16$ possible subsets.
1. Supersets of $\{A, B\}$:
Must contain $A$ and $B$. The remaining attributes are $\{C, D\}$. There are $2^2 = 4$ such supersets:
- $\{A, B\}$
- $\{A, B, C\}$
- $\{A, B, D\}$
- $\{A, B, C, D\}$
2. Supersets of $\{A, C\}$:
Must contain $A$ and $C$. The remaining attributes are $\{B, D\}$. There are $2^2 = 4$ such supersets:
- $\{A, C\}$
- $\{A, B, C\}$
- $\{A, C, D\}$
- $\{A, B, C, D\}$
3. Intersection (supersets containing both $\{A, B\}$ and $\{A, C\}$):
Must contain $A, B, C$. The remaining attribute is $\{D\}$. There are $2^1 = 2$ such supersets:
- $\{A, B, C\}$
- $\{A, B, C, D\}$
By the Principle of Inclusion-Exclusion:
$$\text{Total superkeys} = |\text{Supersets}(AB)| + |\text{Supersets}(AC)| - |\text{Supersets}(ABC)|$$
$$\text{Total superkeys} = 4 + 4 - 2 = 6$$
The distinct superkeys are:
1. $\{A, B\}$
2. $\{A, C\}$
3. $\{A, B, C\}$
4. $\{A, B, D\}$
5. $\{A, C, D\}$
6. $\{A, B, C, D\}$
The correct answer is 6.