Functional Dependencies and Closure
One algorithm — attribute closure — answers every question about keys, implication and lossless splits.
Skip to the animationA functional dependency X → Y says that fixing X fixes Y; computing the closure of an attribute set answers essentially every question about keys, implication and decomposition.
What a dependency claims
X → Y means any two rows agreeing on X must agree on Y. It is a statement about the world being modelled, not about the rows currently stored. No amount of sample data proves a dependency — but a single counterexample row disproves one.
Dependencies are where schema design starts, because every normal form is a rule about which ones are allowed to exist in which relation.
The vocabulary
- Functional dependency (X → Y)
- Knowing X pins down Y. If two rows agree on X they must agree on Y. This is a statement about the world being modelled, not about the rows that happen to be in the table today.
- Superkey and candidate key
- A superkey determines every attribute in the relation. A candidate key is a superkey with nothing spare in it — remove any attribute and it stops working.
- Prime attribute
- One that appears in some candidate key. The normal forms are mostly rules about how non-prime attributes are allowed to depend on prime ones.
- Partial dependency
- A non-prime attribute determined by only part of a composite key. Forbidden by 2NF, and the direct cause of the update, insert and delete anomalies.
- Transitive dependency
- Key → X → Y where X is not a key. Forbidden by 3NF: the fact really belongs in a table keyed by X.
- Lossless decomposition
- Splitting a relation so that re-joining it gives back exactly the original rows — no more, no fewer. Guaranteed when the shared attribute is a key of one of the two pieces.
Attribute closure
The closure X⁺ is every attribute determined by X, directly or indirectly. The algorithm is three lines and runs in linear time:
- 1Start with the attributes of X themselves.
- 2Find any dependency whose entire left-hand side is already in the set, and add its right-hand side.
- 3Repeat until a full pass adds nothing.
Iteration is essential. CD → E is useless until both C and D have been derived by earlier steps — a single pass would miss it.
Everything closure answers
| Question | Test |
|---|---|
| Is X a superkey? | X⁺ contains every attribute |
| Is X a candidate key? | X⁺ is everything, and no proper subset's closure is |
| Is X → Y implied? | Y ⊆ X⁺ |
| Is R in BCNF? | for every X → Y, X⁺ is everything |
| Is a decomposition lossless? | the shared attributes' closure covers one of the two pieces |
One algorithm, five questions. This is why closure is worth being fluent in — it turns schema-design problems into a mechanical computation.
Armstrong's axioms
Closure is an efficient way of applying three rules that are sound (never derive a false dependency) and complete (every implied dependency follows from them):
- Reflexivity — X → Y whenever Y ⊆ X. These are the trivial dependencies.
- Augmentation — if X → Y then XZ → YZ. Adding context never breaks a dependency.
- Transitivity — if X → Y and Y → Z then X → Z.
Union, decomposition and pseudo-transitivity are commonly quoted too, but all three are derivable from the axioms above rather than independent.
Advantages and disadvantages
Advantages
- Closure runs in linear time and settles almost every design question.
- Armstrong's axioms are complete, so nothing implied is ever out of reach.
- Makes "is this a key?" a calculation rather than a judgement call.
Disadvantages
- The dependencies themselves must be supplied — they come from understanding the domain, not from the data.
- Finding all candidate keys is exponential in the worst case, even though testing one is cheap.
- Only expresses one kind of constraint; multivalued and join dependencies need 4NF and 5NF machinery.
Watch it work
Check yourself
question 1 / 4
One question at a time. Pick an answer to see why it is right or wrong, then move on — there is no score to keep and nothing is saved.