数据库 规范覆盖的计算、多值依赖

1、(1) F中每个中每个FD的的右部右部只含一个属性只含一个属性。 函数依赖集的函数依赖集的最小覆盖最小覆盖 定义定义 : 设设F 是是R(U)上的上的FD集，集， 如果如果F满足以下满足以下三个条件三个条件： (2) F中中无无多余多余FD。 即不存在即不存在XA, 满足满足F与与FXA等价。等价。 (3) F中每个中每个FD的的左部左部都不含都不含多余属性多余属性。 即不存在即不存在XA，X有真子集有真子集Z，满足：满足： F与与(FXA)ZA等价。等价。 则称则称F为为最小依赖集最小依赖集或或最小覆盖最小覆盖。 则对应的则对应的规范覆盖规范覆盖为：为： Fc= 。 例：例：设设最小覆盖最小

2、覆盖为：为：Fm=CB, BA, CD, AE, BD, 将将最小覆盖最小覆盖中左部相同的中左部相同的FD合并合并成一个后得到的成一个后得到的FD集集 称为称为规范覆盖规范覆盖。 CBD, BAD, AE 函数依赖集的函数依赖集的最小覆盖最小覆盖 (1) 用用分解规则分解规则将将F中的每个中的每个FD右部右部分解为分解为单属性单属性。 如何计算如何计算FD集集F的的最小覆盖最小覆盖？分三步： 分三步： F (F - XY )X Ai | i=1,2,k 。 对每个对每个XY F, 若若Y=A1A2Ak (k2), 则置：则置： (2) 删除删除F中中多余的多余的FD。 对每个对每个XA F,

3、令令G=F - XA, 若若A XG , 则置 则置F G。 因：由因：由A XG 可得 可得XA， 故故F中的中的XA多余多余。 (3) 删除删除F中每个中每个FD左部的左部的多余属性多余属性。 对每个对每个XA F, 设设X=B1B2Bm (m2),逐个逐个考查考查Bi (i=1.m): 若若A (X- Bi)F , 因：由因：由A (X-Bi)F 可得 可得(X-Bi)A，故故XA中中Bi是是多余属性多余属性。 则置则置F (F - XA )(X- Bi)A。 F= ACA, CB, BA, CD, CA, ACD, CBB, CBE 例例: 求求F= ACA, CB, BA, CD,

4、CA, ACD, CBBE 的的最小覆盖最小覆盖 (1) 用用分解规则分解规则将将F中的每个中的每个FD右部右部分解为分解为单属性单属性。 (2) 删除删除F中中多余的多余的FD。 G= CB, BA, CD, CA, ACD, CBB, CBE (AC)G+= A,C,， A (AC)G ， ， 置置F G 。 函数依赖集的函数依赖集的最小覆盖最小覆盖 函数依赖集的函数依赖集的最小覆盖最小覆盖 F= CB, BA, CD, CA, ACD, CBB, CBE G= BA, CD, CA, ACD, CBB, CBE CG+= ，F不变不变 。, DC, AB CG ， ， 例例: 求求F=

5、ACA, CB, BA, CD, CA, ACD, CBBE 的的最小覆盖最小覆盖 (1) 用用分解规则分解规则将将F中的每个中的每个FD右部右部分解为分解为单属性单属性。 (2) 删除删除F中中多余的多余的FD。 函数依赖集的函数依赖集的最小覆盖最小覆盖 F= CB, BA, CD, CA, ACD, CBB, CBE 例例: 求求F= ACA, CB, BA, CD, CA, ACD, CBBE 的的最小覆盖最小覆盖 BG+= B ，F不变不变 。A BG ， ， G= CB, CD, CA, ACD, CBB, CBE (1) 用用分解规则分解规则将将F中的每个中的每个FD右部右部分解为

