Normalization

A systematic approach to decide whether a particular relation is in good form. Helps ensure correctness and maintainability. But might degrade query performance.

Normalization theory was introduced by Edgar F. Codd, the father of relational databases, in 1970.

“Good” Form?

A relation is in good form when it has these properties:

• easier to understand and to extend
• clear keys that uniquely identify tuples
• appropriate atomic domains for attributes
• functional dependencies that do not introduce partial or transitive redundancy
• constraints captured by a suitable normal form (1NF, 2NF, 3NF, BCNF, etc.) given the application needs.

A database is in a good form when all of its relations are in good form.

Normal Forms

Normal forms prevent anomalies.

Several normal forms are defined, each builds on the previous one and defines a set of rules. Consecutive normal forms ensure the relations are in a better form.

Each normal form defines a set of conditions. If one of the conditions are violated, the relation is said to be violate the normal form.

If a relation violates $n$th normal form, it is violating $i$th normal forms where $i \gt n$.

1st Normal Form (1NF)

If all the below conditions are met, the relation is in 1NF:

• Row order is not used to convey information.
• Domain of any attribute contains values of a single type, not multiple types.
  Not possible in relational DBMS.
• It has a primary key.
• It has no repeating groups.

2nd Normal Form (2NF)

If all the below conditions are met, the relation is in 2NF:

• It’s in 1NF
• All non-key attributes must depend on the entire primary key.

If not, the relation must be decomposed into smaller relations.

3rd Normal Form (3NF)

If all the below conditions are met, the relation is in 3NF:

• It’s in 2NF
• All non-key attributes must depend only on the entire primary key.

Allows key attributes to depend on non-key attributes.

Aims to remove data redundancy.

Boyce-Codd Normal Form (BCNF)

Slightly stronger than 3NF. Can be thought of as 3.5NF.

If all the below conditions are met, the relation is in BCNF:

• It’s in 3NF
• All key attributes must depend on and only on the entire primary key.

Fix for BCNF Violation

Suppose relation $R$ and a non-trivial functional dependency $A \rightarrow B$ cause a violation of BCNF.

$R$ is decomposed into:

• $(A \cup B)$
• $R - (B - A)$

Why BCNF Is the Usual Target

Most designs stop at BCNF, or 3NF when dependency preservation is needed, even though 4NF and 5NF exist.

• Functional dependencies are the most common constraint.
  BCNF removes the redundancy they cause.
• Multivalued and join dependencies are rare.
  They appear only when independent facts are stored together in 1 relation.
• A careful ER model already avoids them.
  Each independent multivalued fact becomes its own entity or relationship, so the resulting tables are usually in 4NF already.
• Join dependencies are hard to spot.
  They are not visible from the real-world constraints the way functional dependencies are.
• Every extra decomposition adds joins.
  Queries get slower for a small gain in redundancy.

4th Normal Form (4NF)

If all the below conditions are met, the relation is in 4NF:

• It’s in BCNF
• All multivalued dependencies must be multivalued dependencies on the key.

If not, the relation must be decomposed into smaller relations.

5th Normal Form (5NF)

If all the below conditions are met, the relation is in 5NF:

• It’s in 4NF
• It cannot be describable as the logical result of joining some other tables together.