上小旺老师的课没听懂，是我太菜了……

从理论层面讨论关系型数据库的设计。本文主要讨论如何化简BC范式。

关系型数据库最重要的就是 关系二字，而关系常常要存在约束，函数依赖就是一个最常见的约束。

函数依赖(FD)

定义

定义：若关系R的两个元组在属性A1,A2,…,An上一致(即对应分量值相等)，那么它们必定在其他属性B1,B2,…,Bm上也一致。

记为A₁,A₂,…,A_n一>B₁,B₂,…,B_m，称为A₁,A₂,…,A_n 函数决定 B₁,B₂,…,B_m。

等价于

A₁,A₂,…,A_n一>B₁

A₁,A₂,…,A_n一>B₂

……

A₁,A₂,…,A_n一>B_m

若关系R上的每个实例都能使一个给定的FD为真，则称R满足 函数依赖f

关系的键

若满足下列条件，则认为一个/多个属性集{ A₁,A₂,…,A_n}是关系R的键：

• 这些属性 函数决定 关系的所有其他属性。<==> R中不可能有两个不同元组具有相同的 A₁,A₂,…,A_n值。
• 在{ A₁,A₂,…,A_n}的真子集中，没有一个能函数决定R的所有其他属性。键必须是最小的！

当键只有一个属性A时，称A为键

一个关系可能有多个键，通常需要设置一个主键。(primary key)

超键

即键的超集，因此每个键都是超键.

函数依赖的规则

即假设已知道关系满足一些FD集合，如何通过已知FD推导出其他存在的FD。

对FD集合S和T，若关系实例集合满足S于其满足T的情况一样，就认为S和T等价

若满足T中所有FD的每个关系实例也满足S中所有的FD，则认为S是从T中推断而来的

分解/结合规则

分解规则：

使用FD集合： A₁,A₂,…,A_n一>B_i(i=1,2,…,m)替换FD集合：A₁,A₂,…,A_n一>B₁,B₂,…,B_m。

组合规则：

使用FD集合：A₁,A₂,…,A_n一>B₁,B₂,…,B_m替换FD集合： A₁,A₂,…,A_n一>B_i(i=1,2,…,m)。

平凡函数依赖规则

若关系上的一个约束对所有关系实例都成立，且与其他约束无关，则称其为平凡的。

即平凡FD右边是左边的子集

平凡函数依赖规则：

A₁,A₂,…,A_n一>B₁,B₂,…,B_m等价于A₁,A₂,…,A_n一>C₁,C₂,…,C_k

C是在集合B中而不在A中的属性

传递规则

若关系R中有FD：A₁,A₂,…,A_n一>B₁,B₂,…,B_m 和B₁,B₂,…,B_m 一>C₁,C₂,…,C_k 都成立，那么A₁,A₂,…,A_n一>C₁,C₂,…,C_k 在R中也成立。

可以使用闭包来验证

属性的闭包

算法 3.7

Input: 属性集合{A1,A2,...,An}，FD集合S
Output: 闭包{A1,A2,...,An}+

1. 如果必要，分解S中的FD，使每个FD右边只有一个属性
2. 设X为最后输出(闭包)。初始化为{A1,A2,...,An}
3. 反复寻找FD:B1B2...Bm —> C, s.t B1B2...Bm在X中且C不在X中;
   若找到，则将C加入X，并重复该步骤。
   当最终X不能再加入任何元素后，本步骤结束
4. 得到结果X

很像Dijkstra算法

应用：

• 使用闭包算法可以用来判断任一给定的FDA₁,A₂,…,A_n一>B是否可以由FD集合推导出来。

  只要计算FD集合计算闭包，若B在闭包中，则可以根据FD集合推导出来。

• 使用闭包算法判断属性集合是否是键，只有当A₁,A₂,…,A_n 是超键时，其闭包才会包括所有属性。

  若要验证A₁,A₂,…,A_n是否是键，则先求闭包，看是否包含了所有属性，再检查最小性。

FD的闭包

有些情况下，需要使用FD集合来表示一个关系的完全FD集合。但因为FD集合中等价的集合太多(基本集太多)。为了避免基本集激增，只考虑右边为单一属性的基本集。

最小化基本集：

• B中所有FD的右边均为单一属性
• 从B中删除任何一个FD后，该集合不再是基本集
• 对B中任何一个FD，若从其左边删除一个或多个属性，B将不是基本集

无平凡FD

Armstrong公理

判断FD能否从已知FD集合推断出了，除了闭包算法，也可以使用该公理

