第八章数据依赖和关系模式规范化 8.1关系模式设计中的数据语义问题 数据依赖,函数依赖,多值依赖 8.2函数依赖 符号:R,r,U,F,Ⅹ,t,tx] 定义82-:设R为关系模式,X,YcU,若Ⅴtlt∈r都有如果 tX]2(X],则必有tlIY=t2[Y],则称在R上X函数决定Y或者 Y函数依赖于Ⅹ,记为Ⅹ→Y,X称为决定子 平凡函数依赖 定义82-2:完全函数依赖 定义823:X,Y,Z是R的属性集,如果X→Y,YH>X,Y→Z, 则称Z传递函数依赖于X 定义8.2-4:F是函数依赖集合,Ⅹ→Y是函数依赖,如果F在某 个R上成立,则必然有Ⅹ→Y也成立,则称F逻辑蕴涵ⅹ→Y 定义8.2-5:函数依赖集合F所逻辑蕴含的函数依赖的全体称为F 的闭包 Armstrong公理系统: A1:自反率:如果 YCXCU,则X→Y成立 A2:扩展率:如果X→Y成立,且ZcU,则XZ→YZ成立 A3:传递率:如果Ⅹ→Y,Y→Z成立,则X→Z成立 引理82-1: Armstrong公理是正确的,完备的 引理8.2-2:下列三条推理规则也是正确的: (1)合并规则:若X→Y,X→Z,则Ⅹ→YZ
第八章 数据依赖和关系模式规范化 8.1 关系模式设计中的数据语义问题 数据依赖，函数依赖，多值依赖 例 8.2 函数依赖 符号：R，r，U，F，X，t，t[x] 定义 8.2-1：设 R 为关系模式，X，Y U，若 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，Y X，Y→Z， 则称 Z 传递函数依赖于 X。 定义 8.2-4：F 是函数依赖集合，X→Y 是函数依赖，如果 F 在某 个 R 上成立，则必然有 X→Y 也成立，则称 F 逻辑蕴涵 X→Y。 定义 8.2-5：函数依赖集合 F 所逻辑蕴含的函数依赖的全体称为 F 的闭包 Armstrong 公理系统： A1：自反率：如果 Y X U，则 X→Y 成立 A2：扩展率：如果 X→Y 成立，且 Z U，则 XZ→YZ 成立 A3：传递率：如果 X→Y，Y→Z 成立，则 X→Z 成立 引理 8.2-1：Armstrong 公理是正确的，完备的 引理 8.2-2：下列三条推理规则也是正确的： (1)合并规则：若 X→Y，X→Z，则 X→YZ
(2)伪传递规则:若Ⅹ→Y,WY→Z,则WX→Z (3)分解规则:若X→Y,且ZcY,则Ⅹ→Z 定义8.26:X关于F的闭包X定义为X+={AA∈U,X→A可由 Armstrong公理推出} 引理82-3:X→Y可由 Armstrong公理推出的充要条件是YcX 定理82-1: Armstrong公理是正确的,完备的 算法8,2-1:计算X 例 定义8.2-7:F,G是两个函数依赖集合,如果F+=G+,责成F等 价于G。 (1)如果F=G,则F=G (2)如果FcG,则FcG (3)如果F∈G,则FcG 引理8.2-4:F+=G+的充分必要条件是FcG+且GcF 由该引理可得判定F+=G+的方法,只需判断FcG+及GcF+ 引理825:任意一个函数依赖集合F总可以为一右部恒为单属性 的函数依赖集合所覆盖。(构造) 定义8,2-8:若F满足下列条件, (1)F中所有函数依赖的右部均为单属性 (2)F中不存在这样的函数依赖X→A:使F=(F-{X→A}) 3)F中不存在这样的函数依赖Ⅹ→A及ZcX,使得F+=(F {x→A}U{z→A}) 则称F为最小函数依赖集或最小覆盖
(2)伪传递规则：若 X→Y，WY→Z，则 WX→Z (3)分解规则：若 X→Y，且 Z Y，则 X→Z 定义 8.2-6：X 关于 F 的闭包 X ＋定义为 X ＋＝{A|A∈U，X→A 可由 Armstrong 公理推出} 引理 8.2-3：X→Y 可由 Armstrong 公理推出的充要条件是 Y X ＋ 定理 8.2-1：Armstrong 公理是正确的，完备的 算法 8.2-1：计算 X ＋ 例 定义 8.2-7：F，G 是两个函数依赖集合，如果 F ＋＝G ＋，责成 F 等 价于 G。 (1)如果 F＝G，则 F ＋＝G ＋ (2)如果 F G，则 F ＋ G ＋ (3)如果 F G ＋，则 F ＋ G ＋ 引理 8.2-4：F ＋＝G ＋的充分必要条件是 F G ＋且 G F ＋ 由该引理可得判定 F ＋＝G ＋的方法，只需判断 F G ＋及 G F ＋ 引理 8.2-5：任意一个函数依赖集合 F 总可以为一右部恒为单属性 的函数依赖集合所覆盖。（构造） 定义 8.2-8：若 F 满足下列条件， (1)F 中所有函数依赖的右部均为单属性 (2)F 中不存在这样的函数依赖 X→A：使 F ＋＝(F－{X→A})＋ (3)F 中不存在这样的函数依赖 X→A 及 Z X，使得 F ＋＝(F －{X→A}∪{Z→A})＋ 则称 F 为最小函数依赖集或最小覆盖
定理8.2-2:任一函数依赖集合必等价于某一最小函数依赖集合Fmm 构造性证明 求关系模式上所有候选键的方法 83多值依赖(MVD 定义8.31:设R为关系模式,X、Y是R的属性集,如果对于R 的任何实例r都有:如果r中存在两个元组s,t使得sX]=tX 则R中必然存在两个元组u,ⅴ使得 uX=vX=sX=tXI u[Y]=t[YHu[U-X-Y=SU-X-YI vIY]=sYE vU-X-Y]=t[U-X-YI 则称R满足X→→Y MVD与FD的区别与联系 MVD的公理系统 A4互补率:如果X→→Y,则X→→(U-X-Y) A5扩展率:如果X→→Y,且VcW,则WX→→VY 6传递率:如果Ⅹ→→Y,Y→→Z,则Ⅹ→→(Z-Y) 7如果Ⅹ→Y,则Ⅹ→→Y A8如果Ⅹ→→Y,ZcY,且对某一W当Y∩W=Φ时有W→Z, 则X→Z A1~A8是完备的 推理规则: (1)合并规则:Ⅹ→→Y,X→→Z,则有X→→Y (2)伪传递规则:X→→Y,WY→→Z,则有WX→→(Z-WY) (3)混合伪传递规则:X→→Y,XY→Z,则有X→(Z-Y) (4)分解规则:X→→Y,X→→Z,则有Ⅹ→→(Y∩Z),X→→(Y一 Z),→→(Z-Y) 8.4模式分解 定义84-1:R的分解p
定理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，且 V W，则 WX→→VY A6 传递率：如果 X→→Y，Y→→Z，则 X→→(Z－Y) A7 如果 X→Y，则 X→→Y A8 如果 X→→Y，Z Y，且对某一 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 的分解
定义84-2:F在Ui上的投影 定义8.43:设p=(R1,R2R)是R的一个分解,r是R的任一个 值,如果满足r=Iu(r)<∏ua(r)pq∏ur).D<∏u(r)则称p 是无损连接分解 定义84-4:分解P保持函数依赖 引理84-1:设p=(R1,R2R是R的一个分解,r是R的一个值 ri=Iu),则有(1)rmp();(2如果s=mp(r),则∏u)=ri; B)mpmp(r=mp(r) 算法8.4-1:判别无损连接 定理84-1:算法84-1可以正确判断一个分解是否是无损的(i 定理84-2:R的一个分解p={R1,R2}无损的充要条件是U1n U2)→(U1-U2)∈F或者U∩U2)→(U2-U1)∈F+ 算法8.4-2:判别一个分解是否保持函数依赖 8.5关系模式规范化 定义8.5-1:如果关系模式R中的所有非主属性都完全函数依赖于 所有CK,则称R属于2NF 定义8.5-2:如果关系模式R中的非主属性既不部分依赖也不传递 依赖所有CK,则称R属于3NF (等价定义) 定义853:若对于R上的任何非平凡函数依赖X→Y都有Ⅹ必为 R上的SK,则称R属于BCNF
定义 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) r m (r)；(2)如果 s= m (r)，则ΠUi(r)＝ri； (3) m m (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:无损分解 引理85-2:无损分解 算法8.5-1:将关系模式分解为BCNF且保持无损连接的方法(分 解法) 算法8.52:将关系模式分解为3NF且保持函数依赖的方法(合成 法) 定理85-1:算法8.5-2产生一个保持函数依赖且化为3NF的分解 算法85-3:既保持函数依赖又无损的3NF转换算法 定理85-2:算法85-3产生一个保持函数依赖的化为3NF的无损 分解 定理8.5-3:p={R1,R2}是R的一个分解,D是R的函数依赖 和多值依赖集合,则P为无损分解当且仅当(U∩U2)→→(U1-U2) 或者(U∩U2)→→(U2-U1) 定义85-4:R中若存在非平凡的多值依赖Ⅹ→→Y,则Ⅹ必为R 的SK,满足此条件的R属于4NF 定义8.5-5:R中除了由SK构成的连接依赖外,别无其他连接依 赖,则称R属于5NF
引理 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