GATE 2024 DA Q.46: solution and answer

GATE 2024 · DAQ.46 · 2 marks · MSQ

Given the relational schema $R = (U, V, W, X, Y, Z)$ and the set of functional dependencies:

${U \to V, U \to W, W X \to Y, W X \to Z, V \to X}$

Which of the following functional dependencies can be derived from the above set?

(A)
$V W \to Y Z$
(B)
$W X \to Y Z$
(C)
$V W \to U$
(D)
$V W \to Y$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The derivable dependencies are $V W \to Y Z$ , $W X \to Y Z$ and $V W \to Y$ , that is options (A), (B) and (D).

Official answer: A, B, DSource: Official answer key, GATE 2024 DA (IISc Bengaluru)

A dependency $P \to Q$ can be derived from a set $F$ exactly when $Q \subseteq P^{+}$ , where $P^{+}$ is the closure of $P$ under $F$ . So compute the closures needed.
Closure of $V W$ . Start with ${V, W}$ .
Apply $V \to X$ : the left side $V$ is in the set, so add $X$ . The set becomes ${V, W, X}$ .
Apply $W X \to Y$ and $W X \to Z$ : $W$ and $X$ are both in the set, so add $Y$ and $Z$ . The set becomes ${V, W, X, Y, Z}$ .
$U$ appears on the right side of no dependency, so it can never be added. The other dependencies ( $U \to V$ , $U \to W$ ) need $U$ on the left and add nothing new. Hence $(V W)^{+} = {V, W, X, Y, Z}$ .
(A) $V W \to Y Z$ : ${Y, Z} \subseteq (V W)^{+}$ , so it can be derived.
(C) $V W \to U$ : $U \in / (V W)^{+}$ , so it cannot be derived.
(D) $V W \to Y$ : $Y \in (V W)^{+}$ , so it can be derived.
(B) $W X \to Y Z$ : $W X \to Y$ and $W X \to Z$ are given. By the union rule (if $P \to Q$ and $P \to R$ then $P \to QR$ ), $W X \to Y Z$ holds. Equivalently, $(W X)^{+} \supseteq {W, X, Y, Z}$ .
The derivable dependencies are (A), (B) and (D).

KEY IDEA

$P \to Q$ is derivable exactly when $Q \subseteq P^{+}$ . Compute the closure of the left side by repeatedly firing every dependency whose left side is already inside the set. Here $V \to X$ is what lets $V W$ reach $W X$ and so pull in $Y$ and $Z$ .

WATCH OUT FOR

Stopping the closure of $V W$ at ${V, W, X}$ and forgetting to fire $W X \to Y$ and $W X \to Z$ afterwards. Another slip is to think $V W \to U$ holds because $U$ determines $V$ and $W$ . The converse does not follow, since nothing determines $U$ .

From the GATE 2024 DA paper. Every question of this paper · Download the full paper · All 6 Normal forms questions, with notes

GATE 2024 DA Q.46: solution and answer

Answer and solution

More Normal forms questions