Dependency Preservation

A decomposition of relation R into R1, R2, ..., Rn is dependency-preserving if every functional dependency in the original set F can be verified using only...

Definition

A decomposition of relation R into R1, R2, ..., Rn is dependency-preserving if every functional dependency in the original set F can be verified using only the attributes present in at least one of the decomposed relations — without needing to join tables back together.

Formally, let Fi be the restriction of F to the attributes of Ri (i.e., all FDs in F⁺ that involve only attributes of Ri). The decomposition is dependency-preserving if:

Example

(F1 U F2 U ... U Fn)⁺ = F⁺

This means: the union of locally enforceable FDs logically implies all original FDs.

Example — Dependency IS Preserved

Decompose into	R1(A, B) and R2(B, C)
F1 (FDs restricted to {A, B})	{ A -> B }
F2 (FDs restricted to {B, C})	{ B -> C }
Now check	does (F1 U F2)⁺ contain all FDs in F?
From these, by transitivity	A -> C (since A->B and B->C)
So (F1 U F2)⁺ includes	A->B, B->C, A->C = all of F

Each original FD can be checked locally:

A -> B: check in R1 (both A and B are in R1)
B -> C: check in R2 (both B and C are in R2)
A -> C: implied by the combination (no direct check needed, but derivable)

Example — Dependency NOT Preserved

Candidate Keys	(Student, Course) and (Student, Teacher)
BCNF Decomposition (violating FD	Teacher -> Course):
Check	Can we verify (Student, Course) -> Teacher locally?

Algorithm to Check Dependency Preservation

For each FD X -> Y in F, apply this test:

Example

Algorithm: Check if X -> Y is preserved in decomposition {R1, R2, ..., Rn} result = X REPEAT FOR each Ri in the decomposition: t = (result INTERSECT attributes(Ri))⁺ INTERSECT attributes(Ri) result = result UNION t END FOR UNTIL result does not change IF Y is a subset of result THEN X -> Y is preserved ELSE X -> Y is NOT preserved

Applying to the Example Above

Example

Check if (Student, Course) -> Teacher is preserved. R1 = {Teacher, Course}, R2 = {Student, Teacher} Iteration 1: result = {Student, Course} R1: result INTERSECT R1 = {Course} Course⁺ (using F restricted to R1) = {Course} (no FD with Course alone on LHS in R1) Course⁺ INTERSECT R1 = {Course} result = {Student, Course} U {Course} = {Student, Course} R2: result INTERSECT R2 = {Student} Student⁺ (using F restricted to R2) = {Student} Student⁺ INTERSECT R2 = {Student} result = {Student, Course} U {Student} = {Student, Course} No change -> STOP Is Teacher in result {Student, Course}? NO. -> FD (Student, Course) -> Teacher is NOT preserved.

Dependency Preservation vs. Lossless Join

These are two independent properties of a decomposition:

Property	Meaning	Guarantee
Lossless Join	No spurious tuples when joining back	Data reconstruction is correct
Dependency Preservation	All FDs enforceable locally	Constraints can be checked efficiently

A decomposition can be:

Lossless AND dependency-preserving (ideal)
Lossless but NOT dependency-preserving (BCNF decomposition may cause this)
Neither (bad decomposition — never acceptable)

It is NOT possible for a decomposition to be dependency-preserving but lossy (if it were, the FDs themselves would guarantee losslessness).

3NF Always Preserves Dependencies

The 3NF synthesis algorithm (minimal cover approach) guarantees both lossless join and dependency preservation:

Example

3NF Synthesis Algorithm: 1. Compute the canonical cover Fc of F 2. For each FD X -> Y in Fc: Create relation Ri(X, Y) with primary key X 3. If no relation contains a candidate key of R: Add one more relation containing a candidate key Result: Always lossless AND dependency-preserving.

This is why 3NF is sometimes preferred over BCNF — when dependency preservation is essential and the minor redundancy of 3NF is acceptable.

Practical Implications

Example

