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

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= 。例：例：设设最小覆盖最小覆盖为：为：Fm

2、=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, 令令G=F - XA, 若若A XG,

3、 则置则置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, CA, ACD, CBBE 的最小覆盖的最小覆盖(1) 用用分解规

4、则分解规则将将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= ACA, CB, BA, CD, CA, ACD, CBBE 的最小覆盖的最小覆盖(1)

5、 用用分解规则分解规则将将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右部右部分解为分解为单属性单属性。(2) 删除删除F中中多余的多余的FD。函数依赖集的函数依赖集的最小覆盖最小覆盖例例

6、: 求求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, CB, BA, CD, CA, ACD, CBBE 的最小覆盖的最小覆盖F= CB, BA, CA, ACD, CBB,

7、 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, CF= CB, BA, ACD, CBB, CBE G= CB, BA, CBB, CBE (AC)G+= ，F不变不变 。, B, ED (AC)G+ ，(1) 用用分解规则分解规则将将F中的每个中的

8、每个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右部右部分解为分解为单属性单属性。(2) 删除删除F中中多余的多余的FD。函数依赖集的函数依赖集的最小覆盖最小覆盖例例: 求求F= ACA, CB, BA, CD, CA,

9、ACD, CBBE 的最小覆盖的最小覆盖(CB)G+= ，C, BF= 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 的最小覆盖的最小覆盖F= CB, BA, ACD, CBE (3) 删除删除F中每个中每个FD左部的左部的多余属性多余属性。F= CB, BA, ACD, CBE CF+=

10、 ，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, BA, ACD, CBE (1) 用用分解规则分解规则将将F中的每个中的每个FD右部右部分解为分解为单属性单属性。(2) 删除删除F中中多余的多余的FD。 CD,BF+= ，BC不是不是多余

11、多余属性，保留。属性，保留。, 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右部右部分解为分解为单属性单属性。(2) 删除删除F中中多余的多余的FD。 CD,(3) 删除删除F中每个中每个FD左部的左部的多余属性多余属性。CF+= ，CB是是多余多余属性，删去。属性，删去。, B, AE C

12、F+，, D, ECEF的的规范覆盖规范覆盖为：为：Fc= 最后得到最后得到F的的最小覆盖最小覆盖为：为：Fm= CB, BA, CD, CE , BACBDE多值依赖多值依赖 在在函数依赖函数依赖范畴内，范畴内，BCNF已经非常完美已经非常完美。但是属于但是属于BCNF的关系模式仍可能存在问题。的关系模式仍可能存在问题。例例如：如： 假设假设多个教师上同一门课程，使用同一套参考书：多个教师上同一门课程，使用同一套参考书：注意：注意： TC不成立，因为一个教师可以上多门课。不成立，因为一个教师可以上多门课。 BC不成立，因为参考书可以跨课程交叉使用。不成立，因为参考书可以跨课程交叉使用。数学分

13、析数学分析高等代数高等代数微分方程微分方程数学数学邓军邓军陈斯陈斯物理物理李平李平王强王强邓军邓军普通物理普通物理微分方程微分方程用关系模式用关系模式Teach( C, T, B ) 表示。表示。 课程课程 教师教师 参考书参考书F = ， 候选码为候选码为CTB, 即全码，所以即全码，所以TeachBCNF否则：否则：候选码是候选码是TBTeach2NF TBC是是部分依赖部分依赖Teach关系存在以下关系存在以下4个问题：个问题：Teach( C, T, B ) 存在的问题存在的问题数据冗余大数据冗余大：有多少教师上同一门：有多少教师上同一门课，参考书就重复多少次课，参考书就重复多少次;(

14、2)更新异常更新异常：改某一门课的参考：改某一门课的参考书需要修改该课的所有记录书需要修改该课的所有记录;(3)插入异常插入异常: : 某门课增加一个教师，某门课增加一个教师，该课有多少参考书就需要插入多少该课有多少参考书就需要插入多少个元组个元组; (4)删除异常删除异常: 删除某门课的一本参考删除某门课的一本参考书，该课程有多少教师就要删除多书，该课程有多少教师就要删除多少元组。少元组。原因：原因： 对于每一门课，对于每一门课，Teach表中都表中都存储了存储了T和和B的笛卡尔积的笛卡尔积, 即下列条即下列条件对每门课件对每门课x都成立：都成立：TeachCTB数学数学数学数学数学数学数学

15、数学数学数学数学数学物理物理物理物理物理物理物理物理物理物理物理物理邓军邓军邓军邓军邓军邓军陈斯陈斯陈斯陈斯陈斯陈斯李平李平李平李平王强王强王强王强邓军邓军邓军邓军数学分析数学分析高等代数高等代数微分方程微分方程数学分析数学分析高等代数高等代数微分方程微分方程普通物理普通物理微分方程微分方程普通物理普通物理微分方程微分方程普通物理普通物理微分方程微分方程P PT, B( s( sC=x(Teach) ) = P PT ( s( sC=x(Teach) )P PB( s( sC=x(Teach) )由此引出由此引出多值依赖多值依赖的定义：的定义：R(U)UXY ZrXYZ设设R(U)是是U上的关

16、系模式，上的关系模式，定义定义( (多值依赖多值依赖) )：X,Y,Z U, 且且Z= =U-X-Y, ,若对若对R(U)的的任意关系任意关系r， 都有：都有：以及以及r在在X属性组上的任意值属性组上的任意值x, ,成立，成立，P PY, Z( s( sX=x(r) ) = P PY ( s( sX=x(r) )P PZ( s( sX=x(r) )xx说明：说明：则称则称X多值确定多值确定Y或或Y多值依赖于多值依赖于X，记作记作X Y。条件必须对条件必须对R(U)的的所有可能所有可能关系关系在在X属性组上的属性组上的所有可所有可能值能值都成立都成立, ,只要在只要在某个可某个可能值能值上上条件

17、条件不成立，则不成立，则:X Y不成立。不成立。R(U)UXY ZrXYZ设设R(U)是是U上的关系模式，上的关系模式，多值依赖多值依赖的另一个定义：的另一个定义：X,Y,Z 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 z1x y2 z2x y2 z1x y1 z2y1 z1y2 z2y2 z1y1 z2y

18、1y2z1z2=多值依赖的性质多值依赖的性质(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 Z -Y 证明非常复杂，大大超出了本课程的范围。证明非常复杂，大大超出了本课程的范围。(3)复制性复制性： 若若X Y, 则则X Y。rXYZ x

19、xyyz1zk X Y:若若X上的上的分量相等分量相等，则，则Y上上的分量相的分量相等。等。P PY, Z(. (.)P PY (. (.)P PZ(. (.)y z1y zkyz1zk=证明证明：所以所以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

20、)传递性传递性： 若若X Y，Y Z , 则则X 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-XXY=UXXYXY(4)XYXYY-XTeach(C, T, B )存在问题的原因：存在问题的原因： 存在非平凡多值依赖存在非平凡多值依赖CT, 且且C不含候选码不含候选码CTB 。解决办法：解决办法： 分解分解关系模式关系模式, 消