GATE CS 2017 Set 1 Q.16 (CS Q.16): Functional Dependencies and Normalization

The following functional dependencies hold true for the relational schema $R(V, W, X, Y, Z)$ :

V \to W

VW \to X

Y \to VX

Y \to Z

Which of the following is irreducible equivalent for this set of functional dependencies?

$V \to W$
$V \to X$
$Y \to V$
$Y \to Z$

$V \to W$
$W \to X$
$Y \to V$
$Y \to Z$

$V \to W$
$V \to X$
$Y \to V$
$Y \to X$
$Y \to Z$

$V \to W$
$W \to X$
$Y \to V$
$Y \to X$
$Y \to Z$

Official answer and solution

Official answer: A
From: Official GATE 2017 answer key

Solution

Find the canonical cover (minimal cover) by decomposing right-hand sides, eliminating extraneous left-hand attributes, and removing redundant functional dependencies.

Given the functional dependency set:

F = \{V \to W, \; VW \to X, \; Y \to VX, \; Y \to Z\}

Step 1: Decompose right-hand sides into single attributes:

F_1 = \{V \to W, \; VW \to X, \; Y \to V, \; Y \to X, \; Y \to Z\}

Step 2: Check for extraneous attributes on the left-hand side of $VW \to X$ :
Compute the attribute closure of $V$ under $F_1$ :

V^+ = \{V, W, X\}

Since $W \in V^+$ , attribute $W$ is extraneous in the left-hand side of $VW \to X$ . Thus, $VW \to X$ simplifies to $V \to X$ .
The dependency set becomes:

F_2 = \{V \to W, \; V \to X, \; Y \to V, \; Y \to X, \; Y \to Z\}

Step 3: Check for redundant functional dependencies in $F_2$ :

Test $Y \to X$ : Compute $Y^+$ under $F_2 \setminus \{Y \to X\}$ : $Y^+ = \{Y\} \to \{Y, V, Z\} \to \{Y, V, Z, W, X\}$ Since $X \in Y^+$ , the dependency $Y \to X$ is inferred via $Y \to V$ and $V \to X$ . Hence, $Y \to X$ is redundant and can be removed.

Testing the remaining dependencies:

$V \to W$ : $V^+$ without it is $\{V, X\}$ , which does not contain $W$ . Retained.
$V \to X$ : $V^+$ without it is $\{V, W\}$ , which does not contain $X$ . Retained.
$Y \to V$ : $Y^+$ without it is $\{Y, Z\}$ , which does not contain $V$ . Retained.
$Y \to Z$ : $Y^+$ without it is $\{Y, V, W, X\}$ , which does not contain $Z$ . Retained.

The resulting irreducible equivalent set is:

\{V \to W, \; V \to X, \; Y \to V, \; Y \to Z\}

This matches Option A.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2017 Computer Science and Information Technology (CS) Session 1
Question: 16 of 65, printed as CS Q.16
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source