Windows Server数据库课件--第06章 关系数据理论(3).ppt

1、数据库系统概论 An Introduction to Database System 第六章 关系数据理论 （3）,公理系统复习,1.范式及分类 2.逻辑蕴含 3.Armstrong公理系统 4.Armstrong公理系统的导出规则 5.XF+,关系模式R ,其任何一个关系r，若函数依赖XY都成立, 则称F 逻辑蕴含XY.,Al.自反律： A2.增广律： A3.传递律：,若Y X U，则XY为F 所蕴含 若XY为F所蕴含，且Z U， 则XZYZ为F所蕴含。 若XY 及YZ 为F所蕴含， 则XZ 为F所蕴含。,公理系统复习,3.Armstrong公理系统,公理系统复习,4.Armstrong公理

2、系统的导出规则,合并规则 ：由XY，XZ， 伪传递规则：由XY，WYZ， 分解规则 ：由XY及 ZY，,得XYZ 得XWZ 得XZ,有关系模式： 项目研发人员(职工号，姓名，年龄，学历，职称，所在单位，课题编号，分工，排名，参加月数),属性间的函数依赖如下： (课题编号,所在单位,职工号) (姓名,年龄,学历,职称,分工,排名,参加月数) (所在单位,职工号 ) (姓名,年龄,学历,职称),回答以下问题 (1)该关系会产生什么问题。 (2)该关系为几范式？ (3)将其分解为第三范式，并指出各关系模式的主键。,第六章 关系数据理论,6.1 数据依赖 6.2 规范化 6.3 数据依赖的公理系统 6

3、.4 模式的分解,解：设X(0) =AB； 计算X(1) :找左部为AB子集的函数依赖， 于是： X(1) = X(0) CD=ABCD。 因为X(0) X(1)，并且X(1) U,所以计算X(2) 计算X(2): 找出左部为ABCD子集的函数依赖， 于是： X(2)=X(1)BCDE=ABCDE。 因为X(2) =U，算法终止。 所以(AB)F+ =ABCDE。,例：已知关系模式R，其中U=A，B，C，D，E, F=ABC,BD,CE,ECB,ACB，求(AB)F+,ABC,BD,ABC,BD,CE, ACB,1.已知关系R,其中U=A,B,C,D,E,F,F=AC, BCDE,DA,FB,

4、则(A,B)关于函数依赖集F的 闭包是？ 2.已知关系R,其中U=A,B,C,D,E,F, F=ABC,BCAD,DE,CFB,则下列依赖蕴 含于F的有_. A. ABC B. ABD C. ABE D. ABF,练习,6.3 数据依赖的公理系统,5.定理6.2 Armstrong公理系统的有效性与完备性 有效性(正确性)：由F出发根据Armstrong公理推导出的每个函数依赖一定在F+中。 完备性：F+中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来。,Armstrong公理的完备性及有效性说明: “蕴含” = “导出”等价的概念 F +=由F出发借助Armstrong

5、公理导出的函数依赖的集合,6.函数依赖集的等价 覆盖和等价的概念 定义6.14：设F和G是两个函数依赖集： (1)如果F+ G+，则称 G是F的一个覆盖， 或称 G覆盖F。 (2)如果F+G+和 G+ F+同时成立,即 F+=G+ ， 则称G和F等价。,6.3 数据依赖的公理系统,6.函数依赖集的等价 引理6.3： F+ =G+ 的充分必要条件是F G+ 和G F+。 证: 必要性。 若：F+ =G+ 则： F F+ G+ 和 G G+ F+； 所以：F G+ 和 GF+ 是成立的。,6.3 数据依赖的公理系统,引例：描述一个学校的数据库Student 。 U Sno, Sdept, Mnam

