Skip to content

Lesson 23: Lossless Join and Dependency Preservation

Lossless join, dependency preservation, and how to test them

About this lesson

Course: Database Management Systems

Unit 5: Database Design · 10 Lecture Hours

Lesson duration: 2 lectures

Reading: Elmasri & Navathe, Ch. 15.2, 15.3

Learning Outcomes

  1. Define attribute preservation, lossless join and dependency preservation.
  2. Demonstrate spurious tuples from a lossy decomposition.
  3. Apply the binary lossless-join test and justify it.
  4. Apply the chase (tableau) algorithm for a decomposition into three or more relations.
  5. Test a decomposition for dependency preservation.

23.1 The Three Desirable Properties

Decomposition

A decomposition of a relation schema R is a set of relation schemas D = {R1, R2, ..., Rm} obtained by distributing the attributes of R among them.

Property 1 — Attribute preservation

R1 ∪ R2 ∪ ... ∪ Rm = R

Every attribute of R must appear in at least one fragment. Obvious, but worth checking first: a decomposition that quietly drops an attribute has lost information before any join is attempted.

Property 2 — Lossless join (non-additive join)

For every legal state r of R:

π<sub>R1</sub>(r) ⋈ π<sub>R2</sub>(r) ⋈ ... ⋈ π<sub>Rm</sub>(r) = r

Projecting onto the fragments and joining them back must reproduce exactly the original relation — no rows lost and, more importantly, no rows invented.

The name is misleading

"Lossless" suggests tuples might be lost. In fact projecting and rejoining can never lose a tuple — every original tuple always reappears.

The danger is the opposite: extra tuples appear. These are spurious tuples, and they assert facts that were never true. Elmasri and Navathe therefore prefer the name non-additive join property, which is more accurate.

Property 3 — Dependency preservation

Let π<sub>Ri</sub>(F) denote the dependencies of F⁺ involving only attributes of Ri. The decomposition is dependency preserving if

( π<sub>R1</sub>(F) ∪ π<sub>R2</sub>(F) ∪ ... ∪ π<sub>Rm</sub>(F) )⁺ = F⁺

In words: every original constraint can be checked on a single fragment, with no join required.

23.2 Spurious Tuples — the Concrete Danger

Take EMP_PROJ( Ssn, Pnumber, Hours, Ename, Pname, Plocation ):

Ssn Pnumber Hours Ename Pname Plocation
111 1 32.5 Smith ProductX Bellaire
111 2 7.5 Smith ProductY Sugarland
222 3 40.0 Narayan ProductZ Houston
333 1 20.0 English ProductX Bellaire

A bad decomposition — split on Plocation, which determines nothing:

EMP_LOCS(Ename, Plocation) and EMP_PROJ1(Ssn, Pnumber, Hours, Pname, Plocation)

EMP_LOCS:

Ename Plocation
Smith Bellaire
Smith Sugarland
Narayan Houston
English Bellaire

EMP_PROJ1:

Ssn Pnumber Hours Pname Plocation
111 1 32.5 ProductX Bellaire
111 2 7.5 ProductY Sugarland
222 3 40.0 ProductZ Houston
333 1 20.0 ProductX Bellaire

Now join them back on Plocation:

Ssn Pnumber Hours Pname Plocation Ename Genuine?
111 1 32.5 ProductX Bellaire Smith yes
111 1 32.5 ProductX Bellaire English SPURIOUS
111 2 7.5 ProductY Sugarland Smith yes
222 3 40.0 ProductZ Houston Narayan yes
333 1 20.0 ProductX Bellaire Smith SPURIOUS
333 1 20.0 ProductX Bellaire English yes

Six rows instead of four. Row 2 asserts that employee 111 is named English; row 5 that 333 is named Smith. Both are false.

Why this is worse than a lost dependency

Nothing in the decomposed database is wrong when examined table by table. Both fragments are individually correct and consistent. The corruption appears only when the data is reassembled, and there is no way to distinguish the spurious rows from the genuine ones.

