Armstrong's Axioms

relational-algebra

Definition

Armstrong's Axioms

Armstrong’s axioms are a set of axioms (or, more precisely, inference rules) used to infer all the functional dependencies.

Inference Rules

Reflexivity

Reflexivity

Let $\mathcal{R}$ be a schema of a relation $R$ and $\alpha ,\beta \subseteq \mathcal{R}$ (subsets of attributes of $\mathcal{R}$).

If $\beta \subseteq \alpha$, then $\alpha$ functionally determines $\beta$:

$$\beta \subseteq \alpha ⟹a\to \beta$$

Augmentation

Augmentation

Let $\mathcal{R}$ be a schema of a relation $R$ and $\alpha ,\beta ,\gamma \subseteq \mathcal{R}$ (subsets of attributes of $\mathcal{R}$).

If $\alpha$ functionally determines $\beta$, then $\alpha \gamma$ functionally determines $\beta \gamma$.

$$\alpha \to \beta ⟹\alpha \gamma \to \beta \gamma$$

Trivially, this is true since $\gamma \to \gamma$ is a trivial functional dependency.

Transitivity

Transitivity

Let $\mathcal{R}$ be a schema of a relation $R$ and $\alpha ,\beta ,\gamma \subseteq \mathcal{R}$ (subsets of attributes of $\mathcal{R}$).

If $\alpha$ functionally determines $\beta$ and $\beta$ functionally determines $\gamma$, then $\alpha$ functionally determines $\gamma$.

$$\alpha \to \beta \wedge \beta \to \gamma ⟹\alpha \to \gamma$$

Further Inference Rules

Further inference rules can be derived from the base rules.

Composition

Composition

Let $\mathcal{R}$ be a schema of a relation $R$ and $\alpha ,\beta ,\gamma \subseteq \mathcal{R}$ (subsets of attributes of $\mathcal{R}$).

If $\alpha$ functionally determines $\beta$ and $\alpha$ functionally determines $\gamma$, then $\alpha$ functionally determines $\beta \gamma$.

$$\alpha \to \beta \wedge \alpha \to \gamma ⟹\alpha \to \beta \gamma$$

Decomposition

Decomposition

Let $\mathcal{R}$ be a schema of a relation $R$ and $\alpha ,\beta ,\gamma \subseteq \mathcal{R}$ (subsets of attributes of $\mathcal{R}$).

If $\alpha$ functionally determines $\beta \gamma$, then $\alpha$ functionally determines $\beta$ and $\alpha$ functionally determines $\gamma$.

$$\alpha \to \beta \gamma ⟹\left(\alpha \to \beta \wedge \alpha \to \gamma \right)$$

Pseudo Transitivity

Pseudo Transitivity

Let $\mathcal{R}$ be a schema of a relation $R$ and $\alpha ,\beta ,\gamma ,\delta \subseteq \mathcal{R}$ (subsets of attributes of $\mathcal{R}$).

If $\alpha$ functionally determines $\beta$ and $\gamma \beta$ functionally determines $\delta$, then $\alpha \gamma$ functionally determines $\delta$.

$$\alpha \to \beta \wedge \gamma \beta \to \delta ⟹\alpha \gamma \to \delta$$