数据库复习（四）

函数依赖

设有关系模式R(U)，X和Y是属性集U的子集，函数依赖（Functional Dependency，简记为FD）
是形为X→Y的一个命题，只要r是R的当前关系，对r中任意两个元组t和s，都有t[X]=s[X]蕴涵t[Y]=s[Y]，
那么称FD  X→Y在关系模式R (U)中成立。 X→Y读作“X函数决定Y”，或者“Y函数依赖于X”。

FD的逻辑蕴涵

定义4.2  设F是在关系模式R上成立的函数依赖的集合，X→Y是一个函数依赖。
如果对于R的每个满足F的关系r也满足X→Y，那么称F逻辑蕴涵X→Y，记为F ⊨X→Y。

定义4.3  设F是函数依赖集，被F逻辑蕴涵的函数依赖全体构成的集合，
称为函数依赖集F的闭包（Closure），记为F+。即：
                   F+=｛X→Y | F⊨X→Y ｝。

FD的推理规则

属性集的闭包

FD推理规则的完备性

推理规则的正确性是指“从FD集F使用推理规则集推出的FD必定在F+中”，
完备性是指“F+中的FD都能从F集使用推理规则集导出”。
也就是正确性保证了推出的所有FD是正确的，完备性保证了可以推出所有被蕴涵的FD。
这就保证了推导的有效性和可靠性。
定理4.5  FD推理规则{A1，A2，A3}是完备的。

FD等价

  如果关系模式R(U)上的两个函数依赖集F和G，有F+=G+，
  则称F和G是等价的函数依赖集。

FD集的最小依赖集

设F是属性集U上的FD集。如果Fmin是F的一个最小依赖集，
那么Fmin应满足下列四个条件：
⑴ F+min =F+；
⑵ 每个FD的右边都是单属性；
⑶ Fmin中没有冗余的FD；
   （即F中不存在这样的函数依赖X→Y，使得F与F－{X→Y }等价）
⑷ 每个FD的左边没有冗余的属性。
   （即F中不存在这样的函数依赖X→Y，X有真子集W，使得
F－{ X→Y}∪{ W→Y }与F等价）

关系模式的分解特性

模式分解问题

无损分解的测试方法

保持函数依赖的分解

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

第一范式（1NF）

定义4.16  如果关系模式R的每个关系r的属性值都是不可分的原子值，
那么称R是第一范式(first Normal Form，简记为1NF)的模式。
1NF是关系模式应具备的最起码的条件，满足1NF的关系称为规范化的关系
否则称为非规范化的关系。关系数据库研究的关系都是规范化的关系。

第二范式（2NF）

定义4.17  对于FD W→A，如果存在X⊂W有X→A成立，那么称W→A是局部依赖（A局部依赖于W）；
否则称W→A是完全依赖（也称为“左部不可约依赖” ）
定义4.18  如果A是关系模式R的候选键中属性，那么称A是R的主属性；否则称A是R的非主属性。
定义4.19  如果关系模式R是1NF，且每个非主属性完全函数依赖于候选键，
那么称R是第二范式（2NF）的模式。
如果数据库模式中每个关系模式都是2NF，则称数据库模式为2NF的数据库模式。
算法4.4  分解成2NF模式集的算法
设关系模式R(U)，主键是W，R上还存在FD X→Z，并且Z是非主属性和X是W的子集，
那么W→Z就是一个局部依赖。此时应把R分解成两个模式:
R1(XZ)，主键是X；
R2(Y)，其中Y=U-Z，主键仍是W，外键是X(REFERENCES  R1)。
利用外键和主键的连接可以从R1和R2重新得到R。
如果R1和R2还不是2NF，则重复上述过程，一直到数据库模式中每一个关系模式都是2NF为止。 

第三范式（3NF）

定义4.20  如果X→Y，Y→A，且Y↛X和A∉ Y，那么称X→A是传递依赖（A传递依赖于X）。
定义4.21   如果关系模式R是1NF，且每个非主属性都不传递依赖于R的候选键，
那么称R是第三范式（3NF）的模式。如果数据库模式中每个关系模式都是3NF，
则称其为3NF的数据库模式 。
算法4.5  分解成3NF模式集的算法
设关系模式R(U)，主键是W，R上还存在FD X→Z。
并且Z是非主属性，Z不是X的子集，X不是候选键，这样W→Z就是一个传递依赖。
此时应把R分解成两个模式：
R1(XZ)，主键是X；
R2(Y)，其中Y=U-Z，主键仍是W，外键是X(REFERENCES  R1)。
利用外键和主键相匹配机制，R1和R2通过联接可以重新得到R。
如果R1和R2还不是3NF，则重复上述过程，一直到数据库模式中每一个关系模式都是3NF为止。 
定理4.8  如果R是3NF模式，那么R也是2NF模式。
证明：只要证明其逆否命题成立即可，即模式中局部依赖的存在蕴涵着传递依赖即可。
设A是R的一个非主属性，K是R的一个候选键，且K→A是一个局部依赖。那么R中必存在某个K’⊂ K，
有K’→A成立。由于A是非主属性，因此A∩KK’=φ。由K’⊂ K，可知 K’→K，但K→K’成立。
因而从K→K’ 和K’→A可知K→A是一个传递依赖。

局部依赖和传递依赖是模式产生冗余和异常的两个重要原因。

BCNF

定义4.23  如果关系模式R是1NF，且每个属性都不传递依赖于R的候选键，那么称R是BCNF的模式。
如果数据库模式中每个关系模式都是BCNF，则称为BCNF的数据库模式。
定理4.9 如果R是BCNF模式，那么R也是3NF模式。

一个好的模式设计方法应符合三条原则：表达性、分离性和最小冗余性。 
表达性是指数据等价和语义等价问题,分别用无损分解和保持函数依赖来衡量。
分离性是将间接有联系的属性放在不同的表中。
最小冗余性是指分解后的模式个数和模式中的属性总数尽可能最小。

参考博客

数据库复习（一）
数据库复习（二）
数据库复习（三）