The cause: Plocation is a common attribute that is not a key of either fragment. Joining on a non-key column matches every row to every other row sharing that value.

23.3 Testing for Lossless Join — the Binary Case

The binary test

A decomposition of R into exactly two relations R1 and R2 is lossless if and only if the common attributes form a superkey of at least one fragment:

(R1 ∩ R2) → R1 or (R1 ∩ R2) → R2

Operationally: compute (R1 ∩ R2)⁺ under F, and check whether it contains all of R1 or all of R2.

Why the test works

The join matches rows of R1 and R2 that agree on the common attributes C = R1 ∩ R2.

If C is a superkey of R2, then each value of C occurs in at most one tuple of R2. So each tuple of R1 finds exactly one partner, the join produces exactly |R1| rows, and no combination can be invented.

If C is a superkey of neither, several tuples on each side may share a C value, and the join forms every cross-combination — precisely the spurious tuples of Section 5.2.

Worked tests

Test 1 — the good decomposition. STUDENT(Rollno, Sname, Dno) and DEPARTMENT(Dno, Dname, Dhead), with Rollno → Sname, Dno and Dno → Dname, Dhead.

Common attributes: {Dno}. Dno⁺ = {Dno, Dname, Dhead}, which contains all of DEPARTMENT. So Dno is a superkey of DEPARTMENT. Lossless.

Test 2 — the bad decomposition. R(A,B,C) with A → B and C → B, split into R1(A,B) and R2(B,C).

Common attributes: {B}. B⁺ = {B}, which contains neither R1 = {A,B} nor R2 = {B,C}. Lossy.

Confirm with data. Let r = {(a1,b1,c1), (a2,b1,c2)}:

π<sub>AB</sub>(r) = {(a1,b1), (a2,b1)}; π<sub>BC</sub>(r) = {(b1,c1), (b1,c2)}.

The join on B gives four tuples — (a1,b1,c1), (a1,b1,c2), (a2,b1,c1), (a2,b1,c2) — two of which are spurious.

Test 3 — the BCNF algorithm is always lossless. The algorithm splits Q on a violating X → Y into Q1 = X ∪ Y and Q2 = Q − Y. The common attributes are exactly X, and X is by construction a superkey of Q1 = X ∪ Y (since X → Y and trivially X → X). The condition is therefore satisfied at every step. This is why the algorithm can be applied without checking losslessness each time.

23.4 The Chase (Tableau) Algorithm — Three or More Fragments

The binary test does not generalise. For m ≥ 3 fragments, use the chase.

Algorithm

  1. Build a matrix S with one row per fragment Ri and one column per attribute of R.
  2. Initialise: cell S(i, j) is the distinguished symbol a_j if attribute A_j belongs to Ri; otherwise the non-distinguished symbol b_ij.
  3. Repeat until no change: for each dependency X → Y in F, find rows that agree on all attributes of X. Make them agree on Y too — if one of the rows has an a symbol in a Y column, set the others to that a; otherwise set them all to the same b symbol.
  4. If, at the end, any row consists entirely of a symbols, the decomposition is lossless. Otherwise it is lossy.

Worked example

R(A,B,C,D,E) with F = {A → C, B → C, C → D, DE → C, CE → A}, decomposed into R1(A,D), R2(A,B), R3(B,E), R4(C,D,E), R5(A,E).

Initial tableau:

A B C D E
R1(A,D) a₁ b₁₂ b₁₃ a₄ b₁₅
R2(A,B) a₁ a₂ b₂₃ b₂₄ b₂₅
R3(B,E) b₃₁ a₂ b₃₃ b₃₄ a₅
R4(C,D,E) b₄₁ b₄₂ a₃ a₄ a₅
R5(A,E) a₁ b₅₂ b₅₃ b₅₄ a₅

Apply A → C. Rows 1, 2 and 5 agree on A (all a₁). Make their C values agree — none is a₃, so set all three to b₁₃.

