华中科技大学数据库课件第06章关系数据理论ppt.ppt

《华中科技大学数据库课件第06章关系数据理论ppt.ppt》由会员分享，可在线阅读，更多相关《华中科技大学数据库课件第06章关系数据理论ppt.ppt（46页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 2011 by1为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能6.1 问题的提出6.2 函数依赖6.3 函数依赖的公理系统6.4 关系模式的规范化6.5 关系模式的分解6.6 小结第第6章章 关系数据理论关系数据理论 2011 by2为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能6.5.1 模式分解的定义模式分解的定义6.5.2 模式分解中的问题模式分解中的问题6.5.3 无损连接分解无损连接分解6.5.4 保持函数依赖的分解保持函数依赖的分解6.5.5 关系模式的

2、分解算法关系模式的分解算法6.5 关系模式的分解关系模式的分解 2011 by3为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能定义定义6.17 设有关系模式设有关系模式R,称用称用=R1，R2，Rn 代替代替R的过程为的过程为R模式的模式的分解分解，称为称为R的一个的一个分解分解，这，这里里Ui和和Fi必须同时满足：必须同时满足：U=U1U2UnUi与与Uj可以相交可以相交,但不允许但不允许Ui Uj或或Uj Ui,ij,i,j=1,2,nFi是是F在在Ui上的投影上的投影(也可记作也可记作Ri(F)6.5 关系模式的分解关系模式

3、的分解 2011 by4为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能定义定义6.18 函数依赖集合函数依赖集合 XY|XY F+XY Ui 的一个覆盖的一个覆盖 Fi 叫作叫作 F 在属性在属性 Ui 上的投影上的投影 设有设有R,U=A,B,C,D,F=AB,CD (R最高为几范式最高为几范式?)1:R1(A,B,C),R2(C,D),F在在R1,R2上的投影是什么上的投影是什么?F1=AB,F2=CD (R1最高为几范式最高为几范式?R2呢呢?)6.5 关系模式的分解关系模式的分解 2011 by5为深入学习习近平新时代中国

4、特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能设有设有R,U=A,B,C,F=AB,BC(R最高为几范式最高为几范式?)1:R1(A,B),R2(A,C),F在在R1,R2上的投影是什么上的投影是什么?F1=AB,F2=AC (R1最高为几范式最高为几范式?R2呢呢?)6.5 关系模式的分解关系模式的分解 2011 by6为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能SCD(Sno,Sname,Age,Dept,Mn,Cno,Score)F=sno*,DeptMn,(sno,cno)score

5、分解分解1=SD,SC:SD(Sno,Sname,Age,Dept,Mn),F1=sno*,deptMn SC(Sno,Cno,Score),F2=(sno,cno)score分解分解2=S,D,SC:S(Sno,Sname,Age,Dept),F1=sno(sname,age,dept)D(Dept,Mn),F2=deptMn SC(Sno,Cno,Score),F3=(sno,cno)score6.5 关系模式的分解关系模式的分解 2011 by7为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能6.5.1 模式分解的定义模式分解

6、的定义6.5.2 模式分解中的问题模式分解中的问题6.5.3 无损连接分解无损连接分解6.5.4 保持函数依赖的分解保持函数依赖的分解6.5.5 关系模式的分解算法关系模式的分解算法6.5 关系模式的分解关系模式的分解 2011 by8为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能把低一级的关系模式分解为若干个高一级的把低一级的关系模式分解为若干个高一级的关系模式的方法并不是唯一的关系模式的方法并不是唯一的只有能够保证分解后的关系模式与原关系模只有能够保证分解后的关系模式与原关系模式式等价等价，分解方法才有意义，分解方法才有意义无

7、损连接性无损连接性保持函数依赖保持函数依赖既保持函数依赖，又无损连接既保持函数依赖，又无损连接6.5 关系模式的分解关系模式的分解 2011 by9为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能6.5 关系模式的分解关系模式的分解A学生学生B学院学院C院长院长赵赵计算机计算机王王钱钱计算机计算机王王孙孙机械机械张张李李软件软件王王A B,B C(A,B):(学生学生,学院学院)(A,C):(学生学生,院长院长)(A,C):(学生学生,院长院长)(B,C):(学院学院,院长院长)(A,B):(学生学生,学院学院)(B,C):(学院学

8、院,院长院长)2011 by10为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能6.5 关系模式的分解关系模式的分解AC院长院长赵赵王王钱钱王王孙孙张张李李王王A CB学院学院C院院长长计算机计算机 王王机械机械张张软件软件王王B C=ABC赵赵计算机计算机王王赵赵软件软件王王钱钱计算机计算机王王钱钱软件软件王王孙孙机械机械张张李李计算机计算机王王李李软件软件王王多出违背事实的元组有损连接的分解A B,B C 2011 by11为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人

9、功能6.5 关系模式的分解关系模式的分解AB学院学院赵赵 计算机计算机钱钱 计算机计算机孙孙机械机械李李软件软件周周 计算机计算机A BAC院长院长赵赵王王钱钱王王孙孙张张李李王王周周江江A C=A学生学生B学院学院C院长院长赵赵计算机计算机王王钱钱计算机计算机王王孙孙机械机械张张李李软件软件王王周周计算机计算机江江插入违反 B C:不保持FD的分解A B,B C 2011 by12为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能6.5 关系模式的分解关系模式的分解AB学院学院赵赵 计算机计算机钱钱 计算机计算机孙孙机械机械李李软件

10、软件A BB学学院院C院长院长赵赵王王钱钱王王孙孙张张李李王王B C=A学生学生B学院学院C院长院长赵赵计算机计算机王王钱钱计算机计算机王王孙孙机械机械张张李李软件软件王王无损连接，且保持FDA B,B C 2011 by13为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能6.5.1 模式分解的定义模式分解的定义6.5.2 模式分解中的问题模式分解中的问题6.5.3 无损连接分解无损连接分解6.5.4 保持函数依赖的分解保持函数依赖的分解6.5.5 关系模式的分解算法关系模式的分解算法6.5 关系模式的分解关系模式的分解 2011

11、by14为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 定义定义6.19 关系模式关系模式R的一个分解的一个分解=R1，R2，Rn 若若R与与R1、R2、Rn自然连接的结果相等，则称关自然连接的结果相等，则称关系模式系模式R的这个分解的这个分解具有无损连接性（具有无损连接性（Lossless join）。）。具有无损连接性的分解保证不丢失信息具有无损连接性的分解保证不丢失信息无损连接性不一定能解决插入异常、删除异常、无损连接性不一定能解决插入异常、删除异常、修改复杂、数据冗余等问题修改复杂、数据冗余等问题6.5 关系模式的分解关系

12、模式的分解 2011 by15为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能算法算法6.2 判别一个分解是否具有无损连接性判别一个分解是否具有无损连接性U=A1,A2,An =R1,R2,Rk1.建立一个建立一个n列列k行的矩阵行的矩阵 TB=Cij|若若Aj Ui,Cij=aj,否则否则Cij=bij6.5 关系模式的分解关系模式的分解A1A2AnU1CijUk 2011 by16为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能算法算法6.2(续续)2.对对F中每一个

13、函数依赖中每一个函数依赖XY，若，若TB中存在中存在元组元组t1，t2，使得，使得t1X=t2X，t1Yt2Y，则对每一个，则对每一个Ai Y：若若t1Ai,t2Ai中有一个等于中有一个等于aj,则另一个也改为则另一个也改为aj；若若不成立不成立,则取则取t1Ai=t2Ai(t2的行号小于的行号小于t1)。(即即Ai列上，只要其中有一个列上，只要其中有一个aj则全改为则全改为aj,否则全改否则全改为行号最小的即一列的值为行号最小的即一列的值)6.5 关系模式的分解关系模式的分解 2011 by17为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图

14、书室育人功能算法算法6.2(续续)3.反复执行反复执行2,直至：直至：TB中出现一行为中出现一行为a1,a2,an 的一行。的一行。TB不再发生变化不再发生变化,且没有一行为且没有一行为a1,an。在在情况下，情况下，为无损分解，否则为有损分解。为无损分解，否则为有损分解。定理定理6.4 为无损连接的分解当且仅当是算法为无损连接的分解当且仅当是算法5.2终止时终止时,表中有一行为表中有一行为a1,an。6.5 关系模式的分解关系模式的分解 2011 by18为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能【例【例6.17】U=A,B

15、,C,D,E,F=ABC,CD,DE,=(A,B,C),(C,D),(D,E)，判断分解是否具有无损连接性。，判断分解是否具有无损连接性。6.5 关系模式的分解关系模式的分解ABCDEABCa1a2a3b14b15CDb21b22a3a4b25DEb31b32b33a4a5ABCDEABCa1a2a3b14b15CDb21b22a3a4b25DEb31b32b33a4a5ABCABCDEABCa1a2a3a4b15CDb21b22a3a4b25DEb31b32b33a4a5CDABCDEABCa1a2a3a4a5CDb21b22a3a4a5DEb31b32b33a4a5DE 2011 by19

16、为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能【别解】【别解】U=A,B,C,D,E,F=ABC,CD,DE,=(A,B,C),(C,D),(D,E)，判断分解是否具有无损连接性。，判断分解是否具有无损连接性。6.5 关系模式的分解关系模式的分解ABCDEABCa1a2a3CDa3a4DEa4a5ABCDEABCa1a2a3CDa3a4DEa4a5ABCABCDEABCa1a2a3a4CDa3a4DEa4a5CDABCDEABCa1a2a3a4a5CDa3a4a5DEa4a5DE 2011 by20为深入学习习近平新时代中国特色社

17、会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能【例【例6.18】U=A,B,C,D,E,F=AC,BC,CD,DEC,CEA,=AD,AB,BE,CDE,AE,判断判断分解是否无损连接。分解是否无损连接。6.5 关系模式的分解关系模式的分解ABCDEADa1a4ABa1a2BEa2a5CDEa3a4a5AEa1a5ACBCCDDECCEAb13b13a1a1a3a4a4a4b13b13a3无损连接无损连接 2011 by21为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能定理定理6.5 R的一个分解无

18、损连接的一个分解无损连接 =R1,R2 具有无损连接性的充要条件是：具有无损连接性的充要条件是：U1 U2 U1-U2 F+或或U1 U2 U2-U1 F+6.5 关系模式的分解关系模式的分解 2011 by22为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能证明证明 借助算法借助算法6.2,将将R的属性分成三部分的属性分成三部分,6.5 关系模式的分解关系模式的分解U1 U2U1-U2U2-U1U1aaaaaabbbU2aaabbbaaa(1)充分性充分性如有如有U1 U2 U1-U2,则则U2行行(U1-U2)列全改为列全改为a

19、,于于是是U2行全为行全为a.分解具有无损连接性分解具有无损连接性;同理同理,(2)必要性必要性如是无损连接，则必有一行全如是无损连接，则必有一行全a，2011 by23为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能【例【例6.19】R,U=A,B,C,F=A B的两个分解：的两个分解：(1)1=R1(A,B),R2(A,C)(2)2=R1(A,B),R2(B,C)问两分解具有无损连接性吗问两分解具有无损连接性吗?解解:(1)ABAC=A,AB-AC=B,A B F+,故分解故分解 1具有无损连接性。具有无损连接性。(2)ABBC

20、=B,AB-BC=A,BC-AB=C.无论无论B A，还是还是B C都不在都不在F+中，所以分解中，所以分解 2不不具有无损连接性。具有无损连接性。6.5 关系模式的分解关系模式的分解 2011 by24为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能【例【例6.20】R,U=A,B,C,F=A B,C B 的分解：的分解：(1)1=AC,BC (2)2=AB,BC 问两分解具有无损连接性吗问两分解具有无损连接性吗?解解:(1)ACBC=C,AC-BC=A,BC-AC=B,C B F+,故分解故分解 1具有无损连接性。具有无损连接性

21、。(2)ABBC=B,AB-BC=A,BC-AB=C.无论无论B A，还是还是B C都不在都不在F+中，所以分解中，所以分解 2不具有无不具有无损连接性。损连接性。6.5 关系模式的分解关系模式的分解 2011 by25为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能【例【例6.21】R,U=A,B,C,D,E,F,F=A B,C F,E A,CED 的分解：的分解：=ABE,CDEF 问分解具有无损连接性吗问分解具有无损连接性吗?解解:ABECDEF=E,ABE-CDEF=AB,E AB F+(为什么为什么?).故分解具有无损连接

22、性。故分解具有无损连接性。思考：思考：R的候选码是什么？它最高是几范式？分解后的候选码是什么？它最高是几范式？分解后的两个关系模式又是几范式的两个关系模式又是几范式?6.5 关系模式的分解关系模式的分解 2011 by26为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能6.5.1 模式分解的定义模式分解的定义6.5.2 模式分解中的问题模式分解中的问题6.5.3 无损连接分解无损连接分解6.5.4 保持函数依赖的分解保持函数依赖的分解6.5.5 关系模式的分解算法关系模式的分解算法6.5 关系模式的分解关系模式的分解 2011 by

23、27为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能定义定义6.20 关系模式关系模式R的一个的一个=R1，R2，Rn 若若 F 与与 F1 F2 Fn等价等价则称分解则称分解保持函数依赖。保持函数依赖。(Fi是是F在在Ui上的投上的投影影)引理引理6.4 F+=G+F G+，G F+给出了判断分解是否保持函数依赖的算法。给出了判断分解是否保持函数依赖的算法。6.5 关系模式的分解关系模式的分解 2011 by28为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能【例【例6

24、.22】R,U=A,B,C,F=A B,C B 的分解：的分解：(1)1=AC,BC (2)2=AB,BC 问两个分解是否为保持函数依赖的分解问两个分解是否为保持函数依赖的分解?解解:(1)F1=,F2=C B;F1 F2=C B,显然与显然与F=A B,C B 不等价。不等价。分解不具保持函数依赖性。分解不具保持函数依赖性。(2)F1=A B,F2=C B;F1 F2=A B,C B =F.分解是保持函数依赖的分解。分解是保持函数依赖的分解。6.5 关系模式的分解关系模式的分解 2011 by29为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学

25、图书室育人功能【例【例6.23】R,U=A,B,C,D,E,F,F=A B,C F,E A,CED 的分解：的分解：=ABE,CDEF 问分解具有保持函数依赖性吗问分解具有保持函数依赖性吗?解解:ABE(F)=E A,A B CDEF(F)=C F,CE D ABE(F)CDEF(F)=F 故分解具有保持函数依赖性。故分解具有保持函数依赖性。前面已经发现分解是无损连接的。问前面已经发现分解是无损连接的。问:该分解是否理想该分解是否理想?6.5 关系模式的分解关系模式的分解 2011 by30为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育

26、人功能6.5 关系模式的分解关系模式的分解AB学院学院赵赵 计算机计算机钱钱 计算机计算机孙孙机械机械李李软件软件周周 计算机计算机A BAC院长院长赵赵王王钱钱王王孙孙张张李李王王周周江江A C=A学生学生B学院学院C院长院长赵赵计算机计算机王王钱钱计算机计算机王王孙孙机械机械张张李李软件软件王王周周计算机计算机江江插入违反 B C:不保持FD的分解A B,B C 2011 by31为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能【例【例6.24】R,U=A,B,C,F=A B,B C 的分解：的分解：=AB,AC 保持函数依赖吗

27、保持函数依赖吗?解解:F1=A B,F2=A C;F1 F2=A B,A C,与与 F=A B,B C 并不等价。因为并不等价。因为 (B C)(F1 F2)+,但但(B C)F+。所以，分解不具保持函数依赖性。所以，分解不具保持函数依赖性。6.5 关系模式的分解关系模式的分解 2011 by32为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能6.5.1 模式分解的定义模式分解的定义6.5.2 模式分解中的问题模式分解中的问题6.5.3 无损连接分解无损连接分解6.5.4 保持函数依赖的分解保持函数依赖的分解6.5.5 关系模式的分

28、解算法关系模式的分解算法6.5 关系模式的分解关系模式的分解 2011 by33为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能模式分解的几个重要事实：模式分解的几个重要事实：若仅要求分解具有无损连接性，则分解一定能达若仅要求分解具有无损连接性，则分解一定能达到到4NF。若仅要求分解保持若仅要求分解保持FD，则分解一定能达到，则分解一定能达到3NF，但不一定能达到但不一定能达到BCNF。若既要求分解具有无损连接性，又保持了若既要求分解具有无损连接性，又保持了FD，则，则分解一定能达到分解一定能达到3NF，但不一定能达到，但不一定能达

29、到BCNF。6.5 关系模式的分解关系模式的分解 2011 by34为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能算法算法6.3 达到达到BCNF的无损连接分解算法。的无损连接分解算法。输入输入:给定关系模式给定关系模式R 输出输出:无损连接分解无损连接分解 =R1,Rk,且且每个每个Ri相对于相对于Fi=Ri(F)是是BCNF(i=1,k)步骤步骤：1.初始化初始化:=R;2.若若 中所有的中所有的Ri BCNF，则算法终止，则算法终止;3.设设 中的某个中的某个Ri BCNF，则存在非平凡函，则存在非平凡函数依赖数依赖XA F

30、i+，且，且X不是不是Ri的码的码.则则XA是是Ui的的真子集真子集.对对Ri进一步进一步分解为分解为=S1，S2，其中，其中US1 =XA，US2 =Ui A.以以 代替代替Ri，返回到，返回到2.6.5 关系模式的分解关系模式的分解 2011 by35为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能【例【例6.25】R,U=S#,D,M,C#,G,F=S#D,S#M,D M,(S#,C#)G.试将试将R分解分解BCNF,并保持并保持无损连接无损连接.解解:第第1遍遍:R的码为的码为(S#,C#).U1=S#,D,F1=S#D;U

31、2=S#,M,C#,G,F2=S#M,(S#,C#)G;第第2遍遍:对对R2进一步分解进一步分解.U2=S#,M,F2=S#M;U3=S#,C#,G,F2=(S#,C#)G;=(S#,D#),(S#,M),(S#,C#,G).(保持保持FD吗吗?)6.5 关系模式的分解关系模式的分解 2011 by36为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能【例【例6.26】R(C,T,H,R,S,G),其中其中:C课程课程,T教师教师,H时间时间,R教室教室,S学生学生,G成绩成绩.F：1.CT(每门课仅一名教师上每门课仅一名教师上)2.

32、HRC(任一时间，一个教室只能上一门课任一时间，一个教室只能上一门课)3.HTR(一个时间，一个教师只能在一个教室上课一个时间，一个教师只能在一个教室上课)4.CSG(一个学生，一门课只有一个成绩一个学生，一门课只有一个成绩)5.HSR(一个时间，一个学生只能在一个教室上课一个时间，一个学生只能在一个教室上课)求求R的一个无损连接分解，要求分解后的模式为的一个无损连接分解，要求分解后的模式为BCNF。解解:(HS)+=HSRCTG=U HS U,HS是是R的候选码的候选码,易证是唯一候选码易证是唯一候选码6.5 关系模式的分解关系模式的分解 2011 by37为深入学习习近平新时代中国特色社会

33、主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能(1)考察考察CSG,决定因素不含码决定因素不含码.1=CSG,CTHRS,CSGBCNF,CTHRS BCNF CSG(F)=CSG CTHRS(F)=CT,HRC,HTR,HSR(2)继续分解继续分解CTHRS,考察考察CT，决定因素不含码决定因素不含码.2=CSG,CT,CHRS,CTBCNF,CHRS BCNF CT(F)=CT CHRS(F)=HRC,HSR(3)继续分解继续分解CHRS,考察考察HRC.3=CSG,CT,HRC,HRS6.5 关系模式的分解关系模式的分解 2011 by38为深入学习习近平新

34、时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 CSG:学生课程与成绩学生课程与成绩 CT:各门课程的任课老师各门课程的任课老师 HRC:课表课表(什么时间，在什么教室，上什么课什么时间，在什么教室，上什么课)HRS:学生课表学生课表(什么学生，什么时间该去什么教室什么学生，什么时间该去什么教室)CSG(F)=CSG CT(F)=CT HRC(F)=HRC HRS(F)=HSR 应该注意到依赖关系应该注意到依赖关系HTR在分解后被丢失在分解后被丢失,故分故分解虽具无损连接性，但不保持函数依赖。解虽具无损连接性，但不保持函数依赖。6.5 关系模式的分

35、解关系模式的分解 2011 by39为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能算法算法6.4 达到达到3NF且保持函数依赖的分解算法。且保持函数依赖的分解算法。输入输入:给定关系模式给定关系模式R 输出输出:=R1,Rk,Ri 3NF,i=1,2,k步骤步骤:1.求求R的最小函数依赖集的最小函数依赖集F;2.若若F中有中有XA,且且XA=U,则则 =R,算法终止算法终止;3.找出不在找出不在F中出现的属性，将它们构成一个关系模中出现的属性，将它们构成一个关系模式，并从式，并从U中去掉它们中去掉它们(剩余属性仍记为剩余属性仍记为

36、U);4.对于对于F中的每个中的每个XA,构成一个关系模式构成一个关系模式XA.如果如果F中有中有XA1,XA2,XAn,则可以用则可以用XA1 A2 An代替代替n个模式个模式XA1,XA2,XAn;5.如发现某个如发现某个Ui Uj,则应将则应将Ui去掉。去掉。6.5 关系模式的分解关系模式的分解 2011 by40为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能例例6.27 R,U=S#,D,M,C#,G,F=S#D,S#M,D M,(S#,C#)G.试将试将R分解分解3NF,并保持函数并保持函数依赖依赖。(比较例比较例5.2

37、5的无损连接分解的无损连接分解)解解:(1)最小依赖集最小依赖集F=S#D,D M,(S#,C#)G (2)分解分解R1(S#，D)，S#DR2(D，M)，DMR3(S#，C#，G)，(S#,C#)G这个分解是无损连接的分解吗？这个分解是无损连接的分解吗？6.5 关系模式的分解关系模式的分解 2011 by41为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能例例6.28 R(C,T,H,R,S,G),其中其中:C课程课程,T教师教师,H时间时间,R教室教室,S学生学生,G成绩成绩.F：1.CT(每门课仅一名教师上每门课仅一名教师上)

