GATE CS 2022 Q21 — Normal Forms

To find the number of superkeys for the relation $R(A, B, C, D, E)$, we first determine the candidate keys of the relation.

Step 1: Identify the Candidate Key(s)

Let's analyze the given functional dependencies (FDs):

• $AB \rightarrow C$
• $BC \rightarrow D$
• $C \rightarrow E$

Notice that the attributes $A$ and $B$ do not appear on the right-hand side of any functional dependency. Therefore, $A$ and $B$ must be part of every candidate key.

Let's compute the attribute closure of $\{A, B\}$:

Since $\{A, B\}^+$ contains all the attributes of the relation $R$, $\{A, B\}$ is a candidate key. Since $A$ and $B$ are essential, there are no other candidate keys.

Step 2: Calculate the Number of Superkeys

A superkey is any set of attributes that contains a candidate key. Since $\{A, B\}$ is the unique candidate key, any superkey of $R$ must contain both $A$ and $B$.

The remaining attributes that can be optionally included in the superkey are $\{C, D, E\}$.

The number of ways to choose a subset from these $3$ remaining attributes is:

Thus, the total number of superkeys is 8.