A B C D E
R1 a₁ b₁₂ b₁₃ a₄ b₁₅
R2 a₁ a₂ b₁₃ b₂₄ b₂₅
R3 b₃₁ a₂ b₃₃ b₃₄ a₅
R4 b₄₁ b₄₂ a₃ a₄ a₅
R5 a₁ b₅₂ b₁₃ b₅₄ a₅

Apply B → C. Rows 2 and 3 agree on B (a₂). Set both C values to b₁₃.

Row 3 C becomes b₁₃.

Apply C → D. Rows 1, 2, 3, 5 now share C = b₁₃. Row 1 has D = a₄, a distinguished symbol, so set all of them to a₄.

A B C D E
R1 a₁ b₁₂ b₁₃ a₄ b₁₅
R2 a₁ a₂ b₁₃ a₄ b₂₅
R3 b₃₁ a₂ b₁₃ a₄ a₅
R4 b₄₁ b₄₂ a₃ a₄ a₅
R5 a₁ b₅₂ b₁₃ a₄ a₅

Apply DE → C. Rows 3, 4 and 5 agree on D = a₄ and E = a₅. Row 4 has C = a₃, so set rows 3 and 5 to a₃.

A B C D E
R3 b₃₁ a₂ a₃ a₄ a₅
R5 a₁ b₅₂ a₃ a₄ a₅

Apply CE → A. Rows 3, 4 and 5 agree on C = a₃ and E = a₅. Row 5 has A = a₁, so set rows 3 and 4 to a₁.

A B C D E
R1 a₁ b₁₂ b₁₃ a₄ b₁₅
R2 a₁ a₂ b₁₃ a₄ b₂₅
R3 a₁ a₂ a₃ a₄ a₅
R4 a₁ b₄₂ a₃ a₄ a₅
R5 a₁ b₅₂ a₃ a₄ a₅

Row 3 is now a₁ a₂ a₃ a₄ a₅ — all distinguished symbols.

Conclusion: the decomposition is LOSSLESS.

Reading the chase

A row of all a symbols means: whatever legal tuples the fragments contain, the join can always reconstruct a tuple identical to the original on every attribute. The b symbols represent values the fragment does not constrain; the dependencies gradually force them to coincide with the real values.

If the algorithm halts with no complete a-row, the remaining b symbols correspond exactly to the freedom that lets spurious tuples arise.

23.5 Testing Dependency Preservation

Procedure

  1. For each fragment Ri, compute its projected dependencies π<sub>Ri</sub>(F) — every FD X → Y in F⁺ with X ∪ Y ⊆ Ri. In practice: for each subset X of Ri, compute X⁺ under the full F, then intersect with Ri.
  2. Let G be the union of all the projected sets.
  3. For each dependency X → Y in the original F, test whether Y ⊆ X⁺ computed under G.
  4. If every one passes, the decomposition is dependency preserving.

The subtlety in step 3

It is not enough to check whether each original dependency lies inside a single fragment. A dependency may be recoverable from the combination of projected dependencies even though it appears in no fragment.

Example. R(A,B,C) with F = {A → B, B → C}, decomposed into R1(A,B) and R2(B,C). The dependency A → C (which is in F⁺) spans both fragments and appears in neither. Yet A⁺ under G = {A → B, B → C} is {A,B,C}, so A → C is preserved. Always run the closure test.

Worked test 1 — preserved

R(Rollno, Sname, Dno, Dname) with Rollno → Sname, Dno and Dno → Dname, decomposed into R1(Rollno, Sname, Dno) and R2(Dno, Dname).

  • π<sub>R1</sub>(F) contains Rollno → Sname, Dno.
  • π<sub>R2</sub>(F) contains Dno → Dname.
  • G = {Rollno → Sname, Dno ; Dno → Dname}.

Test each original FD: Rollno⁺ under G = {Rollno, Sname, Dno, Dname} ⊇ {Sname, Dno} ✓. Dno⁺ under G = {Dno, Dname} ⊇ {Dname} ✓.

