关系数据理论讲稿.ppt

《关系数据理论讲稿.ppt》由会员分享，可在线阅读，更多相关《关系数据理论讲稿.ppt（110页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关系数据理论第一页，讲稿共一百一十页哦教学目的教学目的：关系模式的异常问题 函数依赖 Armstrong公理 闭包及其计算算法 最小依赖集和候选码的求解方法 1NF,2NF,3NF和BCNF的概念 模式分解的等价标准重点难点重点难点：Armstrong公理系统 最小依赖集和候选码的求解方法 如何将模式分解为1NF,2NF,3NF和BCNF教学方法教学方法：多媒体教学教学课时教学课时：10节理论课+2节习题课第二页，讲稿共一百一十页哦目目 录录6.1 问题的提出问题的提出6.2 规范化规范化6.3 函数依赖的公理系统函数依赖的公理系统6.4 模式的分解模式的分解第三页，讲稿共一百一十页哦6.1

2、问题的提出针对一个具体的问题，应该如何构造一个适合于它的数据模式？即应该构造几个关系模式？每个关系模式由哪些属性组成呢？这就是数据库设计的问题。对于一个信息系统来说，如果所设计的数据库均具有良好的、合理的范式级别，那么系统的正确性将自动得到某种保证。第四页，讲稿共一百一十页哦如：对于学生和课程的关系模式，属性集：U=sno、dept、dean、cno、grade关系模式包含的语义：(1)一个系有多名学生，但一个学生只属于一个系(2)一个系只有一名正系主任(3)一个学生可以选修多门课程，一门课程有多名学生选修根据语义，得到属性之间有某种关系，即属性值之间的相互依赖又相互制约的关系，称它为数据依赖

3、。数据依赖分为：函数依赖和多值依赖。1 1、数据依赖、数据依赖一个关系模式描述为：R(U,D,dom,F)，F是属性组U上的一组数据依赖。第五页，讲稿共一百一十页哦假如有下关系模式：学生表D(Sno,Sname,Sdept,Sage,Cno,Cname,Credit,Grade)D(Sno,Sname,Sdept,Sage,Cno,Cname,Credit,Grade)在数据库中的D表模式信息如图表：Sno(5)Sname(10)Sdept(10)Sage(2)Cno(5)Cname(20)Credit(2)Grade(2)0001张三计算机17c101数据结构4900001张三计算机17c1

4、02网络安全3880001张三计算机17c103软件工程4780001张三计算机17c105数值分析2800001张三计算机17c110编译原理3860002李四物理19c103软件工程 4820002李四物理19c105数值分析2800003王五计算机17c107C语言475此关系的关键字：sno+cno2 2、什么是不好的关系模式？、什么是不好的关系模式？第六页，讲稿共一百一十页哦此表包含了哪些信息呢？一个学生可以选多门课程一门课程可以被多名学生选修一个学生选修一门课程的成绩在实际应用中，此关系会不会出现问题呢？可能出现些什么问题？第七页，讲稿共一百一十页哦第一类问题是数据冗余太大，这表现

5、在：总字节数=(5+10+10+2+5+20+2+2)*8=448B 关于学生张三的sname、sdept和Sage在关系中出现了五次。这样，一方面浪费存储空间，另一方面系统要付出很大的代价来维护数据库的完整性。第二类问题是更新出现异常，这表现在：（1）修改异常：如果把张三同学的sdept改为“数学”，那么它要修改5次，在维护D表时不够小心的话，可能我只修改了四次，漏掉了一个，那么张三同学的sdept的值就有两个（计算机，数学），这样造成数据不一致。第八页，讲稿共一百一十页哦(2)插入异常：此表的主关键字是(sno,cno),那么这两个字段不能为空。在这个数据表中，如果我们要插入一门课程的信息

6、，但此课程本学期不开设，故无学生选读，这样就无法将这门课程的信息存入到数据表中，这就使表在功能上产生了极不正常的现象。如果在Sno和Sname两属性上定义了非空约束，上述元组的插入就是非法操作。（该插入的数据不能插入。）(3)删除异常：如果在这个数据表中0003的王五同学因病退学，因而有关他的元组在数据表中就被删除，但遗憾的是在王五的有关情况删除时，连课程“C语言”的有关信息也同时被删除了(因为在这个数据表中，只有在王五这个元组中记载有“C语言”课程的有关信息)，并且在整个数据表中再也找不到有关课程“C语言”的有关信息了。这就叫做：“城门失火，殃及池鱼”。这也是数据表中的一种极其不正常的现象，

