Unit 3 Summary — Normalization

Normalization is the systematic process of organizing a relational database to eliminate redundancy and prevent insertion, deletion, and update anomalies....

Core Concept

Normalization is the systematic process of organizing a relational database to eliminate redundancy and prevent insertion, deletion, and update anomalies. The process works by decomposing relations into smaller, well-structured relations based on the functional dependencies that exist among their attributes.

The goal is not to achieve the highest possible normal form blindly, but to find the right balance between reducing anomalies and maintaining practical query performance. In most real-world applications, Third Normal Form (3NF) or Boyce-Codd Normal Form (BCNF) is the target.

Quick Reference: Normal Form Requirements

Normal Form	Prerequisite	Additional Requirement
1NF	—	Atomic values, no repeating groups
2NF	1NF	No partial dependencies
3NF	2NF	No transitive dependencies
BCNF	3NF	Every determinant is a superkey
4NF	BCNF	No non-trivial multi-valued dependencies
5NF	4NF	No join dependencies not implied by candidate keys

Functional Dependencies: The Foundation

A functional dependency X → Y means: if two tuples have the same value for attributes X, they must have the same value for attributes Y. Knowing X uniquely determines Y.

Armstrong's Axioms (Inference Rules)

Axiom	Rule	Example
Reflexivity	If Y ⊆ X, then X → Y	{A, B} → A
Augmentation	If X → Y, then XZ → YZ	A → B implies AC → BC
Transitivity	If X → Y and Y → Z, then X → Z	A → B, B → C implies A → C

Derived Rules

Rule	Statement	Derivation
Union	If X → Y and X → Z, then X → YZ	From augmentation + transitivity
Decomposition	If X → YZ, then X → Y and X → Z	From reflexivity + transitivity
Pseudo-transitivity	If X → Y and WY → Z, then WX → Z	From augmentation + transitivity

Closure of Attributes

The closure of attribute set X (written X⁺) is the set of all attributes functionally determined by X.

1. Start	result = X
2. For each FD A	B in the dependency set:
Use case	X is a candidate key if X⁺ contains ALL attributes of the relation

Decomposition Properties

Two critical properties that any decomposition must satisfy:

Lossless Join (Mandatory)

R1 ∩ R2	R1 (common attributes determine all of R1)
R1 ∩ R2	R2 (common attributes determine all of R2)
Lossless means	R1 ⋈ R2 = R (natural join reconstructs original)
Lossy means	R1 ⋈ R2 ⊃ R (join produces spurious extra tuples)

Dependency Preservation (Desirable)

A decomposition preserves dependencies if

Every FD in the original set F can be verified using

attributes within a SINGLE decomposed relation.

If dependencies are not preserved

Enforcing them requires joining tables back together

(expensive and impractical for integrity checking)

Comparison: 3NF vs BCNF

Aspect	3NF	BCNF
Rule	X → A: X is superkey OR A is prime	X → A: X must be superkey
Strictness	Allows prime attribute on RHS exception	No exceptions
Dependency Preservation	Always achievable	May not be achievable
Lossless Decomposition	Always achievable	Always achievable
Practical Use	When dependency preservation needed	When maximum anomaly elimination needed

Multi-Valued Dependencies and 4NF

A multi-valued dependency X →→ Y exists when: for a given X value, the set of Y values is independent of other attributes. Two independent multi-valued facts about the same key create redundancy.

Example

CourseInfo(Course, Teacher, Textbook)

Course →→ Teacher (a course has multiple teachers, independent of textbook)

Course →→ Textbook (a course has multiple textbooks, independent of teacher)

This causes combinatorial redundancy

DBMS is taught by 3 teachers using 2 textbooks → 6 rows needed!

4NF Solution: Decompose into:

CourseTeacher(Course, Teacher)

CourseTextbook(Course, Textbook)

Fifth Normal Form

5NF handles join dependencies — situations where a relation cannot be decomposed into two relations without loss, but can be losslessly decomposed into three or more. This is rare in practice and typically only relevant in very specific domains.

Key Decision Guide

When to normalize further

✓ High redundancy causing storage waste

✓ Frequent update operations (anomalies are costly)

✓ Data integrity is critical (financial, medical)

When to stop or denormalize

✓ Read-heavy workloads (joins are expensive)

✓ Reporting and analytics queries

✓ Performance requirements outweigh storage concerns

✓ Data rarely changes after insertion

Common Exam Patterns

Given a relation and FDs → determine highest normal form
Given violations → decompose to desired normal form
Verify if decomposition is lossless using intersection test
Check if decomposition preserves all dependencies
Compute attribute closure to identify candidate keys
Apply Armstrong's axioms to derive new FDs

Core Concept

Quick Reference: Normal Form Requirements