38、2.HRC(任一时间，一个教室只能上一门课任一时间，一个教室只能上一门课)3.HTR(一个时间，一个教师只能在一个教室上课一个时间，一个教师只能在一个教室上课)4.CSG(一个学生，一门课只有一个成绩一个学生，一门课只有一个成绩)5.HSR(一个时间，一个学生只能在一个教室上课一个时间，一个学生只能在一个教室上课)求求R的的3NF分解，并要求保持函数依赖。分解，并要求保持函数依赖。解解:(1)最小依赖集最小依赖集 F=CT,HRC,HTR,CSG,HSR6.5 关系模式的分解关系模式的分解 2011 by42为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分

39、发挥中小学图书室育人功能 (2)分解分解CT(C,T),CT 授课老师安排表授课老师安排表HRC(H,R,C),HRC 教室安排表教室安排表HTR(H,T,R),HTR 教师课表教师课表 CSG(C,S,G),CSG 成绩表成绩表HSR(H,S,R),HSR 学生课表学生课表这个分解是无损连接的分解吗？这个分解是无损连接的分解吗？6.5 关系模式的分解关系模式的分解 2011 by43为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能算法算法6.5 达到达到3NF既保持函数依赖又无损连接既保持函数依赖又无损连接的分解。的分解。设设 =