7、这种现象就叫删除异常。（不该被删除的数据被删除。）第九页，讲稿共一百一十页哦问题的分析 这两类现象的根本原因在于关系的结构。一个关系可以有一个或者多个候选键，其中一个可以选为主键。主键的值唯一确定其他属性的值，它是各个元组之间区别的标识，也是一个元组存在的标识。这些候选键的值不能重复出现，也不能全部或者部分设为空值。本来这些候选键都可以作为独立的关系存在，而现在却不得不依附于其他关系而存在。这就是关系结构带来的限制，它不能正确反映现实世界的真实情况。如果在构造关系模式的时候，不从语义上研究和考虑到属性间的这种关联，而简单地将有关系和无关系的、关系密切的和关系松散的属性都随意编排在一起，就必然发

8、生某种冲突，引起某些“排它”现象出现，即冗余度水平较高，更新产生异常。解决问题的根本方法就是将关系模式进行分解，也就是进行关系的规范化。第十页，讲稿共一百一十页哦6.2 规范化关系数据库中关系规范化问题在1970年Codd提出关系模型时同时被提出来。关系模式必须是规范化的，规范化的最基本要求是关系的每个分量必须是不可再分的数据项。但是，并不是所有满足基本要求的关系模式就是一个好的关系模式，一个好的关系模式必须能很好的反映现实世界。为了说明一个好的关系模式如何能真实的反映现实世界，必须首先要研究关系模式中属性之间的数据依赖关系。第十一页，讲稿共一百一十页哦snocnogradesdeptdean

9、1、函数依赖FD(Functional Dependency)给定一个属性的值，另一个属性的值也会唯一的确定了。这种关系像数学中的函数。因此称之为函数依赖。如前例：学生(sno，sdept、dean、cno、grade)规定：一个学生只能属于一个系，一个系只能有一个系主任，每个学生每学一门课程只有一个成绩。即：sno的值一经确定后sdept的值也随之唯一地确定了，此时即称sno函数决定sdept或称sdept函数依赖于sno，它可用下面符号表示：snosdept同样，我们还可以有：sdeptdean (sno，cno)grade其函数依赖图为：6.2.1 函数依赖第十二页，讲稿共一百一十页哦定

10、义6.1：设有关系模式R(U)，属性集合U=A1,A2,An，X，Y是U的子集，设u,v是关系r中的任意两个元组，若有uX=vX，就有uY=vY(即r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等。换句话说，对于任一个关系R中的任一元组在X中的属性值确定后则在Y中的属性值必确定)，则称Y函数依赖于X或称X函数决定Y,并记作XY，而其中X称为决定因素，Y称为依赖因素。例如：在关系D中，各属性间的函数依赖集合为：F=snosname,snosdept,snosage,cno cname，cno credit,cno+snograde第十三页，讲稿共一百一十页哦课堂练习：设有一个关系模

11、式R(A,B,C,D)，在关系R中，属性值间有这样的联系：A值与B值有一对多联系，即每个A值有多个B值与之联系，而每个B值只有一个A值与之联系；C值与D值是一对一联系，即每个C值只有一个D值与之联系，每个D值只有一个C值与之联系。试写出相应的函数依赖。BADC，CD第十四页，讲稿共一百一十页哦函数依赖与属性关系：函数依赖与属性关系：属性之间有3种关系，但并不是每一种关系中都存在函数依赖。设有属性集X、Y以及关系模式R：如果X和Y之间是“1：1”关系(学校和校长)，则存在函数依赖：XY 和YX如果X和Y之间是“m：1”关系(学生和班长)，则存在函数依赖：XY 如果X和Y之间是“m：n”关系(学生

12、和课程)，则X和Y之间不存在函数依赖。第十五页，讲稿共一百一十页哦注意：注意：不是R的某个关系，而是R的一切关系，任意抽取两个元组函数依赖与码有关，而函数依赖和码都是由语义决定的，是由数据库开发人员，根据用户模型和事务规则人为确定的。所以数据依赖属于语义范畴，不能用数学方法去证明。第十六页，讲稿共一百一十页哦2、平凡函数依赖与非平凡函数依赖 设函数依赖关系XY，若满足Y X，则称此函数依赖是非平凡的函数依赖。在本章中若无特殊声明，凡提到函数依赖时总认为指的是非平凡的函数依赖。设函数依赖关系XY，若满足Y X，则称此函数依赖是平凡的函数依赖。若XY，YX，称为XY第十七页，讲稿共一百一十页哦这里

