Lossless-join decomposition: binary test and chase (table) method

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. What is a minimal cover? from Lesson 4.2.5
2. How do you test whether X → Y is implied by F? from Lesson 4.2.4
3. Why must a split of ENROLL_INFO be done carefully? from Lesson 4.1.1

1 · The Hook

To remove anomalies, we split one table into several (a decomposition). But the information must still be there: joining the pieces should give back exactly the original rows. Split badly, and the join invents rows that never existed. The test for a good split is short and GATE asks it every year.

2 · Predict First

R(roll, cid, dept) holds (1, C1, CS) and (2, C2, CS). Split it into R1(roll, dept) and R2(cid, dept). Join R1 ⋈ R2. How many rows come back?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

R1 = {(1, CS), (2, CS)}, R2 = {(C1, CS), (C2, CS)}. Joining on dept pairs every roll with every cid: 4 rows, two of them (1, C2, CS) and (2, C1, CS) are spurious. The split is lossy.

Decomposition

A decomposition of R is a set of relation schemas {R₁, …, Rₙ} whose attributes together cover R. Each Rᵢ gets the projection πRᵢ(r) of the data.

Lossless join

The decomposition is lossless (non-additive) if, for every legal state r of R:

πR₁(r) ⋈ πR₂(r) ⋈ … ⋈ πRₙ(r) = r.

The join always contains r; the danger is extra (spurious) tuples. "Lossy" means information is lost because you can no longer tell real rows from invented ones.

Binary test (two pieces)

{R₁, R₂} is lossless iff the common attributes determine one side:

(R₁ ∩ R₂) → R₁ or (R₁ ∩ R₂) → R₂ is in F⁺.

Equivalently: R₁ ∩ R₂ is a superkey of R₁ or of R₂. Compute (R₁ ∩ R₂)⁺ and check whether it contains all of R₁ or all of R₂. If R₁ ∩ R₂ = ∅, the decomposition is lossy (unless one piece has at most one row).

Example: R(A, B, C, D), F = {A → B, C → D}.

• {AB, CD}: common = ∅ → lossy.
• {AB, ACD}: common = A, A⁺ = AB ⊇ AB → lossless.

Chase (table) method: any number of pieces

1. Make a table: one row per piece, one column per attribute. Put a symbol a (for "agreed") in row i, column A if A ∈ Rᵢ; otherwise put bi (a placeholder unique to that row).
2. For each FD X → Y: whenever two rows agree on all X columns, make their Y columns equal (if either is a, both become a; otherwise pick one b).
3. Repeat until nothing changes.
4. Lossless iff some row becomes all a's.

Chase example

R(A, B, C, D, E), F = {A → B, B → C, C → D, D → E}, pieces R₁ = AB, R₂ = BC, R₃ = CDE.

• B → C: rows 1, 2 agree on B (a), so C becomes a in row 1.
• C → D: rows 1, 2, 3 agree on C (a), so D becomes a in rows 1, 2.
• D → E: now all agree on D, so E becomes a in rows 1, 2.
• Row 1 = a a a a a → lossless.

(For two pieces the chase reduces to the binary test.)

Successive binary splits

If R is split losslessly into R₁ and R₂, and R₂ is split losslessly again, the three-piece result is lossless. BCNF decomposition (Lesson 4.4.6) relies on this.

4 · Visual

Binary test:   common = R1 ∩ R2      lossless iff  common -> R1  or  common -> R2

R(A,B,C,D), F = {A->B, C->D}

{AB, CD}    common = {}   {}+ = {}          -> LOSSY
{AB, ACD}   common = A    A+  = AB ⊇ AB     -> LOSSLESS
{AC, BD}    common = {}                     -> LOSSY

5 · Worked Examples

Example 1 Easy

R(A, B, C), F = {B → C}. Is {AB, BC} lossless? Is {AB, AC}?

Solution

{AB, BC}: common B, B⁺ = BC ⊇ BC → lossless. {AB, AC}: common A, A⁺ = A → lossy.

Example 2 Medium

ENROLL_INFO(roll, name, dept, hod, cid, title, grade) is split into S(roll, name, dept, hod) and E(roll, cid, title, grade). Lossless?

Solution

Common = roll. roll⁺ = roll, name, dept, hod ⊇ S → lossless.

Example 3 GATE

R(A, B, C, D, E, F) with F = {A → B, B → C, C → D, D → E} is decomposed into {AB, BCD, DEF}. Lossless?

Solution

Chase: row AB gains C, D, E (through B → C, C → D, D → E) but never F; row DEF never gains A, B or C. No row becomes all a's: lossy. (Every key of R contains both A and F, and no piece can reach both.)

8 · Connect the Dots

Chapter 4.2 gave closures; this lesson used them to check that splitting a table loses nothing. Next: the second property a good split should have: every original FD can still be checked inside a single piece: dependency preservation.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · MCQ · 1 mark(s) — Binary test

R(A, B, C), F = {A → B}. Which decomposition is lossless?

1. (A) {A, BC}
2. (B) {AB, AC}
3. (C) {AC, BC}
4. (D) {AB, BC}

Q2 · MCQ · 2 mark(s) — Binary test

R(A, B, C, D), F = {AB → C, C → D}. Decomposition {ABC, CD}:

1. (A) lossless, because C → CD
2. (B) lossy, because C is not a key of R
3. (C) lossless, because AB is a key of R
4. (D) lossy, because the pieces overlap

Q3 · MSQ · 2 mark(s) — Chase

R(A, B, C, D, E), F = {A → BC, C → D, D → E}. Which decompositions are lossless?

1. (A) {ABC, CD, DE}
2. (B) {AB, CDE}
3. (C) {ABC, CDE}
4. (D) {AD, BCE}

Q4 · NAT · 1 mark(s) — Spurious tuples

R(A, B, C) holds (1, x, p) and (2, x, q). It is split into AB and BC. How many tuples does the join of the two projections have?

Numerical answer: ________

Q5 · MCQ · 1 mark(s) — Definition

A decomposition is lossless if:

1. (A) every piece is in BCNF
2. (B) every FD is preserved
3. (C) joining the projections gives back exactly the original relation
4. (D) no attribute is lost

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

decompositionprojection of a relation onto a piecelossless (non-additive) joinlossy decompositionspurious tuplesbinary lossless testchase (table) method