6、e, Cno, Grade,F SnoSdept, SnoMname , SdeptMname, (Sno,Sdept)Sdept (Sno, Cno) Grade,6.3 数据依赖的公理系统,FSnoSdept, SdeptMname, (Sno, Cno) Grade,7.最小依赖集 定义6.15 如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集，亦称为最小依赖集或最小覆盖。 F中任一函数依赖的右部仅含有一个属性。 F中不存在这样的函数依赖XA，使得F与 F XA等价。 F中不存在这样的函数依赖XA，X有真子集Z使得FXAZA与F等价。,6.3 数据依赖的公理系统,无冗余的函数依赖

7、,函数依赖左边无多余的属性,函数依赖右部为单属性,例：设关系模式S中, U= Sno,Sdept,Mname,Cno,Grade 判断下列函数依赖F和F 是否是最小依赖集： F= SnoSdept, SdeptMname， (Sno,Cno)Grade F= SnoSdept，SnoMname， SdeptMname, (Sno,Cno)Grade ， (Sno,Sdept)Sdept,6.3 数据依赖的公理系统,Yes,No,8.求F最小依赖集Fm的过程,6.3 数据依赖的公理系统,(1)逐一检查F 中各函数依赖FDi： XY,若Y=A1A2 Ak , k2， 则用 XAj |j=1，2，

8、k来取代XY.,定理6.3 每一个函数依赖集F 均等价于一个极小函数依赖集Fm ,此Fm 称为F 的最小依赖集。,求最小依赖集的步骤：,8.求F最小依赖集Fm的过程,6.3 数据依赖的公理系统,(2)逐一检查F 中各函数依赖FDi： XA，令G=F-XA， 若AXG+，则从F中去掉此函数依赖。,(3)逐一取出F 中各函数依赖FDi： XA，设X=B1B2Bm， 逐一考查Bi (i=l，2，m),若A (X-Bi )F+ , 则以X-Bi 取代X。,例： 确定F的最小依赖集。,6.3 数据依赖的公理系统,F= SnoSdept，SnoMname， SdeptMname, (Sno,Cno)Gra

9、de ， (Sno,Cno) Mname ,Fm= SnoSdept， SdeptMname, (Sno,Cno)Grade ,例：F=AB，BA，BC，AC，CA， 确定F的最小依赖集。,6.3 数据依赖的公理系统,G,解：AG+=AC B AG+ ， 所以AB不是冗余依赖,例：F=AB，BA，BC，AC，CA， 确定F的最小依赖集。,6.3 数据依赖的公理系统,G,解： AF+=ABC AG+=AC B AG+ ， 所以AB不是冗余依赖 BF+=ABC BG+=ABC A BG+ ， 所以BA是冗余依赖 F=AB，BC，AC，CA 依此类推,例：F=AB，BA，BC，AC，CA， 确定F的

10、最小依赖集。 Fm1=AB,BC,CA,6.3 数据依赖的公理系统,例：F=AB，BA，BC，AC，CA， 确定F的最小依赖集。 Fm1=AB,BC,CA Fm2=AB,BA,AC,CA,6.3 数据依赖的公理系统,结论：F的最小依赖集Fm不一定是唯一的，它与对各函数依赖FDi及XA中X各属性的处理顺序有关。,6.3 数据依赖的公理系统,练习：设有关系模式R，其中： U= E,F,G,H F= EG,GE ,FEG ,HEG,FHE 求：F的最小依赖集,解：(1) 将函数依赖右边的属性单一化,F=EG,GE ,FE , FG ,HE, HG,FHE,F=EG,GE ,FE , FG ,HE,

11、HG,FHE,6.3 数据依赖的公理系统,练习：设有关系模式R，其中： U= E,F,G,H F= EG,GE ,FEG ,HEG,FHE 求：F的最小依赖集,解：(1) 将函数依赖右边的属性单一化,(2) 去掉冗余的函数依赖,F=EG,GE ,FE , FG ,HE, HG,FHE,6.3 数据依赖的公理系统,练习：设有关系模式R，其中： U= E,F,G,H F= EG,GE ,FEG ,HEG,FHE 求：F的最小依赖集,解：(1) 将函数依赖右边的属性单一化,(2) 去掉多余的函数依赖,F=EG,GE ,FE , FG ,HE, HG,FHE,6.3 数据依赖的公理系统,练习：设有关系