13、引入一种完全函数依赖的概念，这个概念为真正的函数依赖打下基础。例如在D中我们有SnoSdept，因而我们同样也会有：(Sno，Sname)Sdept(Sno，Sage)Sdept比较这三种函数依赖后我们会发现，实际上真正起作用的函数依赖是：SnoSdept 而其他两种函数依赖都是由它派生而成的，即是说在函数依赖中真正起作用的是Sno，而不是Snane或Sage等。这样，我们在研究函数依赖时要区别这两种不同类型的函数依赖，前一种叫完全函数依赖，而后一种叫不完全函数依赖(部分函数依赖)。3、完全函数依赖与部分函数依赖、完全函数依赖与部分函数依赖第十八页，讲稿共一百一十页哦定义6.2：R(U)中如有

14、X，YU，满足XY，且对任何X的真子集X，都有XY不成立，则称Y完全函数依赖于X，并记作：X Y 在R(U)中如有X，YU，满足XY，对任何X的真子集X，都有XY成立，则称Y部分依赖于X，或称Y函数依赖于X的某个真子集，记作：X Y 由上所述可知，Sdept完全函数依赖于Sno，但Sdept不完全函数依赖于(Sno，Sname)，亦即有：Sno Sdept (Sno，Sname)Sdept (Sno，Sage)SdeptFPFPP第十九页，讲稿共一百一十页哦 在函数依赖中还要区别直接函数依赖与间接函数依赖这两个不同的概念，例如SnoSdept中Sdept是直接函数依赖于Sno，但如果在属性中有

15、系主任dean(假如每个系有唯一的一个系主任)，则有：Sdeptdean，从而由SnoSdept及Sdeptdean可得到：Snodean 在这个函数依赖中，dean并不直接函数依赖于Sno，而是经过中间属性Sdept传递而依赖于Sno，亦即是dean直接依赖于Sdept(Sdept不依赖于Dean)，而Sdept又直接依赖于Sno，从而构成了dean依赖于Sno。这种函数依赖关系，是一种间接依赖关系，或叫传递依赖关系。我们可以对它定义如下。定义6.3：在R(U)中如有X，Y，ZU且满足：XY，(YX)Y /X，YZ 则称Z传递函数依赖于X，否则，称为非传递函数依赖。记为：X ZT4、传递函数

16、依赖、传递函数依赖第二十页，讲稿共一百一十页哦定义6.4：设K为R中的属性或属性组合，若KU且满足 K U,则K为R的候选码。若候选码多于一个，则选定其中的一个为主码。在最简单的情况下，候选码只包含一个属性。包含在任何一个候选码中的属性，叫做主属性。不包含在任何码中的属性称为非主属性或非码属性。所有的属性的组合构成候选码，这时称为全码。F例：有关系CSZ(city，st，zip)，其中有三个属性：城市city，街道st，邮政编码zip。其函数依赖关系为：F=(city,st)zip，zipcity解：在这个关系模式中，有两个候选码(city，st)和(st，zip)。所以city，st，zip

17、都是主属性。6.2.2 码码(键键)第二十一页，讲稿共一百一十页哦6.3 函数依赖的公理系统1、逻辑蕴涵、逻辑蕴涵定义6.11：设F是关系模式R的函数依赖集合，由F出发可以证明其他某些函数依赖也成立，我们称这些函数依赖被F逻辑蕴涵。如：F=AB，BC，从这个函数依赖集中可以推出AC，所以说函数依赖集F逻辑蕴涵函数依赖AC。1974年W.W.Armstrong首先提出了函数依赖的公理系统，称为Armstrong公理(Armstrongs axioms)。对于一组已知的函数依赖，利用该公理可导出所逻辑蕴函的函数依赖，从而确定一个关系模式中的码。第二十二页，讲稿共一百一十页哦2、Armstrong公

18、理公理 公理如下：设U为属性集总体，X，Y，Z，W均是U的子集，F是U上的一组函数依赖,于是有关系模式RU,F。对RU,F且有：A1：若Y X U,则XY为F所蕴涵(自反律)。A2：若XY为F所蕴含,且Z U,则XZYZ为F所蕴涵(增广律)。A3：若XY及YZ为F所蕴含,则XZ为F所蕴涵(传递律)。根据Armstrong公理可以得到下面另三条很有用的推论:推论1：由XY,XZ,有XYZ（合并律）。推论2：由XY,WYZ,有XWZ（伪传递律）。推论3：由XZY,有XY及XZ 成立（分解律）。第二十三页，讲稿共一百一十页哦4、算法、算法6.1 属性集闭包的计算。属性集闭包的计算。原则上讲，对于一个

19、关系模式R(U,F)，根据已知的函数依赖F，反复使用前面的规则，可以计算函数依赖集合F的闭包F+。但是，利用推理规则求出其全部的函数依赖F+是非常困难的，而且也没有必要。因此，可以计算闭包的子集，即选择一个属性子集，判断该属性子集能函数决定哪些属性，这就是利用属性集闭包的概念。(1)定义：设F为属性集U上的一组函数依赖，X U，即X是U的一个子集。在函数依赖集合F下，被X函数决定的所有属性为F+下属性集X的闭包，记作X+，记X+=A|XA。(2)计算属性集闭包X+的算法如下：输入：X，F 输出：X+3、函数依赖集合、函数依赖集合 F的闭包的闭包F+定义6.13：由F所逻辑蕴涵的所有的函数依赖的

