Normalization

Think of these are audits or sanity checks that make sure you’ve designed your database properly. Doing things properly means that the query planners and optimizers work well, that you enjoy all the benefits of consistency (the “C” in ACID.)

There are five levels.

The Progression

Each form is the previous one plus one more rule. Every fix is the same move: split a table so that a fact is stored in exactly one place.

Why bother? Redundant facts cause anomalies:

• Update: change a fact in one row, forget the other copies, now the DB disagrees with itself.
• Insert: can’t record a fact without some unrelated fact (e.g. can’t add a patient until they have a diagnosis).
• Delete: deleting one fact accidentally deletes another.

Vocab

• Key: column(s) that uniquely identify a row. Key columns are underlined in the tables below.
• Functional dependency $A \to B$: knowing $A$ tells you $B$. Each value of $A$ goes with exactly one value of $B$. E.g. $pid \to name$.
• Multivalued dependency $A \twoheadrightarrow B$: knowing $A$ tells you a whole set of $B$s, independent of the other columns. E.g. a patient has a set of allergies.

Redundant values are shown in $\color{red}\text{red}$.

---

Unnormalized

A spreadsheet someone emailed you:

$$\begin{array}{|c|c|c|} \hline \textbf{name} & \textbf{age} & \textbf{diagnoses} \\ \hline \text{Ana} & 34 & {\color{red}\text{flu, asthma}} \\ \hline \text{Cy} & {\color{red}\text{"seventy-one"}} & \text{copd} \\ \hline \text{Ana} & 34 & \text{flu} \\ \hline \end{array}$$

Problems: a list crammed into one cell, a string in a number column, and no way to tell whether the two Anas are the same person. Plus, “the last row is the most recent visit” is information hiding in row order.

First Normal Form (1NF)

1. Using row order to convey information is not permitted
2. Mixing data types within the same column is not permitted
3. Having a table without a primary key is not permitted
4. Repeating groups are not permitted

In plain terms: it’s an actual relation. One value per cell, one type per column, a key, and row order means nothing. This is just the definition of a relation from Relational Algebra: a set of tuples over fixed domains.

Fix: one row per (patient, diagnosis), store dates explicitly, add IDs. Key is $(pid, icd)$. We’ve also pulled in the patient’s primary care doctor (PCP):

$$\begin{array}{|c|c|c|c|c|c|} \hline \underline{\textbf{pid}} & \underline{\textbf{icd}} & \textbf{name} & \textbf{pcp} & \textbf{phone} & \textbf{date} \\ \hline 1 & \text{J11} & \text{Ana} & \text{Dr. Lee} & \text{555-0101} & \text{Jan 5} \\ \hline 1 & \text{J45} & {\color{red}\text{Ana}} & {\color{red}\text{Dr. Lee}} & {\color{red}\text{555-0101}} & \text{Feb 10} \\ \hline 3 & \text{J44} & \text{Cy} & \text{Dr. Kim} & \text{555-0199} & \text{Mar 15} \\ \hline 3 & \text{J11} & {\color{red}\text{Cy}} & {\color{red}\text{Dr. Kim}} & {\color{red}\text{555-0199}} & \text{Apr 20} \\ \hline \end{array}$$

Valid 1NF, but Ana’s name and doctor are stored once per diagnosis.

Second Normal Form (2NF)

Each non-key attribute in the table must be dependent on the entire primary key.

In plain terms: no column depends on just part of the key. Only matters when the key has multiple columns.

Problem: $pid \to name, pcp, phone$. None of those care about $icd$. Only $date$ needs the whole key $(pid, icd)$.

Fix: split the patient facts out.

$$\begin{array}{c} \textbf{Patient} \\[4pt] \begin{array}{|c|c|c|c|} \hline \underline{\textbf{pid}} & \textbf{name} & \textbf{pcp} & \textbf{phone} \\ \hline 1 & \text{Ana} & \text{Dr. Lee} & \text{555-0101} \\ \hline 2 & \text{Bo} & \text{Dr. Lee} & {\color{red}\text{555-0101}} \\ \hline 3 & \text{Cy} & \text{Dr. Kim} & \text{555-0199} \\ \hline \end{array} \end{array} \qquad \begin{array}{c} \textbf{Diagnosis} \\[4pt] \begin{array}{|c|c|c|} \hline \underline{\textbf{pid}} & \underline{\textbf{icd}} & \textbf{date} \\ \hline 1 & \text{J11} & \text{Jan 5} \\ \hline 1 & \text{J45} & \text{Feb 10} \\ \hline 3 & \text{J44} & \text{Mar 15} \\ \hline 3 & \text{J11} & \text{Apr 20} \\ \hline \end{array} \end{array}$$

