Part 2 · 2 chapters · ~12 min

Functional Dependencies and Normalisation

Functional dependencies from the domain, Armstrong's axioms and derived rules, attribute closure and computing candidate keys mechanically, minimal covers, 1NF through BCNF with the anomaly each removes, lossless-join and dependency-preserving decomposition, multivalued dependencies and 4NF, join dependencies and 5NF, domain-key normal form, 6NF for temporal data, and when to denormalise with a cost model.

Closure, keys and BCNF, computed

code

const closure = (X, F) => { const c = new Set(X); let changed = true;
  while (changed) { changed = false;
    for (const [l, r] of F) if (l.every(a => c.has(a)) && r.some(a => !c.has(a))) { r.forEach(a => c.add(a)); changed = true; } }
  return [...c].sort(); };
// Armstrong's axioms (reflexivity, augmentation, transitivity) justify every step of this loop

const F = [[['T'], ['A']], [['A'], ['O', 'B']], [['B'], ['M']]];
closure(['A'], F)            // ABMO
candidateKeys(U, F)          // ['T']
bcnfViolations(U, F)         // ['A→OB', 'B→M']

// the classic case where BCNF and dependency preservation conflict: Student, Course, Professor
// SC → P (a student takes a course from one professor), P → C (a professor teaches one course)
candidateKeys(['S','C','P'], F2)    // ['CS', 'PS']
bcnfViolations(['S','C','P'], F2)   // ['P→C']: in 3NF (C is part of a key) but not BCNF
// decomposing to BCNF (P,C) + (S,P) loses SC → P, which can then only be enforced across tables

FUNCTIONAL DEPENDENCIES, ANALYSED

Transfer(T id, A account, O owner, B branch, M manager): T→A, A→OB, B→M

swipe the figure sideways, or tap expand for full screen

1/4

dependencies

X → Y means tuples agreeing on X agree on Y. They come from the domain: an account has one owner and one branch; a branch has one manager.

facts about the domainnot about current data

Normal forms and their anomalies

form	rule	anomaly removed
1NF	atomic values, no repeating groups	querying inside lists ("phone1, phone2, phone3")
2NF	no non-key attribute depends on part of a composite key	order_items(order_id, product_id, product_name): name repeated per order
3NF	no non-key attribute depends on another non-key attribute	transitive facts (branch → manager) repeated per row
BCNF	every determinant is a superkey	remaining anomalies where key attributes depend on non-keys
4NF	no non-trivial multivalued dependencies	independent lists (skills, languages) multiplied together
5NF	every join dependency implied by keys	facts only reconstructible by three-way joins
6NF	at most one non-key attribute per table	temporal data: each attribute changes on its own timeline

Lossless join: splitting R into R1 and R2 is lossless when the shared attributes are a key of R1 or R2; otherwise joining back invents spurious rows. Domain-key normal form (every constraint follows from domains and keys) is the theoretical ideal with no general algorithm. When to denormalise: when a measured read path joins the same tables on every request and the duplicated data changes rarely; write down the cost (extra writes, consistency jobs, reconciliation) next to the benefit (fewer joins, lower p99), and keep the normalised source of truth (ledger postings) untouched.