第八章 数据依赖和关系模式规范化
8.1关系模式设计中的数据语义问题
数据依赖，函数依赖，多值依赖
例
8.2函数依赖
符号：R，r，U，F，X，t，t[x]
定义8.2-1：设R为关系模式，X，YU，若t1,t2∈r都有如果t1[X]=t2[X]，则必有t1[Y]=t2[Y]，则称在R上X函数决定Y或者Y函数依赖于X，记为X→Y，X称为决定子。
平凡函数依赖
定义8.2-2：完全函数依赖
定义8.2-3：X，Y，Z是R的属性集，如果X→Y，YX，Y→Z，则称Z传递函数依赖于X。
定义8.2-4：F是函数依赖集合，X→Y是函数依赖，如果F在某个R上成立，则必然有X→Y也成立，则称F逻辑蕴涵X→Y。
定义8.2-5：函数依赖集合F所逻辑蕴含的函数依赖的全体称为F的闭包
Armstrong公理系统：
A1：自反率：如果YXU，则X→Y成立
A2：扩展率：如果X→Y成立，且ZU，则XZ→YZ成立
A3：传递率：如果X→Y，Y→Z成立，则X→Z成立
引理8.2-1：Armstrong公理是正确的，完备的
引理8.2-2：下列三条推理规则也是正确的：
合并规则：若X→Y，X→Z，则X→YZ
伪传递规则：若X→Y，WY→Z，则WX→Z
分解规则：若X→Y，且ZY，则X→Z
定义8.2-6：X关于F的闭包X＋定义为X＋＝{A|A∈U，X→A可由Armstrong公理推出}
引理8.2-3：X→Y可由Armstrong公理推出的充要条件是YX＋
定理8.2-1：Armstrong公理是正确的，完备的
算法8.2-1：计算X＋
例
定义8.2-7：F，G是两个函数依赖集合，如果F＋＝G＋，责成F等价于G。
(1)如果F＝G，则F＋＝G＋
(2)如果FG，则F＋G＋
(3)如果FG＋，则F＋G＋
引理8.2-4：F＋＝G＋的充分必要条件是FG＋且GF＋
由该引理可得判定F＋＝G＋的方法，只需判断FG＋及GF＋
引理8.2-5：任意一个函数依赖集合F总可以为一右部恒为单属性的函数依赖集合所覆盖。（构造）
定义8.2-8：若F满足下列条件，
F中所有函数依赖的右部均为单属性
F中不存在这样的函数依赖X→A：使F＋＝(F－{X→A})＋
F中不存在这样的函数依赖X→A及ZX，使得F＋＝(F－{X→A}∪{Z→A})＋
则称F为最小函数依赖集或最小覆盖
定理8.2-2：任一函数依赖集合必等价于某一最小函数依赖集合Fmin
构造性证明
求关系模式上所有候选键的方法
8.3多值依赖(MVD)
定义8.3-1：设R为关系模式，X、Y是R的属性集，如果对于R的任何实例r都有：如果r中存在两个元组s，t使得s[X]＝t[X],则R中必然存在两个元组u，v使得
u[X]＝v[X]＝s[X]＝t[X]
u[Y]＝t[Y]且u[U―X―Y]＝s[U―X―Y]
v[Y]＝s[Y]且v[U―X―Y]＝t[U―X―Y]
则称R满足X→→Y
MVD与FD的区别与联系
MVD的公理系统
A4互补率：如果X→→Y，则X→→(U―X―Y)
A5扩展率：如果X→→Y，且VW，则WX→→VY
A6传递率：如果X→→Y，Y→→Z，则X→→(Z－Y)
A7如果X→Y，则X→→Y
A8如果X→→Y，ZY，且对某一W当Y∩W＝时有W→Z，则X→Z
A1～A8是完备的
推理规则：
(1)合并规则：X→→Y，X→→Z，则有X→→YZ
(2)伪传递规则：X→→Y，WY→→Z，则有WX→→(Z－WY)
(3)混合伪传递规则：X→→Y，XY→Z，则有X→(Z－Y)
(4)分解规则：X→→Y，X→→Z，则有X→→(Y∩Z)，X→→(Y－Z)，X→→(Z－Y)
8.4模式分解
定义8.4-1：R的分解
定义8.4-2：F在Ui上的投影
定义8.4-3：设＝(R1,R2…Rk)是R的一个分解，r是R的任一个值，如果满足r＝ΠU1(r) ΠU2(r) ΠU3(r)…ΠUk(r)则称是无损连接分解
定义8.4-4：分解保持函数依赖
引理8.4-1：设＝(R1,R2…Rk)是R的一个分解，r是R的一个值，
ri＝ΠUi(r)，则有(1) rm(r)；(2)如果s= m(r)，则ΠUi(r)＝ri；(3) mm(r)= m(r)
算法8.4-1：判别无损连接
定理8.4-1：算法8.4-1可以正确判断一个分解是否是无损的（iff）
定理8.4-2：R的一个分解＝{R1，R2}无损的充要条件是(U1∩U2)→(U1－U2)∈F＋或者(U1∩U2)→(U2－U1)∈F＋
算法8.4-2：判别一个分解是否保持函数依赖
8.5关系模式规范化
定义8.5-1：如果关系模式R中的所有非主属性都完全函数依赖于所有CK，则称R属于2NF
定义8.5-2：如果关系模式R中的非主属性既不部分依赖也不传递依赖所有CK，则称R属于3NF
（等价定义）
定义8.5-3：若对于R上的任何非平凡函数依赖X→Y都有X必为R上的SK，则称R属于BCNF
引理8.5-1：无损分解
引理8.5-2：无损分解
算法8.5-1：将关系模式分解为BCNF且保持无损连接的方法（分解法）
算法8.5-2：将关系模式分解为3NF且保持函数依赖的方法（合成法）
定理8.5-1：算法8.5-2产生一个保持函数依赖且化为3NF的分解
算法8.5-3：既保持函数依赖又无损的3NF转换算法
定理8.5-2：算法8.5-3产生一个保持函数依赖的化为3NF的无损分解
定理8.5-3：＝{R1，R2}是R的一个分解，D是R的函数依赖和多值依赖集合，则为无损分解当且仅当(U1∩U2)→→(U1－U2)或者(U1∩U2)→→(U2－U1)
定义8.5-4：R中若存在非平凡的多值依赖X→→Y，则X必为R的SK，满足此条件的R属于4NF
定义8.5-5：R中除了由SK构成的连接依赖外，别无其他连接依赖，则称R属于5NF
