Functional dependencies and normalization

The ER method of lessons 6 and 7 usually produces sensible tables, but it guarantees nothing: a designer can still put facts in the wrong place and end up storing the same fact many times. Normalization is the formal theory that detects and removes such redundancy. It is built on functional dependencies, statements of the form 'the student number determines the student's name', which capture the real-world rules that make some data redundant. This lesson defines functional dependencies and the reasoning rules for them, shows how to find keys, explains the normal forms from first normal form to Boyce–Codd normal form, and shows how to decompose a bad table into good ones without losing information. The computations are short enough to do by hand and are also implemented in Python here.

Redundancy and anomalies

Consider a single table that a registrar might build from a spreadsheet, recording which student took which section with what grade, together with the student's name and department, the course title, and the department's building.

Ava's name and department are stored once for each of her courses; the CS building is stored once for every enrollment of every CS student; each course title is stored once per enrollment. This redundancy wastes space, but its real cost is three kinds of anomaly. An update anomaly: if the CS department moves, every row for every CS student must change, and missing one leaves the data contradicting itself. An insertion anomaly: a new course cannot be recorded until some student enrolls, because every row needs a student and a grade. A deletion anomaly: if Chloe drops CMPUT-272 and that was her only row, we lose the fact that the Mathematics department is in Central Hall. Normalization removes these anomalies by splitting the table so that each fact is stored once.

Functional dependencies

A functional dependency (FD) \(X \to Y\), read 'X determines Y', holds on a relation if any two tuples that agree on all attributes in X also agree on all attributes in Y. In grade_report, student_id \(\to\) student_name holds because a student has one name; course_id \(\to\) title holds; dept_id \(\to\) building holds; and {student_id, course_id} \(\to\) grade holds. An FD is a statement about every legal instance, so, exactly as with keys, it comes from the meaning of the data. Data can refute an FD with one pair of tuples, but cannot prove one.

Keys are a special case: X is a superkey of R exactly when \(X \to R\), that is, X determines every attribute. So FDs generalize keys. Normalization says, roughly, that the only FDs a table should have are those implied by its keys; any other FD means some attribute depends on something that is not a key, and that fact is being repeated.

Reasoning about FDs: Armstrong's axioms and closure

Given some FDs, others follow. If student_id determines dept_id and dept_id determines building, then student_id determines building. William Armstrong's axioms (1974) are a complete set of rules for deriving all implied FDs. Reflexivity: if \(Y \subseteq X\), then \(X \to Y\). Augmentation: if \(X \to Y\), then \(XZ \to YZ\). Transitivity: if \(X \to Y\) and \(Y \to Z\), then \(X \to Z\). Useful derived rules are union (if \(X \to Y\) and \(X \to Z\), then \(X \to YZ\)), decomposition (if \(X \to YZ\), then \(X \to Y\)) and pseudo-transitivity.

In practice we rarely apply the axioms directly. Instead we compute the closure of a set of attributes X, written \(X^{+}\): the set of all attributes that X determines. The algorithm starts with X and repeatedly adds the right side of any FD whose left side is already contained in the result, until nothing changes. Then \(X \to Y\) is implied exactly when \(Y \subseteq X^{+}\), and X is a superkey exactly when \(X^{+}\) contains every attribute.

from itertools import combinations

def closure(attrs, fds):
    """Attribute closure: every attribute determined by attrs under fds."""
    result = set(attrs)
    changed = True
    while changed:
        changed = False
        for lhs, rhs in fds:
            if lhs <= result and not rhs <= result:
                result |= rhs
                changed = True
    return result

def candidate_keys(R, fds):
    keys = []
    for k in range(1, len(R) + 1):
        for combo in combinations(sorted(R), k):
            s = set(combo)
            if closure(s, fds) == R and not any(key <= s for key in keys):
                keys.append(s)
    return keys

def fd(s):  # "A B -> C" to (frozenset, frozenset)
    l, r = s.split("->")
    return frozenset(l.split()), frozenset(r.split())

R = set("student_id student_name dept_id building course_id title grade".split())
F = [fd("student_id -> student_name dept_id"), fd("dept_id -> building"),
     fd("course_id -> title"), fd("student_id course_id -> grade")]

print("closure of {student_id}:", sorted(closure({"student_id"}, F)))
print("closure of {student_id, course_id} is all of R:",
      closure({"student_id", "course_id"}, F) == R)
print("candidate keys:", [sorted(k) for k in candidate_keys(R, F)])

closure of {student_id}: ['building', 'dept_id', 'student_id', 'student_name']
closure of {student_id, course_id} is all of R: True
candidate keys: [['course_id', 'student_id']]