Decision Framework: Given R with FDs F: 1. Try BCNF decomposition 2. Check if all FDs are preserved - If YES -> use BCNF (best: no redundancy + preserved FDs) - If NO -> choose: a) Accept BCNF, enforce lost FDs via application-level triggers b) Stay in 3NF (preserves all FDs, accepts minor redundancy) c) Use materialized views or assertions (if DBMS supports)

In real production systems, option (a) is common — decompose into BCNF for clean storage, then add a trigger or application check for the lost dependency. This gives you the storage benefits of BCNF with programmatic enforcement of the constraint.

Summary

Dependency preservation ensures all constraints can be checked locally (one table at a time)
BCNF decomposition may lose dependencies; 3NF synthesis never does
Use the algorithmic test (iterative closure computation) to verify preservation
When BCNF loses a dependency, enforce it via triggers or accept 3NF as the compromise

Definition

Formally, let Fi be the restriction of F to the attributes of Ri (i.e., all FDs in F⁺ that involve only attributes of Ri). The decomposition is dependency-preserving if:

Example

(F1 U F2 U ... U Fn)⁺ = F⁺

This means: the union of locally enforceable FDs logically implies all original FDs.

Example — Dependency IS Preserved

Decompose into	R1(A, B) and R2(B, C)
F1 (FDs restricted to {A, B})	{ A -> B }
F2 (FDs restricted to {B, C})	{ B -> C }
Now check	does (F1 U F2)⁺ contain all FDs in F?
From these, by transitivity	A -> C (since A->B and B->C)
So (F1 U F2)⁺ includes	A->B, B->C, A->C = all of F

Each original FD can be checked locally:

A -> B: check in R1 (both A and B are in R1)
B -> C: check in R2 (both B and C are in R2)
A -> C: implied by the combination (no direct check needed, but derivable)

Example — Dependency NOT Preserved

Candidate Keys	(Student, Course) and (Student, Teacher)
BCNF Decomposition (violating FD	Teacher -> Course):
Check	Can we verify (Student, Course) -> Teacher locally?

Algorithm to Check Dependency Preservation

For each FD X -> Y in F, apply this test:

Example

Applying to the Example Above

Example

Dependency Preservation vs. Lossless Join

These are two independent properties of a decomposition:

Property	Meaning	Guarantee
Lossless Join	No spurious tuples when joining back	Data reconstruction is correct
Dependency Preservation	All FDs enforceable locally	Constraints can be checked efficiently

A decomposition can be:

Lossless AND dependency-preserving (ideal)
Lossless but NOT dependency-preserving (BCNF decomposition may cause this)
Neither (bad decomposition — never acceptable)

It is NOT possible for a decomposition to be dependency-preserving but lossy (if it were, the FDs themselves would guarantee losslessness).

3NF Always Preserves Dependencies

The 3NF synthesis algorithm (minimal cover approach) guarantees both lossless join and dependency preservation:

Example

This is why 3NF is sometimes preferred over BCNF — when dependency preservation is essential and the minor redundancy of 3NF is acceptable.

Practical Implications

Example

Summary

Dependency preservation ensures all constraints can be checked locally (one table at a time)
BCNF decomposition may lose dependencies; 3NF synthesis never does
Use the algorithmic test (iterative closure computation) to verify preservation
When BCNF loses a dependency, enforce it via triggers or accept 3NF as the compromise

Dependency Preservation

Definition

Example — Dependency IS Preserved

Example — Dependency NOT Preserved

Algorithm to Check Dependency Preservation

Applying to the Example Above

Dependency Preservation vs. Lossless Join

3NF Always Preserves Dependencies

Practical Implications

Summary

Study next in this module

Dependency Preservation

Definition

Example — Dependency IS Preserved

Example — Dependency NOT Preserved

Algorithm to Check Dependency Preservation

Applying to the Example Above

Dependency Preservation vs. Lossless Join

3NF Always Preserves Dependencies

Practical Implications

Summary

Study next in this module