第3-4讲函数依赖和公理.ppt

1、1,第3-4讲 数 据 依 赖 函数依赖是数据库理论中最主要的组成部分，是设计规范的数据库模式的理论基础。数据依赖表示数据间存在的一种制约或约束关系。 有多种数据依赖，常见的数据依赖有：函数依赖、多值依赖、连接依赖。,2,本章的主要内容： 函数依赖的概念及函数依赖公理 函数依赖集的等价和覆盖 多值依赖及多值依赖公理 连接依赖,3,3.1 函数依赖(Functional dependency FD) 定义1(FD) 设关系模式R(U)，X,Y U，r是R(U)上的任一关系，对任意t1、t2r, 如果 t1X=t2X 有t1Y=t2 Y，称X函数决定Y，或Y函数依赖于X，记为：FD XY。,定义2

2、（FD的等价定义） 对X中的任一值x，Y(X=x(r) 的值仅有一个元组，则有XY。,4,练习1,设关系r 如下所示： r( A B C D E ) a1 b1 c1 d1 e1 a1 b2 c2 d2 e1 a2 b1 c3 d3 e1 a2 b1 c4 d3 e1 a3 b2 c5 d1 e1 说明r上函数依赖： AD, ABD, CBDE，EA 是否成立？,5,定义(平凡/非平凡的FD):设FD XY，如果YX，则称 FD XY为非平凡的函数依赖；否则，若YX，称FD XY为平凡的函数依赖。 定义(完全FD): 设FD XY，如果对任意的XX，XY都不成立，则称XY是完全函数依赖；若对X

3、的真子集X有XX，而XY成立，则称FD XY是部分函数依赖，即Y函数依赖于X的一部分。 练习1中函数依赖 ABD是完全依赖还是部分依赖？ 思考： 如果X只有一个属性， XY是否一定是完全函数依赖？,6,函数依赖的例子,学校数据库的语义： 一个系有若干学生， 一个学生只属于一个系； 一个系只有一名主任； 一个学生可以选修多门课程， 每门课程有若干学生选修； 每个学生所学的每门课程都有一个成绩。,R(SNO,CNO,SNAME,GRADE,DEPT,MNG) （1）找出其中基本的函数依赖？ （2）哪些是平凡依赖？指出哪些是完全依赖？哪些是部分依赖？哪些是传递依赖 ？,SNO DEPT, DEPT

4、MNG; SNO,CNOGRADE; SNO,CNOSNO; SNO,CNOSNAME; SNOMNG,7,3.2 函数依赖公理 3.2.1 函数依赖公理 由关系模式R上的函数依赖组成的集合F称为R上的函数依赖集，记为： FDs F。 定义(FD的逻辑蕴涵) ： 设关系模式R(U,F)，X,YU，如果能从函数依赖集F推导出FD XY，则称 F逻辑蕴涵 FD XY，或称XY逻辑蕴涵于F。记为 F|= XY。,8,已知函数依赖集F，如何判断一个函数XY是否逻辑蕴涵于F ？需要哪些推理法则（包括3个公理和3个推论）？ Armstrong公理（三个公理）： 设r是R(U)上的一个关系，X、Y、Z、WU

5、。 A1. 自反律: 若YXU, 则 XY; A2. 增广律: 若XY且ZU，则 XZYZ; A3. 传递律: 若XY, YZ，则 XZ. 有以上三个公理，可以推出以下3个推论： 推论1（合成规则）： 若XY，XZ，则XYZ 推论2（分解规则）： 若XY且ZY，则XZ 推论3（伪传递规则） 若XY，YZW，则XZW。,9,推论1（合成规则）： 若XY，XZ，则XYZ。 证明：若XY X XY XZ XYYZ,XYZ （增广和传递律,推论2（分解规则）： 若XY且ZY，则XZ。 证明： ZY YZ （自反和传递律） 推论3（伪传递规则） 若XY，YZW，则XZW。 证明： XY XZY Z YZ

6、 W,XZW（增广和传递律）,10,示例：SC(SNO,CNO,SNAME,GRADE,DEPT,MN) F= SNO,CNOGRADE， SNO SNAME，DEPT， DEPT MN,F|= SNO,CNO SNAME,GRADE,DEPT,MN ？ SNO SNAME，DEPT，MN （分解规则，传递律，合成规则） SNO,CNO SNAME，DEPT，MN （自反律和传递律） SNO,CNO SNAME,GRADE,DEPT,MN（合成规则） 思考：由最后一个依赖关系，那否得出是SNO,CNO关系SC的键？,11,定理1 如果Ai (i =1, 2, , n)是关系模式R的属性，则 X

7、 A1 A2 An 成立的充要条件是： X Ai (i =1, 2, , n) 都成立。 3.2.2 公理的完备性 定理2 Armstrong公理是完备的。 即：F所蕴涵的函数依赖XY一定能被公理推出。,12,例： 设F=ABE，AGJ，BEI，EG，GIH 试证：F|= ABGH 证明：用公理系统和F中的函数依赖，推导过程如下： 1. 已知 ABE，EG 则：ABG； (传递律) 2. 已知 ABE 则：ABBE； (增广律) 3. 已知 BEI，又 ABBE 则：ABI (传递律) 4. 由1和3有ABG， ABI 则：ABGI (合成规则) 5. 由4有 ABGI，又 GIH 则：ABH

8、 (传递律) 6. 由1和5有 ABH，ABG 则：ABGH (合成规则),13,定义(使用集) 用公理从F推出 XY成立所使用的函数依赖组成的序列称F上的一个推理序列。在推理序列中出现的且包含在F中的函数依赖的集合称推理序列的使用集(use set)，记为： U(F, XY),例：U(F, ABGH) =ABE，EG， BEI， GIH,14,定义(函数依赖集F的闭包 F +) 设F是关系r(R)上的函数依赖集，F所蕴含的所有FD的集合称为F的闭包，记作F +。 F + = XY | 所有F |= XY 例：设F=ABC，CB。 求F+,15,设F=ABC，CB。 F+ 为： F+ = AA

9、, ABA, ACA, ABCA, BB, ABB, BCB，ABCB，CC，ACC，BCC,ABCC，ABAB，ABCAB，ACAC，ABCAC，BCBC, ABCBC, ABCABC, ABC, ABAC, ABBC, ABABC，CB, CBC，ACB ，ACAB,16,为了判定函数依赖集F是否蕴涵XY，引入的属性闭包： 定义(属性集X的闭包X + ) 设关系模式R(U, F)，U=A1A2An ,X U, 所有用公理和F推出的函数依赖XAi中Ai的集合，称X对于函数依赖集F的闭包，记作：X+ X+ = Ai | F |= XAi 且Ai U,17,3.2.1 函数依赖集闭包及成员测试算

10、法 算法1 计算属性集X的闭包X+的算法 输入：属性集X和函数依赖集F 输出：X的闭包X+,While RESULTVAR do Begin VAR:=RESULT; for every FD WZ in F do if WRESULT then RESULT:=RESULTZ end; return(RESULT) end. /其中的原理：由 WRESULT ,由自反律：RESULT W，再由传递律： RESULT Z,CLOSURE(X, F) Begin VAR:=; RESULT:=X;,18,例： F=AD, ABE, BIE，CDI，EC 求： AE+ 解： AE0 = AE AE

11、1 = AED AE2 = AEDC (第一轮扫描后的结果） AE+ = ACDEI,练习： 属性集U 为ABCD， F=AB, BC, DB 求： A + , (AD) +, (BD)+,19,算法3.2.3 判定F是否蕴涵XY的成员测试算法 输入：函数依赖集F和FD XY。 输出：若F蕴涵XY输出为true，否则为false MEMBER(F, XY) begin if Y CLOSURE(X,F) then return(true) eles return(false) end.,20,成员测试算法练习,练习：F=AD, ABDE, CEG，EH 判断： （1）F |= ABCD? （2

12、）F |= ABEH?,21,综合练习,设F =ABC,BD,CDE,CEGH,GA （1） 用成员测试法（MEMBER(F, ABG) 证明ABG， （2）用推理的方法证明F |= ABG （3）并比较两种方法更好用语言来实现。,22,（1）设F =ABC,BD,CDE,CEGH,GA， 证明F |= AB G,AB0 = AB AB1 = ABC AB2 = ABCD AB3 = ABCDE AB4 = ABCDEGH AB+ = ABCDEGH G AB+ 所以，F |= AB G,23,3.3 函数依赖的等价和覆盖 包括函数依赖集的等价和覆盖、无冗余覆盖、化简覆盖、规范覆盖、最小覆盖等

13、。 3.3.1 函数依赖的等价和覆盖,对于在模式R上的函数依赖集F和G，如果对G中的每一个函数依赖XY，都有F|=XY，称F是G的一个覆盖。把逻辑蕴含符号引入函数依赖集的覆盖中， 记为：F|= G 定义(等价和覆盖) 在模式R上的FDs F和G，若F+=G+，则称F和G等价。 记作FG。,24,定理4 已知模式R上的函数依赖集 F和G。当且仅当 F|=G 且 G|=F ，则 F G。,证明：如果F|=G，若有XYG，则F|=XY，即XYF +， 有GF +，(G)+(F+)+ = F+， 则(G)+(F+)。 同理，如果G|=F，有F + G +。因此，F +=G +，则FG。 反之，若FG，

14、则F|=G和G|=F是显然的。证毕。 研究函数依赖集等价和覆盖的目的是对函数依赖集的化简，比如：无冗余的覆盖、规范覆盖、最小覆盖等。,25,例: 证明F=ABC, AD, CDE和 G=ABCE, AABD, CDE等价,证明：根据前面的定理，只需证明F|=G和 G|=F （1）F|=G （a）ABCE的推导： 由 ABC, AD ，合并规则： ABCD;分解规则 ACD，又 CDE，有传递律： AE；有合并规则ABCE。 ( b）AABD 的推导： ABC, AD ,合并规则： ABCD;分解规则 ABD;增广律： AABD 。 (c) CDE 已有 （2） G|=F ABCE, AABD,

15、合并规则： AABCDE, 由分解律： ABC, AD,26,3.3.2 无冗余覆盖 定义(无冗余覆盖)：如果函数依赖集F不存在真子集F使F F成立，则F是无冗余的。 如果F是G的一个覆盖且F是无冗余的，则F是G的一个无冗余覆盖。,27,算法3.3.1 计算函数依赖集F的无冗余覆盖 NONREDUN(F) begin G: =F ; for each FD XY in F do if MEMBER(GXY, XY) then G: =GXY; return(G) end.,28,无冗余覆盖的例子,例: 求F=AB, BA, BC, ABC 的无冗余覆盖。 求无冗余覆盖基本过程： 用算法3.3.

16、1 ，把计算无冗余覆盖问题转化为 用成员测试算法 MEMBER(GXY, XY)，进一步转化为属性集X的闭包X+， 即： CLOSURE(X, G XY, ) 然后判断Y是否属于CLOSURE(X, G XY, ),29,例: 求F=AB, BA, BC, ABC 的无冗余覆盖。,解:（1）G1= F- AB = BA, BC, ABC MEMBER(G1,AB)? A+=CLOSURE(A, G1 ) = A, B不属于 A+, 所以AB不是多余 （2）G2= F- BA = AB, BC, ABC MEMBER(G2,BA)? B+=CLOSURE(B, G2 ) =B,C, A不属于B

17、+,所以BA不是多余 （3）G3= F- BC = AB, BA, ABC MEMBER(G3,BC)? B+=CLOSURE(B, G3 ) =A,B,C, C属于B +,所以BC是多余 （4）G4= G3 - ABC = AB, BA MEMBER(G4,ABC)? B+=CLOSURE(AB, G4 ) =A,B, C不属于B +,所以ABC不是多余 所以G3是F的无冗余覆盖,30,另外，（1）、（2）同上，先考察ABC是否多余？ （4）G5= F- ABC = AB, BA, BC MEMBER(G5,ABC)? B+=CLOSURE(AB, G5 ) =A,B,C, C属于B +,所

18、以ABC是多余， 同时可以验证在G5中， BC 不是多余的 所以G5也是F的无冗余覆盖。 结论：无冗余覆盖不是唯一的。 无冗余覆盖是在F的覆盖集中去掉多余的函数依赖，还可以从其它角度去化简覆盖，比如：下面的化简覆盖是去掉多余的属性。,31,3.3.3 规范覆盖(canonical cover) 定义 设F是模式R上的一个FDs集，XYF。若模式R中的属性A满足下列条件，则称属性A在XY中是外部属性。 1. X=AZ, XZ，且(FXY)ZY F 或者; 2. Y=AW, YW，且(FXY)XW F。,36,35,32,定义(化简覆盖) 若FD XY的左部或右部都不包含外部属性，称FD XY是化

19、简的。 如果FDs集F中的所有FD都是化简的，称FDs集F是化简的。如果F是G的一个覆盖且F是化简的，称F是G的一个化简覆盖。 化简覆盖的算法类似于无冗余覆盖，也是用成员测试算法，不同之处在分别对F的每个函数依赖的左边和右边的属性分别进行检测，看是否存在多余的属性，去掉多余的属性。,33,定义(规范覆盖) 如果FDs集F是G的一个覆盖，F中的每个FD都具有XA形式而且F是左化简的和无冗余的，称F是G的一个规范覆盖。,计算规范覆盖： （1）将每个FD的右部化为单属性； （2）将每个FD化为左简化的； （3）计算无冗余的覆盖。,34,3.3.4 最小覆盖 定义(最小覆盖) 如果FDs集F和任一等价

20、的FDs集G相比，具有最少的函数依赖数，则称F为G的最小覆盖。,例： G=ABC, BA, ADE, BDI F=ABC, BA, ADEI,35,3.4 多值依赖 3.4.1多值依赖(Multivalued Dependency，MVD),36,下下,t1 t3 t4 t2,COURSE TEACHER COURSE CLASS,下页,37,定义(MVD) 设关系模式R，X、Y R 且 Z=R-(XY)。若对r(R)中任意元组t1、t2有t1X=t2X，则在r中存在元组t3且满足： t3X=t1X，t3Y=t1Y，且t3Z=t2Z 关系r(R)满足多值依赖 (MVD) XY，称X多值决定Y或

21、Y多值依赖于X。 关于多值依赖，还有下面等价的定义：,定义（MVD）设关系模式R，X、Y R 且Z=R-(XY)。若关系模式R满足多值依赖 (MVD) XY，当且仅当对R上的任一关系r，给定一对（x, z）的值，有一组y的值，这组值仅仅决定于x值而与z的值无关。,38,MVD的示意图： 表示已存在的元组： 可推出还应该存在的元组： x y1 z1 x y2 z1 x y2 z2 x y1 z2 引理： 设关系模式R和R上的关系r，X、YR 且Z=R-(XY)。若r满足多值依赖XY，则r满足多值依赖XZ。 该引理称为多值依赖的对称性或互补性。,39,3.4.2 多值依赖的性质 定理12 设关系r

22、(R)，X、Y和Z是R的子集且 Z=R-(XY)，当且仅当关系r无损地分解成关系模式R1 =XY和R2 =XZ，则 r满足XY。,无损分解: 设r是模式R(XYZ)上的关系，r 分解成r1 (XY)和r2(XZ)，即r1 =XY(r), r2=XZ (r)。则有：,40,测试关系r是否满足MVD ： (1). 根据多值依赖的性质； (2). r是否满足： |Y ( X=x(r)| = |Y ( XZ=xz(r)| 其中， R=XYZ, Z=R -(XY),推论： 设r是模式R上的一个关系，并设X和Y是R的子集。如果r满足FD XY，则r满足MVD XY。,41,3.4.3 多值依赖的推理公理

23、多值依赖的推理公理M1M9 M1：自反性 若Y X 则XY。 M2：增广性 若XY，W Z，则XZYW。 M3：相加性 若XY、XZ，则XYZ。 M4：投影性 若XY、XZ，则 XYZ 、 XYZ 。 M5：传递性 若XY、YZ，则XZY。 M6：伪传递性 若XY、YWZ，则 XWZ(YW)。 M7：互补性 若XY、ZR(XY)，则XZ。 M8：重复性 若XY，则XY。 M9：结合性 若XY，ZW，其中W Y和 YZ，则XW。,42,例： 设R=ABCDE，F=ABC，DEC 求证：F |= ADBE,证明：由ABC，由M7(互补性）得： ADE， 已知 DEC，由M5（传递性）得： AC， 又 A AD,由M1得： ADA ， 由M5（传递性）得:ADC 由M7 (互补性）得： ADBE。 思考：上面例子中传递性是否正确？传递性：若XY、YZ，