20、集合，称为F的闭包，记为F+第二十四页，讲稿共一百一十页哦迭代算法的步骤：选取X+的初始值为X，即X+X；计算X+，X+XZ，其中Z要满足如下条件：Y X+，且F中存在一函数依赖YZ，就把Z并到X+中。实际上就是以X+中的属性子集作为函数依赖的决定因素，在F中搜索函数依赖集，找到函数依赖的被决定属性Z放到X+中。判断：如果X+没有变化？或X+等于U？则X+就是所求的结果，算法终止。否则转。因为U是有穷的，所以上述迭代过程经过有限步骤之后就会终止。第二十五页，讲稿共一百一十页哦例：已知关系模式R(U，F)，其中U=A,B,C,D,E,F=AB C,B D,C E,EC B,AC B,求(AB)+

21、。解：令(AB)+=AB在F中找出左边是AB子集的函数依赖，其结果是：ABC,BD,所以(AB)+=(AB)+CD=ABCD，在F中找出左边是ABCD子集的函数依赖，其结果是：CE,ACB，得到(AB)+=(AB+BE)=ABCDE判断(AB)+=ABCDE=U，算法结束。由于(AB)+有变化但不等于U，所以继续迭代。由计算结果可知，(AB)可以决定属性集合U=A,B,C,D,E，所以，(AB)是一个候选码。但不是唯一的候选码。第二十六页，讲稿共一百一十页哦课堂练习：设有关系模式R(U,F),其中U=A,B,C,D,E,I,F=AD,ABE,BIE,CDI,EC,计算(AE)+结果为：(AE)

22、+=ACDEI第二十七页，讲稿共一百一十页哦5、Armstong公理系统的完备性和有效性有效性是指：由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F所逻辑蕴涵的函数依赖。也就是说只要使用F中的依赖为真，则用公理推出的函数依赖也为真。完备性是指：F所逻辑蕴涵的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来。也就是说F+中的所有函数依赖都能用公理推出。实质上：Armstrong公理是正确和完备的。第二十八页，讲稿共一百一十页哦6、求函数依赖的最小集定义6.15：对于给定的函数依赖F，当满足下列条件时，称为F的最小依赖集，记作FM。(1)FM的每个依赖的右边都是

23、单个属性。(2)对于FM中的任何一个XA和X的真子集Z，(FM-XA)ZA与FM都不等价。(保证了FM中每个函数依赖的左边没有多余的属性)(3)对于FM中的任何一个函数依赖XA，FM-XA与FM都不等价。(保证了在FM中不存在多余的函数依赖)定理：每个函数依赖集与它的最小依赖集FM等价。第二十九页，讲稿共一百一十页哦输入：一个函数依赖集F输出：F的一个等价最小依赖集G方法：(1)应用分解规则，使F中每一个依赖的右边属性单一化。(2)去掉各依赖左边多余的属性。具体做法是；一个一个地检查F中左边是非单属性的依赖，例如XYA。现在要判断Y是否多余的，即以XA代替XYA是否等价。只要在F中求X+，若X

24、+包含A，则Y是多余的属性；否则Y不是多余的属性。依次判断其他属性即可消除各依赖左边的多余属性。(3)去掉多余的依赖。具体做法是：从第一个依赖开始，从F中去掉它(假设该依赖是XY)，然后在剩下的依赖中求X+，看X+是否包含Y，若是，则可以去掉XY；若不包含Y，则不能去掉。第三十页，讲稿共一百一十页哦例：设有依赖集：F=ABC，CA，BCD，ACDB，DEG，BEC，CGBD，CEAG，计算其等价的最小依赖集。解：(1)将依赖右边属性单一化，结果为：F1=ABC，CA，BCD，ACDB，DE，DG，BEC，CGB，CGD，CEA，CE G (2)在F1中去掉左边多余的属性。、对于ACDB，由于(

25、CD)+=ABCDEG，则A是多余的，所以结果为：F2=ABC，CA，BCD，CDB，DE，DG，BEC，CGB，CGD，CE G、对于CEA，由于CA，则E是多余的 (3)在F2中去掉多余的依赖。对于CDB，在剩下的函数依赖中，由于(CD)+=CDAEGB，所以CDB是多余的，则Fm=ABC，CA，BCD，DE，DG，BEC，CGB，CGD，CEG或者对于CGB，由于(CG)+=ABCDEG，所以CGB是多余的，则Fm=ABC，CA，BCD，CDB，DE，DG，BEC，CGD，CEG总结：总结：求得的最小依赖集并不是唯一的。第三十一页，讲稿共一百一十页哦课堂练习：设有关系模式，其中U=E，F

