从理论层面讨论关系型数据库的设计。本文主要讨论如何化简BC范式。
关系型数据库最重要的就是 关系二字,而关系常常要存在约束,函数依赖就是一个最常见的约束。
函数依赖(FD)
定义
定义:若关系R的两个元组在属性A1,A2,…,An上一致(即对应分量值相等),那么它们必定在其他属性B1,B2,…,Bm上也一致。
记为A1,A2,…,An一>B1,B2,…,Bm,称为A1,A2,…,An函数决定 B1,B2,…,Bm。
等价于
A1,A2,…,An一>B1
A1,A2,…,An一>B2
…
A1,A2,…,An一>Bm
若关系R上的每个实例都能使一个给定的FD为真,则称R满足 函数依赖f
关系的键
若满足下列条件,则认为一个/多个属性集{ A1,A2,…,An}是关系R的键:
- 这些属性 函数决定 关系的所有其他属性。<==> R中不可能有两个不同元组具有相同的 A1,A2,…,An值。
- 在{ A1,A2,…,An}的真子集中,没有一个能函数决定R的所有其他属性。键必须是最小的!
当键只有一个属性A时,称A为键
一个关系可能有多个键,通常需要设置一个主键。(primary key)
超键
即键的超集
,因此每个键都是超键.
函数依赖的规则
即假设已知道关系满足一些FD集合,如何通过已知FD推导出其他存在的FD。
对FD集合S和T,若关系实例集合满足S于其满足T的情况一样,就认为S和T等价
若满足T中所有FD的每个关系实例也满足S中所有的FD,则认为S是从T中推断而来的
分解/结合规则
分解规则:
使用FD集合: A1,A2,…,An一>Bi(i=1,2,…,m)替换FD集合:A1,A2,…,An一>B1,B2,…,Bm。
组合规则:
使用FD集合:A1,A2,…,An一>B1,B2,…,Bm替换FD集合: A1,A2,…,An一>Bi(i=1,2,…,m)。
平凡函数依赖规则
若关系上的一个约束对所有关系实例都成立,且与其他约束无关,则称其为平凡的
。
即平凡FD右边是左边的子集
平凡函数依赖规则:
A1,A2,…,An一>B1,B2,…,Bm等价于A1,A2,…,An一>C1,C2,…,Ck
C是在集合B中而不在A中的属性
传递规则
若关系R中有FD:A1,A2,…,An一>B1,B2,…,Bm 和B1,B2,…,Bm 一>C1,C2,…,Ck 都成立,那么A1,A2,…,An一>C1,C2,…,Ck 在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算法
应用:
-
使用闭包算法可以用来判断任一给定的FDA1,A2,…,An一>B是否可以由FD集合推导出来。
只要计算FD集合计算闭包,若B在闭包中,则可以根据FD集合推导出来。
-
使用闭包算法判断属性集合是否是键,只有当A1,A2,…,An 是超键时,其闭包才会包括所有属性。
若要验证A1,A2,…,An是否是键,则先求闭包,看是否包含了所有属性,再检查
最小性
。
FD的闭包
有些情况下,需要使用FD集合来表示一个关系的完全FD集合。但因为FD集合中等价的集合太多(基本集太多)。为了避免基本集激增,只考虑右边为单一属性的基本集。
最小化基本集:
- B中所有FD的右边均为单一属性
- 从B中删除任何一个FD后,该集合不再是基本集
- 对B中任何一个FD,若从其左边删除一个或多个属性,B将不是基本集
无平凡FD
Armstrong公理
判断FD能否从已知FD集合推断出了,除了闭包算法,也可以使用该公理
-
自反律
若{B1,B2,…,Bm}⊆{A1,A2,…,An} 则 A1,A2,…,An一>B1,B2,…,Bm
即平凡FD
-
增广律
若A1,A2,…,An一>B1,B2,…,Bm
则A1,A2,…,AnC1,C2,…,Ck 一>B1,B2,…,BmC1,C2,…,Ck ,对于任何属性集合C1,C2,…,Ck都成立
-
传递律
若有A1,A2,…,An一>B1,B2,…,Bm 和B1,B2,…,Bm 一>C1,C2,…,Ck 都成立,那么A1,A2,…,An一>C1,C2,…,Ck 也成立
投影函数依赖
如何根据已有的关系R和他的FD集合S, 得到R的投影 R1=πL®的FD集合?
原则上可以通过集合S进行推断,找到只包含R1的属性,但这样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 A1,A2,…,An一>B1,B2,…,Bm成立则{A1,A2,…,An} 是关系R的键
也就是说,每个非平凡FD的左边都必须是超键
二元关系一定是BCNF
分解为BCNF
策略:
-
找到违反BCNF的非平凡FD A1,A2,…,An一>B1,B2,…,Bm.
-
尽可能地向FD右边增加由A1,A2,…,An决定的属性(可以减少工作量)
-
将属性集合分为两个关系模式。
一个包含了上述FD的所有属性,另一个包含该FD左边属性和不属于该FD的所有属性
-
再找到这两个关系模式的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)