Chapter 07 · Functional Dependencies and Data Anomalies
Lossless Decomposition and Dependency Preservation
Understand lossless decomposition and dependency preservation, verify when a split can be recombined safely, and recognize decompositions that silently lose constraints.
Learning outcomes
Normalization often decomposes one relation into several smaller relations. A decomposition is useful only if it is semantically safe. Two major properties matter: lossless join and dependency preservation. Losslessness ensures we can reconstruct the original valid information without inventing false combinations. Dependency preservation ensures important rules can still be enforced without expensive multi-table joins.
Explain lossless versus lossy decomposition.
Apply the binary lossless-join test using functional dependencies.
Explain dependency preservation and why it matters operationally.
Evaluate decompositions that trade stronger normalization for simpler constraint enforcement.
Why decomposition can go wrong
Suppose we split:
R(A,B,C)into:
R1(A,B)R2(B,C)If the common attribute B does not determine enough structure, joining R1 and R2 may generate combinations that never existed in the original relation.
Lossless join
A decomposition is lossless when every valid original relation can be reconstructed exactly by joining the decomposed relations.
For binary decomposition of R into R1 and R2, a standard sufficient-and-necessary test under F is:
\[ (R_1 \cap R_2) \rightarrow R_1 \]
or:
\[ (R_1 \cap R_2) \rightarrow R_2 \]
under the functional dependencies.
Intuition behind the test
The shared attributes must identify all attributes on at least one side. Then the join cannot arbitrarily combine multiple unrelated rows from both sides.
Lossless example
Suppose:
Employee(employee_id, department_id, department_name)with:
\[ department\_id \rightarrow department\_name \]
Decompose into:
Employee(employee_id, department_id)Department(department_id, department_name)The intersection is department_id, and it determines all attributes of Department. Therefore the decomposition is lossless.
Lossy example
Original rows:
A | B | C--+---+--1 | x | p2 | x | qDecompose:
R1(A,B):1 x2 xR2(B,C):x px qJoin them back:
1 x p1 x q <-- spurious2 x p <-- spurious2 x qTwo false combinations appear.
A decomposition that produces spurious tuples changes the meaning of the data even if each smaller table looks reasonable in isolation.
WorkshopHub lossless decomposition
Bad relation:
Asset( asset_id, manufacturer_id, manufacturer_name, serial_number)Dependency:
\[ manufacturer\_id \rightarrow manufacturer\_name \]
Decompose:
Asset(asset_id, manufacturer_id, serial_number)Manufacturer(manufacturer_id, manufacturer_name)The common attribute manufacturer_id determines Manufacturer, so the join is lossless.
Dependency preservation
A decomposition is dependency preserving if the original functional dependencies can be enforced by checking dependencies within the decomposed relations, without joining them back together.
Why dependency preservation matters
Suppose the business rule:
\[ X \rightarrow Y \]
spans two tables after decomposition. If no single table contains enough attributes to enforce it, every write may require a join or more complex transaction logic. The schema may be normalized yet operationally inconvenient.
Preserved example
Original:
R(Student, Course, CourseTitle)Dependencies:
\[ Course \rightarrow CourseTitle \]
Decompose:
Enrollment(Student, Course)Course(Course, CourseTitle)The dependency Course -> CourseTitle remains entirely inside the Course relation.
Dependency loss example
Suppose:
\[ R(A,B,C) \]
with:
\[ A \rightarrow B,\quad B \rightarrow C \]
and decompose into:
R1(A,B)R2(A,C)The dependency \(B \rightarrow C\) is not directly enforceable in either relation.
Lossless does not imply dependency preserving
A decomposition can reconstruct data perfectly yet make some original dependencies difficult to enforce. Conversely, preserving dependencies does not automatically guarantee a lossless join. These are separate properties.
Normalization tradeoffs
In formal design, we often prefer:
- lossless decomposition as non-negotiable;
- dependency preservation when practical;
- higher normal forms when they do not make critical constraints impractical.
BCNF decomposition, for example, is always achievable losslessly but may sacrifice dependency preservation. Third normal form can preserve dependencies while removing most harmful redundancy.
Binary lossless test step by step
Given decomposition \(R \to R_1,R_2\):
- Find \(I = R_1 \cap R_2\).
- Compute \(I^+\) under F.
- If \(R_1 \subseteq I^+\) or \(R_2 \subseteq I^+\), the decomposition is lossless.
Example with closure
Let:
\[ R(A,B,C,D) \]
with:
\[ B \rightarrow C,D \]
Decompose into:
\[ R_1(A,B),\quad R_2(B,C,D) \]
Intersection = {B}. Since:
\[ B^+ = \{B,C,D\} \]
the intersection determines all of R2. The decomposition is lossless.
Chase intuition
For decompositions involving more than two relations, the chase is a formal technique for testing losslessness. You construct symbolic rows for each decomposed relation and repeatedly apply dependencies. If a row becomes fully distinguished, the decomposition is lossless. You do not need the full algorithm yet, but know that multi-relation losslessness can be tested systematically.
Decomposition should follow determinants
A useful practical heuristic is:
When \(X \rightarrow Y\) causes redundancy and X is not the right key for the current relation, create a relation containing X and Y, and keep X as the reference from the original relation—then verify losslessness and relevant dependencies formally.
WorkshopHub complete example
Bad relation:WorkOrder( work_order_id, status_code, status_name, asset_id, asset_serial_number)Dependencies:work_order_id -> status_code, asset_idstatus_code -> status_nameasset_id -> asset_serial_numberDecompose to:
WorkOrder(work_order_id, status_code, asset_id)WorkOrderStatus(status_code, status_name)Asset(asset_id, asset_serial_number)Each decomposition is lossless because the shared foreign-key attribute determines the referenced relation, and the important dependencies are preserved locally.
Practice: test the decomposition
Lossless or lossy?
Let \(R(A,B,C)\) with \(A \rightarrow B\). Decompose into:
R1(A,B)R2(A,C)Is the decomposition lossless? Is the dependency A → B preserved?
Review answer
The intersection is {A}. Because A → B, A determines all attributes of R1, so the decomposition is lossless. A → B is preserved directly in R1.
Chapter 7 checkpoint
Dependency analysis workflow
Given a wide reporting table, follow this order:
- state the row grain;
- list candidate keys;
- write functional dependencies from business rules;
- identify partial and transitive dependencies;
- describe possible anomalies;
- propose decompositions;
- check losslessness;
- check whether important dependencies remain enforceable.
Why this sequence works
It keeps normalization grounded in semantics. Rather than splitting tables mechanically, you prove what determines what, identify the concrete problem, and then verify that your decomposition preserves both information and constraints.
Summary and next chapter
Chapter 7 supplied the formal machinery behind normalization: functional dependencies, partial and transitive dependencies, anomalies, attribute closure, candidate-key reasoning, lossless decomposition, and dependency preservation. Chapter 8 applies these ideas directly to First, Second, and Third Normal Forms with step-by-step normalization examples.
References
- E. F. Codd, “Further Normalization of the Data Base Relational Model,” 1971.
- C. J. Date, Database Design and Relational Theory.
- Jeffrey Ullman and Jennifer Widom, A First Course in Database Systems.
- Ramez Elmasri and Shamkant B. Navathe, Fundamentals of Database Systems.