Dependency preserving.

Worked test 2 — not preserved

TEACHING(Student, Subject, Teacher) with Student,Subject → Teacher and Teacher → Subject, decomposed into TEACHES(Teacher, Subject) and STUDIES(Student, Teacher).

  • π<sub>TEACHES</sub>(F) = {Teacher → Subject}.
  • π<sub>STUDIES</sub>(F): compute Student⁺ = {Student}; Teacher⁺ = {Teacher, Subject}, intersected with {Student, Teacher} gives {Teacher} — nothing new. So π<sub>STUDIES</sub>(F) = ∅.
  • G = {Teacher → Subject}.

Test Student, Subject → Teacher: {Student, Subject}⁺ under G = {Student, Subject}. Teacher ∉ it.

Not preserved. This confirms by algorithm what Lesson 4 argued informally.

23.6 Summary of the Whole Unit

   REQUIREMENTS
        |
        v
   ER DIAGRAM              (Unit 2)
        |
        |  seven-step mapping algorithm            (Lesson 1)
        v
   RELATIONAL SCHEMA
        |
        |  identify FUNCTIONAL DEPENDENCIES        (Lesson 2)
        |  compute ATTRIBUTE CLOSURES
        |  find ALL CANDIDATE KEYS
        v
   TEST NORMAL FORM        1NF / 2NF / 3NF         (Lesson 3)
                           BCNF                    (Lesson 4)
        |
        |  DECOMPOSE if necessary
        v
   VERIFY   lossless join?          (binary test or chase)   (Lesson 5)
            dependency preserving?  (projection + closure)
        |
        v
   FINAL SCHEMA -> SQL DDL          (Unit 4)

23.7 Solved Questions

Solved Question 1

Q. Define the lossless-join property. Why is "lossless" a misleading name? Demonstrate spurious tuples.

A. A decomposition of R into R1, ..., Rm has the lossless-join property if, for every legal state r of R,

π<sub>R1</sub>(r) ⋈ ... ⋈ π<sub>Rm</sub>(r) = r

The name is misleading because projecting and rejoining can never lose a tuple — every original tuple always reappears in the join. The actual failure is the reverse: extra tuples are produced. These are spurious tuples, and they assert facts that were never true. Elmasri and Navathe therefore prefer non-additive join property.

Demonstration. R(A,B,C) with A → B and C → B, decomposed into R1(A,B) and R2(B,C). Take

r = { (a1, b1, c1), (a2, b1, c2) }

π<sub>R1</sub>(r) = {(a1,b1), (a2,b1)} and π<sub>R2</sub>(r) = {(b1,c1), (b1,c2)}.

Joining on the common attribute B, every row on the left matches every row on the right because all share b1:

A B C Genuine?
a1 b1 c1 yes
a1 b1 c2 spurious
a2 b1 c1 spurious
a2 b1 c2 yes

Four tuples instead of two. The cause: the common attribute B is not a superkey of either fragment (B⁺ = {B}), so the join matches many rows to many rows.

Solved Question 2

Q. State the binary lossless-join test and prove why it works. Apply it to two examples.

A. Test. A decomposition of R into exactly two relations R1 and R2 is lossless if and only if

(R1 ∩ R2) → R1 or (R1 ∩ R2) → R2

— that is, (R1 ∩ R2)⁺ under F contains all of R1 or all of R2.

Why it works. Let C = R1 ∩ R2. The natural join pairs a tuple of π<sub>R1</sub>(r) with a tuple of π<sub>R2</sub>(r) exactly when they agree on C.

Suppose C is a superkey of R2. Then within π<sub>R2</sub>(r) each value of C occurs in at most one tuple. So each tuple of π<sub>R1</sub>(r) has at most one partner, the join yields at most |π<sub>R1</sub>(r)| tuples, and each reconstructs exactly the original tuple it came from. No combination can be invented.