• 自反律

  若{B₁,B₂,…,B_m}⊆{A₁,A₂,…,A_n} 则 A₁,A₂,…,A_n一>B₁,B₂,…,B_m

  即平凡FD

• 增广律

  若A₁,A₂,…,A_n一>B₁,B₂,…,B_m

  则A₁,A₂,…,A_nC₁,C₂,…,C_k 一>B₁,B₂,…,B_mC₁,C₂,…,C_k ，对于任何属性集合C₁,C₂,…,C_k 都成立

• 传递律

  若有A₁,A₂,…,A_n一>B₁,B₂,…,B_m 和B₁,B₂,…,B_m 一>C₁,C₂,…,C_k 都成立，那么A₁,A₂,…,A_n一>C₁,C₂,…,C_k 也成立

投影函数依赖

如何根据已有的关系R和他的FD集合S, 得到R的投影 R₁=π_L(R)的FD集合？

原则上可以通过集合S进行推断，找到只包含R₁的属性，但这样emmm未免太麻烦。

算法3.12

Input: 关系R和投影得到的R1,以及在R中成立的FD集合S
Output: 在R1中成立的FD集合S

1. 设T为最终输出，T初始化为∅
2. 对于R1属性的每一个子集X，根据FD集合S计算X+。
   对所有在X+中且属于R1的属性A，将非平凡FD: X—>A添加到T中
3. 现在T为在R1成立的FD基本集，但不是最小化基本集。用下列方法构造最小化基本集
   a. 若T中某FD F可通过其他FD推断出来，则从T中删除F
   b. 若Y—>B在T中，且Y至少有两个属性，从Y中删除一个属性改为Z.
   	  若Z->B可以被推断出来，则用Z->B替换Y->B
   C. 以各种方式执行ab直到T不再变化。

emmm，这算法就挺麻烦的。

BC范式

啊，前面说了那么多就是为了引出BC范式。

首先来看为什么要有BC范式

因为我们在设计数据库时，当你试图在一个关系中包含过多信息是，就会产生 异常，例如：

• 冗余
• 更新异常
• 删除异常

而我们一般使用 分解关系的方法来消除异常，BC范式就是一个确保异常不存在的条件！

定义

BC范式，即BCNF

关系R属于BCNF iff 如果R中非平凡FD A₁,A₂,…,A_n一>B₁,B₂,…,B_m成立则{A₁,A₂,…,A_n} 是关系R的键

也就是说，每个非平凡FD的左边都必须是超键

二元关系一定是BCNF

分解为BCNF

策略：

1. 找到违反BCNF的非平凡FD A₁,A₂,…,A_n一>B₁,B₂,…,B_m.

2. 尽可能地向FD右边增加由A₁,A₂,…,A_n决定的属性(可以减少工作量)

3. 将属性集合分为两个关系模式。

   一个包含了上述FD的所有属性，另一个包含该FD左边属性和不属于该FD的所有属性

4. 再找到这两个关系模式的FD集合，判断是否为BCNF，若是则结束。若不是则对该FD再1执行上述操作。

算法3.20

BCNF分解算法

Input: 关系R0和其FD集合 S0
Output: 由R0分解出的关系集合，旗帜每个关系集合都属于BCNF

1. 检验R是否属于BCNF，若是，则直接返回{R}
2. 若存在BCNF违例，假设为X->Y。
   使用算法3.7计算X+，选择R1=X+为一个关系列表。
   使用另一个关系列表R2包含X及不在X+中的属性
3. 使用算法3.12计算R1和R2的FD集合，分别即为S1,S2
4. 使用本算法递归地分解R1,R2.最后返回分解的集合

Example

R(A,B,C,D) FD: AB->C、C->D、D->A

对{A,B,C,D}各个子集求闭包

{A}+={A}, {B}+={B}, {C}+={C,D,A}, {D}+={D,A}

{A,B}+={A,B,C,D}, {A,C}+={A,C}, {A,D}+={A,D},{B,C}+={A,B,C,D}, {B,D}+={A,B,C,D}

可以得到 AB, BC, BD 都是键，所以无需继续求闭包了(都是超键)

FD集合中：C->D, D->A不是BCNF

选择C->D

将属性划分为(A,D,C) 和(B,C)

可知(B,C)一定属于BCNF(二元关系一定是)

现在求(A,D,C)的FD集合，使用算法3.12

FD为： C->D, D->A

且(A,D,C)中C为键，

所以D->A违反BCNF,所以(A,D,C)不属于BCNF

将(A,D,C)分为

(A,D), (C,D)为BCNF(二元关系一定是)

所以分解为：(B,C) (A,D) (C,D)