Functional Dependency

Functional dependency (FD) is a combinations of constraints between 2 attributes in a relation. Functional dependency explians that if two records have same values for attributes A1, A2,…, An, then those two records must have to have same values for attributes B1, B2, …, Bn.

Functional dependency is represented by an arrow sign (→) that is, X→Y, where X functionally determines Y. The left-hand side attributes determine the values of attributes on the right-hand side.

Armstrong’s Axioms

If F is a set of functional dependencies then the closure of F, denoted as F+, is the set of all functional dependencies logically implied by F. Armstrong’s Axioms are a set of rules, that when applied again and again, generates a closure of functional dependencies.

  • Reflexive rule − If alpha is a set of attributes and beta is_subset_of alpha, then alpha holds beta.
  • Augmentation rule − If a → b holds and y is attribute set, then ay → by also holds. That is adding attributes in dependencies, does not change the basic dependencies.
  • Transitivity rule − Same as transitive rule in algebra, if a → b holds and b → c holds, then a → c also holds. a → b is called as a functionally that determine to b.

Trivial Functional Dependency

  • Trivial − If a functional dependency (FD) X → Y holds, where Y is a subset of X, then it is called a trivial FD. Trivial FDs always hold.
  • Non-trivial − If an FD X → Y holds, where Y is not a subset of X, then it is called a non-trivial FD.
  • Completely non-trivial − If an FD X → Y holds, where x intersect Y = Φ, it is said to be a completely non-trivial FD.