6、分解为单属性单属性。 (2) 删除删除F中中多余的多余的FD。 函数依赖集的函数依赖集的最小覆盖最小覆盖 例例: 求求F= ACA, CB, BA, CD, CA, ACD, CBBE 的的最小覆盖最小覆盖 F= CB, BA, CD, CA, ACD, CBB, CBE G= CB, BA, CA, ACD, CBB, CBE CG+= ，置置F G 。, BC, AD CG ， ，, D, E (1) 用用分解规则分解规则将将F中的每个中的每个FD右部右部分解为分解为单属性单属性。 (2) 删除删除F中中多余的多余的FD。 函数依赖集的函数依赖集的最小覆盖最小覆盖 例例: 求求F= ACA

7、, CB, BA, CD, CA, ACD, CBBE 的的最小覆盖最小覆盖 F= CB, BA, CA, ACD, CBB, CBE G= CB, BA, ACD, CBB, CBE CG+= ，置置F G 。, BC, AA CG ， ，, D, E (1) 用用分解规则分解规则将将F中的每个中的每个FD右部右部分解为分解为单属性单属性。 (2) 删除删除F中中多余的多余的FD。 函数依赖集的函数依赖集的最小覆盖最小覆盖 例例: 求求F= ACA, CB, BA, CD, CA, ACD, CBBE 的的最小覆盖最小覆盖 A, C F= CB, BA, ACD, CBB, CBE G= C

8、B, BA, CBB, CBE (AC)G+= ，F不变不变 。, B, ED (AC)G+ ， (1) 用用分解规则分解规则将将F中的每个中的每个FD右部右部分解为分解为单属性单属性。 (2) 删除删除F中中多余的多余的FD。 函数依赖集的函数依赖集的最小覆盖最小覆盖 例例: 求求F= ACA, CB, BA, CD, CA, ACD, CBBE 的的最小覆盖最小覆盖 (CB)G+= ，C, B, F= CB, BA, ACD, CBB, CBE G= CB, BA, ACD, CBE 置置F G 。B (CB)G+， (1) 用用分解规则分解规则将将F中的每个中的每个FD右部右部分解为分解

9、为单属性单属性。 (2) 删除删除F中中多余的多余的FD。 函数依赖集的函数依赖集的最小覆盖最小覆盖 例例: 求求F= ACA, CB, BA, CD, CA, ACD, CBBE 的的最小覆盖最小覆盖 (CB)G+= ，C, B F= CB, BA, ACD, CBE G= CB, BA, ACD F不变不变 。, A, DE (CB)G+， (1) 用用分解规则分解规则将将F中的每个中的每个FD右部右部分解为分解为单属性单属性。 (2) 删除删除F中中多余的多余的FD。 函数依赖集的函数依赖集的最小覆盖最小覆盖 例例: 求求F= ACA, CB, BA, CD, CA, ACD, CBBE

10、 的的最小覆盖最小覆盖 F= CB, BA, ACD, CBE (3) 删除删除F中每个中每个FD左部的左部的多余属性多余属性。 F= CB, BA, ACD, CBE CF+= ，CA是是多余多余属性，删去。属性，删去。, B, AD CF+，, D, E CD, (1) 用用分解规则分解规则将将F中的每个中的每个FD右部右部分解为分解为单属性单属性。 (2) 删除删除F中中多余的多余的FD。 函数依赖集的函数依赖集的最小覆盖最小覆盖 例例: 求求F= ACA, CB, BA, CD, CA, ACD, CBBE 的的最小覆盖最小覆盖 F= CB, BA, ACD, CBE F= CB, B

11、A, ACD, CBE (1) 用用分解规则分解规则将将F中的每个中的每个FD右部右部分解为分解为单属性单属性。 (2) 删除删除F中中多余的多余的FD。 CD, BF+= ，BC不是不是多余多余属性，保留。属性，保留。, AE BF+， (3) 删除删除F中每个中每个FD左部的左部的多余属性多余属性。 函数依赖集的函数依赖集的最小覆盖最小覆盖 例例: 求求F= ACA, CB, BA, CD, CA, ACD, CBBE 的的最小覆盖最小覆盖 F= CB, BA, ACD, CBE F= CB, BA, ACD, CBE (1) 用用分解规则分解规则将将F中的每个中的每个FD右部右部分解为分

