数据库系统笔记5-Relational Database Design 关系型数据库的设计

发表于 | 分类于

函数依赖 Functional Dependencies

给定一个关系模式r(R)的实例，那么这个实例满足函数依赖α→β的条件是：

对实例中的所有元组对，若t1[α]=t2[α]，则t1[β]=t2[β]

如果r(R)在每个合法实例legal instance上都满足函数依赖α→β，则称函数依赖在模式r(R)上成立Hold

例如一个关系r(A,B)的一个实例如下

A B
1 4
1 5
3 7

那么在这个实例上，函数依赖A→B不成立，但是B→A成立

  • 当且仅当if and only ifK→R时，K是关系模式R的一个超键
  • 若所有关系都满足一个函数依赖，则称这么函数依赖是平凡的Trivial，一般上，β⊆α则α→β这个函数依赖是平凡的

函数依赖的使用

  • 检验关系在指定的函数依赖F下是否合法
  • 在合法的关系中确定约束

即便一个函数依赖在一个关系的所有合法实例上不都成立，这个关系的一个具体实例也可能满足这个函数依赖

闭包 Closure

给定一组函数依赖F，其他的函数依赖是由这一组函数依赖的逻辑蕴含logical imply，那么所有由F实现的函数依赖称为F的闭包Closure

将F的闭包标识为F+，F+是F的超集

Boyce-Coddy 范式 BCNF

具有函数依赖集F的关系模式R是BCNF的条件是：

对F+中所有形如α→β的函数依赖，至少有一项成立：

  1. α→β是平凡的函数依赖（β⊆α）
  2. α是模式R的一个超码

函数依赖的闭包

关系模式r(R)的每一个满足F的实例也满足f，则R上的函数依赖f被r上的函数依赖集F逻辑蕴含logical imply，所有被函数依赖集F逻辑蕴含的函数依赖称为F的闭包Closure，表示为F+

例如给定关系模式r(A,B,C,G,H,I)以及函数依赖A->B,A->C,CG->H,CG->I,B->H；则函数依赖A->H被逻辑蕴含。

寻找F的所有F+的三条规则（Armstrong公理 Armstrong’s Axioms）

  • 自反律 reflexivity 若β⊆α，则α→β成立
  • 增补律 augmentation 若α→β，则γα→γβ成立
  • 传递律 transitivity 若α→β，β→γ，则α→γ成立

这三条规则都是：

  • 可靠的 Sound
  • 完备的 Complete

另外还有额外三条规则：

  • 合并律 union 若α→β，α→γ，则α→βγ成立
  • 分解率 decomposition 若α→βγ，则α→β，α→γ成立
  • 伪传递律 pseudotransitivity 若α→β，βγ→σ，则αγ→σ成立

计算F+的步骤

1
2
3
4
5
6
7
F+=F
  do
    for each f in F+:
      f上应用自反率并将结果加入到F+
    for each (f1,f2) in F+:
      if (f1,f2)可以使用传递率结合，则将结果加入到F+
  while(F+结果变化)

属性集的闭包

给定一个属性α集，则函数依赖集F下属性α所确定的的所有属性的集合称为F下α的闭包：

计算α+的步骤

1
2
3
4
5
result=α
do
  for each β→γ in F
    若 β⊆result 则 result=result∪γ
while(result有变化)

属性闭包的使用

  • 检验超键
  • 检验函数依赖
  • 计算F的闭包

检验BCNF

简单的检验方法：

  • 检验平凡的函数依赖α→β是否违反BCNF，计算α+并验证它是否包含R中的所有属性，即验证它是否是R的超码
  • 检验关系模式R是否属于BCNF，仅需要检验函数依赖集F是否违反了BCNF，而不需要检验F+

关系分解时，只使用F来判断就不再适用，判断R分解后的Ri是否满足BCNF：

对与Ri中属性的每一个子集α，确保α+要么不包含Ri-α，要么包含Ri的全部属性，即Ri没有违反BCNF

无损分解 Lossless Decomposition

r(R)是一个关系模式，F是r(R)上的函数依赖集，令R1，R2是关系模式R的分解，若用两个关系模式r1(R1),r2(R2)来替代r(R)时没有信息损失，则称之为无损分解Lossless Decomposition

BCNF的分解算法

1
2
3
4
5
6
7
8
9
10
11
result={R}
done=false
计算F+

while(not done) do
  if result 中存在模式不满足BCNF
    then
      令 α→β是一个在Ri上成立的非平凡函数依赖，满足α→Ri不属于F+，且α∩β=Ø
      result=(result-Ri)∪(Ri-β)∪(α,β)
    end
  else done=true

保持依赖 Dependency Preservation

对关系R进行分解时，R的函数依赖集也进行相应的分解，若分解后的总函数依赖集与原来的函数依赖集保持一致，则称为依赖保持

保持依赖的验证

对每一个函数依赖α→β：

1
2
3
4
5
6
result=α
do 
  for each Ri in decomposition
    t=(result∩Ri)+∩Ri
    result=result∪t
while(result有变化)

若result包含β的中的所有属性，则函数依赖α→β保持，当且仅当上述过程中F的所有依赖都被保持时分解是保持依赖的

BCNF的保持依赖

第三范式 3NF

对于F+所有的函数依赖α→β至少有一项成立：

  • α→β是一个平凡函数依赖
  • α是R的一个超码
  • β-α中的每一个属性A都包含在R的一个候选码中

若关系满足BCNF则一定也满足3NF，BCNF成立两个条件之一为上面的前两条

检验3NF

…

正则覆盖 Canonical Cover

没有多余依赖redundant dependencies的函数依赖集例如在{A->B,B->C}这一依赖集中，若出现了A->C则这个函数依赖是多余的依赖

无关属性 Extraneous Attributes

若去除函数依赖集中的一个属性不改变该函数依赖集的闭包，则这个属性是无关属性

  • 例题计算正则覆盖：R = (A, B, C),F = {A → BC,B → C,A → B,AB → C}
  1. 合并{A→BC,A→B}为A→BC则得到{A→BC,B→C,AB→C}
  2. A在AB→C中是无关属性，得到{A→BC,B→C}
  3. C在A→BC中数无关的，得到{A→B,B→C}

3NF的分解算法

1
2
3
4
5
6
7
8
9
10
令Fc为F的正则覆盖
i=0
for each α→β in Fc
  if 模式Rj,j=1,2...i 都不包含α，β
    i=i+1
    Ri=αβ
  if 模式Rj,j=1,2...i 都不包含R的候选码
    i=i+1
    Ri=R的任意候选码
return (R1...Ri)

BCNF和3NF的比较

…

数据库设计目标

  • BCNF
  • Lossless Join
  • Dependency Preservation