Ana’s name is now stored once. Bonus: we can now add Bo, who has no diagnoses yet (insert anomaly gone).

Third Normal Form (3NF)

Each non-key attribute in the table must depend on the key, the whole key, and nothing but the key.

In plain terms: no column depends on another non-key column. No chains like $key \to X \to Y$.

Problem: $pid \to pcp \to phone$. The phone belongs to the doctor, not the patient. Dr. Lee’s number is stored once per patient. If it changes, every one of Lee’s patients’ rows needs updating.

Fix: give doctors their own table.

$$\begin{array}{c} \textbf{Patient} \\[4pt] \begin{array}{|c|c|c|} \hline \underline{\textbf{pid}} & \textbf{name} & \textbf{pcp} \\ \hline 1 & \text{Ana} & \text{Dr. Lee} \\ \hline 2 & \text{Bo} & \text{Dr. Lee} \\ \hline 3 & \text{Cy} & \text{Dr. Kim} \\ \hline \end{array} \end{array} \qquad \begin{array}{c} \textbf{Doctor} \\[4pt] \begin{array}{|c|c|} \hline \underline{\textbf{pcp}} & \textbf{phone} \\ \hline \text{Dr. Lee} & \text{555-0101} \\ \hline \text{Dr. Kim} & \text{555-0199} \\ \hline \end{array} \end{array}$$

(Diagnosis unchanged.) This is where most real schemas stop. Mnemonic: “the key, the whole key, and nothing but the key, so help me Codd.” 1NF = there is a key, 2NF = the whole key, 3NF = nothing but the key.

Boyce-Codd Normal Form (BCNF)

Each attribute in the table must depend on the key, the whole key, and nothing but the key.

In plain terms: if any column determines another, it must be a key. 3NF only polices non-key columns. BCNF polices all of them. The difference only shows up when a non-key column determines part of the key.

New table. Rules: a patient sees one doctor per specialty, and each specialist practices one specialty. Key is $(pid, specialty)$:

$$\begin{array}{|c|c|c|} \hline \underline{\textbf{pid}} & \underline{\textbf{specialty}} & \textbf{doctor} \\ \hline 1 & \text{cardio} & \text{Dr. Shah} \\ \hline 1 & \text{derm} & \text{Dr. Ito} \\ \hline 3 & {\color{red}\text{cardio}} & \text{Dr. Shah} \\ \hline 3 & \text{derm} & \text{Dr. Park} \\ \hline \end{array}$$

Problem: $doctor \to specialty$, but $doctor$ isn’t a key. Passes 3NF (because $specialty$ is part of the key), but “Shah is a cardiologist” is stored twice. Delete Cy’s derm row and you lose the fact that Park is a dermatologist.

Fix:

$$\begin{array}{c} \textbf{Specialist} \\[4pt] \begin{array}{|c|c|} \hline \underline{\textbf{doctor}} & \textbf{specialty} \\ \hline \text{Dr. Shah} & \text{cardio} \\ \hline \text{Dr. Ito} & \text{derm} \\ \hline \text{Dr. Park} & \text{derm} \\ \hline \end{array} \end{array} \qquad \begin{array}{c} \textbf{Referral} \\[4pt] \begin{array}{|c|c|} \hline \underline{\textbf{pid}} & \underline{\textbf{doctor}} \\ \hline 1 & \text{Dr. Shah} \\ \hline 1 & \text{Dr. Ito} \\ \hline 3 & \text{Dr. Shah} \\ \hline 3 & \text{Dr. Park} \\ \hline \end{array} \end{array}$$

Trade-off: “one doctor per specialty per patient” is no longer enforceable by a simple key constraint, because the two columns now live in different tables. This is why people sometimes stay at 3NF.

Fourth Normal Form (4NF)

The only kinds of multivalued dependency allowed in a table are multivalued dependencies on the key.

In plain terms: don’t store two independent lists in one table.

Ana has allergies ${penicillin, peanuts}$ and meds ${albuterol, oseltamivir}$. These have nothing to do with each other, but in one table every allergy must be paired with every med. Key is all three columns:

$$\begin{array}{|c|c|c|} \hline \underline{\textbf{pid}} & \underline{\textbf{allergy}} & \underline{\textbf{med}} \\ \hline 1 & \text{penicillin} & \text{albuterol} \\ \hline 1 & \text{penicillin} & \text{oseltamivir} \\ \hline 1 & {\color{red}\text{peanuts}} & {\color{red}\text{albuterol}} \\ \hline 1 & {\color{red}\text{peanuts}} & {\color{red}\text{oseltamivir}} \\ \hline \end{array}$$

