BCNF and Lossless Decomposition

Why go beyond 3NF?

3NF removes most redundancy, but not all. Take R(Student, Course, Teacher): each student takes a course from one teacher (SC → T), and each teacher teaches only one course (T → C).

“Rao teaches DBMS” is stored once for every student Rao has. If Rao switches to OS, many rows must change (an update anomaly). If Meera leaves, we lose the fact that Iyer teaches DBMS (a deletion anomaly). R is in 3NF, because C is part of the key SC. But the root problem is that T → C holds while T is not a key.

The definition

A relation is in BCNF (Boyce–Codd normal form) if for every non-trivial functional dependency X → Y that holds in it, X is a superkey.

The decomposition algorithm

1. Find a relation Ri and a set X ⊂ Ri such that X determines more of Ri but isn’t a superkey of Ri. Use attribute closure: X⁺ ∩ Ri ≠ X and X⁺ ∩ Ri ≠ Ri.
2. Split Ri into R1 = X⁺ ∩ Ri (X and everything it determines) and R2 = Ri − (X⁺ − X) (the rest, keeping X so the parts can be joined).
3. Repeat until no part breaks BCNF.

Every split is lossless. R1 and R2 share exactly X, and X determines all of R1. By the binary test (R1 ∩ R2 → R1), joining them gives back exactly the original rows, with no extra “spurious” ones.

Worked examples

R(S, C, T), F = {SC → T, T → C}. Keys: SC and ST. T⁺ = TC, so T → C breaks BCNF.

• Split on T: (C, T) and (S, T). Both have two attributes, so both are in BCNF.
• But SC → T is lost. No single part contains S, C and T, so the database can’t check it without a join. This is the classic case where BCNF costs a dependency.

R(A, B, C, D, E), F = {A → B, B → C, C → D, D → E}. Key: A.

Result: (A, B), (B, C), (C, D), (D, E), and every FD is preserved.

Code

from itertools import combinations

def closure(X, F):
    c = set(X)
    changed = True
    while changed:
        changed = False
        for L, R in F:
            if L <= c and not R <= c:
                c |= R
                changed = True
    return c

def violation(Ri, F):
    """Smallest X in Ri that determines more of Ri but is not a superkey of Ri."""
    for size in range(1, len(Ri)):
        for X in combinations(sorted(Ri), size):
            got = closure(X, F) & Ri
            if got != set(X) and got != Ri:
                return set(X), got
    return None

def bcnf(Ri, F):
    v = violation(Ri, F)
    if not v:
        return [Ri]
    X, got = v
    return bcnf(got, F) + bcnf((Ri - got) | X, F)   # lossless: the parts share X, and X -> got

def preserved(L, R, F, parts):
    """Can L -> R be checked using only the parts (closure through projections)?"""
    got = set(L)
    while True:
        add = set().union(*(closure(got & P, F) & P for P in parts)) - got
        if not add:
            return R <= got
        got |= add

F = [({'S', 'C'}, {'T'}), ({'T'}, {'C'})]
parts = bcnf({'S', 'C', 'T'}, F)
print([''.join(sorted(p)) for p in parts])          # ['CT', 'ST']
print([preserved(L, R, F, parts) for L, R in F])    # [False, True]

Choosing between 3NF and BCNF

• If BCNF keeps every dependency, use BCNF.
• If it would lose an important dependency (like SC → T above), many designers stop at 3NF, which always keeps every dependency, and accept a little redundancy.
• Different choices of violating FD can give different BCNF decompositions. All of them are correct, and some preserve more dependencies than others.

Common mistakes

• Checking only the given FDs inside the parts. A part can break BCNF through a derived FD. Use closures.
• Forgetting to keep X in both parts. Without the shared X the join is lossy and invents rows.
• Thinking BCNF always keeps every dependency. It doesn’t, as the S, C, T example shows.
• Mixing up superkey and candidate key. X only has to be a superkey (it may contain extra attributes).