The closure of student_id contains the student's name, department and building, but not the title or grade, so student_id alone is not a key. The pair {student_id, course_id} determines everything and is the only candidate key. A helpful shortcut for finding keys by hand: any attribute that never appears on the right side of an FD must be in every key, because nothing else can determine it. Here student_id and course_id never appear on a right side, so every key contains both, and since together they are a key, the search ends immediately.

The normal forms

Normal forms are conditions on a relation and its FDs, each stronger than the last, that limit redundancy. First normal form (1NF) requires atomic values: no lists or nested tables in a column. The relational model assumes it, and lesson 7's mapping of multivalued attributes achieves it. Second normal form (2NF) forbids partial dependencies, where a non-key attribute depends on only part of a composite key: in grade_report, student_name depends on student_id alone, part of the key {student_id, course_id}, so the table is not in 2NF. 2NF matters only for composite keys and is mostly of historical interest; the two important forms are 3NF and BCNF.

A relation is in Boyce–Codd normal form (BCNF) if, for every non-trivial FD \(X \to Y\) that holds, X is a superkey. In words: every determinant is a key. BCNF eliminates all redundancy that FDs can detect. A relation is in third normal form (3NF) if, for every non-trivial FD \(X \to Y\), either X is a superkey or every attribute in \(Y - X\) is prime, meaning part of some candidate key. 3NF is slightly weaker than BCNF; the extra escape clause exists so that every relation can be decomposed into 3NF without losing the ability to check FDs locally, which BCNF cannot always guarantee.

Decomposition: lossless and dependency preserving

To normalize, we decompose a relation R into smaller relations whose attributes together cover R. Two properties make a decomposition acceptable. It must be lossless: joining the pieces back together must give exactly the original relation, no more and no fewer tuples. A lossy decomposition creates spurious tuples, false facts, when the pieces are rejoined. And it should be dependency preserving: every FD should be checkable within a single piece, so that the DBMS can enforce it with a key or unique constraint instead of an expensive join on every update.

There is a simple test for a decomposition into two pieces \(R_1\) and \(R_2\): it is lossless exactly when the common attributes \(R_1 \cap R_2\) determine all of \(R_1\) or all of \(R_2\), that is, when the shared attributes are a key of at least one piece. Splitting grade_report into student(student_id, student_name, dept_id) and the rest is lossless because the shared attribute student_id is the key of student. Splitting on a non-key attribute, for instance putting dept_id and grade in one table and the rest in another sharing only dept_id, would be lossy.

from itertools import combinations

def closure(attrs, fds):
    """Attribute closure: every attribute determined by attrs under fds."""
    result = set(attrs)
    changed = True
    while changed:
        changed = False
        for lhs, rhs in fds:
            if lhs <= result and not rhs <= result:
                result |= rhs
                changed = True
    return result

def candidate_keys(R, fds):
    keys = []
    for k in range(1, len(R) + 1):
        for combo in combinations(sorted(R), k):
            s = set(combo)
            if closure(s, fds) == R and not any(key <= s for key in keys):
                keys.append(s)
    return keys

def fd(s):  # "A B -> C" to (frozenset, frozenset)
    l, r = s.split("->")
    return frozenset(l.split()), frozenset(r.split())

def lossless_binary(R1, R2, fds):
    common = R1 & R2
    c = closure(common, fds)
    return R1 <= c or R2 <= c

F = [fd("student_id -> student_name dept_id"), fd("dept_id -> building"),
     fd("course_id -> title"), fd("student_id course_id -> grade")]
good1 = set("student_id student_name dept_id".split())
good2 = set("student_id course_id title grade building".split())
bad1  = set("dept_id grade".split())
bad2  = set("student_id student_name dept_id building course_id title".split())
print("split on student_id lossless:", lossless_binary(good1, good2, F))
print("split on dept_id lossless:   ", lossless_binary(bad1, bad2, F))

# Demonstrate the spurious tuples a lossy split creates
rows = [("Ava", "CS", 88), ("Ben", "CS", 72)]          # (name, dept, grade)
p1 = {(d, g) for n, d, g in rows}                       # (dept, grade)
p2 = {(n, d) for n, d, g in rows}                       # (name, dept)
rejoined = {(n, d, g) for n, d in p2 for d2, g in p1 if d == d2}
print("original rows:", len(rows), " rows after rejoin:", len(rejoined), sorted(rejoined))

split on student_id lossless: True
split on dept_id lossless:    False
original rows: 2  rows after rejoin: 4 [('Ava', 'CS', 72), ('Ava', 'CS', 88), ('Ben', 'CS', 72), ('Ben', 'CS', 88)]

The BCNF decomposition algorithm

