Which of the following conditions must hold for decomposition of
Which of the following conditions must hold for a decomposition of a relation R into R1 and R2 to be lossless?
- A.
R1∩R2→R1
- B.
R1∩R2→R2
- C.
Either (A) or (B)
- D.
Both (A) and (B)
Attempted by 207 students.
Show answer & explanation
Correct answer: C
Key insight: the common attributes (R1∩R2) must functionally determine all attributes of at least one of the decomposed relations.
If the common attributes functionally determine all attributes of the first relation (R1∩R2 → R1), then those common attributes act as a key for the first relation. Joining the two relations on the common attributes recovers the original tuples for the first relation without introducing spurious tuples.
Similarly, if the common attributes functionally determine all attributes of the second relation (R1∩R2 → R2), then the join is lossless because the second relation is uniquely recoverable from the common attributes.
Therefore, for a decomposition of R into R1 and R2 to be lossless it is sufficient that the intersection of their attributes functionally determines either all attributes of R1 or all attributes of R2. Requiring both directions is stronger than necessary.
A short way to test this in practice is the chase: if starting with a row symbolization the intersection attributes force one side's attributes to a single symbol via functional dependencies, the decomposition is lossless.