数据依赖的公理系统

Armstrong 公理

设有关系模式 R(U) 及其函数依赖集 F，如果对于 R 的任一个满足 F 的关系 r 函数依赖 X→Y 都成立，则称 F 逻辑蕴涵 X→Y，或称 X→Y 可以由 F 推出。给定关系模式 R(U) 和 FD 集 F，Armstrong 公理规定了以下的推理规则：

根据以上三条公理，可得到以下推理规则：

函数依赖闭包

在关系模式 R 中为 F 所逻辑蕴含的函数依赖的全体叫作 F 的闭包，记为 F+。设 F 为属性集 U 上的一组函数依赖，X⊆U，XF+={A|X→A 能由 F 根据 Armstrong 公理导出}，XF+ 称为属性集 X 关于函数依赖集 F 的闭包。
翻译成人话就是你有一些字母 X，通过函数依赖集 F 的箭头可以得到的所有字母就是 X 关于 F 的闭包。例如设属性集 U={A,B,C}，函数依赖集 F={A→B, B→C} 则 AF+={A，B，C}，BF+={B，C}，CF+={C}。

最小函数依赖集

最小函数依赖集的定义

最小函数依赖集是函数依赖集 F 如果满足下列条件，则称 F 为最小函数依赖集：

1. F 中每一个函数依赖的右部都是单个属性；
2. 对 F 中任一函数依赖 X→A，F-{X→A｝都不与 F 等价；
3. 对于 F 中的任一函数依赖 X→A，X 有真子集 Z 使得｛X→A}∪{Z→A｝都不与 F 等价。

翻译成人话就是你有一些你有一些字母 X 和函数依赖集 F，你可以找到一个更小的函数依赖集，它的所有函数依赖的箭头右边都只有一个字母，且不影响把箭头右边的字母都推出来。

最小依赖集的计算算法

1. 应用分解规则，使 F 中每一个依赖的右部属性单一化。
2. 去掉各依赖左部多余的属性。具体做法是：一个一个地检查 F 中左边是非单属性的依赖，例如 XY→A。判断Y是否为多余的，即以 X→A 代替 XY→A 是否等价，在 F 中求 X+，若 X+ 包含
   A，则 Y 是多余的属性；否则 Y 不是多余属性。依次判断其他属性即可消除各依赖左边的多余属性。
3. 去掉多余的依赖。具体做法是：从第一个依赖开始，从 F 中去掉它(假设该依赖为 X→Y)，然后在剩下的依赖中求 X，看 X+ 是否包含 Y，若是则去掉 X→Y，若不包含 Y 则不能去掉 X→Y。

   样例

   样例一

   先看一个简单的例，属性集 ABC 上的 FD 集，设 F={A→BC, B→AC, C→A}，求 Fm。第一步先将每一个依赖的右部属性单一化：

   F={A→B, A→C, B→A, B→C, C→A}

   接着去掉各依赖左部多余的属性： ``` 判断 A→B 是否冗余：G1={A→C, B→A, B→C, C→A} AG1+=AC，B 不属于 AG1+，A→B 不冗余；

判断 A→C 是否冗余：G2={A→B, B→A, B→C, C→A} AG2＋= ABC，C∈AG2＋，A→C 冗余， 修改为：F={A→B, B→A, B→C,C→A}；

判断 B→A 是否冗余：G3={A→B, B→C, C→A} BG3＋= ABC，A∈BG3＋，B→A 冗余， F={A→B, B→C, C→A}；

判断 B→C 是否冗余：G4={A→B, C→A} BG4＋=B，C 不属于 BG4＋，B→C 不冗余；

判断 C→A 是否冗余：G5={A→B, B→C} CG5＋=C，A 不属于 CG5＋，C→A 不冗余。

由于例中函数依赖的决定因素均为单属性，因而不需要第三步检查，上述结果就是最小函数依赖集。

Fm＝{A→B, B→C, C→A}

<a name="NiqQp"></a>
### 样例二
接着看一个啰嗦点的例子，设有依赖集 F，计算与其等价的最小依赖集。

F＝{MN→XZ, M→X, GP→N, ZP→M, XYZ→P, HN→P, Y→H, MNX→PG}

第一步，右边单一化：

F1＝{MN→X, MN→Z, M→X, GP→N, ZP→M, XYZ→P, HN→P, Y→H, MNX→P, MNX→G}

第二步：逐个求，在去掉它的 F 中求闭包

去掉 MN→X 后，求得的闭包包含 X，不保留 去掉 MN→Z 后，求得的闭包不包含 Z，保留 去掉 M→X 后，求得的闭包不包含 X，保留 去掉 GP→N 后，求得的闭包不包含 N，保留 去掉 ZP→M 后，求得的闭包不包含 M，保留 去掉 XYZ→P 后，求得的闭包不包含 P，保留 去掉 HN→P 后，求得的闭包不包含 P，保留 去掉 Y→H 后，求得的闭包不包含 H，保留 去掉 MNX→P 后，求得的闭包不包含 P，保留 去掉 MNX→G 后，求得的闭包不包含 G，保留

去掉各依赖左部多余的属性后得到：

F2＝{MN→Z, M→X, GP→N, ZP→M, XYZ→P, HN→P, Y→H, MNX→P, MNX→G}

第三步，对左边属性单一化：

MN→Z： M→Z，求(M)+不包含 Z，所以 N 不冗余。 N→Z，求(N)+不包含 Z，所以 M 不冗余。

GP→N： G→N，求(G)+不包含 N，所以 P 不冗余。 P→N，求(P)+不包含 N，所以 G 不冗余。

ZP→M： Z→M，求(Z)+不包含 M，所以 P 不冗余。 P→M，求(P)+不包含 M，所以 Z 不冗余。

XYZ→P： XY→P，求(XY)+不包含 P，所以 Z 不冗余。 YZ→P，求(YZ)+不包含 P，所以 X 不冗余。 XZ→P，求(XZ)+不包含 P，所以 Y 不冗余。

HN→P： H→P，求(H)+不包含 P，所以 N 不冗余。 N→P，求(N)+不包含 P，所以 H 不冗余。

MNX→P： MN→P，求(MN)+包含 P，所以 X 冗余。 MX→P，求(MX)+不包含 P，所以 N 不冗余。 NX→P，求(NX)+不包含 P，所以 M 不冗余。

MNX→G： MN→G，求(MN)+包含 G，所以 X 冗余。 MX→G，求(MX)+不包含 G，所以 N 不冗余。 NX→G，求(NX)+不包含 G，所以 M 不冗余。

综上所述，去掉多余的依赖后得到最小函数依赖集。

Fm＝{MN→Z, M→X, GP→N, ZP→M, XYZ→P, HN→P, Y→H, MN→P, MN→G}

<a name="oclaT"></a>
### 样例三
最后给一个实际的例子，设有关系模式如下。设一个学生可以选多门课程，一门课程可以被多名学生选。一个学生有唯一的所在系，每门课程有唯一的课程名和学分。每个学生对每门课程有唯一的成绩。

学生修课(学号, 姓名, 所在系, 性别, 课程号, 课程名, 学分, 成绩）

对关系模式归纳出函数依赖如下，得到候选键是{学号，课程号}。

学号→(姓名, 所在系, 性别) 课程号→(课程名, 学分) (学号, 课程号)→成绩

第一步，右边单一化：

学号→(姓名, 所在系, 性别) 课程号→(课程名, 学分) (学号, 课程号)→成绩

第二步逐个求，在去掉它的F中求闭包。

去掉“学号→姓名”后，求得的闭包不包含“姓名”，保留 去掉“学号→所在系”后，求得的闭包不包含“所在系”，保留 去掉“学号→性别”后，求得的闭包不包含“性别”，保留 去掉“课程号→课程名”后，求得的闭包不包含“课程名”，保留 去掉“课程号→学分”后，求得的闭包不包含“学分”，保留 去掉“(学号, 课程号)→成绩”后，求得的闭包不包含“课程号”，保留

去掉各依赖左部多余的属性后得到：

F2={学号→姓名, 学号→所在系, 学号→性别, 课程号→课程名, 课程号→学分, (学号, 课程号)→成绩}

第三步，对左边属性单一化：

(学号，课程号)→成绩： 学号→成绩，求(学号)+不包含“成绩”，所以“学号”不冗余。 课程号→成绩，求(课程号)+不包含“成绩”，所以“课程号”不冗余。

综上所述，去掉多余的依赖后得到最小函数依赖集。

Fm={学号→姓名, 学号→所在系, 学号→性别, 课程号→课程名, 课程号→学分, (学号，课程号)→成绩}

<a name="hz7Z0"></a>
# 求候选键
<a name="quYx2"></a>
## 候选键的求法
博客[数据库原理：数据模型和关系数据库](https://www.cnblogs.com/linfangnan/p/16660258.html)有提到过，**候选码**是它的值能唯一地标识一个元组，而其子集不能标识的属性组。<br />由于其他求法我都没看懂，所以只介绍快速判断方法。先计算函数依赖集 F 的最小函数依赖集，然后采用快速判定法，以及候选键的定义来确定候选键。对于给定的关系 R(U, F)，可将其属性分为四类：
| **属性类别** | **说明** |
| --- | --- |
| L 类 | 仅出现在函数依赖集 F 的左部的属性 |
| R 类 | 仅出现在函数依赖集 F 的右部的属性 |
| LR 类 | 在函数依赖集 F 的左右两边均出现的属性 |
| N 类 | 在函数依赖集 F 的左右两边均未出现的属性 |
快速求解候选码的一个充分条件是，对于给定的关系模式 R(U, F)，X∈U：
1. 若 X 是 R 的 L 类属性，则 X 必为 R 的任一候选码中的属性；
2. 若 X 是 R 的 R 类属性，则 X 必不在 R 的任一候选码中；
3. 若 X 是 R 的 N 类属性，则 X 必为 R 的任一候选码中的属性。
快速求解候选码过程：
1. 将 R 的所有属性分为 L、R、N 和 LR 四类，并令 X 代表 L、N 两类，Y 代表 LR 类；
2. 求属性集闭包 X+，若 X+ 包含了 R 的全部属性则 X 即为 R 的唯一候选码，转(5)；
3. 在 Y 中取一属性 A，求属性集闭包(XA)+，若(XA)+包含了 R 的全部属性，则转(4)；否则调换一属性反复进行这一过程，直到试完所有 Y 中的属性；
4. 如果已找出了所有的候选码，则转(5)；否则在 Y 中依次取 2个、3个、…… 属性，求 X 与它们的属性集闭包，直到其闭包包含 R 的全部属性；
5. 停止，输出结果。
<a name="XvO6l"></a>
## 样例
<a name="INL3E"></a>
### 样例一
设有关系模式 R(M, N, X, Y)，其函数依赖集 F={Y→N, N→Y, MY→N, MX→Y}，求 R 的所有候选键。

Left：{M, X} LR：{N, Y} Not：{} 因为对 {Left，Not}F+=R，所以{M，X}是 R 的所有候选键。

<a name="vXZ8l"></a>
### 样例二
设有关系模式 R(U, F)，其中 U={M, N, X, Y, Z, P}，F={M→N, X→Y, Z→ M ,XZ→Y}，试求此关系的候选键。

Left：{X，Z} LR：{M} Not：{P} 因为对{Left，Not}F+=R，所以{X, Z, P}是 R 的所有候选键

<a name="DIhLH"></a>
### 样例三
设关系模式 R(S, D, I, B, O, Q)，其函数依赖集 F={S→D, I→B, B→O, O→Q, Q→I}，求 R 的所有候选码。

Left：{S} LR：{I, B, O, Q} Not：{}

因为S+=SD，所以 S 不是 R 的候选码； 因为(SI)+=SIDBOQ，所以 SI 是一个候选码； 因为(SB)+=SBDOQI，所以 SB 是一个候选码； 因为(SO)+=SODQIB，所以 SO 是一个候选码； 因为(SQ)+=SQDIBO，所以 SQ 是一个候选码。 ```

参考资料

《数据库系统概论(第5版)》，王珊 萨师煊 编著，高等教育出版社