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 XY
  • Augmentation: If XY, then XZYZ
  • Transitivity: If XY and YZ, then XZ

"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 XY and XZ, then XYZ
  • Decomposition: If XYZ, then XY and XZ
  • Pseudotransitivity: If XY and WYZ, then WXZ

The union and decomposition rules can be combined in a logical equivalence stating that XYZ, holds iff XY and XZ. This is sometimes called the splitting/combining rule.

Another rule that is sometimes handy is:

  • Composition: If XY and ZW, then XZYW

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

Read more about this topic:  Functional Dependency

Famous quotes containing the words properties and/or functional:

    A drop of water has the properties of the sea, but cannot exhibit a storm. There is beauty of a concert, as well as of a flute; strength of a host, as well as of a hero.
    Ralph Waldo Emerson (1803–1882)

    Stay-at-home mothers, . . . their self-esteem constantly assaulted, . . . are ever more fervently concerned that their offspring turn out better so they won’t have to stoop to say “I told you so.” Working mothers, . . . their self-esteem corroded by guilt, . . . are praying their kids turn out functional so they can stop being defensive and apologetic and instead assert “See? I did do it all.”
    Melinda M. Marshall (20th century)