GATE CS 2026 Set 1 Q55 — ER-model

A superkey of a relation is any set of attributes that contains a candidate key as a subset.

Given the relation schema $R(A, B, C, D)$ with the set of all attributes $U = \{A, B, C, D\}$, the candidate keys are:

• $K_1 = \{A, B\}$
• $K_2 = \{A, C\}$

We can find the total number of superkeys using the Principle of Inclusion-Exclusion:

$$\text{Total Superkeys} = |\text{Supersets of } K_1| + |\text{Supersets of } K_2| - |\text{Supersets of both } K_1 \text{ and } K_2|$$

1. Supersets of $K_1 = \{A, B\}$:
   The remaining attributes are $U \setminus \{A, B\} = \{C, D\}$.
   Number of supersets $= 2^{4-2} = 2^2 = 4$.
   These are: $\{A, B\}$, $\{A, B, C\}$, $\{A, B, D\}$, and $\{A, B, C, D\}$.


2. Supersets of $K_2 = \{A, C\}$:
   The remaining attributes are $U \setminus \{A, C\} = \{B, D\}$.
   Number of supersets $= 2^{4-2} = 2^2 = 4$.
   These are: $\{A, C\}$, $\{A, B, C\}$, $\{A, C, D\}$, and $\{A, B, C, D\}$.


3. Supersets of both $K_1$ and $K_2$:
   A set containing both $K_1$ and $K_2$ must contain $K_1 \cup K_2 = \{A, B, C\}$.
   The remaining attribute is $U \setminus \{A, B, C\} = \{D\}$.
   Number of such supersets $= 2^{4-3} = 2^1 = 2$.
   These are: $\{A, B, C\}$ and $\{A, B, C, D\}$.

Applying the formula:

$$\text{Total Superkeys} = 4 + 4 - 2 = 6$$

The $6$ unique 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\}$