12、解为单属性单属性。 (2) 删除删除F中中多余的多余的FD。 CD, (3) 删除删除F中每个中每个FD左部的左部的多余属性多余属性。 CF+= ，CB是是多余多余属性，删去。属性，删去。, B, AE CF+，, D, E CE F的的规范覆盖规范覆盖为：为：Fc= 最后得到最后得到F的的最小覆盖最小覆盖为：为：Fm= CB, BA, CD, CE , BACBDE 多值依赖多值依赖 在在函数依赖函数依赖范畴内，范畴内，BCNF已经非常完美已经非常完美。但是属于但是属于 BCNF的关系模式仍可能存在问题。的关系模式仍可能存在问题。 例例如：如： 假设假设多个教师上同一门课程，使用同一套参考书

13、：多个教师上同一门课程，使用同一套参考书： 注意：注意： TC不成立，因为一个教师可以上多门课。不成立，因为一个教师可以上多门课。 BC不成立，因为参考书可以跨课程交叉使用。不成立，因为参考书可以跨课程交叉使用。 数学分析数学分析 高等代数高等代数 微分方程微分方程 数学数学 邓军邓军 陈斯陈斯 物理物理 李平李平 王强王强 邓军邓军 普通物理普通物理 微分方程微分方程 用关系模式用关系模式Teach( C, T, B ) 表示。表示。 课程课程 教师教师 参考书参考书 F = ， 候选码为候选码为CTB, 即全码，所以即全码，所以TeachBCNF 否则：否则：候选码是候选码是TBTeach

14、2NF TBC是是部分依赖部分依赖 Teach关系存在以下关系存在以下4个问题：个问题： Teach( C, T, B ) 存在的问题存在的问题 (1)数据冗余大数据冗余大：有多少教师上同一门：有多少教师上同一门 课，参考书就重复多少次课，参考书就重复多少次; (2)更新异常更新异常：改某一门课的参考书需：改某一门课的参考书需 要修改该课的所有记录要修改该课的所有记录; (3)插入异常插入异常: : 某门课增加一个教师，某门课增加一个教师， 该课有多少参考书就需要插入多少该课有多少参考书就需要插入多少 个元组个元组; (4)删除异常删除异常: 删除某门课的一本参考删除某门课的一本参考 书，该课

15、程有多少教师就要删除多书，该课程有多少教师就要删除多 少元组。少元组。 原因：原因： 对于每一门课，对于每一门课，Teach表中都表中都 存储了存储了T和和B的笛卡尔积的笛卡尔积, 即下列条即下列条 件对每门课件对每门课x都成立：都成立： Teach CTB 数学数学 数学数学 数学数学 数学数学 数学数学 数学数学 物理物理 物理物理 物理物理 物理物理 物理物理 物理物理 邓军邓军 邓军邓军 邓军邓军 陈斯陈斯 陈斯陈斯 陈斯陈斯 李平李平 李平李平 王强王强 王强王强 邓军邓军 邓军邓军 数学分析数学分析 高等代数高等代数 微分方程微分方程 数学分析数学分析 高等代数高等代数 微分方程微