12、模式R，其中： U= E,F,G,H F= EG,GE ,FEG ,HEG,FHE 求：F的最小依赖集,解：(1) 将函数依赖右边的属性单一化,(2) 去掉多余的函数依赖,(3) 去掉函数依赖左边多余的属性,Fm=EG，GE ，FE ，HE,第六章 关系数据理论,6.1 数据依赖 6.2 规范化 6.3 数据依赖的公理系统 6.4 模式的分解,6.4 模式的分解,模式分解：把低一级的关系模式分解为若干个高一级的关系模式，方法并不唯一。 什么样的分解才有意义？ 保证分解后的关系模式与原关系模式等价。 分解的目的 解决关系模式中可能存在的操作异常情况,降低数据冗余。,6.4 模式的分解,1.模式分

13、解的三个定义 2.分解的无损连接性和保持函数依赖性 3.分解算法,6.4 模式的分解,定义6.16 关系模式R的一个分解是指 =R1, R2, Rn 其中：U=U1U2Un，且Ui Uj， Fi为F在Ui上的投影,定义6.17 函数依赖集合XY|XYF+XYUi的一个覆盖Fi 叫作F 在属性Ui上的投影., Sno Sdept Mname 0215121 CS 张三 0215122 IS 李斯 0215123 MA 王武 0215124 IS 李斯 0215125 CS 张三 ,6.4 模式的分解,引例: SL（Sno， Sdept， Mname） F= SnoSdept，SdeptMname

14、 Sno Mname ,几范式？,分解后的关系为：,R1: R2 ： R3 ： Sno Sdept Mname 0215121 CS 张三 0215122 IS 李斯 0215123 MA 王武 0215124 0215125 ,注意：分解后的数据库丢失了许多信息,6.4 模式的分解,(1)SL分解为下面三个关系模式： 1= R1, R2 (Sdept,), R3 (Mname,) ,查0215121所在的系？,(2) SL分解为下面二个关系模式： 2= R1 ( Sno, Sdept,SnoSdept)， R2 (Sno, Mname,Sno Mname) 分解后的关系为： R1 ： R2

15、： Sno Sdept Sno Mname 0215121 CS 0215121 张三 0215122 IS 0215122 李斯 0215123 MA 0215123 王武 0215124 IS 0215124 李斯 0215125 CS 0215125 张三 ,6.4 模式的分解,R1 R2 Sno Sdept Mname 0215121 CS 张三 0215122 IS 李斯 0215123 MA 王武 0215124 IS 李斯 0215125 CS 张三 ,6.4 模式的分解,注意：此分解的连接与原关系模式等价，但仍然存在数据冗余，原因丢失了原来的函数依赖。,(3) 将SL分解为下面

16、二个关系模式： 3= R1 ( Sno, Sdept,SnoSdept)， R2 (Sdept, Mname,SdeptMname) 分解后的关系为：,R1： R2： Sno Sdept Sdept Mname 0215121 CS CS 张三 0215122 IS IS 李斯 0215123 MA MA 王武 0215124 IS 0215125 CS ,6.4 模式的分解,R1 R2 Sno Sdept Mname 0215121 CS 张三 0215122 IS 李斯 0215123 MA 王武 0215124 IS 李斯 0215125 CS 张三 ,6.4 模式的分解,注意：分解满足

17、了无损连接，又没有丢失函数依赖。,6.4 模式的分解,1.关系模式分解的标准,三种模式分解的等价定义 (1)分解具有无损连接性 (2)分解要保持函数依赖 (3)分解既要保持函数依赖，又要具有无损连接性,定义6.18：关系模式R的一个分解： = R1，R2， ，Rn 若R与R1、R2、Rn自然连接的结果相等， 则称关系模式R的这个分解具有无损连接性。,6.4 模式的分解,特点： 具有无损连接性的分解保证不丢失信息 无损连接性的分解不一定能解决插入异常、删除异常、修改复杂和数据冗余等问题,2.判断模式分解具有无损连接性的方法 算法6.2 判断一个分解的无损连接性 = R1,R2,，Rk 是R的一个

