The GATE Grind

GATE 2021 CS (CS1) – Question 43

Databases · Integrity Constraints and Normal Forms · 2 marks · Multiple choice

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?

  1. $D_1$ is a lossless decomposition, but $D_2$ is a lossy decomposition.
  2. $D_1$ is a lossy decomposition, but $D_2$ is a lossless decomposition.
  3. Both $D_1$ and $D_2$ are lossless decompositions.
  4. Both $D_1$ and $D_2$ are lossy decompositions.

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).

More Integrity Constraints and Normal Forms questions

All Integrity Constraints and Normal Forms questions →