PART 2 • CORRECT DATABASE DESIGN

Prove That a Decomposition Is Safe

Move beyond 3NF to BCNF, 4NF and 5NF while testing whether decomposed relations reconstruct the original information and preserve its rules.

Level 08 of 18Advanced140–180 minutesLevel 7 required

BY THE END, YOU CAN

Distinguish 3NF from BCNF formally.
Test binary lossless decomposition.
Test dependency preservation.
Interpret multivalued dependencies.
Decompose a relation into 4NF.
Explain the purpose of 5NF.

01 • STRENGTHEN THIRD NORMAL FORM

BCNF Requires Every Determinant to Be a Super Key

BCNF removes the prime-attribute exception allowed by 3NF.

THIRD NORMAL FORM

For every non-trivial X → A

X is a super keyORA is a prime attribute

3NF may accept a dependency whose determinant is not a super key when its RHS belongs to a candidate key.

BOYCE–CODD NORMAL FORM

For every non-trivial X → A

X must be a super key

No prime-attribute exception exists. Every meaningful determinant must uniquely identify a tuple.

CLASSIC 3NF-BUT-NOT-BCNF CASE

TEACHING(student, course, instructor)

{student, course} → instructorinstructor → course

Candidate keys are {student, course} and {student, instructor}, so every attribute is prime. The FD instructor → course passes 3NF because course is prime, but violates BCNF because instructor is not a super key.

02 • TEST EACH DETERMINANT

BCNF Violation Laboratory

Select a dependency to compare its determinant closure with the complete schema.

ORIGINALTEACHING(student, course, instructor)

→ decompose on instructor → course →

BCNF RELATIONSINSTRUCTOR_COURSE(instructor, course)STUDENT_INSTRUCTOR(student, instructor)

03 • PRESERVE INFORMATION

A Lossless Join Reconstructs Exactly the Original Relation

After decomposition, the natural join must create neither missing tuples nor spurious tuples.

BINARY TEST FOR R → R₁, R₂

The common attributes must determine one complete component

(R₁ ∩ R₂) → R₁ or (R₁ ∩ R₂) → R₂ in F⁺

Lossless

Joining the projections returns exactly R.

Lossy

The join can invent spurious combinations.

PROOF EXAMPLE

R(A,B,C), F = {A → B}, decomposition R₁(A,B), R₂(A,C)

The intersection is {A}. Because A → AB, the intersection determines all of R₁. Therefore, the decomposition is lossless.

ORIGINAL R

A	B	C
a1	b1	c1
a2	b1	c2

R₁(A,B) ⋈ R₂(B,C)

JOIN RESULT

A	B	C
a1	b1	c1
a1	b1	c2
a2	b1	c1
a2	b1	c2

Here the common attribute B determines neither AB nor BC under F = {A → B}. The highlighted tuples were not in the original relation.

04 • PRESERVE ENFORCEABLE RULES

Dependency Preservation Avoids Joining Tables to Check Constraints

Projected dependencies on the decomposed relations should collectively imply the original FD set.

PRESERVED

R(A,B,C), F = {A → B, B → C}

R₁(A,B) and R₂(B,C)

A → B can be checked in R₁. B → C can be checked in R₂. Every original FD is locally enforceable.

NOT PRESERVED

Same R and F

R₁(A,B) and R₂(A,C)

A → B is available in R₁, but B → C is contained in neither relation. Checking it requires joining R₁ and R₂.

Lossless joinProtects information

No spurious or missing tuples after reconstruction.

Dependency preservationProtects efficient enforcement

Rules can be checked without reconstructing the original relation.

05 • HANDLE INDEPENDENT MULTI-VALUED FACTS

4NF Removes Non-Key Multivalued Dependencies

An MVD X ↠ Y says that, for each X, the set of Y values is independent of the remaining attributes.

STUDENT 101Hobbies

Chess, Music

Languages

English, Telugu

independent sets create every combination

student	hobby	language
101	Chess	English
101	Chess	Telugu
101	Music	English
101	Music	Telugu

MVDsstudent ↠ hobbystudent ↠ language

