Normalization and Denormalization

1The Problem Normalization Solves

Consider a single flat table recording course enrolments:

CREATE TABLE enrolment_flat (
  student_id     INT,
  student_name   TEXT,
  student_email  TEXT,
  course_code    TEXT,
  course_title   TEXT,
  instructor     TEXT,
  instructor_office TEXT,
  grade          TEXT
);

student_id | student_name | course_code | course_title | instructor | instructor_office | grade
-----------+--------------+-------------+--------------+------------+-------------------+------
1          | Ana          | CS101       | Databases    | Karimov    | B-214             | A
1          | Ana          | CS220       | Networks     | Sattorov   | C-101             | B
2          | Leo          | CS101       | Databases    | Karimov    | B-214             | A

Databases / Karimov / B-214 is stored twice. Ana is stored twice. That redundancy is not just wasted bytes — it creates three concrete classes of bug:

• Update anomaly — Karimov moves to office B-300. You must update every row mentioning him. Miss one and the database now asserts he is in two offices simultaneously.
• Insert anomaly — a new course CS330 exists but nobody has enroled yet. There is no row to put it in without inventing a fake student, because student_id is part of what identifies a row.
• Delete anomaly — student 2 drops CS101. If student 2 was the last enrolee, deleting that row also erases the fact that CS101 is titled "Databases" and taught by Karimov.

Normalization is the systematic procedure for decomposing a table so that these anomalies become structurally impossible rather than something application code must remember to prevent.

2Functional Dependencies — The Formal Ground

A functional dependency X → Y means: any two rows that agree on all attributes in X must agree on all attributes in Y. It is a statement about the real world being modelled, not about the data currently present.

In the table above:

student_id                  → student_name, student_email
course_code                 → course_title, instructor
instructor                  → instructor_office
{student_id, course_code}   → grade

The candidate key is {student_id, course_code} — the minimal attribute set that functionally determines every other attribute. Every anomaly above traces to one shape of dependency:

Normal forms are just rules that outlaw specific dependency shapes.

3First Normal Form (1NF)

Every attribute holds a single atomic value; no repeating groups, no arrays crammed into a column.

-- violates 1NF: a comma-joined list in one column
CREATE TABLE student_bad (id INT, name TEXT, phone_numbers TEXT);
INSERT INTO student_bad VALUES (1, 'Ana', '+998901112233,+998907778899');

-- 1NF: one fact per row
CREATE TABLE student (id INT PRIMARY KEY, name TEXT NOT NULL);
CREATE TABLE student_phone (
  student_id INT REFERENCES student(id),
  phone      TEXT,
  PRIMARY KEY (student_id, phone)
);

The cost of violating 1NF is that the database can no longer index, constrain, or join on the individual values — WHERE phone_numbers LIKE '%7778899%' cannot use an index and will also match substrings of other numbers.

4Second Normal Form (2NF)

In 1NF and no non-key attribute depends on only part of a composite key.

-- 1NF but not 2NF: key is {student_id, course_code},
-- yet course_title depends on course_code alone.
CREATE TABLE enrolment_1nf (
  student_id   INT,
  course_code  TEXT,
  course_title TEXT,      -- partial dependency
  grade        TEXT,
  PRIMARY KEY (student_id, course_code)
);

-- 2NF: split the partially-dependent attributes into their own table
CREATE TABLE course (
  code  TEXT PRIMARY KEY,
  title TEXT NOT NULL
);
CREATE TABLE enrolment (
  student_id  INT  REFERENCES student(id),
  course_code TEXT REFERENCES course(code),
  grade       TEXT,
  PRIMARY KEY (student_id, course_code)
);

2NF is only ever at risk when the key is composite. A table with a single-column key is automatically in 2NF.

5Third Normal Form (3NF)

In 2NF and no non-key attribute transitively depends on the key through another non-key attribute.

-- 2NF but not 3NF: code → instructor → instructor_office
CREATE TABLE course_2nf (
  code              TEXT PRIMARY KEY,
  title             TEXT,
  instructor        TEXT,
  instructor_office TEXT    -- depends on instructor, not on code
);

-- 3NF
CREATE TABLE instructor (
  name   TEXT PRIMARY KEY,
  office TEXT
);
CREATE TABLE course (
  code            TEXT PRIMARY KEY,
  title           TEXT NOT NULL,
  instructor_name TEXT REFERENCES instructor(name)
);

Now Karimov's office is stored exactly once. The update anomaly is gone by construction — there is literally no second place to make inconsistent.

6Boyce-Codd Normal Form (BCNF)

For every non-trivial dependency X → Y, X must be a superkey. BCNF is strictly stronger than 3NF; the difference only shows up when a table has overlapping candidate keys.