If C is a superkey of neither, then some C value appears in several tuples on both sides, and the join forms every cross-combination — the spurious tuples of question 1.

Example 1 (lossless). STUDENT(Rollno, Sname, Dno) and DEPARTMENT(Dno, Dname, Dhead) with Rollno → Sname, Dno and Dno → Dname, Dhead. Common attribute {Dno}; Dno⁺ = {Dno, Dname, Dhead} ⊇ DEPARTMENT. Lossless.

Example 2 (lossy). R(A,B,C) with A → B, C → B, split into R1(A,B), R2(B,C). Common attribute {B}; B⁺ = {B}, containing neither fragment. Lossy — as the data in question 1 confirms.

Solved Question 3

Q. Apply the chase algorithm to R(A,B,C,D,E) with F = {A → C, B → C, C → D, DE → C, CE → A} decomposed into R1(A,D), R2(A,B), R3(B,E), R4(C,D,E), R5(A,E).

A. (Full working as in Section 5.4.) Summarising the steps:

  1. Build the tableau: a_j where attribute A_j is in Ri, b_ij otherwise.
  2. A → C: rows 1, 2, 5 share a₁, so their C cells all become b₁₃.
  3. B → C: rows 2, 3 share a₂, so row 3's C becomes b₁₃.
  4. C → D: rows 1, 2, 3, 5 now share C = b₁₃; row 1 has D = a₄, so all become a₄.
  5. DE → C: rows 3, 4, 5 share D = a₄, E = a₅; row 4 has C = a₃, so rows 3 and 5 become a₃.
  6. CE → A: rows 3, 4, 5 share C = a₃, E = a₅; row 5 has A = a₁, so rows 3 and 4 become a₁.

Final row 3 = (a₁, a₂, a₃, a₄, a₅) — all distinguished. The decomposition is LOSSLESS.

Interpretation. A complete a-row means the join can always reconstruct a tuple agreeing with the original on every attribute, whatever legal data the fragments hold. Had the algorithm halted with no such row, the surviving b symbols would mark exactly the attributes the fragments fail to pin down — the freedom that lets spurious tuples appear.

Note. The chase is needed only for three or more fragments; for two the simple binary test suffices, and for a decomposition produced by the BCNF algorithm losslessness is guaranteed by construction.

Solved Question 4

Q. Define dependency preservation and give the test. Show that the BCNF decomposition of TEACHING fails it.

A. A decomposition is dependency preserving if the union of the dependencies projected onto the fragments has the same closure as F:

( π<sub>R1</sub>(F) ∪ ... ∪ π<sub>Rm</sub>(F) )⁺ = F⁺

Practically: every original constraint can be enforced by examining one fragment, with no join.

Test. Compute π<sub>Ri</sub>(F) for each fragment; let G be their union; then for each X → Y in F, check whether Y ⊆ X⁺ computed under G.

Applying it to TEACHING(Student, Subject, Teacher) with F = {Student,Subject → Teacher ; Teacher → Subject}, decomposed into TEACHES(Teacher, Subject) and STUDIES(Student, Teacher):

  • π<sub>TEACHES</sub>(F): within {Teacher, Subject}, we have Teacher⁺ = {Teacher, Subject}, giving Teacher → Subject. (Subject⁺ = {Subject}, nothing.)
  • π<sub>STUDIES</sub>(F): within {Student, Teacher}, Student⁺ = {Student} and Teacher⁺ ∩ {Student,Teacher} = {Teacher}. Nothing is projected.
  • G = { Teacher → Subject }.

Now test the original dependency Student, Subject → Teacher: {Student, Subject}⁺ under G = {Student, Subject}. Teacher is not in it.

The dependency is lost. No constraint on either table can enforce it, because Student and Subject are in different fragments. Enforcement requires joining the two tables on every insert, or a trigger.

Note the contrast with the lossless property, which this same decomposition does satisfy (Teacher⁺ ⊇ TEACHES). It is precisely the standard demonstration that BCNF and dependency preservation can be incompatible.

