Normalization

Normalization splits a badly designed table into smaller ones so that each fact is stored once. The normal forms are a ladder of tests, each stricter than the last, based on the functional dependencies of the previous lesson.

Why: update anomalies

Consider one big table:

with FDs roll → name, dept and dept → hod. The fact "the HOD of CSE is Dr. Rao" is stored once per CSE student, which causes three anomalies:

• Update anomaly: when CSE gets a new HOD, every CSE row must change; missing one leaves the data inconsistent.
• Insertion anomaly: a new department with no students yet cannot be recorded (roll, the key, would be NULL).
• Deletion anomaly: deleting Ravi, the only ECE student, also deletes the fact that Dr. Sen heads ECE.

Splitting it into Student(roll, name, dept) and Dept(dept, hod) removes all three.

The normal forms

Recall: a prime attribute belongs to some candidate key; the others are non-prime. For each test, look at every non-trivial FD X → A (with a single attribute on the right):

2NF only matters when a candidate key has more than one attribute: if every key is a single attribute, a 1NF relation is automatically in 2NF.

3NF can also be phrased as: no non-prime attribute is transitively dependent on a key (key → X → A with X not a superkey). BCNF is 3NF without the "A is prime" escape clause.

Finding the highest normal form

The procedure: find all candidate keys, mark prime attributes, then check each FD against BCNF, 3NF and 2NF in turn.

The same check as a program:

from itertools import combinations

def closure(attrs, fds):
    result = set(attrs)
    while True:
        new = result | {a for lhs, rhs in fds if set(lhs) <= result for a in rhs}
        if new == result:
            return result
        result = new

def highest_nf(relation, fds):
    keys = []
    for size in range(1, len(relation) + 1):
        for c in combinations(relation, size):
            if closure(c, fds) == set(relation) and not any(set(k) <= set(c) for k in keys):
                keys.append(set(c))
    prime = set().union(*keys)
    single = [(set(l), a) for l, r in fds for a in r if a not in l]
    superkey = lambda x: closure(x, fds) == set(relation)
    if all(superkey(l) for l, a in single):
        return "BCNF"
    if all(superkey(l) or a in prime for l, a in single):
        return "3NF"
    if all(a in prime or not any(l < k for k in keys) for l, a in single):
        return "2NF"
    return "1NF"

print(highest_nf("ABCD", [("AB", "C"), ("B", "D")]))
print(highest_nf("ABCD", [("AB", "C"), ("C", "D")]))
print(highest_nf("ABCD", [("AB", "CD"), ("C", "A")]))
print(highest_nf("ABCDEF", [("A", "BCDEF"), ("BC", "ADEF"), ("DEF", "ABC")]))

1NF
2NF
3NF
BCNF

Properties of a decomposition

Splitting R into R₁, R₂, … must not lose information. Two properties matter:

Lossless join. Joining the pieces must give back exactly R, with no extra (spurious) tuples. For a split into two, R₁ and R₂, the test is:

Here is a lossy split. R(A, B, C) is split on B, but B is a key of neither piece, so the join produces tuples that were never in R:

CREATE TABLE r (a INTEGER, b TEXT, c TEXT);
INSERT INTO r VALUES (1, 'x', 'p'), (2, 'x', 'q'), (3, 'y', 'p');
CREATE TABLE r1 AS SELECT DISTINCT a, b FROM r;
CREATE TABLE r2 AS SELECT DISTINCT b, c FROM r;
SELECT COUNT(*) AS original FROM r;
SELECT * FROM r1 NATURAL JOIN r2 ORDER BY a, c;

original
--------
3

a  b  c
-  -  -
1  x  p
1  x  q
2  x  p
2  x  q
3  y  p

Two spurious tuples, (1, x, q) and (2, x, p), appear. "Lossy" means we lose the information of which tuples were real, even though the result has more rows.

Dependency preservation. Every FD of F should be checkable inside a single piece, so the DBMS does not need a join to enforce it. Formally, the union of the FDs that hold on each piece (their projections) must be equivalent to F.

3NF versus BCNF

The standard counterexample: R(A, B, C) with F = { AB → C, C → B }. Keys are AB and AC, so R is in 3NF but not BCNF (C → B, C not a superkey). The BCNF decomposition is R₁(C, B) and R₂(A, C). It is lossless (the common attribute C is a key of R₁), but AB → C can no longer be checked within one table. Any BCNF decomposition of this R loses that FD, so designers often stop at 3NF.

3NF synthesis algorithm: compute a minimal cover, make one table for each FD X → A (merging FDs with the same left side), and if no table contains a candidate key, add one table that is a candidate key. BCNF decomposition: while some table has an FD X → Y with X not a superkey, split it into (X ∪ Y) and (R − Y).

Multivalued dependencies and 4NF

Suppose a teacher teaches several subjects and speaks several languages, independently, stored as Teacher(name, subject, language). There are no non-trivial FDs, so the table is in BCNF, yet every subject is repeated for every language. This is a multivalued dependency (MVD), written name →→ subject (and so name →→ language): the set of subjects of a teacher does not depend on the language.

4NF: for every non-trivial MVD X →→ Y, X is a superkey. The fix is the same as before: split into (name, subject) and (name, language). Every FD is also an MVD, so 4NF implies BCNF.

Practice questions

CREATE TABLE r (a INTEGER, b TEXT, c TEXT);
INSERT INTO r VALUES (1, 'p', 'x'), (2, 'p', 'y'), (3, 'q', 'x'), (4, 'q', 'y'), (5, 'r', 'x');
SELECT COUNT(*) FROM (SELECT DISTINCT a, b FROM r) NATURAL JOIN (SELECT DISTINCT b, c FROM r);