5.3Lossless-join decomposition
The idea
A decomposition is lossless if natural-joining the parts gives back exactly the original table, with no spurious rows.
Think of it like this: Cutting a map into two pieces: they must overlap in a strip that tells you exactly how to glue them back.
Why it exists
Lossless-join questions use either the quick binary rule or the chase test.
How it works
- Two parts: R1 ∩ R2 must determine R1 − R2 or R2 − R1.
- More parts: build a table of rows (one per part), a_j for attributes the part has, b_ij otherwise.
- Apply each FD: rows that agree on the left side get equal right-side symbols (prefer a).
- Lossless if some row ends up all a.
Worked example: R(A, B, C) split into AB and BC with B → C.
AB ∩ BC = B determines BC − AB = C, so lossless. With only A → B it would be lossy.
Now play with it
- →Press the two example buttons and compare the verdicts.
- →Step through the chase table for five relations.
| Relation | A | B | C | D | E |
|---|---|---|---|---|---|
| R1 (AD) | a1 | b12 | b13 | a4 | b15 |
| R2 (AB) | a1 | a2 | b23 | b24 | b25 |
| R3 (BE) | b31 | a2 | b33 | b34 | a5 |
| R4 (CDE) | b41 | b42 | a3 | a4 | a5 |
| R5 (AE) | a1 | b52 | b53 | b54 | a5 |
- Initial tableau: a_j where the relation has the attribute, b_ij otherwise
- Apply A → C: rows 1 and 2 agree on A, so make C equal (b23 → b13)
- Apply A → C: rows 1 and 5 agree on A, so make C equal (b53 → b13)
- Apply B → C: rows 2 and 3 agree on B, so make C equal (b33 → b13)
- Apply C → D: rows 1 and 2 agree on C, so make D equal (b24 → a4)
- Apply C → D: rows 1 and 3 agree on C, so make D equal (b34 → a4)
- Apply C → D: rows 1 and 5 agree on C, so make D equal (b54 → a4)
- Apply DE → C: rows 3 and 4 agree on DE, so make C equal (b13 → a3)
- Apply CE → A: rows 3 and 4 agree on CE, so make A equal (b41 → b31)
- Apply CE → A: rows 3 and 5 agree on CE, so make A equal (b31 → a1)
For a binary split R1, R2 you can skip the table: lossless iff (R1 ∩ R2) → (R1 − R2) or (R1 ∩ R2) → (R2 − R1) holds.
Check yourself
R(A, B, C) with F = {A → B} decomposed into AB and BC is
Exam notes (the dense version)
A decomposition is lossless if joining the parts gives back exactly the original rows. For two relations R1, R2: lossless iff (R1 ∩ R2) → (R1 − R2) or (R1 ∩ R2) → (R2 − R1). For more relations use the chase (tableau) test: start with a row per relation, apply the FDs to equate symbols, lossless if some row becomes all distinguished. Lossy joins create spurious tuples.
Previous year questions: Normal Forms & Decomposition (11)
PYQs are grouped by topic, so this is the full set for Normal Forms & Decomposition; try the ones that match this subtopic. Open all 11 on the topic page.