Chapter 25 of 41

Lossless Join & Dependency Preservation

Every normal form we have studied so far, from 2NF to 5NF, is reached the same way: decompose a table into smaller tables.

But splitting a table is a bit like cutting a photograph into pieces. If you cut carefully, you can put the pieces back together and get the original photo. If you cut carelessly, the pieces don't fit, or worse, they fit in ways that create a picture that never existed.

So every decomposition is judged by two properties:

  • Lossless join: joining the pieces gives back exactly the original table. This one is mandatory.

  • Dependency preservation: every functional dependency can still be checked inside a single table, without joins. This one is highly desirable.

In this chapter we will see what each property means, why it matters, and how to test it quickly, which is a favourite topic in GATE and university exams.


What Is a Decomposition?

A decomposition of a relation schema R is a set of schemas {R1, R2, …, Rn} such that R1 ∪ R2 ∪ … ∪ Rn = R.

Every attribute of R must appear in at least one piece (otherwise you simply threw away a column). The pieces usually share some attributes, and those shared attributes are what we join on later.

Given an instance r of R, the piece tables are the projections:

r1 = π R1 (r),   r2 = π R2 (r),   …,   rn = π Rn (r)

Lossless Join Decomposition

A decomposition {R1, …, Rn} of R is lossless (lossless-join) with respect to a set of FDs F if, for every instance r of R that satisfies F: π R1 (r) ⋈ π R2 (r) ⋈ … ⋈ π Rn (r) = r.

If the join can produce something other than r, the decomposition is called lossy.

A surprising fact: lossy means extra rows

The join of the projections always contains every original tuple. Take any tuple t of r. Its pieces t[R1], t[R2], … are in the projections, and they agree on the shared attributes, so the join glues them back into t.

r  ⊆  π R1 (r) ⋈ π R2 (r) ⋈ … ⋈ π Rn (r)        (always true)

So a lossy join never loses rows. It adds rows that were never in the original table. These are called spurious tuples. We "lose information" because we can no longer tell which rows are real and which are fake.


Seeing Spurious Tuples in MySQL

Here is a small student table. Notice that two different students are both called Rahul:

CREATE TABLE student_city (
  roll_no INT PRIMARY KEY,
  name    VARCHAR(20),
  city    VARCHAR(20)
);
INSERT INTO student_city VALUES
(1, 'Rahul', 'Pune'),
(2, 'Rahul', 'Delhi'),
(3, 'Priya', 'Mumbai');

FD: roll_no → name, city. Names are not unique.

Bad split: join on name

CREATE TABLE r1 AS SELECT roll_no, name FROM student_city;
CREATE TABLE r2 AS SELECT DISTINCT name, city FROM student_city;

SELECT * FROM r1 NATURAL JOIN r2 ORDER BY roll_no, city;

Output:

+-------+---------+--------+
| name  | roll_no | city   |
+-------+---------+--------+
| Rahul |       1 | Delhi  |
| Rahul |       1 | Pune   |
| Rahul |       2 | Delhi  |
| Rahul |       2 | Pune   |
| Priya |       3 | Mumbai |
+-------+---------+--------+