Solved Question 5

Q. For R(A,B,C,D) with F = {A → B, B → C, C → D} decomposed into R1(A,B), R2(B,C), R3(C,D), test both properties.

A.

Attribute preservation. {A,B} ∪ {B,C} ∪ {C,D} = {A,B,C,D} = R ✓

Lossless join. Three fragments, so use the chase.

Initial tableau:

A B C D
R1(A,B) a₁ a₂ b₁₃ b₁₄
R2(B,C) b₂₁ a₂ a₃ b₂₄
R3(C,D) b₃₁ b₃₂ a₃ a₄
  • A → B: only row 1 has a₁; no other row agrees on A. No change.
  • B → C: rows 1 and 2 agree on B = a₂. Row 2 has C = a₃, so row 1's C becomes a₃.
  • C → D: rows 1, 2, 3 now agree on C = a₃. Row 3 has D = a₄, so rows 1 and 2 become a₄.
A B C D
R1 a₁ a₂ a₃ a₄
R2 b₂₁ a₂ a₃ a₄
R3 b₃₁ b₃₂ a₃ a₄

Row 1 is all a symbols → LOSSLESS.

(Cross-check by repeated binary tests: R1 ⋈ R2 on {B} — B⁺ = {B,C,D} ⊇ R2 ✓ lossless, giving R12(A,B,C). Then R12 ⋈ R3 on {C} — C⁺ = {C,D} ⊇ R3 ✓ lossless. Same conclusion.)

Dependency preservation. - π<sub>R1</sub>(F) = {A → B} - π<sub>R2</sub>(F) = {B → C} - π<sub>R3</sub>(F) = {C → D} - G = {A → B, B → C, C → D} = F exactly.

Every original dependency is present. Dependency preserving. ✓

Verdict: this decomposition has all three desirable properties, and each fragment is in BCNF (each has a single-attribute determinant that is its own key). It is an ideal decomposition.

Solved Question 6

Q. Rank the three properties in order of importance and justify the ranking.

A.

1. Attribute preservation — an absolute requirement. If an attribute appears in no fragment, the information is simply gone; no join can recover it. A "decomposition" that drops attributes is not a decomposition at all. This is checked first and never traded away.

2. Lossless join — a correctness requirement, never negotiable. A lossy decomposition corrupts the data. Rejoining the fragments yields spurious tuples that assert facts which were never true — and, crucially, they are indistinguishable from genuine rows. Every query over the reassembled data may then return wrong answers, with no way to detect or repair the damage. Note that the individual fragments look perfectly consistent, so the fault is invisible on inspection.

3. Dependency preservation — highly desirable, but a trade-off. Losing a dependency costs enforcement efficiency, not correctness. The constraint can still be enforced — by joining the fragments, by a trigger, or in the application. The stored data remains accurate and every query still returns the right answer; the system merely has to work harder, and the enforcement is easier to get wrong.

The ranking follows from the kind of failure each prevents:

Property If violated Recoverable?
Attribute preservation Information is absent No
Lossless join Data is silently corrupted No
Dependency preservation Constraint checking is expensive Yes — with a join or trigger

This ranking is exactly why the theorem of Lesson 4 matters in the direction it does. A lossless BCNF decomposition always exists, so we never have to choose between BCNF and correctness. A dependency-preserving BCNF decomposition may not exist — and when it does not, the right response is to give up either BCNF (staying at 3NF) or dependency preservation (enforcing the rule another way), but never losslessness.

23.8 Exercises

A. Short answer

  1. State the three desirable properties of a decomposition.
  2. Why is "lossless" a misleading name?
  3. What is a spurious tuple?
  4. State the binary lossless-join test.
  5. When must you use the chase algorithm rather than the binary test?
  6. What do the a and b symbols mean in a tableau?
  7. Which property must never be sacrificed, and why?

