What are Armstrong's axioms for functional dependencies, and how do you use them to reduce a declared dependency set to a minimal (canonical) cover?

## Why inference rules matter A design starts from a set F of dependencies someone wrote down. The dependencies that actually constrain the data are F+, the closure of F under logical implication. Armstrong's axioms are the proof system that generates F+. ## The three axioms **Reflexivity (trivial dependencies).** If Y is a subset of X then `X -> Y` holds in every relation. It needs no premise, which is why it is sometimes called an axiom scheme rather than a rule. **Augmentation.** If `X -> Y` then `XZ -> YZ` for any Z. Adding the same attributes to both sides preserves the dependency: if two rows agree on XZ they agree on X, hence on Y, and they agree on Z by assumption. **Transitivity.** If `X -> Y` and `Y -> Z` then `X -> Z`. Equal X values force equal Y values, which force equal Z values. **Soundness** means every dependency derivable by these rules genuinely holds in every relation satisfying F - the rules never lie. **Completeness** means every dependency that holds in all such relations is derivable - the rules miss nothing. Together they justify treating syntactic derivation and semantic implication as the same thing, which is what licenses the attribute-closure shortcut used in practice. ## Derived rules Three consequences save work: - **Union**: from `X -> Y` and `X -> Z`, derive `X -> YZ`. - **Decomposition**: from `X -> YZ`, derive `X -> Y` and `X -> Z`. - **Pseudotransitivity**: from `X -> Y` and `WY -> Z`, derive `WX -> Z`. Decomposition is what makes single-attribute right sides lossless as a normalisation of notation. Note the asymmetry: right sides split freely, **left sides do not**. From `XY -> Z` you may *not* conclude `X -> Z`; that is the single most common error in this material. ## Minimal cover Two dependency sets are **equivalent** when each implies the other, i.e. they have the same closure. A **minimal (canonical) cover** of F is an equivalent set G satisfying three conditions: 1. Every dependency in G has exactly one attribute on the right. 2. No dependency `X -> A` in G can have an attribute removed from X while G stays equivalent to F. Such a removable attribute is **extraneous**. 3. No dependency can be deleted from G while G stays equivalent to F. ### Procedure **Step 1 - split right sides.** Rewrite `X -> ABC` as `X -> A`, `X -> B`, `X -> C` using decomposition. **Step 2 - remove extraneous left-side attributes.** For each dependency `XY -> A` with a multi-attribute left side, test whether the smaller left side already suffices: compute `X+` under the *current* set. If A is in `X+`, then Y was extraneous and the dependency becomes `X -> A`. **Step 3 - remove redundant dependencies.** For each remaining `X -> A`, tentatively delete it and compute `X+` under the reduced set. If A is still in `X+`, the dependency was implied by the others; delete it permanently. Otherwise restore it. Steps 2 and 3 must always be evaluated against the set as it currently stands, including changes already made, or you can delete two dependencies that were each redundant only because the other was present, losing information. ### Worked example `F = { A -> BC, B -> C, A -> B, AB -> C }` over R(A, B, C). Split: `A -> B`, `A -> C`, `B -> C`, `A -> B` (duplicate, keep one), `AB -> C`. Extraneous left sides: in `AB -> C`, check `A+ = {A, B, C}` - it contains C, so B is extraneous and the dependency reduces to `A -> C`, which duplicates one we already have. Redundancy: remove `A -> C` and compute `A+` from `{A -> B, B -> C}` - it is `{A, B, C}`, still containing C, so `A -> C` is redundant. Remove it. Minimal cover: `{ A -> B, B -> C }`. ### Non-uniqueness A given F can have several minimal covers depending on processing order. With `F = { A -> B, B -> A, A -> C, B -> C }` you can keep `A -> C` or `B -> C` but not both; either choice yields a valid minimal cover. So "the" minimal cover is a misnomer - claiming uniqueness is a red flag. ## Where it is used Minimal covers are the input to dependency-preserving decomposition: the synthesis approach builds one relation per dependency group in the cover, so a bloated cover produces a bloated schema with redundant tables. They are also useful as a review artefact - the cover is the shortest honest statement of the business rules the schema encodes, and duplicated or implied rules in a specification usually mean two stakeholders described the same rule twice.