18、分解，U=A1，A2，An，F=FD1，FD2，FD，设F是极小依赖集，记FDi为XiAli ： (1) 建立一张n列k行的表；若属性Aj属于Ui，则在j列i行交叉处填上aj，否则填上bij；,6.4 模式的分解,2.判断模式分解具有无损连接性的方法 算法6.2 判断一个分解的无损连接性（续） (2) 对每一个函数依赖XiAli做如下操作： 找到Xi所对应的列中具有相同符号的那些行。考察这些行中li列的元素，若其中有ali则全部改为ali；否则全部改为bmli，m是这些行的行号最小值； (3) 若有一行成为a1,a2,an。则算法终止,6.4 模式的分解,6.4 模式的分解,例：已知R，U=A

19、,B,C,D,E， F=ABC, CD, DE，R的一个分解为: R1A,B,C, R2C,D , R3D,E 。 (1)构造初始表,a1 a2 a3 b14 b15,b21 b22 a3 a4 b25,b31 b32 b33 a4 a5,ABC,(2)根据函数依赖进行变换：,6.4 模式的分解,例：已知R，U=A,B,C,D,E， F=ABC, CD , DE，R的一个分解为: R1A,B,C, R2C,D , R3D,E 。 (1)构造初始表,a1 a2 a3 b14 b15,b21 b22 a3 a4 b25,b31 b32 b33 a4 a5,CD,(2)根据函数依赖进行变换：,a4,

20、6.4 模式的分解,例：已知R，U=A,B,C,D,E， F=ABC,CD, DE ，R的一个分解为: R1A,B,C, R2C,D , R3D,E 。 (1)构造初始表,a1 a2 a3 b14 b15,b21 b22 a3 a4 b25,b31 b32 b33 a4 a5,(2)根据函数依赖进行变换：,a4,DE,a5,a5,结论：此分解具有无损连接性,6.4 模式的分解,例：已知R，U=A,B,C,D,E，F=AC,B C,CD, DE C,CE A，R的一个分解=R1A,D，R2A,B ，3B,E , R4C,D,E , R5A,E ,判断 的无损连接性。 解:(1)构造初始表,a1

21、b12 b13 a4 b15,a1 a2 b23 b24 b25,b31 a2 b33 b34 a5,b41 b42 a3 a4 a5,a1 b52 b53 b54 a5,(2)检查,AC；,b13,b13,B C；,b13,CD；,a4,a4,a4,DE C；,a3,a3,CE A,a1,a1,练习：已知R，U=A,B,C,D,E，F=AC, CD， B C, DE C,CE A，R的一个分解=AD，AB，BC , CDE,AE ,判断 是否具有无损连接性。,6.4 模式的分解,定理6.5：对于R的一个分解为: =R1,R2，如果 U1U2U1-U2F+,或U1U2U2-U1F+, 则具有无

22、损连接性。,例有一个关系模式R(U,F),其上的函数依赖集: U=A,B,C, F=AB，CB， 判断1AB,AC和2AB,BC是否具有无损连接性。,3.判断模式分解保持函数依赖性 定义6.19 设关系模式R被分解为： = R1，R2，Rk 其中：U=U1U2Uk，且Ui Uj； Fi为F在Ui上的投影 若F所逻辑蕴含的函数依赖一定也由分解得到的某个关系模式中的函数依赖Fi所逻辑蕴含，则称关系模式R的这个分解是保持函数依赖的。,6.4 模式的分解,6.4 模式的分解,例1：对关系模式R,其中： U=A,B,C,D,F=ABC,CA,CD, =ACD,BC, 判断该分解是否保持函数依赖。 例2：

