Functional Dependency - Properties and Axiomatization of Functional Dependencies

Properties and Axiomatization of Functional Dependencies

Given that X, Y, and Z are sets of attributes in a relation R, one can derive several properties of functional dependencies. Among the most important are the following, usually called Armstrong's axioms:

• Reflexivity: If Y is a subset of X, then X → Y
• Augmentation: If X → Y, then XZ → YZ
• Transitivity: If X → Y and Y → Z, then X → Z

"Reflexivity" can be weakened to just, i.e. it is an actual axiom, where the other two are proper inference rules, more precisely giving rise to the following rules of syntactic consequence:

.

These three rules are a sound and complete axiomatization of functional dependencies. This axiomatization is sometimes described as finite because the number of inference rules is finite, with the caveat that the axiom and rules of inference are all schemata, meaning that the X, Y and Z range over all ground terms (attribute sets).

From these rules, we can derive these secondary 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

The union and decomposition rules can be combined in a logical equivalence stating that X → YZ, holds iff X → Y and X → Z. This is sometimes called the splitting/combining rule.

Another rule that is sometimes handy is:

• Composition: If X → Y and Z → W, then XZ → YW

Equivalent sets of functional dependencies are called covers of each other. Every set of functional dependencies has a canonical cover.