阿姆斯特朗公理

阿姆斯特朗公理系统（英语：Armstrong's axioms）是一组用于推导关系数据库中所有函数依赖的规则。这一系统由威廉·W·阿姆斯特朗在1974年的论文中首次提出。^[1] 当应用于函数依赖集（用 ${\displaystyle F}$ 表示）时，这些规则在生成该集闭包（用 ${\displaystyle F^{+}}$ 表示）中的函数依赖方面既可靠又完备。换言之，反复应用这些规则，我们能够推导出闭包 ${\displaystyle F^{+}}$ 中的所有函数依赖，且不会产生不属于该闭包的依赖关系。

让我们用更严谨的方式来描述这个概念。假设 ${\displaystyle \langle R(U),F\rangle }$ 代表一个关系模式，其中 ${\displaystyle U}$ 是属性集，${\displaystyle F}$ 是函数依赖集。如果所有满足 ${\displaystyle F}$ 中函数依赖的，${\displaystyle R}$ 的实例 ${\displaystyle r}$，也都同时满足函数依赖 ${\displaystyle f}$，那么我们就说 ${\displaystyle f}$ 被 ${\displaystyle F}$ 逻辑蕴含，记作 ${\displaystyle F\models f}$。我们用 ${\displaystyle F^{+}}$ 来表示所有被 ${\displaystyle F}$ 逻辑蕴含的函数依赖的集合。

再来看推理规则集 ${\displaystyle A}$ 的作用。如果我们能够通过反复运用 ${\displaystyle A}$ 中的规则，从 ${\displaystyle F}$ 中推导出函数依赖 ${\displaystyle f}$，我们就说 ${\displaystyle f}$ 可由 ${\displaystyle F}$ 通过 ${\displaystyle A}$ 所推导，记作 ${\displaystyle F\vdash _{A}f}$。我们用 ${\displaystyle F_{A}^{*}}$ 表示所有可以通过 ${\displaystyle A}$ 从 ${\displaystyle F}$ 推导出的函数依赖的集合。

那么，当且仅当以下条件成立时，推理规则集 ${\displaystyle A}$ 是可靠的：

${\displaystyle F_{A}^{*}\subseteq F^{+}}$

也就是说，使用 ${\displaystyle A}$ 推导出的函数依赖不能超出由 ${\displaystyle F}$ 逻辑蕴含的函数依赖范围。 推理规则集 ${\displaystyle A}$ 的完备性当且仅当以下条件成立：

${\displaystyle F^{+}\subseteq F_{A}^{*}}$

更简单地说，推理规则集 ${\displaystyle A}$ 能够推导出所有由 ${\displaystyle F}$ 逻辑蕴含的函数依赖。

公理（基本规则）

设${\displaystyle R(U)}$是定义在属性集${\displaystyle U}$上的关系模式。在接下来的讨论中，我们将用${\displaystyle X}$、${\displaystyle Y}$、${\displaystyle Z}$表示${\displaystyle U}$的任意子集。为了简洁，我们用${\displaystyle XY}$代替常规的${\displaystyle X\cup Y}$来表示两个属性集${\displaystyle X}$和${\displaystyle Y}$的并集。这种记法在处理数据库理论中的属性集合时是相当常见的。

自反律

如果${\displaystyle X}$是一个属性集，${\displaystyle Y}$是${\displaystyle X}$的一个子集，那么${\displaystyle X}$函数决定${\displaystyle Y}$（也就是${\displaystyle Y}$函数依赖${\displaystyle X}$），记作${\displaystyle X\to Y}$。

若${\displaystyle Y\subseteq X}$则${\displaystyle X\to Y}$.

增广律

如果${\displaystyle X}$决定${\displaystyle Y}$，那么在${\displaystyle X}$和${\displaystyle Y}$中同时添加任意属性集${\displaystyle Z}$后，这种决定关系仍然成立。这表明，增加新的属性不会改变已有的函数依赖关系。

若${\displaystyle X\to Y}$，则对任意属性集${\displaystyle Z}$，都有${\displaystyle XZ\to YZ}$.

传递律

函数依赖关系具有传递性。也就是说，如果${\displaystyle X}$决定${\displaystyle Y}$，且${\displaystyle Y}$决定${\displaystyle Z}$，那么${\displaystyle X}$必然也决定${\displaystyle Z}$。

若${\displaystyle X\to Y}$且${\displaystyle Y\to Z}$，则${\displaystyle X\to Z}$.

公理的推论

这些推论可以从上述公理中推导出来。

分解规则

若${\displaystyle X\to YZ}$，则${\displaystyle X\to Y}$且${\displaystyle X\to Z}$。

证明

1. ${\displaystyle X\to YZ}$	（已知）
2. ${\displaystyle YZ\to Y}$	（自反性）
3. ${\displaystyle X\to Y}$	（1和2的传递性）

合成规则

若${\displaystyle X\to Y}$且${\displaystyle A\to B}$，则${\displaystyle XA\to YB}$。

证明

1. ${\displaystyle X\to Y}$	（已知）
2. ${\displaystyle A\to B}$	（已知）
3. ${\displaystyle XA\to YA}$	（1和A的增广性）
4. ${\displaystyle YA\to YB}$	（2和Y的增广性）
5. ${\displaystyle XA\to YB}$	（3和4的传递性）

合并规则

如果${\displaystyle X\to Y}$且${\displaystyle X\to Z}$，则${\displaystyle X\to YZ}$。

证明

1. ${\displaystyle X\to Y}$	（已知）
2. ${\displaystyle X\to Z}$	（已知）
3. ${\displaystyle X\to XZ}$	（2和X的增广性）
4. ${\displaystyle XZ\to YZ}$	（1和Z的增广性）
5. ${\displaystyle X\to YZ}$	（3和4的传递性）

伪传递规则

若${\displaystyle X\to Y}$且${\displaystyle YZ\to W}$，则${\displaystyle XZ\to W}$。

证明

1. ${\displaystyle X\to Y}$	（已知）
2. ${\displaystyle YZ\to W}$	（已知）
3. ${\displaystyle XZ\to YZ}$	（1和Z的增广性）
4. ${\displaystyle XZ\to W}$	（3和2的传递性）

自确定性

对于任意${\displaystyle I}$，${\displaystyle I\to I}$。这直接由自反性公理得到。

扩展规则

当${\displaystyle Z=X}$时，该属性是增广性的一个特殊情况。

若${\displaystyle X\to Y}$，则${\displaystyle X\to XY}$。

在这种意义上，扩展性可以替代增广性作为公理，因为通过扩展性和其他公理可以证明增广性。

证明

1. ${\displaystyle XZ\to X}$	（自反性）
2. ${\displaystyle X\to Y}$	（已知）
3. ${\displaystyle XZ\to Y}$	（1和2的传递性）
4. ${\displaystyle XZ\to XYZ}$	（3的扩展性）
5. ${\displaystyle XYZ\to YZ}$	（自反性）
6. ${\displaystyle XZ\to YZ}$	（4和5的传递性）