第06章关系数据理论(2)PPT讲稿.ppt

《第06章关系数据理论(2)PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第06章关系数据理论(2)PPT讲稿.ppt（41页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第第0606章关系数据理论章关系数据理论(2)(2)第1页，共41页，编辑于2022年，星期日复复 习习1.1.关系模式存在的四种异常现象关系模式存在的四种异常现象2.2.函数依赖、非平凡函数依赖函数依赖、非平凡函数依赖3.3.完全函数依赖、部分函数依赖完全函数依赖、部分函数依赖4.4.传递函数依赖传递函数依赖5.1NF5.1NF、2NF2NF、3NF3NF第2页，共41页，编辑于2022年，星期日1.BCNF1.BCNF1.BCNF1.BCNF定义：定义：定义：定义：设关系模式设关系模式RR 1NF1NF，如果对于，如果对于R R的每个函数依赖的每个函数依赖XYXY，若若Y Y不属于不属于X

2、 X，则，则X X必含有候选码，那么必含有候选码，那么R R BCNFBCNF。若若R R BCNF BCNF，则，则R R 3NF3NF。2.2.2.2.性质：性质：性质：性质：6.2.6 BCNF6.2.6 BCNF(1)(1)若若R R 3NF3NF，且，且R R只有一个候选码，则只有一个候选码，则R R必属于必属于BCNFBCNF。(2)(2)所有非主属性对每一个码都是完全函数依赖。所有非主属性对每一个码都是完全函数依赖。(3)(3)所有主属性对每一个不包含它的码都是完全函数依赖所有主属性对每一个不包含它的码都是完全函数依赖(4)(4)没有任何属性完全函数依赖于非码的任何一组属性。没有

3、任何属性完全函数依赖于非码的任何一组属性。第3页，共41页，编辑于2022年，星期日例：关系模式例：关系模式SJP(S,J,P)中，中，S-学生、学生、J-课程、课程、P-名次，名次，n每个学生选修每门课程的成绩都有一定的名次，每个学生选修每门课程的成绩都有一定的名次，n每门课程中每一名次只有一个学生每门课程中每一名次只有一个学生(即没有并列名次即没有并列名次)。则有：函数依赖则有：函数依赖(S,J)P，(J,P)S，所以所以(S,J)与与(J,P)都可以作为候选码，都可以作为候选码，SJP BCNF。6.2.6 BCNF6.2.6 BCNF 从函数依赖的范畴考虑，从函数依赖的范畴考虑，BCN

4、FBCNF已完成了模式的彻底分解，已完成了模式的彻底分解，消除了插入、删除和更新异常，数据冗余度大大降低，但从数据消除了插入、删除和更新异常，数据冗余度大大降低，但从数据依赖的角度，依赖的角度，BCNFBCNF的关系模式仍存在一定的问题的关系模式仍存在一定的问题。第4页，共41页，编辑于2022年，星期日6.2.6 BCNF6.2.6 BCNF小结：小结：1.从定义可以看出：从定义可以看出：2.转换方式：转换方式：(1)1NF2NF：消除：消除1NF中中非主属性非主属性对候选码的对候选码的部分依部分依赖赖(2)2NF3NF：消除：消除2NF中中非主属性非主属性对候选码的对候选码的传递依传递依赖

5、赖(3)3NFBCNF：消除：消除3NF中中主属性主属性对候选码的对候选码的部分依部分依赖和传递依赖赖和传递依赖第5页，共41页，编辑于2022年，星期日6.2.6 BCNF6.2.6 BCNF小结：小结：3.如果一个关系模式属于如果一个关系模式属于BCNF，那么在函数依赖，那么在函数依赖的范畴内，已经实现模式的彻底分解，达到了最高的范畴内，已经实现模式的彻底分解，达到了最高的规范化程度，消除了插入异常和删除异常的规范化程度，消除了插入异常和删除异常4.对于不好的关系模式，就是对存在弊端函数依赖对于不好的关系模式，就是对存在弊端函数依赖进行分解。进行分解。第6页，共41页，编辑于2022年，星

