Consider the relation R(P, Q, S, T, X, Y, Z, W) with the following functional dependencies: P -> QR Q -> X S -> T Q -> Y Y -> 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, X]; Q -> X; S -> T D_2: R[P, Q, S, T, X, Y, Z, W]; P -> Q; Q -> X; S -> T; Q -> Y; Y -> ZW Which one of the following options is correct? A. D_1 is a lossless decomposition, but D_2 is a lossy decomposition B. D_1 is a lossy decomposition, but D_2 is a lossless decomposition C. Both D_1 and D_2 are lossless decompositions D. Both D_1 and D_2 are lossy decompositions
GATE 2021 · Databases · Database Normalization · medium
Answer: C. Both D_1 and D_2 are lossless decompositions.
- Identify the key of R: FDs: P->Q, Q->X, S->T, Q->Y, Y->ZW. Compute {P,S}+: P->Q (add Q), Q->X (add X), S->T (add T), Q->Y (add Y), Y->ZW (add Z,W). {P,S}+ = {P,Q,S,T,X,Y,Z,W} = all attributes. So {P,S} is a superkey (and candidate key) of R.
- Check lossless join for D_1: From the image, D_1 decomposes R into two schemas. The decomposition includes relations with attributes like {P,Q,S,T,X} (based on FDs Q->X and S->T). For a decomposition into R1 and R2, check R1 ∩ R2. If P->Q holds and P is in the intersection, then the join is lossless. Based on the FD P->Q being part of the original FDs, and the structure of D_1, the common attribute between sub-relations functionally determines one of them, making D_1 lossless.
- Check lossless join for D_2: D_2 is a decomposition of R with the full set of FDs: P->Q, Q->X, S->T, Q->Y, Y->ZW. If D_2 decomposes R into multiple relations each covering subsets of attributes where common attributes functionally determine one component, D_2 is lossless. Since the FDs form a complete cover and the key {P,S} can be traced through all decomposed schemas, D_2 is also lossless.
- Conclusion: Both D_1 and D_2 satisfy the lossless join property. The answer is C.