7.25

Use the definition of functional dependency to argue that each of Armstrong’s axioms (reflexivity, augmentation, and transitivity) is sound.

---

• Reflexivity rule If $\alpha$ is a set of attributes and $\beta \subseteq \alpha$, then $\alpha \to \beta$ holds.

Let $r(R)$ be a relation schema. Let $\beta \subseteq \alpha \subseteq R$. Let $t_1$ and $t_2$ be two tuples in $r$ such that:

$$t_1[\alpha ]=t_2[\alpha ]$$

Let $x$ be any attribute in $\beta$. Then the value of the attribute $x$ in $t_1$ is the same as the value of the attribute $x$ in $t_2$ (since $x\in \beta \text{ implies }x\in \alpha$).Thus,

$$t_1[\beta ]=t_2[\beta ]$$

Therefore, by definition of functional dependency, $\alpha \to \beta$ holds.

• Augmentation rule If $\alpha \to \beta$ holds and $\gamma$ is a set of attributes, then $\gamma \alpha \to \gamma \beta$ holds.

Let $r(R)$ be a relation schema and $\alpha \to \beta$ holds on $r(R)$. Let $\gamma \subseteq R$. Let $t_1$ and $t_2$ be two tuples in $r$ such that:

$$t_1[\gamma \alpha ]=t_2[\gamma \alpha ]$$

Let $x$ be an attribute in $\gamma \beta$. Then either $x\in \gamma$ or $x\in \beta$. Suppose $x\in \gamma$. Then the value of the attribute $x$ in $t_1$ is the same as the value of the attribute $x$ in $t_2$ (since $x\in \gamma \alpha$ and we assumed that $t_1[\gamma \alpha ]=t_2[\gamma \alpha ]$). Now suppose $x\in \beta$. Then the value of the attribute $x$ in $t_1$ is the same as the value of the attribute $x$ in $t_2$ (this is because of the functional dependency $\alpha \to \beta$ that holds on $r(R)$ and the fact that $t_1$ and $t_2$ have the same values on all attributes in $\alpha$ due to the condition $t_1[\gamma \alpha ]=t_2[\gamma \alpha ]$). Since $x$ was arbitrary in $\gamma \beta$ we conclude that

$$t_1[\gamma \beta ]=t_2[\gamma \beta ]$$

Thus $\gamma \alpha \to \gamma \beta$ holds.

• Transitivity rule If $\alpha \to \beta$ holds and $\beta \to \gamma$ holds, then $\alpha \to \gamma$.

Let $r(R)$ be a relation schema and the set of functional dependencies $F=\{\alpha \to \beta ,\beta \to \gamma \}$ holds on $r(R)$. Let $t_1$ and $t_2$ be two tuples in $r$ such that:

$$t_1[\alpha ]=t_2[\alpha ]$$

Since we know that $\alpha \to \beta$ holds on $r(R)$, it follows from the definition of functional dependency that:

$$t_1[\beta ]=t_2[\beta ]$$

Then, since we know that $\beta \to \gamma$ holds on $r(R)$, it follows from the definition of functional dependency that:

$$t_1[\gamma ]=t_2[\gamma ]$$

Therefore, we have shown that, whenever $t_1$ and $t_2$ are tuples such that $t_1[\alpha ]=t_2[\alpha ]$, it must be that $t_1[\gamma ]=t_2[\gamma ]$. But that is exactly the definition of $\alpha \to \gamma$