-- Each course in each term has one room; each room in each term hosts one course.
-- Candidate keys: {course, term} and {room, term}
CREATE TABLE schedule (
  course TEXT,
  term   TEXT,
  room   TEXT,
  instructor TEXT,
  PRIMARY KEY (course, term),
  UNIQUE (room, term)
);
-- Suppose additionally: instructor → course (each instructor teaches one course).
-- `instructor` is not a superkey, so this violates BCNF while still being 3NF
-- (instructor is a prime-attribute-free determinant but course IS prime,
--  which is exactly the loophole 3NF permits and BCNF closes).

CREATE TABLE instructor_course (
  instructor TEXT PRIMARY KEY,
  course     TEXT NOT NULL
);
CREATE TABLE schedule (
  term       TEXT,
  instructor TEXT REFERENCES instructor_course(instructor),
  room       TEXT,
  PRIMARY KEY (term, instructor),
  UNIQUE (term, room)
);

3NF is the practical target for most schemas; BCNF matters when you have genuine overlapping keys, and it is not always achievable while preserving all dependencies (see Under the Hood).

7Denormalization — Deliberately Adding Redundancy Back

Denormalization is not "failing to normalize". It is starting from a normalized design and reintroducing controlled redundancy for a measured read-path win, accepting a specific, named consistency obligation in exchange.

-- Normalized: computing an order total requires a join + aggregate on every read
SELECT o.id, SUM(oi.quantity * oi.unit_price) AS total
FROM   "order" o JOIN order_item oi ON oi.order_id = o.id
GROUP  BY o.id;

-- Denormalized: store the total on the order row
ALTER TABLE "order" ADD COLUMN total_cents BIGINT NOT NULL DEFAULT 0;

Common denormalization patterns:

-- Keeping a counter honest with a trigger: the obligation, made explicit
CREATE FUNCTION bump_comment_count() RETURNS trigger AS $$
BEGIN
  IF TG_OP = 'INSERT' THEN
    UPDATE post SET comment_count = comment_count + 1 WHERE id = NEW.post_id;
  ELSIF TG_OP = 'DELETE' THEN
    UPDATE post SET comment_count = comment_count - 1 WHERE id = OLD.post_id;
  END IF;
  RETURN NULL;
END; $$ LANGUAGE plpgsql;

CREATE TRIGGER comment_count_trg
AFTER INSERT OR DELETE ON comment
FOR EACH ROW EXECUTE FUNCTION bump_comment_count();

Note what that trigger costs: every comment insert now also takes a row lock on the parent post row. Two people commenting on the same viral post serialize on that lock. That is the real price, and it is invisible until traffic arrives.

An important special case: order_item.unit_price copied from product.price is not denormalization at all. The order must record what the customer actually paid, which is a different fact from what the product costs today. Duplicated-looking columns that capture a point-in-time value are normalized, because they depend on the order, not on the product.

Under the HoodHow it works internally▾

Anomalies are a theorem, not a rule of thumb

The anomalies in section 1 are not a list someone compiled from experience — they follow mechanically from redundancy. If a fact F is derivable from a dependency X → Y and X appears in n rows, then F is physically stored n times. The database has no way to know those n copies are meant to be the same fact, so it cannot enforce their agreement; any write that touches fewer than all n leaves the relation in a state that no longer corresponds to any possible world. Normalization removes the redundancy by ensuring every non-trivial dependency's determinant is a key — and a key, by definition, appears in exactly one row. n = 1 means "update all copies" and "update one row" are the same operation, which is why the anomaly cannot occur.

That is the whole content of the normal-form hierarchy:

Form	Outlaws	Anomaly class removed
1NF	non-atomic values	you cannot even state a dependency over a list
2NF	partial dependencies on a composite key	facts about part of the key duplicated per combination
3NF	transitive dependencies	facts about a non-key attribute duplicated per key
BCNF	any non-superkey determinant	the residue 3NF leaves when candidate keys overlap
4NF	multivalued dependencies	the cartesian-product blowup of two independent multi-valued facts

Lossless join and dependency preservation

A decomposition is only legitimate if it satisfies two properties, and the second one is why BCNF is not always the goal.

Lossless join (the non-negotiable one): decomposing R into R1 and R2 is lossless iff R1 ∩ R2 → R1 or R1 ∩ R2 → R2 — that is, the shared attributes functionally determine one of the halves. If they do not, R1 ⋈ R2 produces spurious tuples, rows that were never in the original data:

textCopy

R:  (Ana, CS101, Karimov)      Split on the wrong attribute:
    (Leo, CS220, Sattorov)     R1(student, course)   R2(course, instructor)  -- lossless, course→instructor
                                R1(student, instr)    R2(instr, course)       -- also fine
                                R1(student, course)   R2(student, instructor) -- LOSSY if a student takes 2 courses:
                                                                                  the join invents (Ana, CS101, Sattorov)

