GATE CS 2014 Set 1 Q21 — Normal Forms

To find the candidate key for the relation scheme $R = (E, F, G, H, I, J, K, L, M, N)$, we can analyze the given set of functional dependencies (FDs):

• $\{E, F\} \to \{G\}$
• $\{F\} \to \{I, J\}$
• $\{E, H\} \to \{K, L\}$
• $\{K\} \to \{M\}$
• $\{L\} \to \{N\}$

Step 1: Identify Essential Attributes

An attribute that does not appear on the right-hand side (RHS) of any functional dependency must be part of every candidate key, as it cannot be determined by any other attribute.

Looking at the RHS of all given FDs, the attributes that are never determined by any dependency are:

Step 2: Compute the Closure of $\{E, F, H\}$

Let's find the attribute closure of $\{E, F, H\}$ to see if it can determine all the attributes of the relation $R$:

1. Start with: $\{E, F, H\}^+ = \{E, F, H\}$
2. Using $\{E, F\} \to \{G\}$: $\{E, F, H\}^+ = \{E, F, H, G\}$
3. Using $\{F\} \to \{I, J\}$: $\{E, F, H\}^+ = \{E, F, H, G, I, J\}$
4. Using $\{E, H\} \to \{K, L\}$: $\{E, F, H\}^+ = \{E, F, H, G, I, J, K, L\}$
5. Using $\{K\} \to \{M\}$: $\{E, F, H\}^+ = \{E, F, H, G, I, J, K, L, M\}$
6. Using $\{L\} \to \{N\}$: $\{E, F, H\}^+ = \{E, F, H, G, I, J, K, L, M, N\} = R$

Since the closure of $\{E, F, H\}$ contains all the attributes of $R$, and no proper subset of $\{E, F, H\}$ can derive all attributes (as $E, F,$ and $H$ are essential), $\{E, F, H\}$ is the unique candidate key for $R$.