26、，G，H，F=EG，GE，FEG，HEG，FHE，计算其等价的最小依赖集。结果为：Fm=EG，GE，FG，HG 或者：Fm=EG，GE，FG，HE 或者：Fm=EG，GE，FE，HG 或者：Fm=EG，GE，FE，HE第三十二页，讲稿共一百一十页哦补充：候选码求解理论和算法补充：候选码求解理论和算法对于给定的关系R(A1,A2,An)和函数依赖集F，可将其属性分为4类：L类：仅出现在F的函数依赖左边的属性R类：仅出现在F的函数依赖右边的属性N类：在F的函数依赖左右边均未出现的属性LR类：在F的函数依赖左右边均出现的属性第三十三页，讲稿共一百一十页哦1、快速求解候选码的一个充分条件定理1：对于给

27、定的关系模式R及其函数依赖集F，若X(XR)是L类属性，则X是R的任一候选码成员。推论：对于给定的关系模式R及其函数依赖集F，若X(XR)是L类属性，且X+包含了R的全部属性，则X必是R的唯一候选码。例：设有关系模式R(A,B,C,D)，其函数依赖集F=DB，BD，ADB，ACD，求R的所有候选码。解：考察F发现，A、C两属性是L类属性，由上面定理1可知，A、C必是R的候选码的成员。又因为(AC)+=ABCD，所以AC必是R的唯一候选码。第三十四页，讲稿共一百一十页哦定理2：对于给定的关系模式R及其函数依赖集F，若X(XR)是R类属性，则X不在任何候选码中。定理3：对于给定的关系模式R及其函数

28、依赖集F，若X(XR)是N类属性，则X必包含在R的任一候选码中。例：设有关系模式R(A,B,C,D,E,P)，其函数依赖集F=AD，ED，DB，BCD，DCA，求R的所有候选码。解：考察F发现，C、E两属性是L类属性，由上面定理1可知，C、E必是R的候选码的成员；P是N类属性，由上面的定理3可知，P也是R的候选码的成员。又因为(CEP)+=ABCDEP，所以CEP必是R的唯一候选码。定理4：对于给定的关系模式R及其函数依赖集F，若X(XR)是N类和L类组成的属性集，且X+包含了R的全部属性，则X必是R的唯一候选码。第三十五页，讲稿共一百一十页哦2、左边是单属性的函数依赖集的候选码成员的图论判定

29、方法定义1：一个函数依赖图G是一个有序二元组(R,F)，记做G=(R,F)，简称依赖图。其中：(1)R=(A1,A2,An)是一个有限非空集，Ai(I=1,2,n)是G 的结点，它们表示对应关系模式R的属性全集。(2)F是G的边集，其元素是G的一条有向线段(即边)，每条边(Ai，Aj)表示一个函数依赖AiAj，F是R的单属性最小依赖集。第三十六页，讲稿共一百一十页哦定义2：在一个函数依赖图中有下列术语：(1)引出线/引入线：(2)原始点：只有引出线而无引入线的结点。它表示L类属性。(3)终结点：只有引入线而无引出线的结点。它表示R类属性。(4)途中点：既有引出线又有引入线的结点。它表示LR类属

30、性。(5)孤立点：即无引出线而无引入线的结点。它表示N类属性。(6)关键点：原始点和孤立点的统称。(7)关键属性：关键点对应的属性。(8)独立回路：不能被其他结点到达的回路。第三十七页，讲稿共一百一十页哦定理5：一个关系模式R的函数依赖图G中若存在关键结点，则关键结点对应的属性必在R的任何候选码中，而所有的终结点必不在R的任何候选码中。定理6：属性集X是R的唯一候选码的充要条件是X为能到达G中任一结点的关键属性集。推论：在单属性情况下，R具有唯一候选码的充要条件是G中不存在独立回路。定理7：设Y是途中点，则Y必在某个候选码中的充要条件是Y为某一独立回路中的结点。第三十八页，讲稿共一百一十页哦定

31、理8：设F为单属性依赖集。R的关键属性集X不能到达G中的某个结点，G中存在K(k=1)个独立回路r1,r2,rk，各回路的结点集分别为：AA1=A11，A12，A1n1AA2=A21，A22，A2n2AAk=Ak1，Ak2，Aknn其中Aij(I=1,2,k，j=1,2,n)都是R的属性，则：(1)R的候选码必不唯一(2)R的每个候选码均由两部分组成 关键属性集X(X可以为空)K个独立回路中，每个独立回路任选一个点作为候选码的成员，候选码的集合Y是AA1，AA2，AKk(3)候选码的个数等于各回路中结点个数的乘积(4)每个候选码所含属性个数是一个常数，它等于关键属性个数|X|独立回路个数，即N

