Decomposition: lossless joins, preservation and 4NF
Goals and assumptions
Decompose a relation without inventing information when its projections are rejoined, distinguish this from checking dependencies locally, and apply BCNF decomposition or 3NF synthesis deliberately. Assume set relations without NULL and functional dependencies (FDs) unless a multivalued dependency (MVD) is explicitly introduced. Decomposed schemas together must contain every original attribute. Projection removes duplicate tuples.
1. Two independent design questions
A decomposition R into R1,...,Rn is lossless with respect to F when every legal instance r satisfying F equals the natural join of its projections onto these schemas. The join always contains every original tuple; the danger is additional, spurious tuples. A sample that happens to rejoin correctly cannot prove the guarantee for every legal instance.
Dependency preservation asks whether the original constraints can be enforced by checking the individual component relations, without joining them. Let Fi be the projection of F onto Ri: all dependencies in F+ whose attributes lie in Ri, not merely the original written FDs that fit. Preservation means the union of Fi implies every FD of F. The reverse implication is automatic because each Fi comes from F+. Losslessness and preservation answer different questions; neither should be inferred from the other.
2. Binary lossless-join test
For a two-way decomposition R1,R2 whose union is R, it is lossless under FDs exactly when F+ includes (R1∩R2)→R1 or (R1∩R2)→R2. Compute the common attributes' closure under F, then see whether it covers either side. The intersection need not determine the entire original schema.
Worked case: R(A,B,C), F={A→B}. Decompose into AB and AC. The intersection is A; A+={A,B}. It contains AB, so the decomposition is lossless even though A does not determine C. It is also dependency preserving because A→B is checked within AB.
Counterexample: decompose the same R into AB and BC. Intersection B has closure {B}; it determines neither AB nor BC. A legal original relation is {(a1,b,c1),(a2,b,c2)}. It obeys A→B. Its projections are AB={(a1,b),(a2,b)} and BC={(b,c1),(b,c2)}. Their join has four tuples, adding (a1,b,c2) and (a2,b,c1). This decomposition preserves A→B locally but is lossy. Different values for A are allowed to share B.
Do not apply the binary intersection criterion to an arbitrary multiway split by checking every pair and declaring success. For general decompositions use a chase/tableau test, or exhibit a sequence of valid binary lossless splits. A sequence of lossless splits is sufficient: each split reconstructs the relation it replaced.
3. BCNF decomposition by a violating dependency
If a nontrivial X→Y violates BCNF in a schema S, let Z=Y−X. Split S into S1=X∪Z and S2=S−Z. The intersection is X, and X determines S1, so this step is lossless. Recompute the projected dependencies on each new schema and repeat until every component is BCNF. The result is lossless, but dependency preservation is not guaranteed and different violation choices may yield different designs.
Worked trade-off: R(A,B,C), F={AB→C,C→B}. Candidate keys are AB and AC. C→B violates BCNF because C cannot determine A. Split into CB and AC. This is lossless because their intersection C determines CB. In CB, C is a key; in AC there are no nontrivial projected FDs, so both are BCNF. But AB→C is not preserved: the union of local nontrivial FDs is just C→B, and the closure of AB under that union cannot add C.
A concrete locally valid but globally invalid combination makes the issue visible: CB={(c1,b),(c2,b)}, AC={(a,c1),(a,c2)}. C→B holds locally; AC has no nontrivial FD restriction. Their join contains (a,b,c1),(a,b,c2), violating AB→C. Losslessness only promises reconstruction of projections of a legal original relation; it does not promise that arbitrary locally valid components satisfy every original dependency.
4. Dependency-preserving 3NF synthesis
Start with a minimal cover G with singleton right sides. For each determinant X, form a schema containing X and all its right-side attributes in G. Remove schemas contained in another schema. If no resulting schema contains a candidate key of the original R, add one schema whose attributes are a candidate key. Under the usual FD model, this synthesis produces a dependency-preserving, lossless 3NF decomposition. The key-containing schema is crucial for the lossless guarantee; preservation alone does not supply it.
Worked synthesis: R(A,B,C,D), F={A→B,B→C}. The set is already a minimal cover. Generate AB and BC. A and D never occur on right sides; AD is a candidate key: A generates B,C and D supplies itself, while neither A nor D alone covers R. Neither AB nor BC contains AD, so add AD. The result {AB,BC,AD} preserves both dependencies locally and is lossless. Notice why simply stopping at AB,BC is invalid: D has disappeared entirely.
An implied dependency can matter during projection. For F={A→B,B→C}, the projection onto AC includes A→C even though that FD was not written explicitly. Testing preservation with only syntactically retained dependencies can therefore give a wrong answer. For each original X→Y, closure under the union of correctly projected dependencies must include Y.
5. Supporting extension: independent multivalued facts and 4NF
An MVD X↠Y says that for a fixed X, the possible Y values are independent of values of the remaining attributes Z=R−(X∪Y). If two tuples agree on X, tuples pairing the first Y with the second Z, and the second Y with the first Z, must also occur. An MVD is trivial when Y⊆X or X∪Y=R. Every FD X→Y implies X↠Y, but an MVD generally does not imply the FD.
Example: PersonSkillLanguage(P,S,L) stores independent skills and languages for each person. A person with two skills s1,s2 and two languages l1,l2 requires all four combinations. P↠S holds, but P→S does not. Assuming no nontrivial FDs, the relation is BCNF; it nevertheless repeats independent facts. 4NF requires every nontrivial MVD determinant to be a superkey, so it fails 4NF when P is not a superkey. Split into PS and PL. Under P↠S, joining these two projections is lossless. Do not assert the MVD if a particular skill is associated only with a particular language: independence is a semantic assumption, not a conclusion from two lists.
Exam pitfalls and checklist
- Verify schema coverage, then losslessness and dependency preservation separately.
- Binary losslessness uses an OR: the intersection must determine either side, not necessarily both.
- A BCNF split can lose preservation, while 3NF synthesis retains it.
- An accidental sample with no spurious tuples is not a proof.
- Recompute projected FDs; hidden implications can become local constraints.
- 4NF is supporting depth for normal forms here, not a claim of a separately named official syllabus heading.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. R(A,B,C), F={A→B}. Is {AB,AC} lossless?
A. Yes, A determines AB B. No, A does not determine C C. Only if B→A also holds D. Only for one-tuple relations
Answer: A
A: The common attribute A determines one full component.
B: Determining the other component is unnecessary.
C: The reverse FD is unnecessary.
D: The FD test applies to every legal instance.
P02. Under F={A→B}, decomposition {AB,BC} of ABC is:
A. Lossless and preserving B. Lossy but preserving C. Lossless but not preserving D. Neither preserving nor schema-covering
Answer: B
A: B determines neither side, so losslessness fails.
B: A→B stays local, but the common B is insufficient for losslessness.
C: The decomposition is lossy and A→B is local.
D: Both schema coverage and dependency preservation hold.
P03. In binary FD-based losslessness, the intersection must determine:
A. Both components necessarily B. At least one component C. Only itself D. Every candidate key in every case
Answer: B
A: The test uses OR, not AND.
B: Determining either full component is necessary and sufficient.
C: Trivial self-determination alone is insufficient.
D: Determining a candidate key of the original schema is stronger than necessary.
P04. For F={AB→C,C→B}, split ABC into CB and AC. Which original FD is not locally preserved?
A. C→B B. AB→C C. C→C D. AB→A
Answer: B
A: C→B is enforced inside CB.
B: AB closure under the local nontrivial FD C→B cannot acquire C.
C: Reflexivity always holds.
D: This is trivial and always holds.
P05. After 3NF synthesis, no component contains an original candidate key. What is the standard next step?
A. Delete all FDs B. Add a schema containing a candidate key C. Declare BCNF automatically D. Join every component permanently
Answer: B
A: Deleting constraints changes the problem.
B: This supplies the standard lossless-synthesis safeguard.
C: 3NF synthesis does not automatically guarantee BCNF.
D: A permanent join undoes the intended decomposition.
P06. A person has 3 independent skills and 2 independent languages in P,S,L. How many tuples for that person are required by the cross-product MVD model?
A. 2 B. 3 C. 5 D. 6
Answer: D
A: Each language must pair with all three skills.
B: Each skill must pair with both languages.
C: Independent combinations multiply rather than add.
D: There are 3×2 distinct skill-language pairs.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Databases syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in