B. Test these decompositions for lossless join

  1. R(A,B,C), F = {A → B}, into R1(A,B), R2(A,C).
  2. R(A,B,C), F = {A → B}, into R1(A,B), R2(B,C).
  3. R(A,B,C,D), F = {A → B, C → D}, into R1(A,B), R2(C,D).
  4. R(A,B,C,D), F = {AB → C, C → D, D → A}, into R1(A,B,C), R2(C,D).
  5. R(A,B,C,D,E), F = {A → BC, CD → E, B → D, E → A}, into R1(A,B,C), R2(A,D,E).
  6. R(A,B,C,D,E), F = {AB → C, C → D, D → E}, into R1(A,B,C), R2(C,D), R3(D,E) — use the chase.
  7. R(A,B,C,D,E,F), F = {A → BC, B → D, C → E, E → F}, into R1(A,B,C), R2(B,D), R3(C,E), R4(E,F) — use the chase.

C. Test these for dependency preservation

  1. R(A,B,C), F = {A → B, B → C}, into R1(A,B), R2(B,C).
  2. R(A,B,C), F = {A → B, B → C}, into R1(A,C), R2(B,C).
  3. R(A,B,C,D), F = {A → B, C → D}, into R1(A,B), R2(C,D).
  4. R(Student, Subject, Teacher), into R1(Teacher, Subject), R2(Student, Teacher).
  5. R(A,B,C,D), F = {AB → CD, D → A}, into R1(A,D), R2(B,C,D).

D. Analysis

  1. Construct a concrete instance demonstrating the spurious tuples in exercise 9, and count how many extra rows appear.
  2. Prove that the BCNF decomposition algorithm always produces a lossless decomposition.
  3. Explain why "each original FD lies inside some fragment" is sufficient but not necessary for dependency preservation. Give an example where the condition fails but the decomposition is still preserving.
  4. Explain, referring to the ranking of properties, why 3NF synthesis is often preferred to BCNF decomposition in practice.
  5. For the college schema of Unit 5 Lesson 1, verify that no decomposition was needed — that is, show every relation is already in BCNF.
  6. A colleague proposes decomposing ADMISSION(Rollno, SID, Dateofadmission) into (Rollno, SID) and (SID, Dateofadmission). Test both properties and explain the practical consequence.

E. Objective — True or False with reason

  1. A lossy decomposition loses tuples.
  2. A lossless decomposition is always dependency preserving.
  3. The binary test works for any number of fragments.
  4. If the common attributes form a superkey of one fragment, the binary decomposition is lossless.
  5. Dependency preservation is more important than losslessness.
  6. Every decomposition produced by the BCNF algorithm is lossless.

Answers to Section E

  1. False. It gains spurious tuples; no original tuple is ever lost. Hence the better name non-additive join.
  2. False. The BCNF decomposition of TEACHING is lossless but loses Student,Subject → Teacher.
  3. False. It applies only to two fragments; for three or more use the chase.
  4. True. That is exactly the condition — each tuple of the other fragment then finds at most one partner.
  5. False. Losslessness is a correctness requirement (a lossy decomposition corrupts data irrecoverably); dependency preservation costs only enforcement efficiency.
  6. True. Each step splits on X → Y into (X ∪ Y) and (R − Y), whose common attributes X form a superkey of the first fragment.

Lesson Summary

  • Three properties: attribute preservation, lossless join, dependency preservation.
  • "Lossless" really means non-additive: the danger is spurious tuples, not missing ones.
  • Binary test: the decomposition is lossless iff (R1 ∩ R2)⁺ contains all of R1 or all of R2.
  • For three or more fragments, use the chase (tableau) algorithm; a row of all a symbols means lossless.
  • Dependency preservation is tested by projecting F onto each fragment and checking that every original FD is recoverable from the union — not merely that each FD sits inside one fragment.
  • Ranking: attribute preservation and losslessness are correctness requirements; dependency preservation is a trade-off.

End of Unit 5. Next: Unit 6, Lesson 1 — Data Storage and File Organisation.