32、=|X|+K第三十九页，讲稿共一百一十页哦例：设有关系模式R(O,B,I,S,Q,D)，其函数依赖集F=SD，DS，IB，BI，BO，OB，求R的所有候选码。解：(1)FM=F=SD，DS，IB，BI，BO，OB(2)构造函数依赖图，如右图所示：sDIBQO(3)关键属性集：Q(4)共有2条回路，SD，IBO，所以候选码个数是2*3=6，每个候选码的属性个数是1+2=3。所以R的候选码不唯一，所有候选码为：QSI，QDI，QSB，QDB，QSO，QDO第四十页，讲稿共一百一十页哦例：设有关系模式R(X,Y,Z,W)，其函数依赖集F=WY，YW，XWY，ZWY，XZW，求R的所有候选码。解：(1

33、)FM=WY，YW，XY，ZW(2)构造函数依赖图，如右图所示：WYZX(3)关键属性集：X，Z(4)无独立回路所以，R只有唯一候选码XZ第四十一页，讲稿共一百一十页哦3、多属性依赖集候选码求解法算法：多属性依赖集候选码求解法输入：关系模式R及其函数依赖集F输出：R的所有候选码方法：(1)将R的所有属性分为L、R、N、LR四类，并令X代表L、N类，Y代表LR类。(2)求X+，若X+包含了R的全部属性，则X即为R的唯一候选码，转(5)；否则，转(3)(3)在Y中取一属性A，求(XA)+。若它包含了R的全部属性，那么XA为其中一个候选码，然后转(4)；否则，调换一属性反复进行这一过程，直到试完所有

34、Y中的属性。(4)如果已找出所有候选码，则转(5)；否则在Y中依次取两个、三个、，求它们的属性闭包，直到其闭包包含了R的所有属性。(5)停止，输出。第四十二页，讲稿共一百一十页哦例：关系模式CSZ(CITY，ST，ZIP)，其中城市CITY，街道ST，邮政编码ZIP。属性的函数依赖集：F=(CITY,ST)ZIP，ZIPCITY，试找出CSZ的候选码。解：候选码为(ST，ZIP)和(ST，CITY)(1)因为ST是L类属性，所以ST是候选码的成员之一。CITY 和ZIP是LR类。(2)(ST)+没有包含CSZ的所有属性，所以ST不是唯一候选码。(3)(ST，ZIP)+包含CSZ的所有属性，所以

35、(ST,ZIP)是一个 候选码。(4)(ST，CITY)+也包含CSZ的所有属性，所以(ST,CITY)是一个候选码。第四十三页，讲稿共一百一十页哦例：设有关系模式R(A,B,C,D,E)，其函数依赖集F=ABC，CDE，BD，EA，求R的所有候选码。解：(1)Fm=AB，AC，CDE，BD，EA(2)A，B，C，D，E五个属性在F中各个函数依赖的右边和左边都出现了，所以候选码中可能包含A，B，C，D，E。(4)除去A，E两个候选码，在B，C，D中查找两个属性的候选码 (BC)+=ABCDE，即BCU，所以BC是一个候选码 (BD)+=BD，即BCU，所以BD不是一个候选码 (CD)+=ABC

36、DE，即CDU，所以CD是一个候选码(3)A+=ABCDE，即AU，所以A是一个候选码 B+，C+，D+U，所以B，C，D不是候选码 E+=ABCDE，即EU，所以也E是一个候选码候选码有：A，E，BC，CD第四十四页，讲稿共一百一十页哦课堂练习：1、设有关系模式，其中U=A，B，C，D，E，P，H，G，F=ABCE，AC，GPB，EPA，CDEP，HBP，DHG，ABCPG，计算其等价的最小依赖集。Fm=ABE，AC，GPB，EPA，CDEP，HBP，DH，DG，ABCP，ABCG2、设有关系模式R(A,B,C,D,E,P)，其函数依赖集F=AB，CP，EA，CED，求R的所有候选码。候选码

