【教学课件】第三章数据依赖.ppt

第三章第三章 数数 据据 依依 赖赖1本章的主要内容：本章的主要内容：u 函数依赖的概念及函数依赖公理函数依赖的概念及函数依赖公理u 函数依赖集的等价和覆盖函数依赖集的等价和覆盖u 多值依赖及多值依赖公理多值依赖及多值依赖公理u 连接依赖连接依赖2数据依赖数据依赖:函数依赖、多值依赖、连接依赖函数依赖、多值依赖、连接依赖数据依赖数据依赖l是通过一个关系中属性间值的相等与否体现出来的是通过一个关系中属性间值的相等与否体现出来的数据间的相互关系数据间的相互关系l是现实世界属性间相互联系的抽象是现实世界属性间相互联系的抽象l是数据内在的性质是数据内在的性质l是语义的体现是语义的体现33.1 3.1 函数依赖函数依赖(Functional dependency FD)Functional dependency FD)定义定义1(1(FD)FD)设关系模式设关系模式R(U)R(U)，X,Y X,Y U U，r r是是R(U)R(U)上的任一关系，上的任一关系，对任意对任意t t1 1、t t2 2 r,r,如果如果 t t1 1X=tX=t2 2X X 有有t t1 1Y=tY=t2 2 YY，称称X X函数决定函数决定Y Y，或或Y Y函数依赖于函数依赖于X X，记为：记为：FD XYFD XY。

定义定义2（FD）对对X中的任一值中的任一值x，Y(X=x(r)的值仅有一个的值仅有一个元组，则有元组，则有XY定义定义(平凡平凡/非平凡的非平凡的FD)设设FDXY，如果如果Y X，则称则称FDXY为为非平凡的函非平凡的函数依赖数依赖；否则，若；否则，若Y X，称称FDXY为为平凡的函数依赖平凡的函数依赖4 定义定义(完全完全FD):FD):设设FD XYFD XY，如果对任意的如果对任意的X XX X，X X YY都不成立，则称都不成立，则称XYXY是完全函数依赖；若对是完全函数依赖；若对X X的真子的真子集集X X 有有X XX X，而而X X YY成立，则称成立，则称FD XYFD XY是部分函数是部分函数依赖，即依赖，即Y Y函数依赖于函数依赖于X X的一部分的一部分定义定义(传递传递FD):FD):设关系模式设关系模式R R，X X、Y Y、Z Z是是R R的属性子集，的属性子集，若若FD XYFD XY，Y XY X，YZYZ，则有则有FD XZFD XZ，称称FD XZFD XZ为为传递函数依赖传递函数依赖5函数依赖的例子函数依赖的例子学校数据库的语义：学校数据库的语义：一个系有若干学生，一个系有若干学生，一个学生只属于一个系；一个学生只属于一个系；一个系只有一名主任；一个系只有一名主任；一个学生可以选修多门课程，一个学生可以选修多门课程，每门课程有若每门课程有若干学生选修；干学生选修；每个学生所学的每门课程都有一个成绩。

