Functional Dependencies
A functional dependency (FD) is a constraint between two sets of attributes in a relation. Given a relation R, attribute set X functionally determines attribute set Y (written X → Y) if and only if each value of X is associated with exactly one value of Y. Functional dependencies are the formal foundation for Normalization — they determine which normal form a relation satisfies and guide decomposition.
Formal Definition
For a relation R, the functional dependency X → Y holds if for any two tuples t₁ and t₂:
if t₁[X] = t₂[X], then t₁[Y] = t₂[Y]
X is called the determinant and Y the dependent.
Types of Dependencies
- Full Functional Dependency — Y is fully functionally dependent on X if removing any attribute from X breaks the dependency. Required for 2NF.
- Partial Dependency — Y depends on a proper subset of a Composite Key. Violates 2NF.
- Transitive Dependency — If X → Y and Y → Z, then X → Z transitively. Violates 3NF.
- Trivial Dependency — X → Y where Y ⊆ X. Always holds.
- Multivalued Dependency — X →→ Y where X determines a set of values for Y independent of other attributes. Relevant to 4NF.
Armstrong’s Axioms
A sound and complete set of inference rules for deriving all functional dependencies from a given set F:
- Reflexivity — If Y ⊆ X, then X → Y (trivial dependency)
- Augmentation — If X → Y, then XZ → YZ for any attribute set Z
- Transitivity — If X → Y and Y → Z, then X → Z
Derived rules:
- 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
Closure
The closure of a set of FDs (F⁺) is the set of all functional dependencies that can be inferred from F using Armstrong’s Axioms.
The closure of an attribute set (X⁺) under F is the set of all attributes functionally determined by X. Used to:
- Determine if X is a Superkey (X⁺ contains all attributes of R)
- Find candidate keys
- Check if a dependency X → Y holds (Y ⊆ X⁺)
Relation to Normal Forms
| Normal Form | Violation |
|---|---|
| 1NF | Non-atomic values, repeating groups |
| 2NF | Partial dependencies on Primary Key |
| 3NF | Transitive dependencies |
| BCNF | Any non-trivial FD where determinant is not a Superkey |
| 4NF | Multivalued dependencies not implied by keys |