6、期日练练 习习指出下列关系模式是第几范式？并说明理由。指出下列关系模式是第几范式？并说明理由。指出下列关系模式是第几范式？并说明理由。指出下列关系模式是第几范式？并说明理由。(1)R1(X,Y,Z)(1)R1(X,Y,Z)(1)R1(X,Y,Z)(1)R1(X,Y,Z)F=(XY F=(XY F=(XY F=(XYZZ)(2)R(X,Y,Z)(2)R(X,Y,Z)(2)R(X,Y,Z)(2)R(X,Y,Z)F=(X F=(XY,X ZY,X Z)(3)R(W,X,Y,Z)(3)R(W,X,Y,Z)F=(X F=(XZ,WX YZ,WX Y)R1是是BCNFR2是是BCNFR3是是1NF第7页，

7、共41页，编辑于2022年，星期日6.3 6.3 数据依赖的公理系统数据依赖的公理系统1.1.1.1.逻辑蕴含逻辑蕴含逻辑蕴含逻辑蕴含定义定义6.116.11对于满足一组函数依赖对于满足一组函数依赖 F F F F 的关系模式的关系模式的关系模式的关系模式R R R R ，其任何一个关系，其任何一个关系，其任何一个关系，其任何一个关系r r，若函数依赖，若函数依赖XYXYXYXY都成立都成立都成立都成立,则称则称F F F F 逻辑蕴含逻辑蕴含逻辑蕴含逻辑蕴含XYXYXYXY。例如：例如：例如：例如：设关系模式设关系模式R，有，有A U、B U、C U；又假设；又假设在在R中有函数依赖集中有函

8、数依赖集F=AB，BC，则称则称则称则称R R中有函数依赖中有函数依赖中有函数依赖中有函数依赖ACAC，即，即，即，即F F逻辑蕴涵逻辑蕴涵逻辑蕴涵逻辑蕴涵ACAC。第8页，共41页，编辑于2022年，星期日6.3 6.3 数据依赖的公理系统数据依赖的公理系统2.Armstrong2.Armstrong2.Armstrong2.Armstrong公理系统公理系统公理系统公理系统一套推理规则，是一套推理规则，是模式分解模式分解算法的理论基础算法的理论基础用途：用途：(1)(1)求给定关系模式的码求给定关系模式的码 (2)(2)从一组函数依赖求得蕴含的函数依赖从一组函数依赖求得蕴含的函数依赖第9页

9、，共41页，编辑于2022年，星期日6.3 6.3 数据依赖的公理系统数据依赖的公理系统(1)Armstrong(1)Armstrong(1)Armstrong(1)Armstrong公理系统的内容公理系统的内容:对关系模式对关系模式R UR F 来说来说,有以下的推理规则：有以下的推理规则：Al.自反律：自反律：若若Y Y X X U U，则，则X XY Y为为F F 所蕴含。所蕴含。A2.增广律增广律：若若X XY Y为为F F所蕴含，且所蕴含，且Z Z U U，则则XZXZYZYZ为为F F所蕴含。所蕴含。A3.传递律传递律：若若X XY Y 及及Y YZ Z 为为F F所蕴含，所蕴含，

10、则则X XZ Z 为为F F所蕴含。所蕴含。注意：由自反律所得到的函数依赖均是平凡的注意：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于函数依赖，自反律的使用并不依赖于F F。第10页，共41页，编辑于2022年，星期日6.3 6.3 数据依赖的公理系统数据依赖的公理系统(2)Armstrong(2)Armstrong(2)Armstrong(2)Armstrong定理的证明定理的证明定理的证明定理的证明 定理定理定理定理 6.l Armstrong6.l Armstrong6.l Armstrong6.l Armstrong推理规则是正确的推理规则是正确的推理规则是正确的

11、推理规则是正确的 自反律：若自反律：若Y Y X X U U，则，则X X Y Y为为F F所蕴含所蕴含证证:设设Y Y X X U U 对对R UR F 的任一关系的任一关系r r中的任意两个元组中的任意两个元组t t，s s：若：若：t t X X=s s X X，由于由于Y Y X X，则有：则有：t t y y=s s y y，所以：所以：X XY Y成立成立.自反律得证自反律得证第11页，共41页，编辑于2022年，星期日6.3 6.3 数据依赖的公理系统数据依赖的公理系统 增广律增广律:若若XYXY为为F F所蕴含，且所蕴含，且Z Z U U，则则XZYZ XZYZ 为为F F所蕴

12、含。所蕴含。证：证：设设XYXY为为F F所蕴含，且所蕴含，且Z Z U U。设设RURF 的任一关系的任一关系r r中任意的两个元组中任意的两个元组t t，s s；若：若：t t XZXZ=s s XZXZ，则有，则有:t t X X=s s X X 和和t t Z Z=s s Z Z；由由X XY Y，于是有，于是有t t Y Y=s s Y Y，所以，所以t t YZYZ=s s YZYZ，所以：所以：XZXZYZYZ为为F F所蕴含所蕴含.增广律得证。增广律得证。(2)Armstrong(2)Armstrong(2)Armstrong(2)Armstrong定理的证明定理的证明定理的证

13、明定理的证明第12页，共41页，编辑于2022年，星期日6.3 6.3 数据依赖的公理系统数据依赖的公理系统 传递律：若传递律：若XYXY及及YZYZ为为F F所蕴含，则所蕴含，则XZXZ为为F F所蕴含。所蕴含。证：设证：设X XY Y及及Y YZ Z为为F F所蕴含。所蕴含。对对RURF 的任一关系的任一关系 r r中的任意两个元组中的任意两个元组 t t，s s。由于由于X XY Y，若若t t X X=s s X X，则有，则有t t Y Y=s s Y Y；再由再由Y YZ Z，若，若t t Y Y=s s Y Y，则有，则有t t Z Z=s s Z Z，所以所以X XZ Z为为F

14、 F所蕴含所蕴含.传递律得证。传递律得证。(2)Armstrong(2)Armstrong(2)Armstrong(2)Armstrong定理的证明定理的证明定理的证明定理的证明第13页，共41页，编辑于2022年，星期日6.3 6.3 数据依赖的公理系统数据依赖的公理系统例：关系模式例：关系模式R,R,属性集属性集U=CITY,STU=CITY,ST，ZIP,ZIP,函数依赖集函数依赖集F=(CITY,ST)ZIPF=(CITY,ST)ZIP，ZIP CITYZIP CITY，证明，证明STST，ZIPZIP和和CITY,ST CITY,ST 为侯选码。为侯选码。证：证：(1)(1)由：由：

15、ZIP CITY (ZIP CITY (已知已知)则：则：(ST(ST，ZIP)(CITYZIP)(CITY，ST)(ST)(增广律增广律)得：得：(ST(ST，ZIP)(CITYZIP)(CITY，STST，ZIP)(ZIP)(增广律增广律)其中：其中：ST(CITYST(CITY，ST ST，ZIP)ZIP)，ZIP(CITYZIP(CITY，STST，ZIP)ZIP)均是不成立的均是不成立的 所以：所以：STST，ZIPZIP是侯选码是侯选码(2)(2)由：由：(CITY(CITY，ST)ZIP (ST)ZIP (已知已知)则：则：(CITY(CITY，ST)(CITYST)(CITY，

16、ST ST，ZIP)(ZIP)(增广律增广律)第14页，共41页，编辑于2022年，星期日(3)Armstrong(3)Armstrong(3)Armstrong(3)Armstrong公理的导出规则：公理的导出规则：根据根据A1A1、A2A2、A3A3三条推理可以导出如下规则：三条推理可以导出如下规则：合并规则：合并规则：由由XY，XZ，有，有XYZ。(A2,A3)伪传递规则伪传递规则：由：由XY，WYZ，有，有XWZ。(A2,A3)分解规则分解规则：由：由XY及及Z Y，有，有XZ。(A1,A3)6.3 6.3 数据依赖的公理系统数据依赖的公理系统根据合并规则和分解规则，可得根据合并规则和

17、分解规则，可得引理引理引理引理6.16.16.16.1：X(A1A2Ak)成立的充分必要条件是成立的充分必要条件是XAi成立成立(i=l,2,k)第15页，共41页，编辑于2022年，星期日3.3.3.3.函数依赖闭包函数依赖闭包函数依赖闭包函数依赖闭包6.3 6.3 数据依赖的公理系统数据依赖的公理系统定义定义6.l26.l2 在关系模式在关系模式RURF中，为中，为F F所逻辑蕴含的函数所逻辑蕴含的函数依赖的全体叫作依赖的全体叫作 F F 的闭包的闭包，记为，记为F F+。例：设关系模式例：设关系模式RRRR，U=AU=AU=AU=A，B B，CCCC，F=ABCF=ABC，CBCBCBC

18、B是是是是RRRR上的一组函数依赖上的一组函数依赖,求求求求F F F F第16页，共41页，编辑于2022年，星期日3.3.3.3.函数依赖闭包函数依赖闭包函数依赖闭包函数依赖闭包6.3 6.3 数据依赖的公理系统数据依赖的公理系统例：设关系模式例：设关系模式例：设关系模式例：设关系模式RR，U=AU=A，B B，CC，F=ABCF=ABC，CBCB是是是是RR上的一组函数依赖，则：上的一组函数依赖，则：上的一组函数依赖，则：上的一组函数依赖，则：FF+=AA=AA，ABAABA，ACAACA，ABCAABCA，BBBB，ABBABB，BCBBCB，ABCBABCB，CCCC，ACCACC，

19、BCCBCC，ABCCABCC，ABABABAB，ABCABABCAB，ACACACAC，ABCACABCAC，BCBCBCBC，ABCBCABCBC，ABCABCABCABC，ABCABC，ABACABAC，ABBCABBC，ABABCABABC，CBCB，CBCCBC，ACAB,ACABCACAB,ACABC 第17页，共41页，编辑于2022年，星期日3.3.3.3.函数依赖闭包函数依赖闭包函数依赖闭包函数依赖闭包6.3 6.3 数据依赖的公理系统数据依赖的公理系统定义定义6.136.13 设关系模式设关系模式RUR F，U=AU=A1 1,A,A2 2,A,An n，X X U U，X

20、 XF F+=A Ai i|XA|XAi i能由能由F F 根据根据ArmstrongArmstrong公理导出公理导出，X XF F+称为称为属性集属性集属性集属性集X X X X关于函关于函关于函关于函数依赖集数依赖集数依赖集数依赖集F F F F 的闭包的闭包的闭包的闭包例：例：设关系模式设关系模式R，U=A，B，C，D，E，F=ABC，CDE，BD，EA是是R上的一组函数依赖，则：上的一组函数依赖，则：BF+是？是？AF+是？是？BF+=B，DAF+=A，B，C，D，E第18页，共41页，编辑于2022年，星期日3.3.3.3.函数依赖闭包函数依赖闭包函数依赖闭包函数依赖闭包6.3 6

21、.3 数据依赖的公理系统数据依赖的公理系统引理引理引理引理6.2 6.2 6.2 6.2 设设F为属性集为属性集U上的一组函数依赖，上的一组函数依赖，X，Y U，XY能由能由F 根根据据Armstrong公理导出的公理导出的充分必要条件充分必要条件是是Y XF+。用途用途用途用途将判定将判定XY是否能由是否能由F根据根据Armstrong公理导出的问题，就公理导出的问题，就转化转化转化转化为为为为求出求出XF+，判定，判定Y是否为是否为XF+的子集的问题的子集的问题第19页，共41页，编辑于2022年，星期日4.4.4.4.求求求求X X X XF F F F+的算法：的算法：的算法：的算法：

22、算法算法算法算法6.16.16.16.1：属性集：属性集：属性集：属性集X(XX(XX(XX(X U)U)U)U)关于关于关于关于U U U U上函数依赖集上函数依赖集上函数依赖集上函数依赖集F F F F的闭包的闭包的闭包的闭包输入：输入：输入：输入：X X X X，F F F F 输出：输出：输出：输出：X X X XF F F F+令令X(0)(0)=X，i=0。求求B，B=A|(V)(W)(VW F V X(i)A W)。X(i+1)(i+1)=B X(i)(i)。判断判断X(i+1)(i+1)=X(i)吗吗?若相等或若相等或X(i)(i)=U,则则X(i)(i)就是就是XF+,算法终

23、止；算法终止；否则否则i=i+1，返回第，返回第2步。步。6.3 6.3 数据依赖的公理系统数据依赖的公理系统第20页，共41页，编辑于2022年，星期日 例：例：设设X X(0)(0)=AB=AB；计算计算X X(1)(1):逐一的扫描逐一的扫描F F集合中各个函数依赖，集合中各个函数依赖，找左部为找左部为A A、B B或或ABAB的函数依赖，有的函数依赖，有ABCABC，BDBD，于是：于是：X X X X(1)(1)(1)(1)=X=X=X=X(0)(0)(0)(0)CD=ABCDCD=ABCDCD=ABCDCD=ABCD。因为因为X X(0)(0)XX(1)(1)，并且，并且X X(1

24、)(1)U,U,所以计算所以计算X X(2)(2)计算计算X X(2)(2):找出左部为找出左部为ABCDABCD子集的那些函数依赖，又得到子集的那些函数依赖，又得到ABCABC，BDBD，CECE，ACBACB，于是，于是 X X X X(2)(2)(2)(2)=X=X=X=X(1)(1)(1)(1)BCDE=ABCDEBCDE=ABCDEBCDE=ABCDEBCDE=ABCDE。因为因为X X(2)(2)=U=U，算法终止算法终止。所以所以(AB)(AB)(AB)(AB)F F F F+=ABCDE=ABCDE=ABCDE=ABCDE。例：已知关系模式例：已知关系模式RR，其中，其中U=A

25、U=A，B B，C C，D D，EE，F=ABC,BD,CE,ECB,ACBF=ABC,BD,CE,ECB,ACB，求，求(AB)(AB)F F+。第21页，共41页，编辑于2022年，星期日 1.1.已知关系已知关系R,R,其中其中U=A,B,C,D,E,F,F=AC,U=A,B,C,D,E,F,F=AC,BCDE,DA,FB,BCDE,DA,FB,则（则（A,BA,B）关于函数依赖集）关于函数依赖集 F F的闭包是？的闭包是？2.2.已知关系已知关系R,R,其中其中U=A,B,C,D,E,F,F=ABC,U=A,B,C,D,E,F,F=ABC,BCAD,DE,CFB,BCAD,DE,CFB

26、,则下列依赖蕴含于则下列依赖蕴含于F F的有的有_._.A.ABC B.ABD A.ABC B.ABD C.ABE B.ABF C.ABE B.ABF练习练习第22页，共41页，编辑于2022年，星期日6.3 6.3 数据依赖的公理系统数据依赖的公理系统5.5.5.5.定理定理定理定理6.2 Armstrong6.2 Armstrong6.2 Armstrong6.2 Armstrong公理系统的有效性与完备性公理系统的有效性与完备性公理系统的有效性与完备性公理系统的有效性与完备性有效性有效性有效性有效性(正确性正确性正确性正确性)：由：由F出发根据出发根据Armstrong公理推导出的每公理

27、推导出的每个函数依赖一定在个函数依赖一定在F+中。中。完备性完备性完备性完备性：F+中的每一个函数依赖，必定可以由中的每一个函数依赖，必定可以由F出发根据出发根据Armstrong公理推导出来。公理推导出来。ArmstrongArmstrong公理的完备性及有效性公理的完备性及有效性说明说明说明说明:“蕴含蕴含”=“导出导出”等价的概念等价的概念F F +=由由F F出发借助出发借助ArmstrongArmstrong公理导出的函数依赖的集公理导出的函数依赖的集合合第23页，共41页，编辑于2022年，星期日6.3 6.3 数据依赖的公理系统数据依赖的公理系统证明：完备性（证明：完备性（证明：

28、完备性（证明：完备性（F+中的每一个函数依赖，必定可以由中的每一个函数依赖，必定可以由F出发根据出发根据Armstrong公理推导出来）。公理推导出来）。假设有关系模式假设有关系模式RR，X X U U U U，Y Y Y Y U U U U，并进一步假设，并进一步假设，并进一步假设，并进一步假设存在如下一个具体的关系存在如下一个具体的关系存在如下一个具体的关系存在如下一个具体的关系r r r r（只包含两个元组），如果（只包含两个元组），如果（只包含两个元组），如果（只包含两个元组），如果能证明以下两点，公理的完备性就证明了：能证明以下两点，公理的完备性就证明了：能证明以下两点，公理的完备性

29、就证明了：能证明以下两点，公理的完备性就证明了：(1)(1)(1)(1)在关系在关系在关系在关系r r r r中，中，中，中，F F F F中的所有函数依赖都成立；中的所有函数依赖都成立；中的所有函数依赖都成立；中的所有函数依赖都成立；(2)(2)(2)(2)在关系在关系在关系在关系r r中，不能根据中，不能根据F F 用用AmstrongAmstrong公理推导出公理推导出的函数依赖的函数依赖XYXY不成立。不成立。XF+U-XF+111111111 000第24页，共41页，编辑于2022年，星期日6.3 6.3 数据依赖的公理系统数据依赖的公理系统证明：完备性证明：完备性证明：完备性证明

30、：完备性(1)(1)(1)(1)在关系在关系在关系在关系r r r r中，中，中，中，F F F F中的所有函数依赖都成立；中的所有函数依赖都成立；中的所有函数依赖都成立；中的所有函数依赖都成立；证：若证：若VWVW F F，有以下两种情况：，有以下两种情况：若若V V X XF F+,则则XV;XV;又由于又由于VWVW成立，根据传递律：成立，根据传递律：XWXW成立；成立；所以：所以：W W X XF F+。若若V V X XF F+，从假设可以看出，从假设可以看出，从假设可以看出，从假设可以看出，如果一个属性集不完全属于如果一个属性集不完全属于X XF F+，则该属性集在两个，则该属性集

31、在两个元组上的属性值必不相等，根据函数依赖的定义可知元组上的属性值必不相等，根据函数依赖的定义可知VWVW在在r r上成立。上成立。第25页，共41页，编辑于2022年，星期日6.3 6.3 数据依赖的公理系统数据依赖的公理系统证明：完备性证明：完备性证明：完备性证明：完备性(2)(2)(2)(2)在关系在关系在关系在关系r r r r中，不能根据中，不能根据中，不能根据中，不能根据F F F F 用用用用AmstrongAmstrongAmstrongAmstrong公理推导出的函数依赖公理推导出的函数依赖公理推导出的函数依赖公理推导出的函数依赖XYXYXYXY不成立。不成立。不成立。不成立

32、。证：若证：若XYXY不能由不能由F F F F 从从AmstrongAmstrongAmstrongAmstrong公理导出，则公理导出，则公理导出，则公理导出，则Y Y Y Y不是不是不是不是X X X XF F F F的子集，但的子集，但X X X XF F+。可以看出，在关系可以看出，在关系r r的两个元组上，的两个元组上，X X的属性值一致，的属性值一致，Y Y的的属性值不一致，根据函数依赖的定义可知，属性值不一致，根据函数依赖的定义可知，XYXY在在r r上是不成立上是不成立的。的。XF+U-XF+111111111 000第26页，共41页，编辑于2022年，星期日6.6.6.6

33、.函数依赖集的等价函数依赖集的等价覆盖和等价的概念覆盖和等价的概念定义定义6.146.14：设设F F和和G G是两个函数依赖集：是两个函数依赖集：(1)(1)如果如果F F GG，则称，则称，则称，则称 GG是是是是F F的一个的一个的一个的一个覆盖覆盖覆盖覆盖，或称或称或称或称 GG覆盖覆盖覆盖覆盖F F。(2)(2)如果如果F F GG和和和和 GG F F同时成立，即同时成立，即同时成立，即同时成立，即 F FGG ，则称则称则称则称GG和和和和F F等价等价等价等价。6.3 6.3 数据依赖的公理系统数据依赖的公理系统第27页，共41页，编辑于2022年，星期日6.6.6.6.函数依

34、赖集的等价函数依赖集的等价函数依赖集的等价函数依赖集的等价引理引理6.3：F+=G+的充分必要条件是的充分必要条件是F G+和和G F+。证证:必要性。必要性。若：若：F+=G+则：则：F F+G+和和G G+F+；所以：所以：F G+和和G F+是成立的。是成立的。6.3 6.3 数据依赖的公理系统数据依赖的公理系统第28页，共41页，编辑于2022年，星期日6.6.6.6.函数依赖集的等价函数依赖集的等价函数依赖集的等价函数依赖集的等价引理引理6.3：F+=G+的充分必要条件是的充分必要条件是F G+和和G F+。证证:充分性。充分性。若：若：F G+，则，则XF+XG+。任取任取XY F

35、+，则有，则有Y XF+XG+，所以：所以：XY(G+)+，而，而(G+)+=G+。即。即F+G+。同理可证同理可证G+F+，所以，所以F+=G+。判断方法：要判定判断方法：要判定F F G G+，只须逐一对，只须逐一对F F中的函数依赖中的函数依赖XYXY，考察，考察Y Y是否属于是否属于X XG+G+就行了。就行了。6.3 6.3 数据依赖的公理系统数据依赖的公理系统第29页，共41页，编辑于2022年，星期日7.7.7.7.最小依赖集：最小依赖集：最小依赖集：最小依赖集：定定定定义义义义6.15 6.15 6.15 6.15 如如果果函函数数依依赖赖集集F F满满足足下下列列条条件件，则

36、则称称F F为为一一个个极极小函数依赖集，亦称为小函数依赖集，亦称为最小依赖集最小依赖集最小依赖集最小依赖集或最小覆盖。或最小覆盖。F F中任一函数依赖的右部仅含有一个属性。中任一函数依赖的右部仅含有一个属性。F F中不存在这样的函数依赖中不存在这样的函数依赖XAXA，使得，使得F F与与F F XA XA等价。等价。F F中不存在这样的函数依赖中不存在这样的函数依赖XAXA，X X有真子集有真子集Z Z使得使得 F FXAZAXAZA与与F F等价。等价。6.3 6.3 数据依赖的公理系统数据依赖的公理系统第30页，共41页，编辑于2022年，星期日例例：设关系模式：设关系模式S中中,U=S

37、no,Sdept,Mname,Cno,Grade设设：F=SnoSdept,SdeptMname，(Sno,Cno)GradeF=SnoSdept，SnoMname，SdeptMname,(Sno,Cno)Grade，(Sno,Sdept)Sdept，验证：验证：F是最小覆盖，而是最小覆盖，而F不是。不是。因为：因为：FSnoMname与与F等价；等价；F(Sno,Sdept)Sdept SnoSdept也与也与F等价等价。F(Sno,Sdept)Sdept也与也与F等价；等价；6.3 6.3 数据依赖的公理系统数据依赖的公理系统第31页，共41页，编辑于2022年，星期日8.8.8.8.求求

38、求求F F F F最小依赖集最小依赖集最小依赖集最小依赖集FmFmFmFm的过程的过程的过程的过程6.3 6.3 数据依赖的公理系统数据依赖的公理系统(1)(1)逐一检查逐一检查F F 中各函数依赖中各函数依赖FDFDi i：X XY Y,若若Y Y=A A1 1A A2 2 A Ak k,k k22，则用，则用 X XA Aj j|j j=1=1，2 2，k k 来取代来取代X XY Y。引理引理6.16.1保证了保证了F F变换前后的等价性。变换前后的等价性。定理定理定理定理6.36.36.36.3每一个函数依赖集每一个函数依赖集F均等价于一个极小函数依赖集均等价于一个极小函数依赖集Fm。

39、此。此Fm称为称为F的最小依赖集。的最小依赖集。求最小依赖集的步骤：求最小依赖集的步骤：求最小依赖集的步骤：求最小依赖集的步骤：（即定理的证明过程）（即定理的证明过程）（即定理的证明过程）（即定理的证明过程）第32页，共41页，编辑于2022年，星期日8.8.8.8.求求求求F F F F最小依赖集最小依赖集最小依赖集最小依赖集FmFmFmFm的过程的过程的过程的过程6.3 6.3 数据依赖的公理系统数据依赖的公理系统(3)(3)逐一取出逐一取出F F 中各函数依赖中各函数依赖FDFDi i：X XA A，设，设X X=B B1 1B B2 2B Bm m，逐一考查逐一考查B Bi i （i

40、i=l=l，2 2，m m），若），若A A （X X-B Bi i ）F F+，则以则以X X-B Bi i 取代取代X X。因为：因为：F F与与F F-X XA AZ ZA A 等价的充要条件是等价的充要条件是 A A Z ZF F+，其中，其中Z Z=X X-B Bi i ,所以：所以：F F变换前后是等价的。变换前后是等价的。(2)(2)逐一检查逐一检查F F 中各函数依赖中各函数依赖FDFDi i：XAXA，令，令G=F-XAG=F-XA，若若A A X XG G+，则从，则从F F中去掉此函数依赖。中去掉此函数依赖。因为：因为：F F与与G=F-XAG=F-XA等价的充要条件是等

41、价的充要条件是A A X XG G+所以：所以：F F变换前后是等价的变换前后是等价的。第33页，共41页，编辑于2022年，星期日例例：F=AB，BA，BC，AC，CA，确定确定F的最小依赖集。的最小依赖集。Fm1=AB,BC,CAFm2=AB,BA,AC,CA6.3 6.3 数据依赖的公理系统数据依赖的公理系统 F F的最小依赖集的最小依赖集F Fm m不一定是唯一的，它与对各函数依赖不一定是唯一的，它与对各函数依赖FDFDi i及及XAXA中中X X各属性的处理顺序有关。各属性的处理顺序有关。练习：设有关系模式练习：设有关系模式R，其中：，其中：UE,F,G,H函数依赖集函数依赖集F=E

42、G，GE，FEG，HEG，FHE，求求F的最小依赖集的最小依赖集第34页，共41页，编辑于2022年，星期日练习练习：设有关系模式：设有关系模式R，其中：，其中：UE,F,G,H函数依赖集函数依赖集F=EG，GE，FEG，HEG，FHE，求求F F的最小依赖集的最小依赖集6.3 6.3 数据依赖的公理系统数据依赖的公理系统(1)将函数依赖右边的属性单一化将函数依赖右边的属性单一化EG，GE，FE，FG，HE，HG，FHE(3)去掉函数依赖左边多余的属性去掉函数依赖左边多余的属性EG，GE，FE，FG，HE，HG，FHE(2)去掉多余的函数依赖去掉多余的函数依赖Fm=EG，GE，FE，HEEG，

43、GE，FE，HE，FHE第35页，共41页，编辑于2022年，星期日练习练习：设有关系模式：设有关系模式R，其中：，其中：UE,F,G,H函数依赖集函数依赖集F=EG，GE，FEG，HEG，FHE，求求F F的最小依赖集的最小依赖集6.3 6.3 数据依赖的公理系统数据依赖的公理系统Fm=EG，GE，FG，HE=EG，GE，FG，HG=EG，GE，FE，HE=EG，GE，FE，HG第36页，共41页，编辑于2022年，星期日练习练习：F=ABC，BCD，ACDB，DEG，CA,BEC,CGBD,CEAG，计算，计算F的等价的最小依赖集的等价的最小依赖集Fm。6.3 6.3 数据依赖的公理系统数

44、据依赖的公理系统(1)将函数依赖右边的属性单一化将函数依赖右边的属性单一化F1ABC，BCD，ACDB，DE，DG，CA，BEC，CGB，CGD,CEA，CEGF2ABC，BCD，CDB，DE，DG，CA，BEC，CGB，CGD，CEG(2)去掉去掉F1中函数依赖左边多余的属性中函数依赖左边多余的属性(3)去掉去掉F2中多余的函数依赖中多余的函数依赖F3ABC，BCD，CDB，DE，DG，CA，BEC，CGD，CEG去掉去掉CGB去掉：去掉：ACDB中的中的A,CEA中的中的E第37页，共41页，编辑于2022年，星期日总结总结1.1.三个概念三个概念 逻辑蕴含、函数依赖闭包、最小依赖集逻辑蕴

45、含、函数依赖闭包、最小依赖集2.Armstrong2.Armstrong公理系统及导出规则公理系统及导出规则3.3.两种方法两种方法 (1)(1)求求X XF F+的算法的算法 (2)(2)求求F F最小依赖集最小依赖集FmFm的过程的过程第38页，共41页，编辑于2022年，星期日作业作业nP196第第2、3、12题。题。n预习预习6.4。第39页，共41页，编辑于2022年，星期日 下课了。下课了。休息。休息。第40页，共41页，编辑于2022年，星期日练习练习 设有关系模式设有关系模式设有关系模式设有关系模式W(C,P,S,G,T,R),W(C,P,S,G,T,R),W(C,P,S,G,

46、T,R),W(C,P,S,G,T,R),其中各属性的含义是：其中各属性的含义是：其中各属性的含义是：其中各属性的含义是：C C C C是课程，是课程，是课程，是课程，P P P P是教师，是教师，是教师，是教师，S S S S是学生，是学生，是学生，是学生，G G G G为成绩，为成绩，为成绩，为成绩，T T T T为时间，为时间，为时间，为时间，R R R R为教室，根据定义为教室，根据定义为教室，根据定义为教室，根据定义有如下的函数依赖集：有如下的函数依赖集：有如下的函数依赖集：有如下的函数依赖集：F=CF=CF=CF=CP P P P,(S,C)G,(T,R)C,(T,P)R,(T,S)

47、R,(S,C)G,(T,R)C,(T,P)R,(T,S)R,(S,C)G,(T,R)C,(T,P)R,(T,S)R,(S,C)G,(T,R)C,(T,P)R,(T,S)R (1)(1)(1)(1)关系模式关系模式关系模式关系模式W W W W的一个码是的一个码是的一个码是的一个码是_;_;_;_;(2)W(2)W(2)W(2)W的规范化程度最高达到的规范化程度最高达到的规范化程度最高达到的规范化程度最高达到_;_;_;_;若将关系模式分解为若将关系模式分解为若将关系模式分解为若将关系模式分解为W1(C,P),W2(S,C,G),W3(S,T,R,C),W1(C,P),W2(S,C,G),W3(

48、S,T,R,C),W1(C,P),W2(S,C,G),W3(S,T,R,C),W1(C,P),W2(S,C,G),W3(S,T,R,C),则：则：则：则：(3)W1(3)W1(3)W1(3)W1的规范化程度最高达到的规范化程度最高达到的规范化程度最高达到的规范化程度最高达到_;_;_;_;(4)W2(4)W2(4)W2(4)W2的规范化程度最高达到的规范化程度最高达到的规范化程度最高达到的规范化程度最高达到_;_;_;_;(5)W3 (5)W3 (5)W3 (5)W3的规范化程度最高达到的规范化程度最高达到的规范化程度最高达到的规范化程度最高达到_;_;_;_;4NF3NFST1NF4NF第41页，共41页，编辑于2022年，星期日