16、分方程 普通物理普通物理 微分方程微分方程 普通物理普通物理 微分方程微分方程 普通物理普通物理 微分方程微分方程 P PT, B( ( s sC=x(Teach) ) = P PT ( ( s sC=x(Teach) )P PB( ( s sC=x(Teach) ) 由此引出由此引出多值依赖多值依赖的定义：的定义： R(U) U XY Z rXYZ 设设R(U)是是U上的关系模式，上的关系模式， 定义定义( (多值依赖多值依赖) )： X,Y,Z U, 且且Z= =U-X-Y, , 若对若对R(U)的的任意关系任意关系r， 都有：都有： 以及以及r在在X属性组上的任意值属性组上的任意值x,

17、, 成立，成立，P PY, Z( ( s sX=x(r) ) = P PY ( ( s sX=x(r) )P PZ( ( s sX=x(r) ) x x 说明：说明： 则称则称X多值确定多值确定Y或或Y多值依赖于多值依赖于X，记作记作X Y。 条件必须对条件必须对R(U)的的所有可能所有可能 关系关系在在X属性组上的属性组上的所有可所有可 能值能值都成立都成立, ,只要在只要在某个可某个可 能值能值上上条件条件不成立，则不成立，则: X Y不成立。不成立。 R(U) U XY Z rXYZ 设设R(U)是是U上的关系模式，上的关系模式， 多值依赖多值依赖的另一个定义：的另一个定义： X,Y,Z

18、 U, 且且Z= =U-X-Y, , 若若R的的任意关系任意关系r满足满足: : 那么那么(x,y2,z1)和和(x,y1,z2)也是也是r的元组，的元组， 只要只要(x,y1,z1)和和(x,y2,z2)是是r的元组的元组, , 说明：说明： 则称则称多值依赖多值依赖X Y在在R(U)上成立上成立。 两种定义是等价的两种定义是等价的： x y1 z1 x y2 z2 x y2 z1 x y1 z2 y1 z1 y2 z2 y2 z1 y1 z2 y1 y2 z1 z2 = 多值依赖的性质多值依赖的性质 (1)对称性对称性： 若若X Y，则则X U-X-Y (即即Z) 证明证明: : P PY

19、, Z( ( s sX=x(r) ) = P PY ( ( s sX=x(r) )P PZ( ( s sX=x(r) )成立，成立， 必有必有P PZ, Y( ( s sX=x(r) ) = P PZ ( ( s sX=x(r) )P PY( ( s sX=x(r) )成立。成立。 (2)传递性传递性： 若若X Y，Y Z , 则则X Z -Y 证明非常复杂，大大超出了本课程的范围。证明非常复杂，大大超出了本课程的范围。 (3)复制性复制性： 若若X Y, 则则X Y。 rXYZ x x y y z1 zk X Y: 若若X上的上的 分量相等分量相等 ，则，则Y上上 的分量相的分量相 等。等。

20、 P PY, Z(. (.)P PY (. (.)P PZ(. (.) y z1 y zk y z1 zk = = 证明证明： 所以所以X Y 多值依赖的性质多值依赖的性质 (1)对称性对称性： 若若X Y，则则X U-X-Y (即即Z) 证明证明: : P PY, Z( ( s sX=x(r) ) = P PY ( ( s sX=x(r) )P PZ( ( s sX=x(r) )成立，成立， 必有必有P PZ, Y( ( s sX=x(r) ) = P PZ ( ( s sX=x(r) )P PY( ( s sX=x(r) )成立。成立。 (2)传递性传递性： 若若X Y，Y Z , 则则X

21、 Z -Y 证明非常复杂，大大超出了本课程的范围。证明非常复杂，大大超出了本课程的范围。 (3)复制性复制性： 若若X Y, 则则X Y。 (4)并规则并规则： 若若XY, X Z, 则则X YZ。 (5)交规则交规则：若：若XY, X Z, 则则X YZ。 (6)差规则差规则：若：若XY, XZ, 则则XY-Z, XZ-Y。 (7)平凡多值依赖平凡多值依赖：对：对U上的多值依赖上的多值依赖XY, 若若Y X, 或或 XY=U，则称则称XY为为平凡多值依赖平凡多值依赖。这是因为：。这是因为： Y XXYXY (3) XX (3) XXXU-X (1) XY-X XY=U XXY XY (4) XY XYY-X Teach(C, T, B )存在问题的原因：存在问题的原因： 存在非平凡多值依赖存在非平凡多值依赖CT, 且且C不含候选码不含候选码CTB 。 解决办法：解决办法： 分解分解关系模式关系模式, 消除消除