Normal Form	Prerequisite	Additional Requirement
1NF	—	Atomic values, no repeating groups
2NF	1NF	No partial dependencies
3NF	2NF	No transitive dependencies
BCNF	3NF	Every determinant is a superkey
4NF	BCNF	No non-trivial multi-valued dependencies
5NF	4NF	No join dependencies not implied by candidate keys

Functional Dependencies: The Foundation

A functional dependency X → Y means: if two tuples have the same value for attributes X, they must have the same value for attributes Y. Knowing X uniquely determines Y.

Armstrong's Axioms (Inference Rules)

Axiom	Rule	Example
Reflexivity	If Y ⊆ X, then X → Y	{A, B} → A
Augmentation	If X → Y, then XZ → YZ	A → B implies AC → BC
Transitivity	If X → Y and Y → Z, then X → Z	A → B, B → C implies A → C

Derived Rules

Rule	Statement	Derivation
Union	If X → Y and X → Z, then X → YZ	From augmentation + transitivity
Decomposition	If X → YZ, then X → Y and X → Z	From reflexivity + transitivity
Pseudo-transitivity	If X → Y and WY → Z, then WX → Z	From augmentation + transitivity

Closure of Attributes

The closure of attribute set X (written X⁺) is the set of all attributes functionally determined by X.

1. Start	result = X
2. For each FD A	B in the dependency set:
Use case	X is a candidate key if X⁺ contains ALL attributes of the relation

Decomposition Properties

Two critical properties that any decomposition must satisfy:

Lossless Join (Mandatory)

R1 ∩ R2	R1 (common attributes determine all of R1)
R1 ∩ R2	R2 (common attributes determine all of R2)
Lossless means	R1 ⋈ R2 = R (natural join reconstructs original)
Lossy means	R1 ⋈ R2 ⊃ R (join produces spurious extra tuples)

Dependency Preservation (Desirable)

A decomposition preserves dependencies if

Every FD in the original set F can be verified using

attributes within a SINGLE decomposed relation.

If dependencies are not preserved

Enforcing them requires joining tables back together

(expensive and impractical for integrity checking)

Comparison: 3NF vs BCNF

Aspect	3NF	BCNF
Rule	X → A: X is superkey OR A is prime	X → A: X must be superkey
Strictness	Allows prime attribute on RHS exception	No exceptions
Dependency Preservation	Always achievable	May not be achievable
Lossless Decomposition	Always achievable	Always achievable
Practical Use	When dependency preservation needed	When maximum anomaly elimination needed

Multi-Valued Dependencies and 4NF

A multi-valued dependency X →→ Y exists when: for a given X value, the set of Y values is independent of other attributes. Two independent multi-valued facts about the same key create redundancy.

Example

CourseInfo(Course, Teacher, Textbook)

Course →→ Teacher (a course has multiple teachers, independent of textbook)

Course →→ Textbook (a course has multiple textbooks, independent of teacher)

This causes combinatorial redundancy

DBMS is taught by 3 teachers using 2 textbooks → 6 rows needed!

4NF Solution: Decompose into:

CourseTeacher(Course, Teacher)

CourseTextbook(Course, Textbook)

Fifth Normal Form

Key Decision Guide

When to normalize further

✓ High redundancy causing storage waste

✓ Frequent update operations (anomalies are costly)

✓ Data integrity is critical (financial, medical)

When to stop or denormalize

✓ Read-heavy workloads (joins are expensive)

✓ Reporting and analytics queries

✓ Performance requirements outweigh storage concerns

✓ Data rarely changes after insertion

Common Exam Patterns

Given a relation and FDs → determine highest normal form
Given violations → decompose to desired normal form
Verify if decomposition is lossless using intersection test
Check if decomposition preserves all dependencies
Compute attribute closure to identify candidate keys
Apply Armstrong's axioms to derive new FDs

Core Concept

Quick Reference: Normal Form Requirements

Functional Dependencies: The Foundation

Armstrong's Axioms (Inference Rules)

Derived Rules

Closure of Attributes

Decomposition Properties

Lossless Join (Mandatory)

Dependency Preservation (Desirable)

A decomposition preserves dependencies if

If dependencies are not preserved

Comparison: 3NF vs BCNF

Multi-Valued Dependencies and 4NF

Example

This causes combinatorial redundancy

Fifth Normal Form

Key Decision Guide

When to normalize further

When to stop or denormalize

Common Exam Patterns

Continue learning this concept

Core Concept

Quick Reference: Normal Form Requirements

Functional Dependencies: The Foundation

Armstrong's Axioms (Inference Rules)

Derived Rules

Closure of Attributes

Decomposition Properties

Lossless Join (Mandatory)

Dependency Preservation (Desirable)

A decomposition preserves dependencies if

If dependencies are not preserved

Comparison: 3NF vs BCNF

Multi-Valued Dependencies and 4NF

Example

This causes combinatorial redundancy

Fifth Normal Form

Key Decision Guide

When to normalize further

When to stop or denormalize

Common Exam Patterns

Continue learning this concept