15.00 - Inference Axioms for Functional Dependencies - Teradata Database

Teradata Database Design

prodname
Teradata Database
vrm_release
15.00
category
User Guide
featnum
B035-1094-015K

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.