Normalization

Wikipedia · Database normalization · CC BY-SA 4.0

Normalization eliminates redundancy by decomposing tables based on functional dependencies. Each normal form (1NF through BCNF) removes a specific kind of anomaly. The goal: every fact is stored exactly once, so updates cannot create inconsistencies.

Functional dependencies

A functional dependency X -> Y means: if two tuples agree on attributes X, they must agree on Y. Example: student_id -> name (knowing the ID determines the name). Normalization decomposes tables so that each non-key attribute depends on the whole key and nothing but the key.

Scheme

; Functional dependency: X -> Y
; If two tuples agree on X, they must agree on Y.

(define data
  (list
    (list (cons "sid" 1) (cons "name" "Alice") (cons "dept" "CS")   (cons "dhead" "Turing"))
    (list (cons "sid" 2) (cons "name" "Bob")   (cons "dept" "CS")   (cons "dhead" "Turing"))
    (list (cons "sid" 3) (cons "name" "Carol") (cons "dept" "Math") (cons "dhead" "Gauss"))))

(define (get-attr t a) (cdr (assoc a t)))

; Check: does dept -> dhead hold?
(define (check-fd data x-attr y-attr)
  (let loop ((pairs data) (ok #t))
    (if (or (null? pairs) (not ok)) ok
      (let ((rest (cdr pairs)))
        (if (null? rest) ok
          (let check-pair ((others rest) (still-ok ok))
            (if (null? others) (loop rest still-ok)
              (if (and (equal? (get-attr (car pairs) x-attr)
                               (get-attr (car others) x-attr))
                       (not (equal? (get-attr (car pairs) y-attr)
                                    (get-attr (car others) y-attr))))
                #f
                (check-pair (cdr others) still-ok)))))))))

(display "dept -> dhead? ")
(display (check-fd data "dept" "dhead"))
(newline)
(display "sid -> name?   ")
(display (check-fd data "sid" "name"))

; Functional dependency: X -> Y
; If two tuples agree on X, they must agree on Y.

(define data
  (list
    (list (cons "sid" 1) (cons "name" "Alice") (cons "dept" "CS")   (cons "dhead" "Turing"))
    (list (cons "sid" 2) (cons "name" "Bob")   (cons "dept" "CS")   (cons "dhead" "Turing"))
    (list (cons "sid" 3) (cons "name" "Carol") (cons "dept" "Math") (cons "dhead" "Gauss"))))

(define (get-attr t a) (cdr (assoc a t)))

; Check: does dept -> dhead hold?
(define (check-fd data x-attr y-attr)
  (let loop ((pairs data) (ok #t))
    (if (or (null? pairs) (not ok)) ok
      (let ((rest (cdr pairs)))
        (if (null? rest) ok
          (let check-pair ((others rest) (still-ok ok))
            (if (null? others) (loop rest still-ok)
              (if (and (equal? (get-attr (car pairs) x-attr)
                               (get-attr (car others) x-attr))
                       (not (equal? (get-attr (car pairs) y-attr)
                                    (get-attr (car others) y-attr))))
                #f
                (check-pair (cdr others) still-ok)))))))))

(display "dept -> dhead? ")
(display (check-fd data "dept" "dhead"))
(newline)
(display "sid -> name?   ")
(display (check-fd data "sid" "name"))

Normal forms: 1NF through BCNF

1NF: every cell holds an atomic value (no lists, no nested tables). 2NF: no partial dependency (every non-key attribute depends on the entire primary key, not just part of it). 3NF: no transitive dependency (non-key attributes do not depend on other non-key attributes). BCNF: for every functional dependency X -> Y, X is a superkey.

Python

import sqlite3

conn = sqlite3.connect(":memory:")
c = conn.cursor()

# Unnormalized: dept and dhead are redundant
c.execute("""CREATE TABLE students_bad (
    sid INTEGER PRIMARY KEY, sname TEXT,
    dept TEXT, dhead TEXT
)""")
for r in [(1,'Alice','CS','Turing'),(2,'Bob','CS','Turing'),(3,'Carol','Math','Gauss')]:
    c.execute("INSERT INTO students_bad VALUES (?,?,?,?)", r)

# Normalized: split into students and departments
c.execute("CREATE TABLE departments (dept TEXT PRIMARY KEY, dhead TEXT)")
c.execute("CREATE TABLE students (sid INTEGER PRIMARY KEY, sname TEXT, dept TEXT REFERENCES departments)")

for d in [('CS','Turing'),('Math','Gauss')]:
    c.execute("INSERT INTO departments VALUES (?,?)", d)
for s in [(1,'Alice','CS'),(2,'Bob','CS'),(3,'Carol','Math')]:
    c.execute("INSERT INTO students VALUES (?,?,?)", s)

# Update anomaly: change dept head in one place
c.execute("UPDATE departments SET dhead = 'Knuth' WHERE dept = 'CS'")

print("After updating CS head to Knuth:")
for row in c.execute("""
    SELECT s.sname, d.dept, d.dhead
    FROM students s JOIN departments d ON s.dept = d.dept
"""):
    print("  " + str(row[0]) + " in " + str(row[1]) + ", head = " + str(row[2]))
print()
print("One update, consistent everywhere. That is normalization.")

import sqlite3

conn = sqlite3.connect(":memory:")
c = conn.cursor()

# Unnormalized: dept and dhead are redundant
c.execute("""CREATE TABLE students_bad (
    sid INTEGER PRIMARY KEY, sname TEXT,
    dept TEXT, dhead TEXT
)""")
for r in [(1,'Alice','CS','Turing'),(2,'Bob','CS','Turing'),(3,'Carol','Math','Gauss')]:
    c.execute("INSERT INTO students_bad VALUES (?,?,?,?)", r)

# Normalized: split into students and departments
c.execute("CREATE TABLE departments (dept TEXT PRIMARY KEY, dhead TEXT)")
c.execute("CREATE TABLE students (sid INTEGER PRIMARY KEY, sname TEXT, dept TEXT REFERENCES departments)")

for d in [('CS','Turing'),('Math','Gauss')]:
    c.execute("INSERT INTO departments VALUES (?,?)", d)
for s in [(1,'Alice','CS'),(2,'Bob','CS'),(3,'Carol','Math')]:
    c.execute("INSERT INTO students VALUES (?,?,?)", s)

# Update anomaly: change dept head in one place
c.execute("UPDATE departments SET dhead = 'Knuth' WHERE dept = 'CS'")

print("After updating CS head to Knuth:")
for row in c.execute("""
    SELECT s.sname, d.dept, d.dhead
    FROM students s JOIN departments d ON s.dept = d.dept
"""):
    print("  " + str(row[0]) + " in " + str(row[1]) + ", head = " + str(row[2]))
print()
print("One update, consistent everywhere. That is normalization.")

Neighbors

Foundations (Wikipedia)

← SQL Basics by june.kim Indexing →