DBMS

Database Design

Normalisation

Split tables until every fact is stored in

JrCodex·8 min read

Jr Codex DBMS Notes

Level: Intermediate Prerequisites: Chapter 3: Functional Dependencies Time to complete: ~25 minutes

Table of Contents

  1. What Normalisation Is
  2. First Normal Form
  3. Second Normal Form
  4. Third Normal Form
  5. Boyce-Codd Normal Form
  6. Lossless Decomposition
  7. How Far to Go
  8. Summary & Next Steps

1. What Normalisation Is

The Procedure
─────────────────────────────────────────
  Split tables until every fact is stored in
  exactly ONE place, determined by a key.

  Each normal form removes one specific kind of
  bad dependency:

    1NF   non-atomic values
    2NF   partial dependencies
    3NF   transitive dependencies
    BCNF  any determinant that is not a super key

  Each form ASSUMES the previous one. They are
  cumulative, not alternatives.
─────────────────────────────────────────

We normalise the broken enrollments_bad table from Chapter 3 step by step.

2. First Normal Form

1NF: every value is atomic; no repeating groups.

The Violation
─────────────────────────────────────────
  students_bad
  ┌──────┬────────┬──────────────────────┐
  │ s_id │ name   │ phones               │
  ├──────┼────────┼──────────────────────┤
  │  1   │ Asha   │ "9876, 9123"         │  ← two values, one cell
  │  2   │ Ravi   │ "9000"               │
  └──────┴────────┴──────────────────────┘
─────────────────────────────────────────

Why It Is Genuinely Broken
─────────────────────────────────────────
  - "find the student with phone 9123" needs LIKE
    '%9123%', which cannot use an index
    (Module 3, Chapter 2)
  - and matches 89123 too
  - you cannot constrain a phone's format
  - adding a third phone means string surgery
  - counting phones means parsing
─────────────────────────────────────────

-- 1NF: the multivalued attribute becomes its own table (Chapter 2, Rule 6).
CREATE TABLE students (
    id   INTEGER PRIMARY KEY,
    name TEXT NOT NULL
);
CREATE TABLE student_phones (
    student_id INTEGER NOT NULL REFERENCES students(id) ON DELETE CASCADE,
    phone      TEXT    NOT NULL,
    PRIMARY KEY (student_id, phone)
);
The Modern Caveat
─────────────────────────────────────────
  JSON and ARRAY columns technically violate 1NF,
  and every major database now offers them.

  Legitimate uses: genuinely schemaless payloads,
  audit blobs, external API responses stored whole.

  Not legitimate: anything you will filter, join
  or constrain on. If you find yourself indexing
  inside the JSON, it wanted to be a table.
─────────────────────────────────────────

3. Second Normal Form

2NF: in 1NF, and no partial dependency — no non-key attribute depends on only part of a composite key.

The Violation
─────────────────────────────────────────
  enrollments_bad(s_id, c_id, s_name, c_title, grade)
  KEY = {s_id, c_id}

  s_id → s_name         ← only PART of the key
  c_id → c_title        ← only PART of the key
  {s_id,c_id} → grade   ← the FULL key. Fine.

  So s_name is repeated for every course the
  student takes, and c_title for every student on
  the course.
─────────────────────────────────────────

-- 2NF: move each partially-dependent attribute to a table keyed by its determinant.
CREATE TABLE students    (id INTEGER PRIMARY KEY, name  TEXT NOT NULL);
CREATE TABLE courses     (id INTEGER PRIMARY KEY, title TEXT NOT NULL, dept_id INTEGER);
CREATE TABLE enrollments (
    s_id  INTEGER NOT NULL REFERENCES students(id),
    c_id  INTEGER NOT NULL REFERENCES courses(id),
    grade TEXT,
    PRIMARY KEY (s_id, c_id)          -- only the FULLY dependent attribute remains
);
The Shortcut
─────────────────────────────────────────
  2NF violations are only possible when the primary
  key is COMPOSITE.

  With a single-column key, no attribute can depend
  on "part" of it — there are no parts. Any table
  with a surrogate integer key is automatically in
  2NF.

  This is one more argument for surrogate keys
  (Module 2, Chapter 2).
─────────────────────────────────────────

4. Third Normal Form

3NF: in 2NF, and no transitive dependency — no non-key attribute determines another non-key attribute.

The Violation
─────────────────────────────────────────
  courses(c_id, title, dept_id, dept_name)
  KEY = {c_id}

  c_id    → dept_id      key determines non-key ✓
  dept_id → dept_name    NON-key determines
                         NON-key ✗

  So c_id → dept_name TRANSITIVELY, and dept_name
  is repeated on every course in that department.

  Rename a department and you must update every
  one of its courses — the update anomaly, back
  again.
─────────────────────────────────────────

-- 3NF: the transitively-dependent attribute moves to a table keyed by its determinant.
CREATE TABLE departments (
    id   INTEGER PRIMARY KEY,
    name TEXT NOT NULL UNIQUE
);
CREATE TABLE courses (
    id      INTEGER PRIMARY KEY,
    title   TEXT    NOT NULL,
    credits INTEGER NOT NULL CHECK (credits > 0),
    dept_id INTEGER NOT NULL REFERENCES departments(id)   -- dept_name lives ONCE
);
The Memorable Statement
─────────────────────────────────────────
  "Every non-key attribute must depend on THE KEY,
   THE WHOLE KEY, and NOTHING BUT THE KEY."

    the key         ──► 1NF (there is a key at all)
    the WHOLE key   ──► 2NF (no partial dependency)
    NOTHING BUT     ──► 3NF (no transitive
    the key              dependency)

  3NF is the practical target for most schemas.
