Functional Dependencies and Armstrong's Axioms

Introduction

Relational database design rests on a formal foundation that predates most modern database systems.
At the core of this foundation lies the concept of functional dependencies, which describe constraints between attributes in a relation.
These constraints drive the normalization process, inform index design, and provide the theoretical basis for query optimization.

William W.
Armstrong formalized a set of inference rules in 1974 that are both sound and complete for reasoning about functional dependencies. "Sound" means every dependency derived using the rules actually holds. "Complete" means every dependency that holds can be derived using the rules.
This combination makes Armstrong's axioms the definitive tool for reasoning about functional dependencies in relational schemas.

Functional Dependencies

A functional dependency (FD) is a constraint between two sets of attributes in a relation.
Given a relation R, we say that attribute set X functionally determines attribute set Y (written X → Y) if and only if, for every valid instance of R, any two tuples that agree on all attributes in X must also agree on all attributes in Y.

More precisely, for tuples t1 and t2 in relation R:

If t1[X] = t2[X], then t1[Y] = t2[Y]

This is a semantic constraint.
It cannot be inferred from inspecting a single instance of the data.
It must be declared based on knowledge of the real-world domain the relation models.

Examples

Consider a relation Employee(EmpID, Name, DeptID, DeptName, Salary).

EmpID → Name, DeptID, and Salary holds because each employee ID uniquely identifies the employee's name, department, and salary.
DeptID → DeptName holds because each department ID maps to exactly one department name.
Name → EmpID does not hold in general, since two employees can share a name.

Trivial and Non-Trivial Dependencies

A functional dependency X → Y is trivial if Y ⊆ X.
For example, {EmpID, Name} → {Name} is trivial because the right-hand side is a subset of the left-hand side.
Trivial dependencies always hold, regardless of the relation's content.
All other dependencies are non-trivial, and these carry actual design information.

Armstrong's Axioms

Armstrong's axioms consist of three inference rules from which all valid functional dependencies can be derived.

The Three Axioms

diagram-1 — Armstrong's axioms and their derived FD rules

1.
Reflexivity (Axiom of Trivial Dependency) If Y ⊆ X, then X → Y.

This states that any set of attributes functionally determines any of its subsets.
It generates only trivial dependencies, but it serves as a base case for derivations.

2.
Augmentation If X → Y, then XZ → YZ for any attribute set Z.

Adding the same set of attributes to both sides of a functional dependency preserves the dependency.
If employee ID determines department, then (employee ID, hire date) determines (department, hire date).

3.
Transitivity If X → Y and Y → Z, then X → Z.

Dependencies compose.
If EmpID → DeptID and DeptID → DeptName, then EmpID → DeptName.

Derived Rules

Several additional rules can be derived from the three axioms.
These derived rules are not new axioms; they are theorems that simplify reasoning in practice.

Union Rule: If X → Y and X → Z, then X → YZ.

Proof: By augmentation, X → Y gives XZ → YZ.
By augmentation on X → Z, we get XX → XZ, which simplifies to X → XZ.
By transitivity on X → XZ and XZ → YZ, we get X → YZ.

Decomposition Rule: If X → YZ, then X → Y and X → Z.

Proof: Since Y ⊆ YZ, by reflexivity YZ → Y.
By transitivity on X → YZ and YZ → Y, we get X → Y.
Analogously for Z.

Pseudotransitivity Rule: If X → Y, and WY → Z, then WX → Z.

Proof: By augmentation on X → Y, WX → WY.
By transitivity on WX → WY and WY → Z, WX → Z.

These derived rules allow you to work with functional dependencies without repeatedly decomposing every step to the three base axioms.

Walkthrough

Computing the Closure of an Attribute Set

diagram-2 — Attribute-closure algorithm with worked-example state progression

The closure of an attribute set X with respect to a set of functional dependencies F, denoted X⁺, is the set of all attributes functionally determined by X under F.
Computing X⁺ is the central algorithmic operation when working with functional dependencies.
It is used to test whether a dependency X → Y holds (check if Y ⊆ X⁺), to find candidate keys, and to compute minimal covers.

ALGORITHM: AttributeClosure(X, F)
Input:  X = a set of attributes
        F = a set of functional dependencies
Output: X⁺ = the closure of X under F

1.  result ← X
2.  changed ← true
3.  while changed do
4.      changed ← false
5.      for each dependency (A → B) in F do
6.          if A ⊆ result then
7.              if B ⊄ result then
8.                  result ← result ∪ B
9.                  changed ← true
10. return result

Worked Example

Given relation R(A, B, C, D, E) with functional dependencies:

F = { A → B,   B → C,   CD → E,   E → A }

Compute {A, D}⁺:

Step	result	Dependency applied
Init	{A, D}
1	{A, B, D}	A → B (A ⊆ {A,D})
2	{A, B, C, D}	B → C (B ⊆ {A,B,D})
3	{A, B, C, D, E}	CD → E (C,D ⊆ {A,B,C,D})
4	No change	E → A (A already in result)

Since {A, D}⁺ = {A, B, C, D, E} = R, the attribute set {A, D} is a superkey of R.

Finding Candidate Keys

A superkey is any attribute set whose closure equals the full set of attributes.
A candidate key is a minimal superkey (no proper subset is also a superkey).
To verify that {A, D} is a candidate key:

Compute {A}⁺ = {A, B, C}. This does not include D or E, so {A} alone is not a superkey.
Compute {D}⁺ = {D}. Clearly not a superkey.

Since neither single-attribute subset of {A, D} is a superkey, {A, D} is a candidate key.

Testing Equivalence of FD Sets

Two sets of functional dependencies F and G are equivalent if they produce the same closure for every attribute set.
In practice, you verify this by checking that every FD in F can be derived from G (i.e., for each X → Y in F, Y ⊆ X⁺ under G) and vice versa.

Soundness and Completeness

The formal guarantees of Armstrong's axioms are worth stating precisely.

Soundness: If a functional dependency X → Y can be derived from a set F using Armstrong's axioms, then X → Y holds in every relation instance that satisfies F.
This was proven in Armstrong's original 1974 paper.

Completeness: If X → Y holds in every relation instance that satisfies F, then X → Y can be derived from F using Armstrong's axioms.
The proof is constructive: given any X → Y that cannot be derived, Armstrong showed how to construct a two-tuple relation instance that satisfies F but violates X → Y.
This is sometimes called an "Armstrong relation."

The combination of soundness and completeness means the axioms capture exactly the set of valid inferences about functional dependencies.
No additional inference rules are needed, and no rule produces a spurious result.

Practical Applications

Normalization

Functional dependencies are the primary input to normalization algorithms.
Second normal form (2NF) eliminates partial dependencies on candidate keys.
Third normal form (3NF) eliminates transitive dependencies.
Boyce-Codd normal form (BCNF) requires that every non-trivial FD has a superkey on its left-hand side.
The closure algorithm and Armstrong's axioms provide the machinery to verify these conditions and decompose relations accordingly.

Minimal Covers

A minimal cover (or canonical cover) of a set of functional dependencies F is a reduced set F_min that is equivalent to F, but contains no redundant dependencies and no extraneous attributes.
Computing a minimal cover involves repeatedly applying closure computations.
The result is used in synthesis algorithms for 3NF decomposition.

Query Optimization

Database query optimizers use functional dependency information to eliminate redundant joins, simplify GROUP BY clauses, and determine when columns can be removed from sort operations.
For example, if the optimizer knows that DeptID → DeptName, it can group by DeptID alone even when DeptName appears in the SELECT list, avoiding a wider sort key.

Schema Validation

In modern systems, FD discovery algorithms mine functional dependencies from data.
Tools like TANE and FUN identify approximate and exact FDs from existing datasets.
These discovered dependencies can be compared against declared constraints using the closure algorithm to find schema anomalies or undocumented business rules.

Key Points

A functional dependency X → Y states that identical values of X always imply identical values of Y across all valid relation instances.
Armstrong's three axioms (reflexivity, augmentation, transitivity) are both sound and complete for deriving all valid functional dependencies.
The union, decomposition, and pseudotransitivity rules are derived from the three base axioms and simplify practical reasoning.
The attribute closure algorithm is the fundamental computational procedure for testing whether a dependency holds under a given set of FDs.
Candidate keys are identified by finding minimal attribute sets whose closure equals the full set of attributes.
Functional dependencies directly drive normalization to 2NF, 3NF, and BCNF by characterizing partial, transitive, and non-superkey dependencies.
Soundness guarantees no false derivations; completeness guarantees no valid dependency is missed.

References

Armstrong, W. W. "Dependency Structures of Data Base Relationships." Proceedings of IFIP Congress, 1974, pp. 580-583.

Codd, E. F. "A Relational Model of Data for Large Shared Data Banks." Communications of the ACM, vol. 13, no. 6, 1970, pp. 377-387.

Ullman, J. D. "Principles of Database and Knowledge-Base Systems, Volume I." Computer Science Press, 1988.

Bernstein, P. A. "Synthesizing Third Normal Form Relations from Functional Dependencies." ACM Transactions on Database Systems, vol. 1, no. 4, 1976, pp. 277-298.

Maier, D. "The Theory of Relational Databases." Computer Science Press, 1983.