Functional Dependencies
A functional dependency is a constraint stating that the values of one set of attributes uniquely determine the values of another; functional dependencies are the semantic input that drives key discovery and normalization.
Definition
A functional dependency X → Y on a relation schema holds if, in every legal instance, any two tuples that agree on all attributes in X also agree on all attributes in Y; that is, X functionally determines Y.
Scope
This topic covers functional dependencies (FDs) and their formal theory: the definition of X → Y, trivial and nontrivial dependencies, Armstrong's axioms (reflexivity, augmentation, transitivity) and their soundness and completeness, the closure of an attribute set and of a set of FDs, canonical (minimal) covers, and the use of FDs to compute candidate keys. It excludes multivalued and join dependencies and the normal forms that are tested using FDs, which are treated in adjacent topics.
Core questions
- What does it mean for one attribute set to functionally determine another?
- Which inference rules (Armstrong's axioms) are sound and complete for FDs?
- How is the closure of an attribute set computed, and what is it used for?
- How are candidate keys derived from a set of functional dependencies?
- What is a minimal (canonical) cover and why is it useful?
Key concepts
- functional dependency X → Y
- trivial versus nontrivial dependency
- Armstrong's axioms
- attribute-set closure
- closure of a set of FDs
- candidate and superkeys
- minimal (canonical) cover
- soundness and completeness
Key theories
- Functional dependency
- X → Y constrains a relation so that the X-values determine the Y-values; FDs formalize the real-world rules (such as a key determining all other attributes) that a schema must enforce.
- Armstrong's axioms
- Reflexivity, augmentation, and transitivity form a sound and complete inference system for functional dependencies, so all and only the logically implied dependencies can be derived from a given set.
- Attribute closure and minimal cover
- The closure of an attribute set under a set of FDs reveals which attributes it determines (and hence whether it is a superkey), and a minimal cover is an equivalent, non-redundant set of FDs used as the basis for normalization.
Clinical relevance
Functional dependencies are the practical input to schema design tools and the reasoning database designers use to identify keys and decide how to split tables; getting them right is what lets normalization remove redundancy without losing information.
History
Functional dependencies were introduced by Codd alongside the relational model and its normalization, and W. W. Armstrong gave in 1974 the axiom system that bears his name, proving it sound and complete. These results made dependency reasoning algorithmic and underpin all subsequent normalization theory.
Key figures
- Edgar F. Codd
- William W. Armstrong
Related topics
Seminal works
- codd1972
- armstrong1974
- silberschatz2019
Frequently asked questions
- How are functional dependencies different from keys?
- A key is a special case: a candidate key K is a minimal set of attributes whose closure is the whole relation, i.e. K functionally determines every attribute. Functional dependencies are the more general constraints from which keys are derived by computing attribute closures.
- Why compute a minimal cover?
- A minimal (canonical) cover is an equivalent set of functional dependencies with no redundant dependencies or extraneous attributes. Working from a minimal cover simplifies key finding and produces cleaner decompositions during normalization, especially when seeking dependency-preserving designs.