37、为：CE3、设有关系模式R(S,D,I,B,O,Q)，其函数依赖集F=SD，IB，BO，OQ，QI，求R的所有候选码。候选码为：SI，SB，SQ，SO第四十五页，讲稿共一百一十页哦6.2.3-6.2.6 范式一、规范化和范式关系模式设计的不好，会引起插入、删除、更新异常。在70年代，诸多专家和学者，各自研究了发生异常的类型及防止异常的方法，使得设计关系的准则得到了改进。这些用以防止异常发生的准则(技术)叫做规范化。规范化的关系模式被称为范式。范式是更符合某些规则的关系模式。关系规范化可按属性间不同的依赖程度分为第一范式、第二范式、第三范式、Boyce-Codd范式以及第四范式。人们对规范化的认

38、识是有一个过程的，在1970年时E.F.Codd已发现属性间的函数依赖关系，从而定义了与函数依赖关系有关的第一、第二、第三范式；1974年Codd和Boyce共同提出BCNF范式。在19761978年间，Fagin，Delobe以及Zanjolo发现了多值依赖关系，从而定义了与多值依赖有关的第四范式。以后又有人提出了5NF。第四十六页，讲稿共一百一十页哦二、规范化的方法分解研究产生异常的原因发现：如果一个关系模式中包含两个或多个不同问题的事实，如：学生(sno，sdept、dean、cno、grade)。增加一行时，必须增加关于两个或多个主题的数据，删除一行时，也必须删除关于两个或多个主题的数

39、据。因此，将关系规范化，就是让每个关系只有一个主题，如果某个关系模式有多于一个的主题，就把他们分解成多个关系(二维表)，就像我们写文章，一个自然段中只有一个中心内容。第四十七页，讲稿共一百一十页哦三、范式级别 1NF 2NF 3NF BCNF 4NF 5NF其规范化的条件按上述次序越来越强。范式概念可以理解为符合某一种级别的关系模式的集合，关系模式 R 为第几范式可以写成 RxNF。把低级范式的关系模式，通过分解转换为高一级范式的关系模式的集合，这个过程称为关系模式的规范化设计。第四十八页，讲稿共一百一十页哦第一范式(1NF)第一范式（1NF）：规定关系的每一个分量必须是一个不可分的数据项。关

40、系数据模型要求所有的关系模式必须满足第一范式的要求。这是对关系模式最起码的规范化要求。第四十九页，讲稿共一百一十页哦非第一范式的例子 如果关系模式仅仅满足第一范式的条件是不够的，可能会存在数据冗余和操作异常。为了消除这些数据冗余和操作异常，需要进行关系模式的规范化。转换为第一范式姓名单位办公电话住宅电话手机号码姓名单位联系电话办公电话住宅电话手机号码第五十页，讲稿共一百一十页哦第二范式第二范式(2NF)(2NF)定义6.6：如果关系模式R满足第一范式，且它的任何一个非主属性都完全函数依赖于任一个候选码，则R满足第二范式（简记为R2NF）。第五十一页，讲稿共一百一十页哦例：学生表D(Sno,Sn

41、ame,Sdept,Sage,Cno,Cname,Credit,Grade)D(Sno,Sname,Sdept,Sage,Cno,Cname,Credit,Grade)是1NF但不是2NF的关系模式Sno(5)Sname(10)Sdept(10)Sage(2)Cno(5)Cname(20)Credit(2)Grade(2)0001张三计算机17c101数据结构4900001张三计算机17c102网络安全3880001张三计算机17c103软件工程4780001张三计算机17c105数值分析2800001张三计算机17c110编译原理3860002李四物理19c103软件工程 4820002李四

42、物理19c105数值分析2800003王五计算机17c107C语言475第五十二页，讲稿共一百一十页哦在关系模式D中，非主属性Sname，sdept，sage对码是部分函数依赖。D属于1NF，但不属于2NF。则D表的函数依赖如下：sno sname，snosdept，snosageCnoCname，cnocredit(Sno,Cno)Grade候选码是(Sno，Cno)，其函数依赖图为：SnoCnoGradecreditCnamesdeptsagesname第五十三页，讲稿共一百一十页哦 根据第二范式的定义，为消除部分函数依赖，将D关系模式分解为s、c和sc这3个关系模式：sc(Sno，Cno

43、，Grade)函数依赖是：(Sno，Cno)GradeS(sno,sname,sdept,sage)函数依赖是：snosname，snosdept，sno sageC(Cno，Cname，credit)函数依赖是：(CnoCname,Cnocredit)sc、S和C都消除了非主属性对码的部分函数依赖，因此都属于2NF。第五十四页，讲稿共一百一十页哦Sno(5)Sname(10)Sdept(10)Sage(2)0001张三计算机170002李四物理190003王五计算机17Sno(5)Cno(5)Grade(2)0001c101900001c102880001c103780001c1058000

