GATE CS 2017 Set 1 Q16 — Normal Forms

To find the irreducible equivalent (also known as the minimal cover or canonical cover) of the given set of functional dependencies (FDs), we follow a systematic three-step process:

Step 1: Decompose the Right-Hand Side (RHS)

Split all FDs so that each has only a single attribute on the right-hand side:

1. $V \rightarrow W$
2. $VW \rightarrow X$
3. $Y \rightarrow V$
4. $Y \rightarrow X$
5. $Y \rightarrow Z$

Step 2: Remove Extraneous Attributes from Left-Hand Side (LHS)

Consider the dependency $VW \rightarrow X$ with multiple attributes on the LHS:

• To check if $W$ is extraneous, we compute the attribute closure of $V$ under the current set of FDs: $$V^+ = \{V, W\}$$ Since $W \in V^+$, the attribute $W$ is redundant on the LHS of $VW \rightarrow X$.
• Thus, we can simplify $VW \rightarrow X$ to $V \rightarrow X$.

Our updated set of FDs is now:

1. $V \rightarrow W$
2. $V \rightarrow X$
3. $Y \rightarrow V$
4. $Y \rightarrow X$
5. $Y \rightarrow Z$

Step 3: Remove Redundant Functional Dependencies

We test each FD to see if it can be derived from the remaining FDs:

• Test $Y \rightarrow X$:
  Compute the closure of $Y$ using all FDs except $Y \rightarrow X$: $$Y^+ = \{Y\} \xrightarrow{Y \rightarrow V} \{Y, V\} \xrightarrow{V \rightarrow X, V \rightarrow W} \{Y, V, W, X\}$$ Since $X \in Y^+$, the dependency $Y \rightarrow X$ is redundant and can be safely removed.
• Testing the remaining FDs ($V \rightarrow W$, $V \rightarrow X$, $Y \rightarrow V$, and $Y \rightarrow Z$) shows that none of them are redundant.

The final irreducible set of functional dependencies is:

• $V \rightarrow W$
• $V \rightarrow X$
• $Y \rightarrow V$
• $Y \rightarrow Z$

This matches Option A.