Consider relation {M,N,O,P,Q,R,S,T} with the following set of dependencies MN

Consider a relation R = {M,N,O,P,Q,R,S,T} with the following set of dependencies :

MN -> Q

M -> RQ

N -> R

R -> ST

Next consider the following set of decomposition for the relation scheme R :

Which of the above decomposition (1) has/have lossless join property?

  1. A.

    Only D1

  2. B.

    Only D2

  3. C.

    Both D1 and D­2

  4. D.

    Neither D1 nor D2

Attempted by 69 students.

Show answer & explanation

Correct answer: A

Functional dependencies:

  • M, N -> Q

  • M -> R, Q

  • N -> R

  • R -> S, T

Candidate key for the full relation:

MNOP is a candidate key because starting from M,N,O,P we can use M -> R,Q and R -> S,T to reach all attributes.

Check the first decomposition (relations: R1 = {M,N,O,P}, R2 = {M,P,Q}, R3 = {N,R}, R4 = {R,S,T}):

  • R1 ∩ R2 = {M, P}. Using M -> Q, {M, P} functionally determines Q, and by reflexivity it determines M and P, so {M, P} -> R2. Thus the join of R1 and R2 is lossless.

  • After joining R1 and R2 we have R12 containing N. R12 ∩ R3 = {N}. Since N -> R, {N} -> R3, so joining R12 with R3 is lossless.

  • After joining R12 and R3 we have R123 containing R. R123 ∩ R4 = {R}. Since R -> S,T, {R} -> R4, so joining R123 with R4 is lossless.

Conclusion for the first decomposition: the successive intersections each functionally determine the corresponding fragment, so the first decomposition is a lossless join decomposition.

Check the second decomposition (relations: R1 = {M,N,O}, R2 = {P,Q}, R3 = {N,R}, R4 = {R,S,T}):

  • R1 ∩ R2 = ∅ (no common attributes). Since there is no shared attribute between these two fragments and no FD that connects attributes of R1 to attributes of R2, the join can produce spurious tuples and the decomposition fails the lossless join test.

Conclusion for the second decomposition: it is not lossless.

Final answer: only the first decomposition has the lossless join property.

Explore the full course: Dsssb Tgt Computer Science Paper 2