To bring a relation into BCNF, find an FD \(X \to Y\) that violates BCNF (X is not a superkey), and split R into \(R_1 = X^{+}\) restricted to R, the attributes X determines, and \(R_2 = R - (X^{+} - X)\), which keeps X so the pieces can be rejoined. Because the shared attributes X are a key of \(R_1\), the split is lossless. Repeat on each piece until all are in BCNF. Different choices of violating FD can give different, equally valid results.

from itertools import combinations

def closure(attrs, fds):
    """Attribute closure: every attribute determined by attrs under fds."""
    result = set(attrs)
    changed = True
    while changed:
        changed = False
        for lhs, rhs in fds:
            if lhs <= result and not rhs <= result:
                result |= rhs
                changed = True
    return result

def candidate_keys(R, fds):
    keys = []
    for k in range(1, len(R) + 1):
        for combo in combinations(sorted(R), k):
            s = set(combo)
            if closure(s, fds) == R and not any(key <= s for key in keys):
                keys.append(s)
    return keys

def fd(s):  # "A B -> C" to (frozenset, frozenset)
    l, r = s.split("->")
    return frozenset(l.split()), frozenset(r.split())

def project(fds, S):
    """FDs implied on attribute subset S (via closures of subsets of S)."""
    out = []
    for k in range(1, len(S)):
        for combo in combinations(sorted(S), k):
            X = set(combo)
            Y = (closure(X, fds) & S) - X
            if Y:
                out.append((frozenset(X), frozenset(Y)))
    return out

def bcnf(R, fds):
    for X, Y in project(fds, R):
        if not closure(X, fds) >= R:                 # X is not a superkey of R: violation
            R1 = closure(X, fds) & R
            R2 = R - (R1 - X)
            return bcnf(R1, fds) + bcnf(R2, fds)
    return [R]

R = set("student_id student_name dept_id building course_id title grade".split())
F = [fd("student_id -> student_name dept_id"), fd("dept_id -> building"),
     fd("course_id -> title"), fd("student_id course_id -> grade")]
for piece in sorted(bcnf(R, F), key=lambda s: sorted(s)):
    keys = candidate_keys(piece, project(F, piece))
    print(sorted(piece), " key:", [sorted(k) for k in keys])

['building', 'dept_id']  key: [['dept_id']]
['course_id', 'grade', 'student_id']  key: [['course_id', 'student_id']]
['course_id', 'title']  key: [['course_id']]
['dept_id', 'student_id', 'student_name']  key: [['student_id']]

The algorithm separates out the department and its building, the student's name and department, and the course title, leaving an enrollment table keyed by student and course that holds only the grade. Each fact now lives in one place: the CS building appears once, Ava's name once, each title once. All three anomalies disappear. These are, not by coincidence, the department, student, course and enrollment tables of the college database.

When BCNF loses dependencies, and 3NF

BCNF decomposition is always lossless but not always dependency preserving. The classic example is R(student, course, instructor) with the rules that each instructor teaches only one course, instructor \(\to\) course, and that for each course a student has one instructor, {student, course} \(\to\) instructor. The candidate keys are {student, course} and {student, instructor}. The FD instructor \(\to\) course violates BCNF, because instructor is not a superkey, so BCNF splits R into (instructor, course) and (student, instructor). Now the rule {student, course} \(\to\) instructor spans both tables and can be checked only by joining them. R is, however, in 3NF, because course is prime (part of the key {student, course}). Designers then choose between BCNF with an application-level check, or 3NF with a little redundancy and full enforcement by keys.

3NF synthesis is an algorithm that always produces a lossless, dependency-preserving 3NF decomposition: compute a minimal cover of the FDs (single attributes on the right, no redundant attributes on the left, no redundant FDs), create one relation for each FD's attributes, add a relation containing a candidate key if none of them does, and remove relations contained in others. In practice, a design that came from a careful ER model usually needs only small adjustments to reach BCNF or 3NF.

Beyond BCNF, and when to denormalize

FDs cannot capture every kind of redundancy. If an instructor teaches several courses and independently speaks several languages, a table instructor_course_language stores every combination, repeating each course for every language. This comes from a multivalued dependency, and fourth normal form (4NF) removes it by splitting into (instructor, course) and (instructor, language). Fifth normal form handles still rarer join dependencies. A design built from a clean ER model, with multivalued attributes in their own tables, usually satisfies 4NF automatically.

Normalization optimizes for correct updates. Sometimes a design deliberately accepts redundancy for read performance, called denormalization: storing a running total of copies on loan in the title table, or a precomputed report table, avoids repeated joins and aggregations. Data warehouses use denormalized star schemas on purpose because they are loaded in batches and mostly read. The rule of thumb is to normalize first, measure, and denormalize only specific, measured hot spots, keeping the redundant copy consistent with triggers, scheduled jobs or materialized views, and documenting why.