GATE 2021 CS (CS1) – Question 43
Consider the relation $R(P,Q,S,T,X,Y,Z,W)$ with the following functional dependencies.
$PQ \rightarrow X;\ P \rightarrow YX;\ Q \rightarrow Y;\ Y \rightarrow ZW$
Consider the decomposition of the relation $R$ into the constituent relations according to the following two decomposition schemes.
$D_1$: $R = [(P,Q,S,T);\ (P,T,X);\ (Q,Y);\ (Y,Z,W)]$
$D_2$: $R = [(P,Q,S);\ (T,X);\ (Q,Y);\ (Y,Z,W)]$
Which one of the following options is correct?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) $D_1$ is a lossless decomposition, but $D_2$ is a lossy decomposition.
Explanation
FDs: $PQ\to X$, $P\to YX$, $Q\to Y$, $Y\to ZW$. Attributes $S,T$ never appear on a right side, so any key contains $P,Q,S,T$, and $PQST$ is a key of $R$.
**D1** $=\{(P,Q,S,T),\ (P,T,X),\ (Q,Y),\ (Y,Z,W)\}$. Use the chase / pairwise-join argument:
1. $(P,Q,S,T)$ is a key, so it determines everything.
2. Join with $(P,T,X)$ on $\{P,T\}$: $P\to X$, so $\{P,T\}$ is a key of $(P,T,X)$. Lossless.
3. Join with $(Q,Y)$ on $Q$: $Q\to Y$, so $Q$ is a key of $(Q,Y)$. Lossless.
4. Join with $(Y,Z,W)$ on $Y$: $Y\to ZW$. Lossless.
D1 is **lossless**.
**D2** $=\{(P,Q,S),\ (T,X),\ (Q,Y),\ (Y,Z,W)\}$. The relations $(P,Q,S)$ and $(T,X)$ share no attribute, so joining them gives a Cartesian product, which creates spurious tuples. D2 is **lossy**.
Answer: (A).