PYQs / GATE CS / 2021 / Set 1 / Q43 GATE CS 2021 Set 1 — Question 43 Go beyond PYQs with Success Tracker AI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply. MCQ +2 / -0.67 Medium Lossless Decomposition Normalization Databases
Databases → Normalization → Lossless Decomposition
Last updated 5 September 2026
Question Consider the relation
R(P, Q, S, T, X, Y, Z, W) with the following functional dependencies.
P Q → X ; P → Y X ; Q → Y ; Y → Z W PQ \rightarrow X; P \rightarrow YX; Q \rightarrow Y; Y \rightarrow ZW P Q → X ; P → Y X ; Q → Y ; Y → Z W Consider the decomposition of the relation
R R 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_1: R = [(P, Q, S, T); (P, T, X); (Q, Y); (Y, Z, W)] 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 ) ] D_2: R = [(P, Q, S); (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?
Correct answer (A) D₁ is a lossless decomposition, but D₂ is a lossy decomposition.
Solution A decomposition is
lossless if for every pair of joined relations
R 1 R_1 R 1 and
R 2 R_2 R 2 , the common attributes
R 1 ∩ R 2 R_1 \cap R_2 R 1 ∩ R 2 form a superkey for at least one of the relations (
R 1 R_1 R 1 or
R 2 R_2 R 2 ).
Given FDs:
1. PQ → X
2. P → Y X ⟹ P → Y P \rightarrow YX \implies P \rightarrow Y P → Y X ⟹ P → Y P → X3. Q → Y
4. Y → Z W ⟹ Y → Z Y \rightarrow ZW \implies Y \rightarrow Z Y → Z W ⟹ Y → Z Y → W
Analyzing Decomposition D 1 D_1 D 1 Relations:
R 1 ( P , Q , S , T ) R_1(P, Q, S, T) R 1 ( P , Q , S , T ) ,
R 2 ( P , T , X ) R_2(P, T, X) R 2 ( P , T , X ) ,
R 3 ( Q , Y ) R_3(Q, Y) R 3 ( Q , Y ) ,
R 4 ( Y , Z , W ) R_4(Y, Z, W) R 4 ( Y , Z , W ) .
1. Join R 3 ( Q , Y ) R_3(Q, Y) R 3 ( Q , Y ) R 4 ( Y , Z , W ) R_4(Y, Z, W) R 4 ( Y , Z , W ) Common attribute: Y Y Y From FD Y → ZW, Y Y Y R 4 R_4 R 4 Join is lossless. Result: S 1 ( Q , Y , Z , W ) S_1(Q, Y, Z, W) S 1 ( Q , Y , Z , W )
2. Join
R 1 ( P , Q , S , T ) R_1(P, Q, S, T) R 1 ( P , Q , S , T ) and
R 2 ( P , T , X ) R_2(P, T, X) R 2 ( P , T , X ) :
Common attributes: { P , T } \{P, T\} { P , T } From FD P → X, we can infer PT → X. Thus, { P , T } \{P, T\} { P , T } R 2 R_2 R 2 Join is lossless. Result: S 2 ( P , Q , S , T , X ) S_2(P, Q, S, T, X) S 2 ( P , Q , S , T , X )
3. Join
S 1 ( Q , Y , Z , W ) S_1(Q, Y, Z, W) S 1 ( Q , Y , Z , W ) and
S 2 ( P , Q , S , T , X ) S_2(P, Q, S, T, X) S 2 ( P , Q , S , T , X ) :
Common attribute: Q Q Q From FD Q → Y and Y → ZW, by transitivity Q → YZW. Thus, Q Q Q S 1 S_1 S 1 Join is lossless.
Since all steps are lossless,
D 1 D_1 D 1 .
Analyzing Decomposition D 2 D_2 D 2 Relations:
R 1 ( P , Q , S ) R_1(P, Q, S) R 1 ( P , Q , S ) ,
R 2 ( T , X ) R_2(T, X) R 2 ( T , X ) ,
R 3 ( Q , Y ) R_3(Q, Y) R 3 ( Q , Y ) ,
R 4 ( Y , Z , W ) R_4(Y, Z, W) R 4 ( Y , Z , W ) .
1. Join R 3 R_3 R 3 R 4 R_4 R 4 S 1 ( Q , Y , Z , W ) S_1(Q, Y, Z, W) S 1 ( Q , Y , Z , W ) 2. Join R 1 ( P , Q , S ) R_1(P, Q, S) R 1 ( P , Q , S ) S 1 ( Q , Y , Z , W ) S_1(Q, Y, Z, W) S 1 ( Q , Y , Z , W ) Q Q Q Q → YZW). Result: S 2 ( P , Q , S , Y , Z , W ) S_2(P, Q, S, Y, Z, W) S 2 ( P , Q , S , Y , Z , W ) 3. Join S 2 ( P , Q , S , Y , Z , W ) S_2(P, Q, S, Y, Z, W) S 2 ( P , Q , S , Y , Z , W ) R 2 ( T , X ) R_2(T, X) R 2 ( T , X ) Common attributes: None . The intersection is empty. A join with no common attributes is a Cartesian product, which is inherently lossy in this context (we cannot reconstruct the original tuples reliably).
Thus,
D 2 D_2 D 2 .
Correct Option:
(A) Turn this into a strength. Explore AI-powered practice and doubt support with Success Tracker. Review answer and solution without JavaScript Interactive answer checking needs JavaScript. The published solution is available below.
Correct answer (A) D₁ is a lossless decomposition, but D₂ is a lossy decomposition.
Solution A decomposition is
lossless if for every pair of joined relations
R 1 R_1 R 1 and
R 2 R_2 R 2 , the common attributes
R 1 ∩ R 2 R_1 \cap R_2 R 1 ∩ R 2 form a superkey for at least one of the relations (
R 1 R_1 R 1 or
R 2 R_2 R 2 ).
Given FDs:
1. PQ → X
2. P → Y X ⟹ P → Y P \rightarrow YX \implies P \rightarrow Y P → Y X ⟹ P → Y P → X3. Q → Y
4. Y → Z W ⟹ Y → Z Y \rightarrow ZW \implies Y \rightarrow Z Y → Z W ⟹ Y → Z Y → W
Analyzing Decomposition D 1 D_1 D 1 Relations:
R 1 ( P , Q , S , T ) R_1(P, Q, S, T) R 1 ( P , Q , S , T ) ,
R 2 ( P , T , X ) R_2(P, T, X) R 2 ( P , T , X ) ,
R 3 ( Q , Y ) R_3(Q, Y) R 3 ( Q , Y ) ,
R 4 ( Y , Z , W ) R_4(Y, Z, W) R 4 ( Y , Z , W ) .
1. Join R 3 ( Q , Y ) R_3(Q, Y) R 3 ( Q , Y ) R 4 ( Y , Z , W ) R_4(Y, Z, W) R 4 ( Y , Z , W ) Common attribute: Y Y Y From FD Y → ZW, Y Y Y R 4 R_4 R 4 Join is lossless. Result: S 1 ( Q , Y , Z , W ) S_1(Q, Y, Z, W) S 1 ( Q , Y , Z , W )
2. Join
R 1 ( P , Q , S , T ) R_1(P, Q, S, T) R 1 ( P , Q , S , T ) and
R 2 ( P , T , X ) R_2(P, T, X) R 2 ( P , T , X ) :
Common attributes: { P , T } \{P, T\} { P , T } From FD P → X, we can infer PT → X. Thus, { P , T } \{P, T\} { P , T } R 2 R_2 R 2 Join is lossless. Result: S 2 ( P , Q , S , T , X ) S_2(P, Q, S, T, X) S 2 ( P , Q , S , T , X )
3. Join
S 1 ( Q , Y , Z , W ) S_1(Q, Y, Z, W) S 1 ( Q , Y , Z , W ) and
S 2 ( P , Q , S , T , X ) S_2(P, Q, S, T, X) S 2 ( P , Q , S , T , X ) :
Common attribute: Q Q Q From FD Q → Y and Y → ZW, by transitivity Q → YZW. Thus, Q Q Q S 1 S_1 S 1 Join is lossless.
Since all steps are lossless,
D 1 D_1 D 1 .
Analyzing Decomposition D 2 D_2 D 2 Relations:
R 1 ( P , Q , S ) R_1(P, Q, S) R 1 ( P , Q , S ) ,
R 2 ( T , X ) R_2(T, X) R 2 ( T , X ) ,
R 3 ( Q , Y ) R_3(Q, Y) R 3 ( Q , Y ) ,
R 4 ( Y , Z , W ) R_4(Y, Z, W) R 4 ( Y , Z , W ) .
1. Join R 3 R_3 R 3 R 4 R_4 R 4 S 1 ( Q , Y , Z , W ) S_1(Q, Y, Z, W) S 1 ( Q , Y , Z , W ) 2. Join R 1 ( P , Q , S ) R_1(P, Q, S) R 1 ( P , Q , S ) S 1 ( Q , Y , Z , W ) S_1(Q, Y, Z, W) S 1 ( Q , Y , Z , W ) Q Q Q Q → YZW). Result: S 2 ( P , Q , S , Y , Z , W ) S_2(P, Q, S, Y, Z, W) S 2 ( P , Q , S , Y , Z , W ) 3. Join S 2 ( P , Q , S , Y , Z , W ) S_2(P, Q, S, Y, Z, W) S 2 ( P , Q , S , Y , Z , W ) R 2 ( T , X ) R_2(T, X) R 2 ( T , X ) Common attributes: None . The intersection is empty. A join with no common attributes is a Cartesian product, which is inherently lossy in this context (we cannot reconstruct the original tuples reliably).
Thus,
D 2 D_2 D 2 .
Correct Option:
(A) Understand the concept, then try another question Revisit Databases with concept notes, common mistakes and an original worked example before your next attempt.
More questions on Normalization 2026 Set 2 Q15 In the context of DBMS, consider the two sets T and S given below. | T | S | |---|---| | I:… 2026 Set 2 Q20 Consider concurrent execution of two transactions T 1 T_1 T 1 T 2 T_2 T 2 2026 Set 1 Q30 Let P , Q , R P, Q, R P , Q , R S S S 2026 Set 1 Q31 In the context of relational database normalization, which of the following statements is/are true? 2026 Set 2 Q42 In the context of schema normalization in relational DBMS, consider a set F of functional… ← Q42 Full paper Q44 → 