7.1 关系模式规范化的必要性

数据冗余一直是影响系统性能的大问题。“分解”是解决冗余的主要办法。
(1) 冗余存储
(2) 更新异常：重复信息的一个副本修改时，所有副本必须进行同样修改，否则造成不一致。
(3) 插入异常：只有当一些信息事先已经存储在数据库中时，另一些信息才能存入到数据库中。
(4) 删除异常：在删除某些信息时可能丢失其他信息。

7.2 函数依赖

关系模式中的各个属性之间相互联系、相互制约的联系称为数据依赖。数据依赖一般分为函数依赖、多值依赖和连接依赖。

1. 函数依赖的定义

设R(U)是属性集U上的关系模式。X，Y是U的子集。若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称X函数确定Y或Y函数依赖于X，记作X → Y。

2. 函数依赖的分类P217

”如果 Y⊆X⊆U， 则 X→Y。“称为平凡依赖。否则称为非平凡依赖，若无特别声明，我们总是讨论非平凡依赖。

  • 完全函数依赖：在关系模式R(U)中，X，Y是U的子集，X’是X的真子集，存在X→Y，但对每一个X’都有X’!→Y，则称Y完全函数依赖于X。
  • 部分函数依赖：在关系模式R(U)中，X，Y是U的子集，存在X→Y，若X’是X的真子集，存在X’→Y，则称Y部分函数依赖于X。
  • 传递函数依赖：在关系模式R(U)中，X，Y，Z是U的子集，存在X→Y(Y∉X)，Y !→X，Y→Z，则有X→Z，称Z传递函数依赖于X。

在此加上条件Y!→X，是因为如果X→Y，Y→X，则X↔Y，实际上就是X直接函数依赖于Z，而不是传递函数依赖。

3. 函数依赖和键的联系

函数依赖是键的推广

  • 设关系模式R的属性集是U，K为U的一个子集。如果K→U在R上成立，则称K为R的一个超键。
  • 如果K→U在R上成立，但对于K的任一真子集K’都有K’→U不成立，那么称K是R上的一个候选键。
  • 关系模式R中的属性或属性组X并非R的主键，但X是另外一个关系模式S的主键，则称X是R的外键。

4. 函数依赖的逻辑蕴含

仅仅考虑函数依赖集是不够的，需要考虑模式上成立的锁于函数依赖。对于给定的函数依赖集F，可以推导出其他一些未知的函数依赖，称这些函数依赖被F“逻辑蕴含”。

设F是在关系模式R上成立的函数依赖的集合，X→Y是一个函数依赖。如果对于R的每个满足F的关系r也满足X→Y(即r中的任意两个元组t，s，若t1[X]=t2[X]，则t1[Y]=t2[Y])，则称F逻辑蕴含X→Y。

5. 函数依赖的推理规则

  • 阿姆斯特朗公理

  • 自反律/包含规则: 如果 Y⊆X⊆U， 则 X→Y。(X→Y 是平凡依赖)

  • 增广律: 如果 X → Y， 且Z⊆X，则 XZ → YZ。

  • 传递率: 如果 X → Y 且 Y → Z, 则 X → Z

  • 阿姆斯特朗公理的推理

  • 合并规则: 如果 X→Y 且 X→Z, 那么 X→YZ.

  • 分解规则: 如果 X → YZ,且 X → Y 且 X → Z.

  • 伪传递: 如果 X→Y 且 WY→Z, 那么 XW → Z.

  • 集合累积规则: 如果 X → YZ 且 Z→W, 那么 X → YZW.

  • 阿姆斯特朗公理是有效的和完备的

  • 有效性：在F中根据阿姆斯特朗公理推导出的每一个函数议定为F所逻辑蕴含。

  • 完备性：F所逻辑蕴含的每一个函数，必定可以可以由F出发根据阿姆斯特朗公理推导出来。

6. 函数依赖集的闭包和属性集的闭包(概念，不考怎么计算F的闭包)

  • 函数依赖集的闭包：F是函数依赖集，F的闭包(closure)是指被F逻辑蕴涵的所有函数依赖的集合，记做F + 。
  • 属性集的闭包：设F为属性集U上的一组函数依赖，X是U的子集，那么属性集X的闭包用X + 表示，它是一个从函数依赖集使用FD(函数依赖)推理规则推出的所有满足X→A的属性A的集合：
    X + = { A | X → A 在 F + 中}

7. 函数依赖的最小依赖集

  • 如果G + = F +，就说函数依赖集F覆盖G(F是G的覆盖，G是F的覆盖)，F与G等价。
  • 如果函数依赖集F满足以下条件，则称F为最小函数依赖集或最小覆盖。
  • F中任一函数依赖的右部仅含一个属性。
  • F中不存在这样的函数依赖X → A，使得 F与F -｛X → A｝等价。
  • F中不存在这样的函数依赖 X → A，X有真子集 Z 使得 F-｛ X → A｝ ∪ ｛ Z → A｝与 F等价。(左边没有多余)

每个依赖都尽可能的小，左边的属性没有多余，右边为单属性，且其中的每个依赖都是必要的。

7.3 关系模式的分解