23、对关系模式R,其中： U=A,B,C,D, F=ABC,CAD, = ABC,ACD， 判断分解是否保持函数依赖。,3.判断模式分解保持函数依赖性,Yes,No,3.判断模式分解保持函数依赖性,6.4 模式的分解,例现有一个关系模式R(A,B,C),函数依赖集: F=A B，C B， 判断1AB,AC和2AB,BC是否具有保持函数依赖性。,你发现了什么？,关于模式分解的几个重要结论： (1)若分解保持函数依赖，可减轻或解决操作异常. 分解:总可以达到3NF，但不一定能达到BCNF。 (2)若分解具有无损连接性，能够保证不丢失信息. 分解:一定可以达到BCNF。 (3)如果要求分解既保持函数依赖

24、，又具有无损连接性，是两个互相独立的标准。 分解:可以达到3NF，但不一定能达到BCNF。,6.4 模式的分解,练习 设有关系模式R, 其中：U=A,B,C,F=ABC,CB 1.候选码是什么？ 2.确定该关系模式是几范式？ 3.在保持函数依赖的前提下如何分解？最高能达到几范式？,6.4 模式的分解,结论：在实践中刻意追求BCNF的意义并不大，因为我们对模式分解的要求总是既要满足无损连接性，又要保持函数依赖。,AB,3NF,3NF,6.4 模式的分解,4.模式分解的算法 (1)合成法 算法6.3 R转换为3NF的保持函数依赖的分解 求F的最小集F。 若R中某些属性与F中所有函数依赖的左右部 均

25、无关，则将这些属性构成一个关系模式;并 把它们从R中去掉。剩余的属性记为U；,6.4 模式的分解,4.模式分解的算法 (1)合成法 算法6.3 R转换为3NF的保持函数依赖的分解(续) 若F中有一函数依赖XA，且XA=U，则=R, 算法终止； 否则，对于F中的每一个XiAi,都构成一个关 系模式Ri,其中Ui=XiAi，若UiUj的去掉Ui ； 将码相同的关系模式合并。,例：涉及到学生、教师和课程的关系模式STC(SNo，SN，SA，TN，CN，G)。 假设：学生有重名，每个教师只教一门课，但一门课可有几个教师开设。当某个学生选定某门课后，其上课教师就固定了。,存在函数依赖： SNoSN， S

26、NoSA， TNCN， (SNo，CN)TN，(SNo，CN)G,6.4 模式的分解,6.4 模式的分解,例：设有关系模式Stc，其中： U= SNo，SN，SA，TN，CN，G， 解： F=SNoSN， SNoSA， TNCN， (SNo，CN)TN，(SNo，CN)G Stc保持函数依赖的一个分解为： = S(SNo,SN,SA)， SD(SNo,CN,TN,Grade) 它具有无损连接性。,6.4 模式的分解,(2)算法6.4 R转换为3NF既有无损连接又保持函数依赖的分解 求出R保持函数依赖的一个分解=R1,R2,Rk 判断是否具有无损连接性，若是，转 。 令=X，其中X是R的候选码。

27、 分解结束，输出。,6.4 模式的分解,例 设有关系模式R(F,G,H,I,J),其上函数依赖集为： F=FI,JI,IG,GHI,IHF 将R分解为3NF，并具有无损连接形和保持函数依赖 (1)按照保持函数依赖分解 =FI,JI,IG,GHI,IHF (2)判断此分解是否具有无损连接性 不具有无损连接性 (3)增加一个候选码构成的关系模式 =FI,JI,IG,GHI,IHF JH,总 结,1.模式分解的目的 2.模式分解的标准（3个） 3.模式分解的方法 (1)先进行函数依赖的分解 (2)再判断该分解的无损连接性 (3)在上述分解的基础上增加由主码构成的关系模式,作业,P196第2、3、4、5、9、12题。 预习7.17.3。,练习：F=ABC，BCD，ACDB，DEG，CA,BEC, CGBD ,CEAG，计算F的等价的最小依赖集Fm。,6.3 数据依赖的公理系统,(1) 将函数依赖右边的属性单一化,F1=,