No functional dependencies at all, so it’s BCNF. But $pid \twoheadrightarrow allergy$ and $pid \twoheadrightarrow med$. The table is literally a Cartesian product: $\{\text{penicillin}, \text{peanuts}\} \times \{\text{albuterol}, \text{oseltamivir}\}$. Adding a third med means adding two rows, one per allergy. Forget one and you’ve implied Ana isn’t allergic to something.

Fix: one table per list.

$$\begin{array}{c} \textbf{Allergy} \\[4pt] \begin{array}{|c|c|} \hline \underline{\textbf{pid}} & \underline{\textbf{allergy}} \\ \hline 1 & \text{penicillin} \\ \hline 1 & \text{peanuts} \\ \hline \end{array} \end{array} \qquad \begin{array}{c} \textbf{Medication} \\[4pt] \begin{array}{|c|c|} \hline \underline{\textbf{pid}} & \underline{\textbf{med}} \\ \hline 1 & \text{albuterol} \\ \hline 1 & \text{oseltamivir} \\ \hline \end{array} \end{array}$$

4 rows became 2 + 2. With $k$ allergies and $j$ meds it’s $k \times j$ vs $k + j$.

Fifth Normal Form (5NF)

It must not be possible to describe the table as being the logical result of joining some other tables together.

In plain terms: if a table can be rebuilt by joining smaller tables, store the smaller tables instead.

Hospital rule: a doctor performs a procedure at a hospital whenever the doctor knows the procedure, the doctor has privileges at the hospital, and the hospital offers the procedure.

$$\begin{array}{|c|c|c|} \hline \underline{\textbf{doctor}} & \underline{\textbf{procedure}} & \underline{\textbf{hospital}} \\ \hline \text{Dr. Shah} & \text{angio} & \text{Mercy} \\ \hline \text{Dr. Shah} & \text{angio} & \text{St. Luke's} \\ \hline \text{Dr. Shah} & \text{stent} & \text{Mercy} \\ \hline \text{Dr. Ito} & \text{stent} & \text{Mercy} \\ \hline \end{array}$$

No independent lists (Shah does stents, has St. Luke’s privileges, but doesn’t do stents at St. Luke’s, since they don’t offer them), so it’s 4NF. But because of the rule, this table is exactly the join of three pairwise facts:

$$\begin{array}{c} \textbf{Skill} \\[4pt] \begin{array}{|c|c|} \hline \underline{\textbf{doctor}} & \underline{\textbf{procedure}} \\ \hline \text{Dr. Shah} & \text{angio} \\ \hline \text{Dr. Shah} & \text{stent} \\ \hline \text{Dr. Ito} & \text{stent} \\ \hline \end{array} \end{array} \qquad \begin{array}{c} \textbf{Privilege} \\[4pt] \begin{array}{|c|c|} \hline \underline{\textbf{doctor}} & \underline{\textbf{hospital}} \\ \hline \text{Dr. Shah} & \text{Mercy} \\ \hline \text{Dr. Shah} & \text{St. Luke's} \\ \hline \text{Dr. Ito} & \text{Mercy} \\ \hline \end{array} \end{array} \qquad \begin{array}{c} \textbf{Offers} \\[4pt] \begin{array}{|c|c|} \hline \underline{\textbf{hospital}} & \underline{\textbf{procedure}} \\ \hline \text{Mercy} & \text{angio} \\ \hline \text{Mercy} & \text{stent} \\ \hline \text{St. Luke's} & \text{angio} \\ \hline \end{array} \end{array}$$ $$\text{Original} = \text{Skill} \bowtie \text{Privilege} \bowtie \text{Offers}$$

Problem with the 3-column table: if St. Luke’s starts offering stents, you have to remember to add a row for every doctor who knows stents and has privileges there. In 5NF you add one row to Offers and the join produces the rest.

Subtle bit: you need all three. Joining just $\text{Skill} \bowtie \text{Privilege}$ invents a fake row (Shah, stent, St. Luke’s). And if the business rule doesn’t hold (doctors are credentialed per procedure per hospital), the 3-column table is irreducible and already 5NF. 5NF depends on what’s true in the world, not just on what the data looks like.

---

Summary

Form	Plain rule	Typical fix
1NF	It’s a real relation: atomic cells, a key, no row order	One row per fact, add IDs
2NF	No column depends on part of the key	Split off the partial dependency
3NF	No column depends on a non-key column	Split off the chain ($X \to Y$)
BCNF	Every determinant is a key	Split off the determinant
4NF	No independent lists in one table	One table per list
5NF	No table that’s just a join of smaller ones	Store the smaller ones

In practice: aim for 3NF/BCNF in transactional (OLTP) databases. 4NF/5NF problems are rare and usually get fixed by common sense. Analytical databases (data warehouses, star schemas) often denormalize on purpose, trading redundancy for fewer joins.