What is Normalization

Designing to eliminate data redundancy and prevent logical inconsistencies in data.

Prerequisites

Keys

• Primary Key
  • An identifier that uniquely identifies a row
• Composite Key
  • A primary key composed of multiple attributes
• Foreign Key
  • A key used to reference another table
• Candidate Key
  • A set of attributes that uniquely identifies a row, is irreducible, and minimal (minimum number of attributes)
• Super Key
  • A combination of attributes that uniquely identifies a row, including extra attributes
• Irreducible
  • A state where there are no extra attributes (≒ cannot reduce attributes further)

Primary Key: {Employee Number, ID}

Candidate Key: {Employee Number, ID}, {Phone Number}

Super Key: {Employee Number, ID}, {Employee Number, ID, Name}, {Employee Number, ID, Name, Gender} etc...

Functional Dependency

• Functional Dependency
  • The property that if A is determined, B is also determined
• Partial Functional Dependency
  • A property where an attribute is dependent on one of the candidate keys
• Full Functional Dependency
  • A property where all non-key attributes are functionally dependent on the primary key
• Transitive Functional Dependency
  • A functional dependency between non-key attributes where if A is determined, B is determined, and if B is determined, C is determined
• Join Dependency
  • The property that decomposed relations can be joined back to the original relation (≒ lossless decomposition)
• Multivalued Dependency
  • A relationship where B and C are independent regarding attributes A and C, and B depends on A
  • A special case of join dependency
• Lossless Decomposition
  • Decomposing a relation in such a way that the original relation can be reconstructed by joining the decomposed parts

Normal Forms

First Normal Form (1NF)

• Rows are not ordered vertically, and columns are not ordered horizontally
  • Although SQL has an order, avoid writing queries that depend on order
    • e.g., Avoid SELECT *, specify column positions in ORDER BY (ORDER BY 1), etc.
• No duplicate rows
• No NULLs
• Each column contains only one value that satisfies the domain (data type)

Second Normal Form (2NF)

• Satisfies 1NF
• Eliminates partial functional dependencies, achieving full functional dependency
  • All non-key attributes are fully functionally dependent on the candidate key

Third Normal Form (3NF)

• Satisfies 2NF
• Eliminates transitive functional dependencies
  • No non-key attributes are transitively functionally dependent on the candidate key

Boyce-Codd Normal Form (BCNF)

• Satisfies 3NF
• Eliminates partial and transitive functional dependencies of candidate keys
• All non-trivial functional dependencies are removed, and no further lossless decomposition is possible due to functional dependencies
  • Trivial {Order Number, Product Number} → {Product Number}
  • Non-trivial {Product Name} → {Material Name}

Fourth Normal Form (4NF)

• Normalization due to multivalued dependencies

Fifth Normal Form (5NF)

• All non-trivial or implicit join dependencies are removed

Normalization

1NF

Non-normalized form

1NF

2NF

Before 2NF

The candidate key {Invoice Number, Product Number} and the non-key attribute Product Name are partially functionally dependent.

2NF Sales Detail Table

Product Table

Partial functional dependency only occurs when the candidate key is a composite key, so it does not occur when the candidate key is a single attribute.

3NF

Before 3NF

When the primary key is {Invoice Number, Product Number}, {Invoice Number, Customer Number}→{Customer Number}→{Customer Name} is transitively dependent.

3NF Sales Detail Table

Customer Table

BCNF

Before BCNF

When the primary key is {Name, Subject}, there is a functional dependency {Teacher}→{Subject}, and the determinant (A in A→B) is not a super key.

BCNF Enrollment Table

Teacher Table

The information {Name, Subject}→{Teacher} is lost, so it is unclear who John's math teacher is.

4NF

Before 4NF

When the primary key is {Name, Hobby, Favorite Food}, multiple attributes are determined by {Name}→{Hobby}→{Favorite Food}.

4NF Hobby Table

Favorite Food Table

5NF

Before 5NF

{Store}→{Stock Item}, {Store}→{Manufacturer}, {Stock Item}→{Manufacturer} can be decomposed into multiple parts.

5NF Stock Table

Supplier Table

Manufacturer Table

Thoughts

I am not very confident in my understanding beyond BCNF...

References

• amzn.to - Learn Database Practice from Theory ~ Efficient SQL with Relational Model (WEB+DB PRESS plus)
• e-words.jp - Partial Functional Dependency
• datascience-lab.sakura.ne.jp - Understanding Various Types of "Keys"
• poppingcarp.com - Various Keys like Primary Key, Candidate Key, Foreign Key, Super Key | Database Basics
• koseki2580.github.io - Normalization
• zenn.dev - Understanding Database Normalization with Illustrations
• youtube.com - Database Normalization (1NF, 2NF, 3NF)
• tabibou.com - Database Normalization from 1NF to 5NF, Boyce-Codd Normal Form Examples
• poppingcarp.com - Various Keys like Primary Key, Candidate Key, Foreign Key, Super Key | Database Basics