关系数据库设计理论

从理论层面讨论关系型数据库的设计。本文主要讨论如何化简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的投影 R1L®的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

策略:

  1. 找到违反BCNF的非平凡FD A1,A2,…,An一>B1,B2,…,Bm.

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

  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)

上一篇:剑指 Offer 16. 数值的整数次方


下一篇:p4各个组件之间的关系