Functional Dependencies
Imagine a `STUDENT` relation storing `(student_id, name, major, advisor_office)`. Every advisor sits in exactly one office. If a clerk updates `advisor_office` for one row but not another, problems arise. The other row shares the same advisor. The database now contradicts itself. One advisor apparently sits in two offices. Nothing in the raw definition of a Relation prevents this. A relation is just a set of tuples over a schema. What is missing is a formal way to state something. The office is determined by the advisor. So any two tuples agreeing on advisor must agree on office. That statement is a functional dependency (FD). Functional dependencies are the semantic glue. They connect a table's informal "meaning" to formal design-flaw checks. A database schema on its own is just a list of attribute names and types. It says nothing about which values must coincide. FDs let a designer encode business rules as precise logical statements. Examples include "an SSN determines a name" or "a course and semester determine an instructor" or "a product ID determines its price." An algorithm, not intuition, then decides whether a schema is well designed. This matters in real systems for two reasons. Badly designed schemas silently corrupt data through insertion, deletion, and update anomalies. Also, query optimizers exploit FDs to guarantee correct, duplicate-free joins. Every relational database course eventually reduces one question to FDs. That question is: "is this schema good?" It becomes: does it satisfy Boyce-Codd Normal Form or Third Normal Form? This is judged with respect to a given set of dependencies. Answering it requires computing closures of attribute sets. It also requires reasoning soundly and completely with Armstrong's axioms. This article gives you several key tools. First, the precise definition of an FD. Second, the closure algorithm used to test whether one FD is implied by others. Third, Armstrong's axioms and why they are sound and complete. Fourth, the standard technique for finding all candidate keys implied by a set of FDs. It is the logical foundation beneath every later discussion of Normalization Motivation and Anomalies, 2NF and 3NF, Boyce-Codd Normal Form, and Lossless-Join Decomposition.
- A functional dependency `X → Y` means: any two tuples agreeing on all attributes in `X` must agree on all attributes in `Y`.
- The attribute closure `X⁺` — the set of all attributes functionally determined by `X` — is the workhorse computation of FD theory.
- Armstrong's axioms (reflexivity, augmentation, transitivity) are sound and complete: they derive exactly the FDs logically implied by a given set.
- Three derived rules — union, decomposition, and pseudotransitivity — make manual and algorithmic reasoning far faster.
- A candidate key is a minimal attribute set whose closure is the entire schema; closure computation makes finding all keys mechanical.
- FDs are the formal prerequisite for Normalization Motivation and Anomalies, 2NF and 3NF, and Boyce-Codd Normal Form.
A functional dependency `X → Y` is a promise that `X`'s value pins down `Y`'s value — and closures let a computer, rather than a human, check every consequence of that promise.
The idea
A functional dependency (FD) over a relation schema `R` is a statement `X → Y`, where `X` and `Y` are subsets of the attributes of `R`. It asserts a constraint on every legal instance (every table conforming to the business rules) of `R`: for any two tuples `t1` and `t2` in the relation, if `t1[X] = t2[X]` (they agree on every attribute in `X`), then `t1[Y] = t2[Y]` (they must also agree on every attribute in `Y`). We say `X` functionally determines `Y`, or `Y` is functionally dependent on `X`. The left side `X` is called the determinant. FDs are not derived from any single table instance — a small sample table can satisfy an FD by coincidence without the FD being a genuine business rule, and a real rule can fail to be violated in a small sample purely by luck. An FD is a statement about the intended meaning of the data, supplied by whoever understands the domain (a database designer, a business analyst), and it constrains every legal instance, present or future. This is exactly analogous to a Superkey or Candidate Key constraint: `X → R` (X determines every attribute of R) is precisely the condition for `X` to be a superkey. Two FDs deserve special vocabulary. An FD `X → Y` is trivial if `Y ⊆ X` — it holds in every relation instance regardless of semantics, because a tuple trivially agrees with itself on any subset of `X`. It is nontrivial if `Y ⊄ X`, and completely nontrivial if `X ∩ Y = ∅`. Design theory cares almost exclusively about nontrivial FDs, since trivial ones carry no information. Given a set `F` of FDs asserted by the designer, the closure of F, written `F⁺`, is the set of all FDs logically implied by `F` — including FDs never explicitly written down. Testing schema quality, in every later normal-form definition, reduces to asking membership questions in `F⁺`.
How it works
The central computational tool is the attribute closure of a set of attributes `X` with respect to `F`, written `X⁺`: the set of all attributes `A` such that `X → A` is implied by `F`. Once you can compute `X⁺`, you can answer almost every question FD theory asks:
- FD membership: does `F` imply `X → Y`? Compute `X⁺`; the answer is yes iff `Y ⊆ X⁺`.
- Superkey test: is `X` a superkey of `R`? Compute `X⁺`; the answer is yes iff `X⁺` contains every attribute of `R`.
- Candidate key test: is `X` a candidate (minimal) key? `X` is a superkey, and no proper subset of `X` is.
- Equivalence of FD sets: do `F` and `G` imply the same FDs? Check that every FD in `F` is implied by `G` and vice versa, using the membership test above.
The closure algorithm. Start with `result = X`. Repeatedly scan the FDs in `F`; whenever you find some `V → W` with `V ⊆ result`, add `W` to `result`. Stop when a full pass adds nothing new. ``` function ATTRIBUTE-CLOSURE(X, F): result ← X // start with the given attributes changed ← true while changed: changed ← false for each FD (V → W) in F: if V ⊆ result and W ⊄ result: result ← result ∪ W changed ← true return result ``` ``` function IS-SUPERKEY(X, F, R): return ATTRIBUTE-CLOSURE(X, F) == attributes(R) function IS-CANDIDATE-KEY(X, F, R): if not IS-SUPERKEY(X, F, R): return false for each attribute A in X: if IS-SUPERKEY(X - {A}, F, R): return false // a proper subset already works — X not minimal return true function FIND-ALL-CANDIDATE-KEYS(F, R): keys ← ∅ for each subset S of attributes(R), in increasing size order: if IS-CANDIDATE-KEY(S, F, R): if no subset of S is already in keys: keys ← keys ∪ {S} return keys ``` The `FIND-ALL-CANDIDATE-KEYS` routine, tried by increasing subset size, is exponential in the worst case (there are `2ⁿ` subsets of `n` attributes), but in practice a much cheaper heuristic narrows the search dramatically before brute force is needed: any attribute that never appears on the right side of any FD must belong to every candidate key (nothing else can determine it), and any attribute that never appears on the left side need not be tried as part of a determinant.
Armstrong's axioms. Rather than run the fixed-point loop above by hand, designers reason with three inference rules, named for William Armstrong, who proved their soundness and completeness in 1974. 1. Reflexivity: if `Y ⊆ X`, then `X → Y`. (Trivial FDs always hold.) 2. Augmentation: if `X → Y`, then `XZ → YZ` for any attribute set `Z`. (Adding the same attributes to both sides preserves the dependency.) 3. Transitivity: if `X → Y` and `Y → Z`, then `X → Z`. From these three, several derived rules follow and are used constantly in practice:
- Union: if `X → Y` and `X → Z`, then `X → YZ`.
- Decomposition: if `X → YZ`, then `X → Y` and `X → Z`.
- Pseudotransitivity: if `X → Y` and `WY → Z`, then `WX → Z`.
Complexity & correctness
Complexity of `ATTRIBUTE-CLOSURE`. Let `n` be the number of attributes and `m` the number of FDs in `F`. The `result` set can grow at most `n` times before it stalls (each successful iteration adds at least one new attribute, and there are only `n` attributes total). In the worst naive implementation, each outer iteration rescans all `m` FDs, each check costing `O(n)` for the subset test, giving `O(n · m · n) = O(m n²)`. A single linear-time pass is possible with a smarter implementation: maintain, for every FD, a counter of "how many of its left-side attributes are still missing from `result`"; when an attribute is newly added to `result`, decrement the counters of every FD whose left side contains it, and fire any FD whose counter hits zero. This yields `O(Σ|Vᵢ| + Σ|Wᵢ|)` total work — linear in the size of `F` — using a work-queue of "newly added attributes" instead of full rescans. Either way, closure computation is polynomial, not exponential.
Why the algorithm is correct. The argument is a straightforward invariant proof. Invariant: at every point during execution, `result ⊆ X⁺` (soundness of what's been added) and every attribute logically forced into `X⁺` by FDs entirely "reachable" from `result` will eventually be added (progress toward completeness). Soundness: `result` starts as `X`, and trivially `X ⊆ X⁺` by reflexivity. Each step adds `W` only when some `V → W ∈ F` and `V ⊆ result ⊆ X⁺` already holds. Since `X⁺` is closed under `F` (it is, by definition, everything implied by `F` starting from `X`), and `V ⊆ X⁺` combined with `V → W ∈ F` forces `W ⊆ X⁺` by transitivity/definition, the new `result` remains a subset of `X⁺`. So `result ⊆ X⁺` is preserved by every step. Completeness: suppose, for contradiction, some attribute `A ∈ X⁺` is never added. Because `A ∈ X⁺`, there is a finite Armstrong-axiom derivation of `X → A` from `F`. Consider the shortest such derivation; it must, at its last transitive step, use some `V → W` with `A ∈ W` and `V` derivable from `X` using a strictly shorter derivation. By strong induction on derivation length, every attribute of `V` is eventually placed into `result` (shorter derivations correspond to earlier loop iterations), at which point `V ⊆ result` and the algorithm's scan will apply `V → W`, adding `A`. This contradicts the assumption, so no such `A` is missed. The loop terminates because `result` is bounded by `n` attributes and strictly grows or the loop exits — a classic fixed-point argument.
Soundness and completeness of Armstrong's axioms. Soundness (every FD derivable via the axioms actually holds in every legal instance) is checked directly against the tuple-agreement definition: reflexivity holds because two tuples trivially agree with themselves on any attribute subset; augmentation holds because adding identical attributes `Z` to both sides of an agreement preserves agreement; transitivity holds because if `t1[X]=t2[X]` forces `t1[Y]=t2[Y]`, and that in turn forces `t1[Z]=t2[Z]`, the composition is valid. Completeness (every FD that holds in all instances satisfying `F` is derivable from `F` via the axioms) is proved by contradiction using a canonical two-tuple counterexample relation: if `X → Y` is not derivable from `F`, one exhibits a two-row relation, agreeing exactly on `X⁺` and differing everywhere else, that satisfies every FD in `F` yet violates `X → Y` — proving `X → Y` is not logically implied either. Soundness and completeness together mean Armstrong's axioms compute exactly `F⁺`, nothing more and nothing less — this is why closures suffice for every downstream design decision.
Honest tradeoffs. Computing a single `X⁺` is cheap (near-linear), but enumerating all candidate keys of a relation is inherently exponential in the worst case, because a relation can have exponentially many minimal keys relative to its attribute count (a classical result: `n` attributes can yield `C(n, n/2)` candidate keys in adversarial FD sets). Real schemas are far more benign, and the "attributes never on a right-hand side must be in every key" heuristic typically collapses the search space to something tiny in practice.
Worked example
Consider a course-scheduling relation: ``` R(course, section, semester, instructor, room, hours, student, grade) ``` with designer-supplied functional dependencies: ``` F = { course, section, semester → instructor, course, section, semester → room, room, semester → hours, instructor, semester → course, -- an instructor teaches one course per semester course, student, semester → grade } ```
Question 1: Is `{course, section, semester}` a superkey? Compute its closure.
| Step | `result` so far | FD applied | Newly added |
|---|---|---|---|
| 0 | `{course, section, semester}` | — | start |
| 1 | `{course, section, semester, instructor}` | `course,section,semester → instructor` | `instructor` |
| 2 | `{course, section, semester, instructor, room}` | `course,section,semester → room` | `room` |
| 3 | `{course, section, semester, instructor, room, hours}` | `room,semester → hours` | `hours` |
| 4 | (no more FDs fire — `student`, `grade` need `student` in `X`) | — | fixed point |
`{course, section, semester}⁺ = {course, section, semester, instructor, room, hours}`. This is not all of `R` (missing `student`, `grade`), so `{course, section, semester}` is not a superkey by itself.
Question 2: Is `{course, section, semester, student}` a candidate key? Extend the closure with `student` in `X`:
| Step | `result` so far | FD applied | Newly added |
|---|---|---|---|
| 0 | `{course, section, semester, student}` | — | start |
| 1 | `+ instructor, room` | `course,section,semester → instructor`, `→ room` | `instructor, room` |
| 2 | `+ hours` | `room, semester → hours` | `hours` |
| 3 | `+ grade` | `course, student, semester → grade` | `grade` |
| 4 | fixed point — all 8 attributes present | — | done |
Closure equals all of `R`, so `{course, section, semester, student}` is a superkey. Is it minimal? Drop each attribute and re-test:
- Drop `course`: closure of `{section, semester, student}` stalls immediately (no FD has left side `⊆ {section, semester, student}`) — cannot reach `instructor` or `grade`. Not a superkey without `course`.
- Drop `section`: closure of `{course, semester, student}` — no FD fires on `course,semester,student` alone (the instructor/room FDs need `section` too); it stalls at 3 attributes. Not a superkey.
- Drop `semester`: closure of `{course, section, student}` stalls similarly. Not a superkey.
- Drop `student`: this is exactly Question 1's set, already shown not a superkey.
Every proper subset fails, so `{course, section, semester, student}` is a candidate key — the minimal set of attributes that pins down every other value in a course-scheduling row, exactly as intuition suggests (you need to know which offering and which student to determine a grade).
Common pitfalls & traps
| Pitfall | Why it happens | Fix |
|---|---|---|
| Treating an FD as "true in this sample table" | A small instance can satisfy `X → Y` by coincidence even when the real-world rule is false | Derive FDs from business semantics, not from eyeballing sample rows |
| Confusing `X → Y` with "X and Y are correlated" | FD is a strict logical constraint, not a statistical association | Only assert an FD if it must hold in every legal instance, always |
| Forgetting trivial FDs when listing `F⁺` | `Y ⊆ X` always gives `X → Y` for free, inflating naive enumerations | Focus analysis on nontrivial FDs; trivial ones need no checking |
| Stopping the closure loop too early | A single pass may miss FDs that only become applicable after later attributes are added | Iterate to a genuine fixed point — keep scanning until a full pass adds nothing |
| Assuming a key found first is the only key | Some schemas admit several distinct candidate keys | Systematically test all minimal subsets, using the "must-be-in-every-key" attribute heuristic to prune |
| Using augmentation/transitivity but skipping soundness check on the base FDs | Downstream errors when `F` itself contains a mis-specified rule | Validate each raw FD against the domain expert before deriving further consequences |
Pioneers & history
Origins · 1 minWilliam Ward Armstrong and how this was discovered
Functional dependency theory grew directly out of Edgar F. Codd's 1970 relational model, which needed a rigorous way to talk about "good" versus "bad" table designs. Codd himself introduced FDs and the first two normal forms as part of formalizing the relational model. William Armstrong, working independently in Grenoble, France, then supplied the missing logical bedrock: a small, provably sound and complete axiom system from which every FD implied by a set could be derived mechanically, replacing ad hoc reasoning with algorithmic certainty. This turned "does this schema have a design flaw?" from a matter of expert judgment into a decidable question answerable by closure computation — the same closure algorithm taught in every database course today.
Origins · 1 minhow this was discovered
Where this matters
Every production relational database — PostgreSQL, MySQL, Oracle, SQL Server — implicitly relies on FD reasoning whenever a schema designer chooses a `PRIMARY KEY` or a `UNIQUE` constraint: those declarations are assertions of specific functional dependencies (`key → all other attributes`), enforced by the engine at write time. Query optimizers use known FDs to simplify queries: if a `GROUP BY` clause includes a key, the optimizer knows every other selected column is functionally determined and can skip redundant aggregation checks (this is exactly the rule some SQL dialects enforce when they reject "non-functionally-dependent" columns in a `SELECT` list under `GROUP BY`). Data warehouse and ETL pipeline designers use FDs to validate dimension tables before loading star schemas, since a broken FD in a slowly changing dimension silently corrupts historical joins. CASE tools and modern schema-migration linters (used in Rails, Django, and enterprise data-modeling suites) run automated FD-closure checks to flag candidate normalization violations before a schema goes to production. Every discussion of Normalization Motivation and Anomalies, the practical definitions of 2NF and 3NF, the stricter Boyce-Codd Normal Form, and the correctness proofs behind Lossless-Join Decomposition all reduce, underneath, to closure and Armstrong-axiom computations exactly like the ones shown here.
Ask the tutor: How do I compute a minimal (canonical) cover of a set of functional dependencies step by step?
What is the difference between a functional dependency and a key?
A functional dependency `X → Y` is a general statement that `X`'s value determines `Y`'s value; it can involve any attribute subsets, not necessarily the whole schema. A key (specifically a superkey) is the special case where `X → R` — that is, `X` determines every attribute of the relation. A candidate key additionally requires minimality: no proper subset of `X` also determines all of `R`. So every candidate key statement is a functional dependency, but most functional dependencies (like `room, semester → hours` in the worked example) are not key statements at all — they describe partial determination relevant to normalization, not uniqueness.
Can a functional dependency have multiple attributes on both sides?
Yes. `X → Y` allows `X` and `Y` to each be arbitrary attribute sets, for example `{course, section, semester} → {instructor, room}`. By the union rule (derivable from Armstrong's axioms), this multi-attribute FD is logically equivalent to writing two single-attribute FDs separately: `{course,section,semester} → instructor` and `{course,section,semester} → room`. Conversely, the decomposition rule lets you split any right side into singletons without losing information. Left sides, however, do not decompose this way — `AB → C` does not imply `A → C` or `B → C` individually, since the dependency may genuinely require both determinant attributes together.
Why is attribute closure computation polynomial when finding all candidate keys is exponential?
Computing a single closure `X⁺` only ever grows a result set that is bounded by the number of attributes `n`, and each growth step is cheap to detect, giving polynomial (near-linear with the right data structures) time. Finding all candidate keys, in contrast, requires checking closures for a combinatorial number of candidate subsets, because in the worst case a relation's FD set can force exponentially many minimal keys (up to `C(n, n/2)` for adversarially constructed FD sets). The single-closure operation is efficient; the key-enumeration search space is what is expensive, not the closure primitive itself.
Do functional dependencies have to be declared, or can a database detect them automatically?
FDs must, in principle, be declared or inferred from domain knowledge, because they are semantic assertions about the real world, not derivable from any finite sample table alone. In practice, tools exist that mine candidate FDs from existing data (algorithms like TANE or FDep scan a table and report FDs that hold in that instance), which is useful for reverse-engineering legacy databases or spotting undocumented business rules. But any FD suggested by data mining must still be validated against actual domain semantics before being trusted as a genuine constraint, since a mined FD might simply reflect an accidental pattern in the current rows.
How do functional dependencies relate to normalization and anomalies?
Functional dependencies are the formal input that normalization theory operates on. Update, insertion, and deletion anomalies (covered under Normalization Motivation and Anomalies) arise precisely when a non-key attribute is functionally dependent on something other than a full candidate key. 2NF and 3NF and Boyce-Codd Normal Form are defined entirely in terms of which FDs are allowed to exist relative to the candidate keys of a relation — for instance, BCNF requires that for every nontrivial FD `X → Y` in `F⁺`, `X` must be a superkey. Without FDs there is no formal vocabulary in which "normal form" can even be defined.
What is a minimal cover, and why does it matter for FD reasoning?
A minimal cover (or canonical cover) of a set `F` is an equivalent set `Fc` of FDs — implying and implied by the same closure `F⁺` — that is stripped of redundancy: every right side is a single attribute, no FD can be removed without changing `F⁺`, and no attribute can be removed from any left side without changing `F⁺`. Minimal covers matter because dependency-preserving decomposition algorithms (used when constructing Lossless-Join Decomposition into 3NF) operate on a minimal cover rather than the raw, possibly redundant designer-supplied `F`, guaranteeing the resulting schema has no wasted or duplicated constraints.
Is X → Y the same as saying X and Y are always equal-length or the same type?
No — this is a common beginner confusion. A functional dependency says nothing about data types, lengths, or value ranges; it is purely about value agreement across tuples. `X → Y` only asserts that whenever two rows share the same values in `X`, they must also share the same values in `Y` — the actual values, types, or attribute counts of `X` and `Y` are otherwise unconstrained and unrelated to each other. For example, `zip_code → city` involves a numeric-like string determining a text field; nothing about their formats needs to match.