每个学生所学的每门课程都有一个成绩R(SNO,CNO,SNAME,GRADE,DEPT,MNG)R(SNO,CNO,SNAME,GRADE,DEPT,MNG)SNO DEPT,DEPT MNG;SNO DEPT,DEPT MNG;SNO,CNO SNO,CNOGRADEGRADE;SNO,CNOSNO;SNO,CNOSNO,CNOSNO;SNO,CNOSNAMESNAME;SNO;SNOMNGMNG 63.2 3.2 函数依赖公理函数依赖公理3.2.1 3.2.1 函数依赖公理函数依赖公理定义定义(FDFD的逻辑蕴涵的逻辑蕴涵)：设关系模式设关系模式R(U,F)R(U,F)，X,YX,Y U U，如果能从函数依赖如果能从函数依赖集集F F推导出推导出FD XYFD XY，则称则称 F F逻辑蕴涵逻辑蕴涵 FD XYFD XY，或称或称XYXY逻辑蕴涵于逻辑蕴涵于F F记为记为 F|=XYF|=XY7ArmstrongArmstrong公理：公理：设设r r是是R(U)R(U)上的一个关系，上的一个关系，X X、Y Y、Z Z、W W U UA1.A1.自反律自反律:若若Y Y X X U,U,则则 XY;XY;A2.A2.增广律增广律:若若XYXY且且Z Z U U，则则 XZYZ;XZYZ;A3.A3.传递律传递律:若若XY,YZXY,YZ，则则 XZ.XZ.8证明：证明：A1.A1.自反律自反律:若若Y Y X X U,U,则则 XY;XY;设设r是是R的关系，的关系，t1,t2是是r的任意元组，的任意元组，X、Y、Z U(1)对对X的任意值的任意值x，有有X(X=x(r)至多有一个元组，至多有一个元组，因因Y X，Y(X=x(r)至多只有一个元组，则有至多只有一个元组，则有XY9证明：证明：A2.A2.增广律增广律:若若XYXY且且Z Z U U，则则 XZYZ;XZYZ;(2)对任意对任意x值，值，X(X=x(r)至多有一个至多有一个元组。

有元组有：XZ=xz(r)X=x(r)，则则Y(XZ=xz(r)Y(X=x(r)所以，所以，Y(XZ=xz(r)至多有一个元组，至多有一个元组，r必满足必满足XZY10证明：证明：A3.A3.传递律传递律:若若XY,YZXY,YZ，则则 XZ.XZ.(3)若若XY，则则t1X=t2X，t1Y=t2Y又又YZ，则有则有t1Y=t2Y，t1Z=t2Z显然，显然，XY在在r中成立11推论推论1 1 若若XYXY，XZXZ，则则XYZXYZ证明：若证明：若XYXXYXZXYYZXYZ推论推论2 2 若若XYXY且且Z Z Y Y，则则XZXZ证明：证明：Z YYZ推论推论3 3 若若XYXY，YZWYZW，则则XZWXZW证明：证明：XYXZYZYZWXZW12示例：示例：SC(SNO,CNO,SNAME,GRADE,DEPT,MN)SC(SNO,CNO,SNAME,GRADE,DEPT,MN)F=F=SNO,CNOGRADESNO,CNOGRADE，SNO SNO SNAMESNAME，DEPTDEPT，DEPT MN DEPT MN SNO SNO SNAMESNAME，DEPTDEPT，MN MN SNO,CNO SNO,CNO SNAMESNAME，DEPTDEPT，MNMN SNO,CNO SNO,CNO SNAME,GRADE,DEPT,MNSNAME,GRADE,DEPT,MN13定理定理1如果如果A Ai i(i=1,2,n)是关系模式是关系模式R的的属性，则属性，则XA A1 1A A2 2A An n成立的充要条件是：成立的充要条件是：XA Ai i(i=1,2,n)都成立。

都成立14 例：例：设设F=ABEF=ABE，AGJAGJ，BEIBEI，EGEG，GIH GIH 试证：试证：F|=ABGHF|=ABGH 证明：用公理系统和证明：用公理系统和F F中的函数依赖，推导过程如下：中的函数依赖，推导过程如下：1.1.已知已知 ABEABE，EGEG 则：则：ABGABG；(传递律传递律)2.2.已知已知 ABE ABE 则：则：ABBEABBE；(增广律增广律)3.3.已知已知 BEIBEI，又又 ABBEABBE 则：则：ABI ABI (传递律传递律)4.4.由由1 1和和3 3有有ABGABG，ABI ABI 则：则：ABGI ABGI (合成规则合成规则)5.5.由由4 4有有 ABGIABGI，又又 GIHGIH 则：则：ABH ABH (传递律传递律)6.6.由由1 1和和5 5有有 ABHABH，ABG ABG 则：则：ABGH ABGH (合成规则合成规则)15定义定义(使用集使用集)用公理从用公理从F推出推出XY成立所使用的函数成立所使用的函数依赖组成的序列称依赖组成的序列称F上的一个推理序列由推上的一个推理序列由推理序列中出现的且包含在理序列中出现的且包含在F中的函数依赖的集中的函数依赖的集合称推理序列的使用集合称推理序列的使用集(useset)，记为：记为：U(F,XY)例：例：U(F,ABGH)=ABE，EG，BEI，GIH163.2.2 3.2.2 公理的完备性公理的完备性定义定义(FDsFDs的闭包的闭包 F F+)设设F F是关系是关系r(R)r(R)上的上的FDsFDs，F F所蕴含的所有所蕴含的所有FDFD的集合称为的集合称为F F的闭包，记作的闭包，记作F F+。

F F+=XY|=XY|所有所有F|=XY F|=XY 17例：例：设设F=ABCF=ABC，CBCBF F+为：为：F F+=AA,ABA,ACA,ABCA,BB,ABB,=AA,ABA,ACA,ABCA,BB,ABB,BCBBCB，ABCBABCB，CCCC，ACCACC，BCC,ABCCBCC,ABCC，ABABABAB，ABCABABCAB，ACACACAC，ABCACABCAC，BCBC,ABCBC,BCBC,ABCBC,ABCABC,ABC,ABAC,ABBC,ABABCABCABC,ABC,ABAC,ABBC,ABABC，CB,CB,CBCCBC，ACB ACB，ACABACAB18定义定义(属性集的闭包属性集的闭包X X+)设关系模式设关系模式R(U,F)R(U,F)，X X U,U,所有用公理推出的所有用公理推出的XAXAi i中中A Ai i的属性集合称的属性集合称X X对于对于F F的闭包，记作：的闭包，记作：X X+X X+=A=Ai i|用公理推出的用公理推出的XAXAi i 且且A Ai i UU19定理定理2Armstrong公理是完备的公理是完备的证明：如果能证明证明：如果能证明XYXY不能由公理推出将不会被不能由公理推出将不会被F F所蕴涵，所蕴涵，则公理得证。

为此，构造一个关系则公理得证为此，构造一个关系r(R)r(R)我们将证明两点：我们将证明两点：(1).(1).F F中的所有函数依赖在中的所有函数依赖在 r(R)r(R)上都成立；上都成立；(2).(2).XYXY在在r(R)r(R)上不成立上不成立20设设R=A1A2An，关系关系r中仅有二个元组中仅有二个元组t和和t元组元组t=a1a2an元组元组t被定义为：被定义为：ai若若Ai X+t(Ai)=bi若若Ai X+X+U-U-X+A1A2.AkAk+1.An t t a1 a2.ak ak+1.an t a1 a2.ak bk+1 .bn21 证明：证明：(1)(1)设设WZWZ F F，W W在在r r中有两种情况中有两种情况:(a)W a)W X X+根据属性闭包定义，有根据属性闭包定义，有XWXW，又因又因WZWZ，根据公理根据公理A3A3有有 XZXZ因此因此 Z Z X X+，即即 tZ=ttZ=tZ=Z=a ai i,所以，所以，WZWZ在在r r上成立b)W b)W X X+则在则在r r中有中有tW tW t tWW，因此，因此，WZWZ在在r r上总是成立的上总是成立的。

由由(a)a)和和(b)b)得：得：r r(R)满足满足F F2)若若XY不能由公理推出即不能由公理推出即X X+而而Y X+，由由r的构造知，的构造知，XY在在r上不成立，即上不成立，即XY不被不被F所蕴涵223.2.3函数依赖集闭包及成员测试算法函数依赖集闭包及成员测试算法算法算法1计算属性集计算属性集X的闭包的闭包X+的算法的算法输入：属性集输入：属性集X和函数依赖集和函数依赖集F输出：输出：X的闭包的闭包X+While RESULTVAR do BeginWhile RESULTVAR do Begin VAR:=RESULT;VAR:=RESULT;for every FD WZ in F do for every FD WZ in F do if Wif W RESULT thenRESULT then RESULT:=RESULTZ RESULT:=RESULTZ end;end;return(RESULT)return(RESULT)end.。