前言
一个设计良好的数据库模式（database schema），应该要具备以下特点：
- 完整性（Completeness）
- 减少冗余（Redundancy freeness）
- 一致的含义（Consistent understanding）
- 良好的性能（Performance）
一个设计不好的数据库模式，可能会出现以下的问题：
- 数据不一致
- 数据冗余
- 更新异常
为什么需要函数依赖（Why Functional Dependencies）
函数依赖（FD）可以以一种正式的方式来定义关系型数据库的“好（goodness）”与“坏（badness）”。函数依赖的设计一般有两种：
- 自上而下（Top down）：从一个大的关系模式和 FD 出发，在这基础上按照确切的正规形式产生较小的数据模式。
- 自下而上（Bottom up）： 从属性和 FD 出发，逐步产生数据模式（现实中不常用）。
定义
一个数据库 R 的一组 FD 可以表示成： X → Y，其中 X 和 Y 是数据库 R 中的两组属性集合，其含义是：对于 R 中的任意两个元组，只要他们的在集合 X 中的属性相等，那么他们在集合 Y 中的属性也相等。这里 X 称为决定因素（Determinant）, Y 称为被决定因素（Dependant）。
在现实应用中，FD 为数据库明确约束，而且该约束在任何时候都需要保证成立。一般常使用以下两种方法来确定某个数据库的函数依赖：
- 分析数据需求
- 分析样本数据
举个例子：
| A | B | C | D | E |
|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 |
| 1 | 2 | 2 | 2 | 2 |
| 1 | 2 | 3 | 2 | 3 |
| 2 | 2 | 2 | 4 | 4 |
对于以下的函数依赖：
- ABC → AB （√）
- A → B （√）
- ABC → D （×）
- E → ABCD （√）
阿姆斯特朗推理法则（Armstrong‘s Inference Rules）
反身法则（Reflexive rule）： XY → Y
增广法则（Augmentation rule）： { X → Y } |= { XZ → YZ }
传递法则（Transitive rule）： { X → Y， Y → Z } |= { X → Z }
其中，公式 ∑ |= X → Y 表示函数依赖 X → Y 可以通过集合 ∑ 中的函数依赖推理得出。
在阿姆斯特朗推理法则的基础上，我们进一步衍生出一些实用的法则：
- 合并律（Union rule）： { X → Y， X → Z } |= { X → YZ }
- 分解律（Decomposition rule）： { X → YZ } |= { X → Y， X → Z }
隐含的函数依赖
想要设计一个好的数据库，我们需要考虑到所有的函数依赖，包括一些隐含的函数依赖。我们常用 ∑* 表示由函数依赖集合 ∑ 所隐含的所有可能的函数依赖。
我们规定：如果 ∑1* = ∑2，那么 ∑1 和 ∑2 是等价的。意思就是，∑1 和 ∑2 可以不相同，只要他们对应的 ∑ 是相等的，我们就可以认为这两个函数依赖集合的等价的。
通过一个属性 X 集合推理出来的所有属性集合，称之为该属性 X 的闭包（Closure），记作 X+。所以我们可以这么表示：
Σ |= X → W 等价于 W ⊆ X+
例如，一个数据库 R = {A, B,C,D, E, F} 具有一下的函数依赖集合：Σ = { AC → B, B → CD,C → E, AF → B }。要判断 Σ |= AC → DE 是否成立。我们首先需要找到属性 AC 的闭包：
(AC)+ ⊇ AC 初始化
⊇ ACB 根据依赖 AC → B
⊇ ACBD 根据依赖 B → CD
⊇ ACBDE 根据依赖 C → E
= ACBDE
其中，我们发现 DE ⊆ (AC)+，所以 Σ |= AC → DE 是成立的。
函数依赖的最小覆盖（Minimal cover）
通过定义函数依赖的最小覆盖，我们可以直接通过最小覆盖推理出数据库的所有函数依赖。一个函数依赖的最小覆盖具有以下特点：
- Σm 与 Σ 是等价的。其中 Σm 是最小覆盖，Σ 是数据库给定的函数依赖集合；
- Dependant：最小覆盖的每一条函数依赖，其右侧只存在单个的属性；
- Determinant：最小覆盖的每一条函数依赖，其左侧可以存在多个属性；
- 任何冗余的函数依赖都会被移除。
通过 FD 寻找键
在一个数据库中，一定存在这样的函数依赖关系： K → R ， 其中 K 是超键，R 是该数据库所有属性的集合。
算法
输入：数据库 R 的 FD 集合 ∑。
输出：数据库 R 所有超键的集合。
步骤：
对于数据库 R 的每一个属性集合的子集 X，计算它的闭包 X+；
如果 X+ = R，那么 X 就是一个超键；
如果不存在 X 的真子集 Y 满足 Y+ = R，那么 X 就是候选键（主键）。
在这个部分，我们把在候选键中出现的所有属性称为主要属性（Prime attribute），其余的属性则称为非主要属性（Non-prime attributes）。
在寻找候选键的过程中，有一些比较好用的小技巧：
- 如果一个属性从来没有出现在任何 FD 的右侧，那么它肯定是候选键的一部分；
- 如果一个属性从来没有出现在任何 FD 的左侧，但它出现在某个 FD 的右侧，那么它肯定不是候选键的一部分；
- 如果某个集合 X 的真子集是候选键，那么 X 肯定不是一个候选键。
网友评论