Dependency preservation

0 · Recall Warm-up

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

1. When is {R₁, R₂} lossless? from Lesson 4.3.1
2. What is X → Y ∈ F⁺ tested with? from Lesson 4.2.4
3. What does entity integrity forbid? from Lesson 2.3.1

1 · The Hook

After splitting, the DBMS must still enforce every FD on every insert. If an FD's attributes now sit in different tables, checking it needs a join on every insert, which is slow. A decomposition is dependency preserving if every FD can be checked inside single pieces. Sometimes you cannot have both lossless and preserving with the strongest normal form, and GATE loves that trade-off.

2 · Predict First

R(A, B, C), F = {AB → C, C → B}. The decomposition {AC, BC} is lossless (common C, C → B). Can AB → C still be checked inside one piece?

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

3 · Core Concept

Predict First — the answer

No. A and B are never in the same piece, so AB → C cannot be checked without joining AC and BC. The decomposition is lossless but not dependency preserving.

Projection of F onto a piece

Fi = the FDs X → Y in F⁺ with X ∪ Y ⊆ Rᵢ. These are the FDs a piece can check alone. Note: F⁺, not just F: an FD can hold on a piece because of a chain through other attributes.

Definition

{R₁, …, Rₙ} is dependency preserving if (F₁ ∪ F₂ ∪ … ∪ Fₙ)⁺ = F⁺, that is, every FD in F is implied by the union of the projected FDs.

Quick check

1. If every FD of F has all its attributes inside some single piece, the decomposition is preserving. Done.
2. Otherwise, for each FD X → Y not inside a piece, test whether it is still implied, with this closure:
   • result = X; repeat: for each piece Rᵢ, result = result ∪ ((result ∩ Rᵢ)⁺ ∩ Rᵢ) (closure under F); until no change.
   • X → Y is preserved iff Y ⊆ result.

Example: preserved through a chain

R(A, B, C), F = {A → B, B → C, C → A}, pieces {AB, BC}. C → A is not inside one piece. Test C → A: result = C. Piece BC: (C)⁺ = CAB, ∩ BC = BC → result BC. Piece AB: (B)⁺ = BCA, ∩ AB = AB → result ABC ⊇ A. Preserved (C → B on BC, B → A on AB).

Example: not preserved

R(A, B, C), F = {AB → C, C → B}, pieces {AC, BC}. Test AB → C: result = AB. AC: (A)⁺ = A → nothing. BC: (B)⁺ = B → nothing. result = AB ⊉ C. Not preserved.

The two properties are independent

Lossless is mandatory (otherwise the data is wrong). Preservation is desirable (otherwise checking needs joins).

4 · Visual

R(A,B,C)  F = {AB -> C, C -> B}   pieces AC | BC

AC holds:  only trivial FDs, and A?  A+ = A
BC holds:  C -> B
AB -> C needs A and B together: no piece has both -> must JOIN to check -> NOT preserved

5 · Worked Examples

Example 1 Easy

R(A, B, C, D), F = {A → B, B → C, C → D}, pieces {AB, BC, CD}. Preserving?

Solution

Every FD lies inside one piece: yes.

Example 2 Medium

R(A, B, C, D), F = {A → B, B → C, C → D, D → A}, pieces {AB, BC, CD}. Is D → A preserved?

Solution

Test D → A: result D; CD: D⁺ = DABC, ∩ CD = CD → CD; BC: C⁺ ∩ BC = BC → BCD; AB: B⁺ ∩ AB = AB → ABCD ⊇ A. Preserved (D → C → B → A inside the pieces).

Example 3 GATE

R(A, B, C, D, E), F = {A → C, B → C, C → D, DE → C, CE → A}, decomposed into {AD, AB, BE, CDE, AE}. Is it dependency preserving?

Solution

Test A → C: start with A. AD adds D (A⁺ = ACD, ∩ AD = AD). AB: A⁺ ∩ AB = A, nothing. CDE: (result ∩ CDE) = D, D⁺ = D, nothing. Result stays AD ⊉ C. Not preserving. (B → C and CE → A are lost too.)

8 · Connect the Dots

Chapter 4.3 is complete: the two tests every decomposition faces. Next: the Chapter 4.3 Lock-in, then Chapter 4.4: the normal forms (1NF, 2NF, 3NF, BCNF) that say when a table needs splitting, and the algorithms that split it with these guarantees.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · MCQ · 1 mark(s) — Preservation

R(A, B, C), F = {A → B, B → C}, pieces {AB, BC}. The decomposition is:

1. (A) lossy, not preserving
2. (B) lossy, preserving
3. (C) lossless and preserving
4. (D) lossless, not preserving

Q2 · MCQ · 2 mark(s) — Preservation

R(A, B, C), F = {A → B, B → C}, pieces {AB, AC}. The decomposition is:

1. (A) lossless and preserving
2. (B) lossless, not preserving
3. (C) lossy, preserving
4. (D) lossy, not preserving

Q3 · MSQ · 2 mark(s) — Properties

Which statements are true?

1. (A) Projected FDs must be taken from F⁺, not only F.
2. (B) Every lossless decomposition is dependency preserving.
3. (C) Lossless join is mandatory for a correct design.
4. (D) A decomposition can be dependency preserving and lossy.

Q4 · MCQ · 2 mark(s) — Test

R(A, B, C, D), F = {A → B, B → C, C → D, D → A}, pieces {AB, CD}. Which FD of F is not preserved?

1. (A) A → B
2. (B) C → D
3. (C) B → C
4. (D) none; all are preserved

Q5 · MCQ · 1 mark(s) — Definition

Dependency preservation means:

1. (A) every piece has a key
2. (B) the union of FDs projected on the pieces implies all of F
3. (C) the join of the pieces equals the original
4. (D) no FD has more than one attribute on the left

11 · Concept Ledger

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

projection of FDs onto a piecedependency preservationpreservation test (piecewise closure)