GATE CS 2013 Q54 — Normal Forms

To find the candidate keys of relation $R(A, B, C, D, E, F, G, H)$, we first identify the attributes that do not appear on the right-hand side (RHS) of any functional dependency in $F$:

• $D$ and $H$ do not appear on the RHS of any FD. Thus, both $D$ and $H$ must be part of every candidate key.

Let's compute the attribute closure of the essential set $\{D, H\}$:

Since $\{D, H\}$ is not a superkey, we must add other attributes to it to find the candidate keys:

1. Testing $A$: $$\{A, D, H\}^+ = \{A, D, H\} \xrightarrow{A \to BC} \{A, B, C, D, H\} \xrightarrow{B \to CFH} \{A, B, C, D, F, H\} \xrightarrow{F \to EG} \{A, B, C, D, E, F, G, H\}$$ Thus, $\{A, D, H\}$ is a candidate key.
2. Testing $B$: $$\{B, D, H\}^+ = \{B, D, H\} \xrightarrow{B \to CFH} \{B, C, F, H, D\} \xrightarrow{F \to EG} \{B, C, E, F, G, H, D\} \xrightarrow{E \to A} \{A, B, C, D, E, F, G, H\}$$ Thus, $\{B, D, H\}$ is a candidate key.
3. Testing $E$: $$\{E, D, H\}^+ = \{E, D, H\} \xrightarrow{E \to A} \{A, E, D, H\} \xrightarrow{A \to BC} \{A, B, C, E, D, H\} \xrightarrow{B \to CFH} \dots = \{A, B, C, D, E, F, G, H\}$$ Thus, $\{E, D, H\}$ is a candidate key.
4. Testing $F$: $$\{F, D, H\}^+ = \{F, D, H\} \xrightarrow{F \to EG} \{E, F, G, D, H\} \xrightarrow{E \to A} \{A, E, F, G, D, H\} \xrightarrow{A \to BC} \dots = \{A, B, C, D, E, F, G, H\}$$ Thus, $\{F, D, H\}$ is a candidate key.

Testing the remaining attributes $C$ and $G$ (e.g., $\{C, D, H\}^+$ or $\{G, D, H\}^+$) does not yield all attributes. Therefore, there are exactly $4$ candidate keys: $\{A, D, H\}$, $\{B, D, H\}$, $\{E, D, H\}$, and $\{F, D, H\}$.