什么是函数依赖

定义：
对于具有多个属性的关系模式 R，如果对于属性集合中的两个子集 A 和 B 和任意的关系 r，r 中不可能出现两个记录使得 A 中的值相等而 B 中的值不等，则称 A 函数决定 B，B 函数依赖于 A，记作 A→B。

另一种说法是，如果将 A 和 B 单独拿出来做一个关系，这个关系中 A 可以作为主键。

性质：
有些函数依赖关系中 B⊆A，这种称为是 平凡 的函数依赖，反之为不平凡的函数依赖。

即使两个属性之间存在函数依赖关系，即 A→B，这不意味着 A 和 B 不能在关系的多条记录中出现。

两个属性子集可能相互函数依赖。

如果关系中，A 上没有相同的两个记录出现，那么任意属性子集都函数依赖于 A。

有基于 模式 的函数依赖，要求对所有可能的关系都成立；也有基于 关系 的函数依赖，只要求对这一个关系成立即可。

部分函数依赖与完全函数依赖

如果 A→B，但是存在 A 的真子集 A’ 使得 A′→B，则称 B 部分函数依赖 于 A。如果不存在这样的子集，此时为 完全函数依赖。

传递函数依赖

函数依赖关系具有传递性：A→B,B→C⇒A→C。

如果加上一些更强的限制：A→B 和 B→C 都是非平凡的，且 C⊈A，BA，则称 C 传递函数依赖 于 A。

函数依赖相关的几个重要概念

把数据库中的相关概念用函数依赖理论重新定义了一下：

候选键：能够 完全决定 关系模式中所有属性的属性组称为关系模式上的 候选键。

主键：对于一个关系模式，可以选取其任意一个候选键作为 主键。

主属性：包含于任意一个候选键中的属性称为 主属性，否则为 非主属性。

超键：超键和候选键类似，但是移除了完全决定的限制。超键是某个候选键对应属性集的超集。

外键：某个属性组不是当前关系模式的候选键，但是是另一个关系模式的候选键，称为当前关系模式的 外键。

其它的一些概念：

逻辑蕴涵：设 F 是关系模式 R 上函数依赖关系的集合（不一定是完整的）。对于 R 的两个属性组 A 和 B，如果从 F 中能够推理出 A→B，则称 F 逻辑蕴涵 A→B，记作 F⊨A→B。

闭包：设 F 是关系模式 R 上函数依赖关系的集合（不一定是完整的）。F 逻辑蕴涵的所有函数依赖关系构成的集合称为 F 的闭包。

可以看到，函数依赖是属性集子集上的一个关系，起码它是传递、自反的。

关于函数依赖的 Armstrong 公理

Armstrong 公理

Armstrong 公理一共有三条，可以用来从函数依赖关系集合中发现新的函数依赖关系。

这一小节使用 X、Y、Z 作为属性组；U 作为属性全集；F 作为某个函数依赖关系的集合。

Armstrong 公理对应的引理

从上述公理出发可以引出下面四条定理（为了方便就不写 ∈F 以及 F⊨ 了）：

什么是属性（集）闭包

设 F 是函数依赖关系的集合，X 是一个属性组。能够从 F 推导出的所有依赖于 X 的属性构成的集合称为 X 关于 F 的属性闭包，记作 。

属性闭包的计算算法与覆盖及其证明

函数依赖关系的集合称为 函数依赖集。

函数依赖集的等价性：
如果两个函数依赖集的闭包相等，则这两个函数依赖集是 等价的。此时称其中一个函数依赖集 覆盖 另一个函数依赖集。

如何计算属性闭包：
可以按照如下循环不断进行，直到序列稳定。假定要求的是 X 在 F 下的属性闭包：

这样可以求出
。

最小覆盖及其构造

对于一个函数依赖集 F，如果和它等价的函数依赖集 F’ 满足下面三个条件，则称为是 F 的最小覆盖（也叫 最小依赖集）：