模式分解的规则

设关系模式R(U)，R1, R2…, Rk都是R的子集(这里把关系模式看成是属性的集合)，R＝R1 ∪ R2 ∪ … ∪ Rk，关系模式R1, R2…, Rk的集合用ρ表示，ρ={R1, R2…, Rk}。用ρ代替R的过程称为关系模式的分解。这里称为R的一个分解，也成为数据库模式。

无损连接分解

设R是一个关系模式，F是R上的一个函数依赖集合。R的一个分解是一个关系集合ρ={R1, R2…, Rk}，如果对R中满足F的每一个关系r，有：r = πR1(r) ⋈ πR2(r) ⋈ … ⋈ πRk(r)，那么称分解ρ相当于F是无损连接分解；否则，称为有损连接分解。

其中 πRi(r) 表示关系 r 在模式 Ri 属性上的投影。

(考试：给出分解，用定理判断)
如果R为一个关系模式，F是R上的函数依赖集。令R1 和R2为R的分解。该分解为R的无损连接分解的条件是：F+中至少存在如下函数依赖中的一个

  • R1 ∩ R2 → R1
  • R1 ∩ R2 → R2

即，R1 和 R2 的公有属性能确定R1或R2。
换句话说，R1 ∩ R2是R1或R2的超键，R上的分解就是无损分解。我们可以用属性闭包的方法来有效的检验超键。P225 例7.16

保持函数依赖的分解

设R是具有属性U和函数依赖集合F的关系模式，ρ={R1, R2…, Rk}为R的一个分解，如果πRi(F)(i = 1, 2, …, k)的并集逻辑蕴含F中的全部函数依赖，则称分解ρ具有函数依赖保持性。

设关系模式R(A, B, C, D)，函数依赖集F = {A → B, B → C, B → D, C → A}，分解为ρ = { R1(AB), R2(ACD) }。检验分解的无损连接性和分解的函数依赖保持性。

由于R1 ∩ R2 = AB ∩ ABC = A，根据A → B，得到A → AB，即R1 ∩ R2 → R1，所以分解ρ是无损分解。
F1 = πR1(F) = { A → B, B → A }
F2 = πR2(F) = { A → C, C → A, A → D }
F1 ∪ F2 = {A → B, B → A, A → C, C → A, A → D } = {A → B, B → C, B → D, C → A} = F，所以分解ρ是保持函数依赖分解。

模式分解的无损分解与保持函数依赖的分解两个特性之间没有必然的联系。

7.4 关系模式的范式

范式以函数依赖为基础，有第一范式(1NF)，第二范式(2NF)，第三范式(3NF),BC范式(BCNF)。其他类型范式：4NF和5NF不详述。各范式之间存在下面的关系：
1NF ⊃ 2NF ⊃ 3NF ⊃ BCNF ⊃ 4NF ⊃ 5NF

第一范式(1NF)

设R是一个关系模式，如果R的每个属性的值域是不可分的(原子的)数据项集合，则称这个关系模式R为第一范式，简称1NF，记作R ∈ 1NF。

第二范式(2NF)

若关系模式R ∈ 1NF，且每一个非主属性完全函数依赖于键，则R ∈ 2NF。[在1NF基础上消除非主属性对键的部分函数依赖]

第二范式（2NF）要求实体的属性完全依赖于(候选)键。所谓完全依赖是指不能存在仅依赖键一部分的属性，如果存在，那么这个属性和键的这一部分应该分离出来形成一个新的实体。

第三范式(3NF)

关系模式R ∈ 2NF，且它的任何一个非主属性都不传递依赖于任何候选键，则R ∈ 3NF。[在2NF基础上消除非主属性对键的传递函数依赖]

即不能存在：非主属性 A 依赖于非主属性 B，非主属性 B 依赖于键的情况。

2NF：非主属性是否完全依赖于键，还是依赖于键的一部分。
3NF：非主键列是直接依赖于键，还是直接依赖于非主属性列。

BC范式(BCNF)

设关系模式R(U, F) ∈ 1NF, 如果对于R的每个函数依赖X → Y (Y ∉ X)，X必包含键，则R ∈ BCNF，又称修正/扩充的第三范式。[在3NF的基础上消除了主属性之间的函数依赖]

  • 所有非主属性都完全依赖于每个候选键
  • 所有主属性都完全函数依赖于每个不包含它的候选键
  • 没有任何属性完全函数依赖于非键的人和一组属性

只要属性或属性组A能够决定任何一个属性B，则A的子集中必须有候选键。
BCNF范式排除了任何属性(不光是非主属性，2NF和3NF所限制的都是非主属性)对候选键的传递依赖与部分依赖。

规范化小结

关系模式在分解时应该保持“等价”。无损连接分解和保持函数依赖分解没有必然联系。

  • 数据等价用无损连接分解来衡量：能保持关系经过自然连接以后仍能恢复回来
  • 语义等价用保持函数依赖费解来衡量：能保证数据在投影或连接中其语义不会发生变化。

范式是衡量关系模式优劣的标准，范式表达了模式中数据依赖之间应满足的联系。范式级别越高，其数据冗余和操作异常现象越少。