─────────────────────────────────────────

5. Boyce-Codd Normal Form

BCNF: for every non-trivial FD X → Y, X is a super key.

Stricter Than 3NF
─────────────────────────────────────────
  3NF permits one exception: a non-key determinant
  is allowed if the attribute it determines is part
  of SOME candidate key.

  BCNF removes that exception entirely. Every
  determinant must be a super key. No exceptions.

  The two forms differ only when a table has
  OVERLAPPING candidate keys — uncommon, but real.
─────────────────────────────────────────

The Classic Example
─────────────────────────────────────────
  tutoring(student, subject, tutor)

  Rules:
    - each tutor teaches exactly ONE subject
    - a student has one tutor per subject

  FDs:
    {student, subject} → tutor      candidate key
    tutor → subject                 ← determinant,
                                      NOT a super key

  In 3NF? Yes — `subject` is part of a candidate
  key, so the exception applies.
  In BCNF? No — `tutor` is not a super key.

  The anomaly: you cannot record that a new tutor
  teaches Physics until some student is assigned
  to them.
─────────────────────────────────────────

-- BCNF: decompose on the offending determinant.
CREATE TABLE tutors (
    tutor   TEXT PRIMARY KEY,
    subject TEXT NOT NULL              -- tutor → subject, now with tutor as the KEY
);
CREATE TABLE student_tutors (
    student TEXT NOT NULL,
    tutor   TEXT NOT NULL REFERENCES tutors(tutor),
    PRIMARY KEY (student, tutor)
);
The Cost of BCNF
─────────────────────────────────────────
  BCNF decomposition is always LOSSLESS but not
  always DEPENDENCY-PRESERVING.

  Here, the FD {student, subject} → tutor now spans
  two tables, so the database can no longer enforce
  it with a single constraint — it needs a trigger
  or application logic.

  3NF is always both lossless AND
  dependency-preserving. That is the trade, and it
  is why 3NF is usually where people stop.
─────────────────────────────────────────

6. Lossless Decomposition

A split is only valid if joining the pieces reproduces the original exactly.

The Test
─────────────────────────────────────────
  Decomposing R into R1 and R2 is LOSSLESS if:

    (R1 ∩ R2) → R1   or   (R1 ∩ R2) → R2

  In words: the shared attributes must be a KEY of
  at least one of the two pieces.
─────────────────────────────────────────

Why It Matters
─────────────────────────────────────────
  A LOSSY split silently invents rows on rejoin.

  Split (student, subject, tutor) into
  (student, subject) and (subject, tutor), sharing
  only `subject` — which is a key of neither.

  Rejoin, and every student studying Physics is
  paired with every Physics tutor. You get MORE
  rows than you started with, and they are false.

  Always decompose on a DETERMINANT — then the
  shared attribute is a key of the new table by
  construction, and losslessness is automatic.
─────────────────────────────────────────

7. How Far to Go

The Higher Forms
─────────────────────────────────────────
  4NF   removes multivalued dependencies —
        two independent multivalued facts in one
        table, which multiply combinatorially

  5NF   removes join dependencies

  6NF   irreducible; used in temporal databases

  Rarely needed. If you designed from an ER model
  (Chapters 1-2) you usually land in 4NF without
  trying, because independent multivalued facts
  naturally became separate entities.
─────────────────────────────────────────

The Practical Target
─────────────────────────────────────────
  NORMALISE TO 3NF (or BCNF where it is free).

  Go further only when a specific anomaly is
  actually biting you.

  Then DENORMALISE deliberately, measured, and
  documented — Chapter 5.
─────────────────────────────────────────

The Honest Note on Performance
─────────────────────────────────────────
  "Normalisation is slow because of all the joins"
  is mostly folklore.

  Indexed joins on integer keys are fast
  (Module 5), and normalised tables are SMALLER, so
  more rows fit in the buffer pool and fewer pages
  are read.

  Normalised designs frequently outperform
  denormalised ones on write-heavy workloads,
  because there is only one copy to update.

  Measure before assuming otherwise.
─────────────────────────────────────────

8. Summary & Next Steps

Key Takeaways

  • Each normal form removes one kind of bad dependency, and they are cumulative: atomicity, then partial, then transitive, then any non-super-key determinant.
  • 2NF violations require a composite key, so a surrogate single-column key puts a table in 2NF automatically.
  • BCNF is stricter than 3NF but is not always dependency-preserving, which is why 3NF is the usual stopping point.
  • Always decompose on a determinant — this makes the split lossless by construction, whereas splitting on a non-key silently invents rows on rejoin.

Concept Check

  1. Why can a table with a single-column primary key never violate 2NF?
  2. In the tutoring example, what specifically can you not record before decomposing to BCNF?
  3. What does a lossy decomposition do when you rejoin the pieces, and what rule prevents it?

Next Chapter

→ Chapter 5: When to Denormalise

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index | Back to DBMS Index