40、R1,Rk是是R的一的一个保持函数依赖的个保持函数依赖的3NF分解分解(可由前一算法求得可由前一算法求得)设设X为为R的码，的码，若有某个若有某个Ui，X Ui，则，则 即为所求，即为所求，否则令否则令=R ，即为所求即为所求(如发现某个如发现某个Ui X,则应将则应将Ui去掉去掉)6.5 关系模式的分解关系模式的分解 2011 by44为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能Review分解的定义分解的定义保持函数依赖的分解保持函数依赖的分解:如何判定？如何判定？无损连接的分解无损连接的分解:如何判定？如何判定？算法算法6

41、.3:无损连接的分解算法无损连接的分解算法-BCNF算法算法6.4:保持函数依赖的分解算法保持函数依赖的分解算法-3NF算法算法6.5:(无损连接无损连接+保持函数依赖保持函数依赖)-3NF6.5 关系模式的分解关系模式的分解 2011 by45为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能基础：函数依赖基础：函数依赖判定：公理，引理，闭包判定：公理，引理，闭包(X+)标准：范式标准：范式(2NF,3NF,BCNF)方法：分解算法方法：分解算法6.5规规范范化化理理论论为为数数据据库库设设计计提提供供了了理理论论指指导导和和工工具具，也也仅仅仅仅是是指指导导。并并不不是是规规范范化化程程度度越越高，模式就越好。应具体情况具体分析。高，模式就越好。应具体情况具体分析。第第6章章 关系数据理论关系数据理论 2011 by46为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能第第6章书面作业章书面作业P195-197习题3,7,10,11,12