WHY NOT AN FD?

One student has several hobbies, so student → hobby is false. The double arrow expresses a set-valued, independent relationship.

4NF CONDITION

For every non-trivial MVD X ↠ Y, X must be a super key.

REDUNDANT RELATIONSTUDENT_HOBBY_LANGUAGE

→

4NF RELATIONSSTUDENT_HOBBY(student, hobby)STUDENT_LANGUAGE(student, language)

The four combination rows become two hobby rows plus two language rows. Adding a hobby no longer requires repeating every language.

06 • HANDLE JOIN DEPENDENCIES

5NF Removes Redundancy Caused Only by Multi-Relation Recombination

5NF, also called project-join normal form, concerns non-trivial join dependencies not implied by candidate keys.

SUPPLIER–PART–PROJECT

SPJ(supplier, part, project)

Suppose the business rule states that a triple is valid whenever its three compatible pairs exist:

SP(supplier, part)SJ(supplier, project)PJ(part, project)

Then SPJ can be reconstructed from the join of those three projections. Storing every triple repeats pairwise facts.

5NF CONDITION

Every non-trivial join dependency must be implied by candidate keys.

5NF is uncommon in routine applications. Apply it only when the business semantics genuinely guarantee the join dependency; arbitrary decomposition can invent tuples.

Form	Main dependency/design issue removed	Key question
1NF	Repeating groups and non-atomic values	Is each cell atomic?
2NF	Partial functional dependency	Does a non-prime fact need the whole key?
3NF	Transitive non-key determination	Does a non-key fact determine another?
BCNF	Any non-super-key FD determinant	Is every determinant a super key?
4NF	Independent non-key MVD	Are independent multi-valued facts mixed?
5NF	Non-key join dependency	Can pairwise facts safely reconstruct triples?

07 • ANALYSE COMPLETE DECOMPOSITIONS

Decomposition Safety Laboratory

Compare losslessness, dependency preservation and target normal form as separate results.

08 • CHECK YOUR UNDERSTANDING

Eight Formative Concept Checks

1. BCNF requires that every non-trivial FD determinant be:

2. Which statement is true?

3. A lossless decomposition guarantees:

4. For binary R₁ and R₂, a standard lossless test is:

5. Dependency preservation mainly allows constraints to be checked:

6. X ↠ Y denotes:

7. 4NF requires a determinant of every non-trivial MVD to be:

8. 5NF primarily addresses:

Answered correctly: 0 of 8

09 • EXPLAIN & PREPARE

University and Interview Questions

2-MARK QUESTIONS

Define BCNF.
What is a lossless join?
Define dependency preservation.
What is an MVD?
State the condition for 4NF.

5-MARK / PROBLEMS

Show a relation that is in 3NF but not BCNF.
Test a binary decomposition for losslessness.
Test whether an FD set is preserved.
Decompose an MVD-based relation into 4NF.

INTERVIEW QUESTIONS

Lossless versus dependency-preserving?
Why might BCNF lose dependency preservation?
When would you choose 3NF over BCNF?
FD versus MVD?
When is 5NF practically useful?

Show the advanced-normalization proof format

Write R, candidate keys and the complete dependency set.
Test the current normal form using every non-trivial dependency.
Name the violating determinant and explain why it is not a super key.
Show the decomposed relation schemas and their keys.
Apply the lossless test using the common attributes or chase method.
Project dependencies onto each new relation.
Check whether their union implies the original dependencies.
State the achieved normal form and any preservation trade-off.

LEVEL 8 SUMMARY

You Can Now Judge Decomposition Quality

BCNF requires every non-trivial FD determinant to be a super key.
Lossless decomposition guarantees exact reconstruction.
Dependency preservation allows local constraint enforcement.
A design should seek both properties, but BCNF can require a trade-off.
4NF removes non-key independent multivalued facts.
5NF handles join dependencies not implied by candidate keys.

COURSE CHECKPOINT

Mark this level when you can test BCNF, prove a binary decomposition lossless, check dependency preservation and explain 4NF.

Saved in this browser only.