CSE Roadmap

Common tier · about 3 hours · 5 parts

Part 4 of 5 · 2 min read

Armstrong's axioms

Three rules for deriving new functional dependencies from known ones.

Armstrong's axioms

Think of three rules of arithmetic that let new true equations be derived from already-known true equations, without needing to re-measure anything from scratch.

In plain words: reflexivity says Y → X whenever X is a subset of Y's own columns. Augmentation says if X → Y holds, then adding the same extra columns Z to both sides, XZ → YZ, also holds. Transitivity says if X → Y and Y → Z both hold, then X → Z holds too.

A worked example. Given book_id → title and title → page_count (assuming titles are unique in this hypothetical), transitivity derives book_id → page_count.

The key lines. No new SQL; these are reasoning rules about dependencies already established, not something queried directly.

Armstrong's axioms

Armstrong's axioms are three rules, reflexivity, augmentation and transitivity, that derive new functional dependencies from already-known ones, without needing to check the raw data again.

Example: transitivity turns book_id → title and title → page_count into the derived dependency book_id → page_count.

For the curious Why this matters next

The next module's normal forms are defined entirely using functional dependencies: a table violates a normal form exactly when it has a dependency of a forbidden shape, such as a partial or transitive dependency on its key. Precisely naming these shapes now is what makes the next module's rules checkable rather than vague.

Quick notes

  • A functional dependency X → Y means rows sharing the same X also share the same Y.
  • A full dependency needs the entire composite key; a partial dependency needs only part of it.
  • Reflexivity, augmentation and transitivity let new dependencies be derived from known ones.
  • Functional dependencies are checked against real data, but once established, can be reasoned about abstractly.
  • Normal forms, covered next, are defined directly in terms of these dependency shapes.