44、01c110860002c103820002c105800003c10775关系关系s 关系关系scCno(5)Cname(20)Credit(2)c101数据结构4c102网络安全3c103软件工程4c105数值分析2c107C语言4c110编译原理3关系关系c是否存在冗余？是否存在冗余？尽管增加了字段，但字节数减少尽管增加了字段，但字节数减少=(5+10+10+2)*3+(5+5+2)*8+(5+20+2)*6=339是否存在更新异常现象？是否存在更新异常现象？第五十五页，讲稿共一百一十页哦练习：设有关系模式如下：T(Sno，Cno，Cname，Tname，room，Grade)若每门课只

45、由一位教师讲授但一个教师可以讲授多门课程，每位教师只在一个教室中讲课。SnoCnoGradeCnameTnameroomS1C178数据库李美丽1234S1C289C语言李美丽1234S2C186数据库李美丽1234S2C296C语言李美丽1234S3C246C语言李美丽1234S3C381英语李刚3422第五十六页，讲稿共一百一十页哦SnoCnoGradeTnameroomCname在关系模式T中，非主属性Cname，Tname，room对码是部分函数依赖，并存在传递函数依赖CnoTname，Tnameroom。T属于1NF，但不属于2NF。则T表的函数依赖如下：(Sno,Cno)Grade

46、 CnoCname CnoTname Tnameroom候选码是(Sno，Cno)第五十七页，讲稿共一百一十页哦 根据第二范式的定义，为消除部分函数依赖，将T关系模式分解为T1和C这2个关系模式：T1(Sno，Cno，Grade)函数依赖是：(Sno，Cno)GradeC(Cno，Cname，Tname，room)函数依赖是:(CnoCname,CnoTname,Tname room)T1和C都消除了非主属性对码的部分函数依赖，因此都属于2NF。第五十八页，讲稿共一百一十页哦CnoCnameTnameroomC1数据库李美丽1234C2C语言李美丽1234C3英语李刚3422SnoCnoGra

47、deS1C178S1C289S2C186S2C296S3C246S3C381关系关系T1 关系关系C第五十九页，讲稿共一百一十页哦 一个关系模式仅仅满足2NF仍是不够的，如在关系模式C(Cno，Cname，Tname，room)中，仍存在着插入、删除和修改异常问题：-新来的教师，还没有分配授课之前，教师的姓名及教室编号都不能加到关系中；-如果要修改教室编号，必须修改与教师授课相对应的所有元组中的教室编号，因为一位教师可能会教多门课。-如果要删除c3这门课程，则殃及李刚老师的教师编号也被删除。存在上述这些问题的原因是关系模式C中存在非主属性对码的传递函数依赖，所以要把关系模式C向第三范式转化，除

48、去非主属性对码的传递函数依赖。第六十页，讲稿共一百一十页哦第三范式(3NF)定义6.7 如果关系模式R满足 2NF，并且它的任何一个非主属性都不传递函数依赖于任何候选码，则称R是第三范式3NF,记作R3NF。第六十一页，讲稿共一百一十页哦在上一例题中，关系模式：C(Cno，Cname，Tname，room)其中存在非主属性room对码的传递函数依赖，即：Cno Tname，Tname room，因此C不属于3NF。分解方法：将起传递作用的函数关系中的主属性(决定方)和非主属性取出单独构成一个关系模式，再将它的决定方和关系式中余下的属性加上主码，构成另一个关系模式。所以，将C分解为：C1(Cno

49、,Cname,Tname)F=Cno Tname,Cno CnameL(Tname，room)F=TnameROOM则关系模式C1和L中都没有非主属性对码的传递函数依赖，因此都属于3NF。第六十二页，讲稿共一百一十页哦 至此，关系模式T分解为下列3个属于3NF的一组关系模式：T1(Sno,Cno,Grade)C1(Cno,Cname,Tname)L(Tname,room)如下一张幻灯片 和关系模式T相比，这些关系模式是对现实世界更加精确的描述。把这3个关系进行连接，总能重构初始的关系。第六十三页，讲稿共一百一十页哦CnoCnameTnameC1数据库李美丽C2C语言李美丽C3英语李刚SnoCn

50、oGradeS1C178S1C289S2C186S2C296S3C246S3C381关系关系T1 关系关系C1Tnameroom李美丽1234李刚3422关系关系L第六十四页，讲稿共一百一十页哦第三范式还有问题吗？例：关系模式STJ(S学生，T教师，J课程)，其包含的语义是：每位教师只教一门课程；每门课有若干个教师，某一学生选定某门课，就对应一个固定的老师。根据语义存在的函数依赖？F=TJ，SJT，STJ此关系的码是：ST或SJ该关系属于第几范式？该关系有没有部分函数依赖和传递函数依赖呢？结论：STJ模式，因为没有非主属性的部分函数依赖和传递函数依赖，所以3NFSTJS4王建华数据结构(计算机