7.25

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

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 \rightarrow \beta\) holds.

Let \(r(R)\) be a relation schema and \(\alpha \rightarrow \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 \rightarrow \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 \rightarrow \gamma\beta\) holds.

Let \(r(R)\) be a relation schema and the set of functional dependencies \(F = \{\alpha \rightarrow \beta, \beta \rightarrow \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 \rightarrow \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 \rightarrow \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 \rightarrow \gamma\)