Normalization

Normalization is the step-by-step splitting of one cluttered table into several clean ones so that *no fact is stored twice*. Each level — 1NF, 2NF, 3NF, BCNF — fixes one specific flaw, and every split is lossless: you can rejoin the pieces to reproduce the original exactly.

Why redundancy hurts: anomalies

Storing the same fact in many rows invites anomalies. An *update anomaly* changes one copy and misses another, so the table contradicts itself. An *insert anomaly* blocks you from recording a course until a student enrols in it. A *delete anomaly* loses the course the moment its last student drops. Normalization removes the redundancy, so these disappear.

A table that needs cleaning up

Take one wide table keyed on the pair {StudentID, CourseID}:

Enroll(StudentID, CourseID, StudentName, CourseName, Instructor, Office, Grade)
key = {StudentID, CourseID}

Functional dependencies:
  StudentID              -> StudentName
  CourseID               -> CourseName, Instructor
  Instructor             -> Office
  {StudentID, CourseID}  -> Grade

1. 11NF — every cell holds a single value and the table has a key. If Instructor ever held a list like Smith, Jones, split it into separate rows. Now atomic: 1NF holds.
2. 22NF — remove *partial dependencies* on the composite key. StudentName depends on StudentID alone, and CourseName, Instructor, Office on CourseID alone — each is only half the key. Split them out.
3. 33NF — remove *transitive dependencies*. In the course table CourseID -> Instructor -> Office, so Office depends on the key only second-hand. Move it to its own table.
4. 4BCNF — tighten 3NF so every determinant is a key (worked separately below).

The 2NF split

Student(StudentID, StudentName)
Course(CourseID, CourseName, Instructor, Office)
Enroll(StudentID, CourseID, Grade)

Now every non-key column depends on the *whole* key of its table. But Course still hides a transitive dependency.

The 3NF split

Course(CourseID, CourseName, Instructor)
Instructor(Instructor, Office)

// Student and Enroll are unchanged

BCNF: when 3NF is not quite enough

Consider Teach(Student, Course, Instructor) where each instructor teaches exactly one course, but a course can have several instructors:

FDs:  {Student, Course} -> Instructor
      Instructor        -> Course

Candidate keys: {Student, Course} and {Student, Instructor}

This is already 3NF — in Instructor -> Course, the column Course is *prime* (part of a candidate key), which 3NF permits. But Instructor is not a superkey, so it violates BCNF. Decompose on the offending FD:

R1(Instructor, Course)   // Instructor is its key
R2(Student, Instructor)