Inference Axioms for Functional Dependencies - Teradata Database

Teradata Database Design
Product
Teradata Database
Release Number
15.10
Language
English (United States)
Last Update
2018-10-06
Product Category
Software

Inference Axioms for Functional Dependencies

The concept of functional dependencies for relations was introduced by Armstrong. Beeri, Fagin, and Howard produced a complete set of inference axioms for functional and multivalued dependencies for relations. Their axioms, which are sometimes referred to as the Armstrong axioms, are described in the following table:

 

Axiom

Formal Expression

Reflexive rule

X →  X

Augmentation rule

IF

X →  Y

THEN

XZ →  Y

Union rule

IF

X →  Y

AND

X →  Z

THEN

X →  YZ

Decomposition rule

IF

X →  Y

THEN

X →  Z

WHERE

Z is a subset of Y

Transitivity rule

IF

X →  Y

AND

Y →  Z

THEN

X →  Z

Pseudotransitivity rule

IF

X →  Y

AND

YZ →  W

THEN

XZ →  W

For the sake of some examples, assume the attribute set R, S, T, U, V with the following set of dependencies:

 

The following table lists many of the dependencies among these attributes implied by the inference axioms:

 

Dependency

Supporting Axiom

R →  R

Reflexive rule

RT →  S

Augmentation rule

TU →  RV

  • Augmentation rule
  • Union rule
    		•

    RU →  T

    Pseudotransitivity rule

    UV →  R

    Pseudotransitivity rule

    TU →  S

    Transitivity rule

    SU →  V

    Transitivity rule

    VU →  R

    Pseudotransitivity rule

    RU →  V

  • Transitivity rule
  • Pseudotransitivity rule
    		•

    UV →  S

  • Transitivity rule
  • Pseudotransitivity rule
    		•

    Bernstein developed an algorithm for synthesizing a minimum set of tables in 3NF using the Armstrong axioms, and Teorey provide a nice example of determining a minimum set of 3NF relations using the Bernstein algorithm.