Functional Dependency — Closure Complexity, Minimal Cover, Finding All Candidate Keys & Real Enforcement (Deep Dive)

A functional dependency is not really "known" until you can compute with it: derive every dependency it implies (closure), shrink the set that describes it (minimal cover), enumerate every key it permits (not just check one), and decide who actually stops a bad write at runtime — the answer to that last one is almost never "the FD itself."

1. Partial vs full functional dependency — what 2NF actually removes

A dependency is partial when a non-key attribute depends on only part of a composite candidate key; it is full when the non-key attribute needs every attribute of the key and would break if any one were dropped. 2NF is exactly the rule "eliminate partial dependencies" — nothing more.

Worked example. Consider Enrollment(Student_ID, Course_ID, Student_Name, Course_Name, Grade) with candidate key {Student_ID, Course_ID}.

Student_Name would be identical on every row for that student regardless of which course they took — Course_ID is dead weight in that determinant, so the dependency is partial. Grade, by contrast, cannot be pinned down by Student_ID alone (a student has many grades) or Course_ID alone (a course has many students' grades) — it genuinely needs the pair, so it is full. 2NF says: split off every partial dependency into its own table keyed on the sub-key it actually depends on (Student_ID → Student table; Course_ID → Course table), leaving only full dependencies on the remaining composite key. This is the precise mechanism, not a rule of thumb — you find it by asking, for each non-key attribute, "does removing one attribute from the key still determine this?"

2. Attribute closure: the algorithm and its complexity

The closure X+ of an attribute set X under a dependency set F is computed by a fixpoint: start with X, then repeatedly scan every FD in F and add its right-hand side whenever its left-hand side is already contained in the running result — repeat full scans until one entire pass adds nothing new.

result := X
repeat
  changed := false
  for each FD (A -> B) in F:
    if A subset-of result and B not subset-of result:
      result := result union B
      changed := true
until not changed
return result

Traced example. Let R have attributes A,B,C,D,E,F,G,H,I,J and F = {A→B, A→C, CG→H, CG→I, B→H}. Compute (AG)+:

1. result = {A, G}
2. A→B: A ⊆ result, B ∉ result → add B. result = {A,B,G}
3. A→C: add C. result = {A,B,C,G}
4. CG→H: CG ⊆ result now (C and G both present) → add H. result = {A,B,C,G,H}
5. CG→I: add I. result = {A,B,C,G,H,I}
6. B→H: H already in result → no change
7. Full rescan produces nothing new → fixpoint. (AG)+ = {A,B,C,G,H,I}, not the full relation, so AG is not a superkey.

Complexity of the naive version. Each full pass costs O(a·f): for every one of the f dependencies, checking "is its LHS ⊆ result" costs O(a) with a hash-set/bitset over the a attributes. Since each pass that changes anything adds at least one new attribute, there can be at most a passes before it must stop — so the naive fixpoint is bounded by O(a²·f) in the worst case. That is fine for exam-sized schemas and even most production schemas, but it is quadratic in the attribute count, and it matters once tooling (schema linters, normalization-synthesis engines, migration analyzers) computes closures over hundreds of FDs repeatedly.

The linear-time alternative (Beeri & Bernstein, 1979). A closure can be computed in time linear in the size of F — roughly O(a+f) — by never rescanning FDs that can't possibly fire yet. Build an index from each attribute to the list of FDs where it appears on the left-hand side, and give every FD a counter equal to the size of its (still-unsatisfied) left-hand side. Push the starting attributes onto a queue; whenever an attribute is dequeued, decrement the counter of every FD indexed under it; the moment an FD's counter hits zero its entire left side is now in the closure, so its right-hand attributes get added and queued too. Every attribute and every FD is touched a bounded number of times — no full rescans, no wasted work re-checking dependencies whose LHS hasn't changed. This is the version production-grade dependency solvers actually use; the fixpoint pseudocode above is the one worth tracing by hand because it makes the "why" visible.

3. Minimal (canonical) cover

A minimal cover of F is an equivalent FD set (same F+) that is "as small as possible": every right-hand side is a single attribute, no left-hand side attribute is extraneous (droppable without changing the closure), and no whole FD is redundant (derivable from the others). It matters because 3NF-synthesis algorithms are defined on a minimal cover — feed them the original bloated F and they can produce wrong or non-minimal decompositions.

Algorithm.

1. Singleton RHS: split every A → B₁B₂...Bₙ into separate FDs A → B₁, A → B₂, ..., A → Bₙ (valid by the decomposition rule).
2. Remove extraneous LHS attributes: for every FD XY → Z with |X∪Y| > 1, test whether Y is extraneous by computing X+ using the rest of the set (including the reduced form, excluding this FD's need for Y); if Z ∈ X+ already, Y was never needed — drop it from the LHS.
3. Remove redundant FDs: for every remaining FD X → A, compute X+ using all other FDs in the set; if A ∈ X+, this FD is implied by the rest — delete it entirely.

Worked example. R(A,B,C,D), starting set F = {A → BC, B → C, AB → D, A → D}.

Step 1 — singleton RHS: {A→B, A→C, B→C, AB→D, A→D}.

Step 2 — extraneous LHS: check AB→D — is B extraneous? Compute A+ using the other FDs {A→B, A→C, B→C, A→D}: A→B adds B, A→C adds C, B→C no-op, A→D adds D → A+ = {A,B,C,D}. Since D ∈ A+ without needing B on the LHS, B is extraneous — AB→D collapses to A→D, which is already present, so it is simply dropped as a duplicate. Remaining: {A→B, A→C, B→C, A→D}.

Step 3 — redundant FDs: is A→C redundant? Compute A+ using only {A→B, B→C, A→D}: A→B adds B, B→C adds C — C is reached via A→B→C already, so A→C is redundant, remove it. Remaining: {A→B, B→C, A→D}. Now recheck the survivors: A→D using only {A→B, B→C} gives A+={A,B,C}, D not reached — keep. A→B using only {B→C, A→D} gives A+={A,D}, B not reached — keep. B→C using only {A→B, A→D} gives B+={B} (B is on no other LHS), C not reached — keep.

Minimal cover: {A → B, B → C, A → D} — three FDs, singleton right-hand sides, nothing extraneous, nothing redundant.

Minimal covers are not unique — a different removal order can land on a different (but equivalent) minimal set. What is invariant is the closure F+ they produce, which is exactly the equivalence test in §5.

4. Finding ALL candidate keys — not just verifying one

Given a single attribute set, checking whether it's a key is one closure computation. Finding every candidate key of a relation is a different, harder question — most engineers only ever practice the first.

Systematic method:

1. Classify every attribute by where it appears in F: L-only (appears on some left-hand side, never on any right-hand side), R-only (appears on some right-hand side, never on any left-hand side), or both.
2. Every L-only attribute must be in every candidate key — nothing can ever derive it, so it has to be given directly.
3. Every R-only attribute can be pruned from consideration as a determinant — adding it to a candidate set never helps derive anything new (it only ever gets derived, it never derives), so it is never needed as a determinant in a minimal key. (This is a pruning heuristic, not a proof by itself — always confirm the final answer with a closure check.)
4. Start from the L-only attributes (call this the "core"). If core+ = all attributes, the core itself is the only candidate key. Otherwise, extend the core with attributes from the "both" category, one at a time or in combination, computing closure each time, until you find sets whose closure is everything — then verify minimality by checking no proper subset also closes to everything.

Trace 1 — the core alone suffices. Reusing the minimal cover result R(A,B,C,D) with F+ ≡ {A→B, B→C, A→D}: A never appears on any right-hand side (L-only), so A must be in every key. Compute A+ = {A,B,C,D} = every attribute. A alone is already a superkey, and a single attribute is trivially minimal — {A} is the only candidate key.

Trace 2 — two candidate keys, none forced by an L-only attribute. R(A,B,C), F = {A→B, B→A, B→C}. Classify: A appears on both sides (LHS of A→B, RHS of B→A); B appears on both sides too (LHS of B→A, B→C; RHS of A→B); C appears only on the RHS of B→C — R-only, prune it from candidacy. No attribute is L-only, so nothing is forced automatically; test the "both" attributes as singleton candidates:

• A+: A→B adds B, B→A no-op, B→C adds C → A+ = {A,B,C} = R. A is a candidate key.
• B+: B→A adds A, B→C adds C, A→B no-op → B+ = {A,B,C} = R. B is a candidate key.
• C+: C is on no LHS at all → C+ = {C} ≠ R. Confirms the R-only pruning was correct — C is never a key.

Result: {A} and {B} are both candidate keys — because A and B mutually determine each other, either one alone reaches everything. Hand-verifying just "is {A} a key?" would have missed {B} entirely; the enumeration procedure is what guarantees completeness.

5. Armstrong's axioms: soundness, completeness, and FD-set equivalence

The three axioms (Armstrong, 1974):

• Reflexivity: if Y ⊆ X, then X → Y.
• Augmentation: if X → Y, then XZ → YZ for any Z.
• Transitivity: if X → Y and Y → Z, then X → Z.

Soundness is the easy direction: every FD these rules produce is guaranteed true (no rule can manufacture a false dependency) — that's a one-line semantic check per rule, shown on the running Enrollment-table trace elsewhere in this guide.

Completeness is the deep claim, and it is not "union/decomposition/pseudo-transitivity are derivable." Those three are convenience rules built from the axioms — useful, but a side effect. Completeness is Armstrong's actual theorem: these three primitive axioms, applied repeatedly in any combination, are sufficient to derive every single FD in F+ — the entire (possibly huge) set of dependencies logically implied by F — with no exceptions requiring an extra rule. Nothing true about F escapes reach of just these three. This is exactly why "compute the closure X+" and "apply IR1–IR3 until nothing new appears" are the same computation viewed two ways: the closure algorithm in §2 is completeness, executed.

Worked derivation — proving the Union rule (X→Y, X→Z ⟹ X→YZ) using only the three axioms:

1. X → Y (given)
2. X → Z (given)
3. From (1), augment both sides by X: X·X → Y·X, i.e. X → XY (using reflexivity's consequence that X∪X = X).
4. From (2), augment both sides by Y: XY → YZ.
5. From (3) and (4), by transitivity: X → YZ. ∎

Every "shortcut" rule you rely on daily (Union, Decomposition, Pseudo-transitivity) has a proof of exactly this shape — a handful of augmentation and transitivity steps chained together. That chaining, run automatically and exhaustively, is the closure algorithm.

FD-set equivalence (F+ = G+): two dependency sets are equivalent iff each is derivable from the other — F ≡ G iff F ⊆ G+ and G ⊆ F+. Mechanically: for every FD X→Y in F, compute X+ under G and check Y ⊆ X+_G (and symmetrically for every FD in G against F). Tiny example: F = {A→B, B→C, A→C}, G = {A→B, B→C}. G ⊆ F trivially (literal subset). For F ⊆ G+: A→B and B→C are already in G; check A→C — compute A+ under G: A→B adds B, B→C adds C, so A+_G = {A,B,C} ⊇ {C}, meaning A→C is implied by G. So F ⊆ G+ too, hence F ≡ G — G is in fact a minimal cover of F (A→C was the redundant FD).

6. Practical enforcement — the #1 senior FD question

An RDBMS enforces only the functional dependencies that are backed by a declared key or UNIQUE constraint. A PRIMARY KEY or UNIQUE index on column set X is, mechanically, the database refusing to store two rows that agree on X — which is precisely the enforcement of the FD "X → every other column in that table." Nothing else in standard SQL declares an arbitrary functional dependency between two ordinary (non-key) columns.

Concrete failure case. Employee(Emp_ID PK, Emp_Name, Dept_ID, Dept_Name, Building) has the real dependency Dept_ID → {Dept_Name, Building} — but Dept_ID is not a key of Employee (Emp_ID is). Nothing stops two Employee rows both holding Dept_ID = 'D01' from disagreeing on Dept_Name — that's exactly the update anomaly normalization exists to prevent, and the database's constraint system does nothing about it on its own, because the FD's determinant isn't unique-indexed anywhere.

Judgment layer — normalize vs. trigger, the actual decision a senior engineer makes:

This is also why "just add a CHECK constraint for the FD" is not a real option in standard SQL: a CHECK constraint's predicate is evaluated against a single row in isolation — it cannot reference other rows of the same table (or another table) to confirm "every other row with this Dept_ID agrees." There is no DDL clause of the form ADD CONSTRAINT FD (Dept_ID -> Dept_Name) in SQL, which is precisely why interview answers that reach for "declare the dependency as a constraint" are describing something that doesn't exist — the only constraint that enforces an FD is a uniqueness constraint on its determinant.

Pitfalls

• Treating naive closure as "free." O(a²·f) is invisible on a 5-attribute homework example and very visible on a schema-analysis tool churning through hundreds of FDs across a real schema — that's when the linear-time approach (§2) earns its complexity.
• Reducing LHS attributes in the wrong order during minimal cover. Extraneous-LHS removal must happen before redundant-whole-FD removal — an FD with a bloated (not-yet-reduced) LHS can look "non-redundant" only because of the extra baggage, hiding the fact that its reduced form is a duplicate of something else.
• Assuming there is one true minimal cover. Different, equally valid removal orders can land on different (but F+-equivalent) minimal sets — don't hard-code "the" answer; check equivalence via closures (§5), not surface syntax.
• Trusting the R-only-attribute heuristic as a proof. It's a correct pruning shortcut for search space, not a substitute for the final closure check — always confirm a candidate set's closure equals every attribute before calling it a key.
• Reaching for a CHECK constraint to "declare" a cross-row functional dependency. Standard CHECK constraints are single-row scalar predicates; they cannot see other rows, so this is a category error, not just an awkward syntax problem.
• Confusing "a candidate key exists" with "that's the PK." A relation can have several candidate keys (as in Trace 2, §4); which one becomes PRIMARY KEY is a design decision (shortest, most stable, most human-friendly to reference), not something the algorithm chooses for you.

Takeaways

1. Attribute closure is the one computational primitive underneath almost everything else here — candidate keys, minimal cover, FD-set equivalence, and normal-form checks all reduce to "compute a closure, check membership."
2. A minimal cover is not unique, but it is always equivalent (same F+) to the original set, and it — not the raw, redundant F — is the correct input to 3NF-synthesis algorithms.
3. Finding all candidate keys needs the enumeration procedure (force in L-only attributes, prune R-only attributes, closure-test the rest); manually verifying one candidate never tells you whether another one exists.
4. An RDBMS auto-enforces a functional dependency only when its determinant is a declared key (PK/UNIQUE); every other true FD is enforced by normalizing it into a table where it becomes key-backed, or by a strictly weaker trigger — never by declaring the FD itself, because SQL has no such clause.

Related pages

• Second Normal Form (2NF) — the partial-dependency elimination rule traced in §1.
• Normalization — 3NF vs BCNF Dependency-Preservation, Lossless Join, Synthesis & 5NF (Deep Dive) — the synthesis algorithm that consumes the minimal cover computed in §3.
• Relational Model — Keys, FK Integrity, NULL Traps & Modeling Judgment (Deep Dive) — how the PK/UNIQUE-backed enforcement in §6 fits into key and FK design more broadly.
• Data Modeling — The Denormalization Decision & Write-vs-Read Cost Framing (Deep Dive) — the update/insert/delete anomalies that an unenforced, non-key FD like Dept_ID→Dept_Name produces.