Dependency preservation: every original dependency should be checkable against a single decomposed table, so a UNIQUE or PRIMARY KEY constraint alone can enforce it. 3NF decomposition is always achievable while preserving both properties. BCNF decomposition is always lossless but sometimes cannot preserve dependencies — the classic proof case being exactly the schedule table above, where forcing BCNF can push a dependency across two tables so that enforcing it requires a join-time check (a trigger or an assertion) rather than a declarative constraint. That is the concrete, non-hand-wavy reason practitioners stop at 3NF: the last increment of purity is paid for in constraints the engine can no longer enforce for free.

What a join actually costs, versus what redundancy costs

The reflexive "normalize for writes, denormalize for reads" advice hides the actual numbers. On a normalized schema, joining enrolment to course on an indexed key is a nested-loop or hash join whose cost is roughly one B-tree descent per outer row — 3-4 page reads, nearly all of which hit the buffer cache for a small dimension table like course. Modern planners will also flip to a hash join and scan course once when the outer side is large. Denormalizing to avoid that join saves microseconds per row.

The write side is where the asymmetry lives. Copying instructor_office into 50,000 enrolment rows means an office change is a 50,000-row UPDATE, which in an MVCC engine like Postgres writes 50,000 new row versions, dirties every page holding them, writes all of it to the WAL, invalidates those pages in every replica's buffer cache, and leaves 50,000 dead tuples for autovacuum. This is write amplification, and it is the reason normalization is the default: the cost of a join is bounded and predictable, while the cost of redundancy scales with the fan-out of the duplicated fact.

Denormalize when you have measured that the join is genuinely the bottleneck (usually: high fan-out aggregate, or a join across a network/shard boundary), and when the duplicated fact changes far less often than it is read.

Where the normal forms stop applying

Normal forms are defined over the relational model with functional dependencies. They say nothing about:

• Time-series or event tables, which are append-only by design; redundancy there is the point, because an event is an immutable historical record.
• Analytical star schemas, which deliberately denormalize into wide fact and dimension tables because the workload is bulk scan + aggregate, not point update, so write amplification never occurs.
• Document stores, where the unit of atomicity is the document, so the equivalent design question is "what must be updated together" rather than "what depends on what" (see 05-json_in_sql_and_nosql/).

⚠️ Common Pitfalls

1. Treating denormalization as an optimization you apply pre-emptively. Without a measurement you have paid the write-amplification and consistency cost for a read win that may not exist. Normalize first; denormalize against a profile.
2. Adding a surrogate id and believing the table is now in 2NF. A surrogate key makes {id} a candidate key, but the natural composite key still exists and partial dependencies on it are still real. 2NF is about dependencies, not about how many columns the declared PK has.
3. Confusing a point-in-time copy with redundancy. order_item.unit_price and invoice.billing_address must be frozen copies — the dependency is on the order, not on the current product or customer. "De-duplicating" them into a join is an actual correctness bug.
4. Decomposing on attributes that do not determine either half, producing a lossy join that silently invents rows. Always check R1 ∩ R2 → R1 or → R2 before splitting.
5. Maintaining a denormalized counter without a transaction or trigger. An application-level UPDATE post SET comment_count = comment_count + 1 issued outside the same transaction as the insert will drift the moment a request fails between the two statements.
6. Normalizing lookup tables into oblivion. A two-column status(id, name) table joined on every query buys nothing over a CHECK (status IN (...)) constraint or an enum, and costs a join plus a foreign key check on every write.
7. Assuming 3NF is free of all redundancy. It permits the overlapping-candidate-key case; if you see a determinant that is not a superkey, you have real duplication even in a "correctly normalized" schema.

📋 Quick Reference

1NF   atomic columns, no repeating groups / embedded lists
2NF   1NF + no non-key attribute depends on PART of a composite key
3NF   2NF + no non-key attribute depends on another NON-KEY attribute
BCNF  every determinant X in X→Y is a superkey
4NF   no non-trivial multivalued dependencies

Mnemonic: every non-key attribute depends on
          "the key, the whole key, and nothing but the key"
          (2NF = whole key, 3NF = nothing but the key)

Decomposition is lossless iff  (R1 ∩ R2) → R1  or  (R1 ∩ R2) → R2
3NF  : always lossless AND dependency-preserving
BCNF : always lossless, NOT always dependency-preserving

Denormalize when:  join is measured-bottleneck, source fact changes rarely,
                   read:write ratio is high, and you name the maintenance path
                   (trigger / materialized view / CDC rebuild)
Cost of redundancy: write amplification proportional to duplication fan-out

🎤 Interview Q&A

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

✅ Check yourself

Source: dbmodel_normalization_and_denormalization_theory.md · generated by tools/build_lessons.py