We started with 3 rows and got 5 back. (1, Rahul, Delhi) and (2, Rahul, Pune) are spurious. Looking only at the two pieces, there is no way to know which Rahul lives in which city. Information is lost. (MySQL's NATURAL JOIN joins on the common column name and lists it first.)

Good split: join on roll_no

CREATE TABLE r3 AS SELECT roll_no, city FROM student_city;

SELECT * FROM r1 NATURAL JOIN r3 ORDER BY roll_no;

Output:

+---------+-------+--------+
| roll_no | name  | city   |
+---------+-------+--------+
|       1 | Rahul | Pune   |
|       2 | Rahul | Delhi  |
|       3 | Priya | Mumbai |
+---------+-------+--------+

Exactly the original. Why the difference? The common attribute roll_no is a key of the pieces, so each roll_no matches exactly one city. The common attribute name is not a key of anything, so one name matches many cities.


Test for Two Pieces

That observation is the standard test:

A decomposition of R into R1 and R2 is lossless if and only if the common attributes R1 ∩ R2 functionally determine all of R1 or all of R2. That is, (R1 ∩ R2) → R1 or (R1 ∩ R2) → R2 is in F⁺.

In other words: the common attributes must be a superkey of at least one of the two pieces.

Why it works: if R1 ∩ R2 → R2, then each value of the common attributes appears with exactly one R2-row. So each R1-row can join with only one R2-row, the one it originally came with. No extra combinations are possible.

How to apply it

1. Check R1 ∪ R2 = R.
2. Compute C = R1 ∩ R2.  If C is empty → lossy (the join is a cross product).
3. Compute C⁺ using F.
4. If C⁺ ⊇ R1 or C⁺ ⊇ R2 → lossless.  Otherwise → lossy.

Examples

R(A, B, C), F = { A → B, B → C }

Decomposition

Common

Closure

Result

(A, B), (B, C)

B

B⁺ = BC ⊇ (B, C)

Lossless

(A, B), (A, C)

A

A⁺ = ABC ⊇ both

Lossless

(A, C), (B, C)

C

C⁺ = C

Lossy

(A, B), (C)

none

—

Lossy


Test for More Than Two Pieces

For three or more pieces there are two common approaches.

Method 1: Merge two at a time

If you can repeatedly pick two pieces whose join is lossless (by the binary test), merge them into one, and end with the full R, the decomposition is lossless.

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

(A, B) + (A, C):   common A,  A⁺ = AB ⊇ (A, B)   → lossless, merged = (A, B, C)
(A, B, C) + (C, D): common C, C⁺ = CD ⊇ (C, D)  → lossless, merged = (A, B, C, D) = R  ✓

This method is quick, but if it fails you cannot immediately conclude "lossy" (you might have tried a bad order). For a definite answer, use the chase.

Method 2: The Chase (Tableau) Test

The chase is the general algorithm and works for any number of pieces:

1. Make a table with one column per attribute of R and one row per piece Ri.
2. In row i, write a (distinguished symbol) under attributes in Ri,
   and a unique b-symbol everywhere else.
3. Repeat for each FD X → Y until nothing changes:
     if two rows agree on X, make them agree on Y
     (if either has an a, both get the a; otherwise pick one of the b's).
4. If some row becomes all a's → lossless. Otherwise → lossy.

Same example. We number symbols as a1…a4 for columns A…D, and b(row)(column) for the others.

Initial tableau:
            A     B     C     D
(A, B)      a1    a2    b13   b14
(C, D)      b21   b22   a3    a4
(A, C)      a1    b32   a3    b34

Apply A → B:  rows 1 and 3 agree on A (a1) → make B equal: b32 becomes a2
(A, C)      a1    a2    a3    b34

Apply C → D:  rows 2 and 3 agree on C (a3) → make D equal: b34 becomes a4
(A, C)      a1    a2    a3    a4      ← all a's

Row 3 is all a's, so the decomposition is lossless.

What if we drop the third piece and use only { (A, B), (C, D) }? The two rows share no a's in any column, no FD can fire, and no row ever becomes all a's: lossy. That matches the binary test: the common attribute set is empty.

Intuition: the all-a row represents "a tuple of the original table". If the FDs force the pieces to reassemble into exactly that tuple, the join cannot invent anything new.


Dependency Preservation

A lossless decomposition guarantees we can always rebuild the data. But there is a second concern: can we still enforce our rules cheaply?

We met this problem in the BCNF chapter. After splitting stc(student, course, teacher) into (teacher, course) and (student, teacher), the rule student, course → teacher could not be checked inside any table, and MySQL happily accepted a row that broke it.

Definition

For each piece Ri, let Fi be the set of FDs in F⁺ that use only attributes of Ri (the projection of F⁺ onto Ri).

A decomposition {R1, …, Rn} is dependency preserving if (F1 ∪ F2 ∪ … ∪ Fn)⁺ = F⁺.

In words: if we enforce, in each table separately, just the FDs local to that table, then all the original FDs are automatically enforced too.

Why do we care? A local FD is enforced by a primary key or UNIQUE constraint on one table, which the DBMS checks almost for free on every insert. A non-local FD needs a join on every insert or update, which means triggers or application code, and it is easy to forget.

The quick check (only one direction)

If every FD in F has all its attributes inside some single Ri, the decomposition is dependency preserving. Done.

But if some FD is not inside any single table, do not immediately conclude that it is lost. It might still be derivable from the local FDs of several tables. For that you need the proper test.

The Closure-Based Test

For each FD X → Y in F, run:

Z = X
repeat
    for each piece Ri:
        Z = Z ∪ ( (Z ∩ Ri)⁺ ∩ Ri )      ← closure computed with the full F
until Z stops changing

If Y ⊆ Z  → X → Y is preserved
else       → X → Y is NOT preserved

The step (Z ∩ Ri)⁺ ∩ Ri means: "using only what table Ri can check, what else can we infer from the attributes we already have?" This avoids computing F⁺ (which can be exponentially large).

Example 1: An FD that looks lost but isn't

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

A → B, B → C and C → D each fit inside a table. But D → A is not inside any table. Lost? Let's test:

Z = {D}
(A,B):  Z ∩ AB = ∅                               → nothing
(B,C):  Z ∩ BC = ∅                               → nothing
(C,D):  (D)⁺ = ABCD,  ∩ CD = CD                  → Z = {C, D}
(A,B):  Z ∩ AB = ∅                               → nothing
(B,C):  (C)⁺ = ABCD,  ∩ BC = BC                  → Z = {B, C, D}
(C,D):  nothing new
(A,B):  (B)⁺ = ABCD,  ∩ AB = AB                  → Z = {A, B, C, D}
A ∈ Z  → D → A is preserved ✓

What happened? Because the FDs form a cycle, table (C, D) locally satisfies D → C, table (B, C) satisfies C → B, and table (A, B) satisfies B → A. Chaining them gives D → C → B → A. The decomposition is dependency preserving even though D → A is not written inside any table.

Example 2: An FD that really is lost

R(A, B, C), F = { A → B, B → C }, decomposition { (A, B), (A, C) }.

Test B → C:
Z = {B}
(A,B):  (B)⁺ = BC,  ∩ AB = B     → nothing new
(A,C):  Z ∩ AC = ∅                → nothing
Z = {B},  C ∉ Z  → B → C is NOT preserved ✗

This decomposition is lossless (A is a key) but not dependency preserving. Compare it with { (A, B), (B, C) }, which is both. So the choice of decomposition matters.


Lossless and Dependency Preserving: Four Combinations

The two properties are independent. Using R(A, B, C) with F = { A → B, B → C }:

Decomposition

Lossless?

Dependency preserving?

(A, B), (B, C)

Yes

Yes

(A, B), (A, C)

Yes

No (B → C lost)

(A, C), (B, C)

No

No (A → B lost)

And from the earlier chase example, R(A, B, C, D) with F = { A → B, C → D } split into { (A, B), (C, D) } is dependency preserving (each FD sits in its own table) but lossy. So all combinations really occur.


Getting Both: 3NF Synthesis

Can we always find a decomposition into a good normal form that is both lossless and dependency preserving?

  • For 3NF: yes, always. The algorithm below guarantees it.

  • For BCNF: lossless, yes (the BCNF algorithm guarantees it), but dependency preservation is not always possible.

The 3NF Synthesis Algorithm

1. Find a canonical cover Fc of F.
2. For each FD X → Y in Fc, create a table (X ∪ Y).
   (Group FDs with the same left side into one table.)
3. If none of the tables contains a candidate key of R,
   add one more table consisting of any candidate key.
4. Remove any table whose attributes are a subset of another table.

Why it works:

  • Step 2 puts every FD of the canonical cover inside some table, so dependencies are preserved.

  • Step 3 makes sure some table contains a key. In the chase, that row becomes all a's, so the decomposition is lossless.

  • Using a canonical cover (see the Canonical Cover chapter) keeps each table in 3NF and avoids redundant tables.

Worked Example

R(A, B, C, D, E), F = { A → B, BC → D, D → A }

Step 1. F is already a canonical cover: every right side is a single attribute; no left side has an extraneous attribute (B⁺ = B and C⁺ = C, so neither alone gives D); and no FD can be derived from the others.

Step 2. One table per FD:

A → B     →   (A, B)
BC → D    →   (B, C, D)
D → A     →   (A, D)

Step 3. Candidate keys of R: C and E appear on no right side, so they are in every key. (CE)⁺ = CE. Adding one more attribute:

(ACE)⁺ = ACE → +B (A → B) → +D (BC → D) = ABCDE   ✓
(BCE)⁺ = BCE → +D → +A                    = ABCDE   ✓
(CDE)⁺ = CDE → +A → +B                    = ABCDE   ✓

Keys: ACE, BCE, CDE. None of (A, B), (B, C, D), (A, D) contains a key, so add (A, C, E).

Step 4. No table is a subset of another.

Result: (A, B), (B, C, D), (A, D), (A, C, E). This is lossless (a chase on it ends with the (A, C, E) row all a's) and preserves all three FDs.

Compare with the BCNF decomposition of the same relation in the BCNF chapter: (A, B), (A, D), (C, D, E). That one is in BCNF, but loses BC → D. The 3NF result keeps BC → D, at the cost of table (B, C, D) not being in BCNF (D → B holds in it, through D → A → B, and D is not a key of that table).


Summary of Guarantees

Target normal form

Lossless always achievable?

Dependency preservation always achievable?

3NF

Yes

Yes

BCNF

Yes

No

4NF

Yes

No


Practice Problems

For Q1–Q3: R(A, B, C, D), F = { AB → C, C → D, D → A }. (Candidate keys: AB, BC, BD.)

Q1. Decomposition { (A, B, C), (C, D) }. Lossless? Dependency preserving?

Common attribute: C. C⁺ = CDA ⊇ (C, D), so lossless.

AB → C lies in (A, B, C) and C → D lies in (C, D). Test D → A: Z = {D}; (A, B, C): Z ∩ ABC = ∅; (C, D): D⁺ = DA, ∩ CD = D, nothing new. A ∉ Z, so D → A is not preserved.

Q2. Decomposition { (A, B), (B, C, D) }. Lossless?

Common attribute: B. B⁺ = B, which contains neither piece. Lossy.

Q3. Decomposition { (A, C, D), (B, C) }. Lossless? Dependency preserving?

Common attribute: C. C⁺ = ACD ⊇ (A, C, D), so lossless. C → D and D → A lie in (A, C, D). Test AB → C: Z = {A, B}; (A, C, D): A⁺ = A, nothing; (B, C): B⁺ = B, nothing. C ∉ Z, so AB → C is not preserved.

Q4. R(A, B, C, D, E), F = { A → B, C → D }. Compare { (A, B), (C, D), (A, C, E) } and { (A, B), (C, D), (A, E) }.

The only key is ACE. The first decomposition contains the key in (A, C, E); merging (A, B) with (A, C, E) on A, then with (C, D) on C, rebuilds R: lossless. The second has no piece containing C together with A or E: in the chase, no row can ever get an a under both C and E. Lossy. Both preserve the FDs, since A → B and C → D each sit in one table.


Common Mistakes

  • Thinking "lossy" means rows go missing. Lossy joins produce extra (spurious) rows.

  • Checking only that the pieces share some attribute. Sharing is necessary but not enough: the shared attributes must be a superkey of one piece.

  • Declaring an FD lost because it doesn't fit in one table. Run the closure test first; cyclic FDs are often preserved indirectly.

  • Computing (Z ∩ Ri)⁺ with only the FDs inside Ri. The closure uses the full F; the "∩ Ri" afterwards is what restricts it to the table.

  • Forgetting the key table in 3NF synthesis. Without it, the result can be lossy.

  • Assuming BCNF always preserves dependencies. It is always lossless, not always dependency preserving.


Interview Questions

What is a lossless join decomposition?

A decomposition where the natural join of the projections always equals the original relation, with no spurious tuples.

How do you test if a decomposition into two relations is lossless?

Check whether the common attributes R1 ∩ R2 functionally determine R1 or R2, i.e. are a superkey of one of the pieces.

What are spurious tuples?

Rows produced by joining the pieces of a lossy decomposition that did not exist in the original relation.

What is dependency preservation and why is it important?

A decomposition is dependency preserving if the FDs that hold within individual tables imply all original FDs. It matters because local FDs can be enforced cheaply by keys and unique constraints, while non-local ones need joins or triggers.

Is it always possible to get a lossless, dependency-preserving decomposition?

Into 3NF, yes, using the 3NF synthesis algorithm. Into BCNF, not always; you can always get lossless, but some FDs may be lost.

Which property is mandatory?

Lossless join is mandatory, because a lossy decomposition corrupts data. Dependency preservation is desirable but is sometimes sacrificed to reach BCNF.


Summary

  • A decomposition splits R into pieces whose union is R.

  • Lossless: the join of the projections equals the original. Lossy joins add spurious tuples.

  • Two pieces: lossless iff (R1 ∩ R2) → R1 or (R1 ∩ R2) → R2.

  • More pieces: merge two at a time, or use the chase (all-a row means lossless).

  • Dependency preserving: the local FDs of the pieces imply all of F. Test each FD with the closure-based algorithm.

  • The two properties are independent of each other.

  • 3NF synthesis always gives both; BCNF guarantees only losslessness.

Lossless: you can always put the data back together. Dependency preserving: you can still check every rule without putting it back together.