数据库关系模式的规范化.ppt

《数据库关系模式的规范化.ppt》由会员分享，可在线阅读，更多相关《数据库关系模式的规范化.ppt（144页珍藏版）》请在三一办公上搜索。

1、第 4 章,关系模式的规范化设计理论,第4章 关系模式的规范化设计理论,建立关系数据库的任务:先设计关系模式，若干关系模式构成关系数据库模式。对一个具体的应用问题，如何构造一个适合于它的数据库模式，即关系数据库模式设计应遵循那些原则。这是本章主要讨论的问题。在介绍第1章的例子，曾经问过为什么要设计成Students,Courses,Reports三个基本表，而不是一张表呢？,第4章 关系模式的规范化设计理论,关系数据库的规范化设计是指面对一个现实问题,如何选择一个比较好的关系模式集合。规范化设计理论主要包括三个方面的内容：数据依赖、范式和模式设计方法。其中数据依赖起着核心的作用。数据依赖研究数

2、据之间的联系，范式是关系模式的标准，模式设计方法是自动化设计的基础。规范化设计理论对关系数据库结构的设计起着重要的作用。,第4章 关系模式的规范化设计理论,4.2 关系模式的函数依赖,4.3 关系模式的规范化,4.4 关系模式的分解特性,4.1 问题的提出,4.1 问题的提出,4.1.2 异常原因分析,4.1.3 异常问题的解决,4.1.1 关系模式可能存在的异常,关系模型的外延和内涵,外延就是通常所说的关系、表或当前值，它的基本性质已在第2章介绍过。由于用户经常对关系进行插入、删除和修改操作，因此外延是与时间有关的，随着时间的推移在不断变化。内涵是与时间独立的，是对数据的定义以及数据完整性约

3、束的定义。对数据的定义包括对关系、属性、域的定义和说明。对数据完整性约束的定义涉及面较广，主要包括以下几个方面：静态约束，涉及到数据之间联系（称为“数据依赖，data dependences）、主键和值域的设计。动态约束，定义各种操作（插入、删除、修改）对关系值的影响。,4.1.1 关系模式可能存在的异常(1),例4.1 以学生选课背景为，假设我们设计了如下一个关系模式：StudyInfo(Sno,Sname,DeptName,DeptHead,Cname,Grade)其中Sno，Cname是唯一候选键，因此是主键。表4.1 是关系模式StudyInfo的一个实例关系。,表4.1 关系Stud

4、yInfo,4.1.1 关系模式可能存在的异常(2),StudyInfo这个关系存在的几个异常问题：插入异常。比如一个刚刚成立的系，但尚未招收学生，则因属性Sno为空，导致诸如系主任姓名之类的信息无法存入数据库；同样，没被学生选修的课程信息也无法存入数据库。删除异常。如一个系的学生毕业了，删除学生记录时不情愿地将系主任姓名等信息也一起删除了。冗余过多。如一个系的系名、系主任姓名都要与该系学生每门课的成绩出现的次数一样多。既浪费存储空间又要付出很大的代价来维护数据库的完整性。当系主任更换后，必须逐一修改该系学生选修课程的每一个元组。,4.1.2 异常原因分析(1),例子启示：一个“好”的模式不应

5、当发生插入异常和删除异常，且数据冗余应尽可能地少。结论：关系模式StudyInfo“不怎么好”或“不好”StudyInfo“不好”或存在异常问题原因：关系模式的属性之间存在过多的“数据依赖”,先非形式地讨论一下这个概念。数据依赖是指关系中属性值之间的相互联系，它是现实世界属性间相互联系的体现，是数据之间的内在性质，是语义的体现。现在人们已经提出了许多种类型的数据依赖，其中最重要的是函数依赖(Functional Dependence，FD)和多值依赖(MultiValued Dependence，MVD)。,4.1.2 异常原因分析(2),函数依赖极为普遍地存在于现实生活中。对关系StudyI

6、nfo，因一个学号Sno仅对应一个学生，一个学生只在一个系注册学习。因而，当学号Sno的值确定之后，姓名Sname和他所在系DeptName的值也就被唯一地确定了。就象自变量x的值确定之后，相应函数f(x)的值也就唯一地确定一样，我们说Sno决定Sname和DeptName，或者说Sname，DeptName函数依赖于Sno，记作:SnoSname，SnoDeptName。,4.1.2 异常原因分析(3),对关系模式StudyInfo，其属性集U=Sno,Sname,DeptName,DeptHead,Cname,Grade。根据学校管理运行的实际情况，我们还知道：一个学生只有一个学号，即Sn

7、oSname；一个系有若干学生，但一个学生只属于一个系，即 SnoDeptName；一个系只有一个系主任，即 DeptNameDeptHead；每个学生学习每一门课都有一个成绩，即Sno,CnameGrade。,4.1.2 异常原因分析(4),这样就得到关系模式StudyInfo属性集U上所有函数依赖组成的集合F，简称函数依赖集。F=SnoSname,SnoDeptName,DeptNameDeptHead,Sno,CnameGrade。所谓关系模式StudyInfo中的数据依赖过多，是指它存在多种类型的函数依赖，比如，既有主健 Sno,CnameGrade，又有Sno,Cname中部分属性S

8、no确定的SnoSname，还有非主键属性DeptName确定的DeptNameDeptHead等。,4.1.3 异常问题的解决(1),异常问题的解决方法：将关系模式分解成若干个只有单一“数据依赖”的关系模式。因为关系模式StudyInfo出现异常问题是由于属性之间存在过多的“数据依赖”造成，分解的目的就是减少属性之间过多的“数据依赖”，以期消除关系模式中出现的异常问题。,4.1.3 异常问题的解决(2),例4.2 将StudyInfo分解为如下三个新的关系模式：Students(Sno,Sname,DeptName)，Reports(Sno,Cname,Grade)，Departments(

9、DeptName,DeptHead)，则分解后的每个关系模式，其属性之间的函数依赖都大大减少，关系 Students的函数依赖是SnoSname,SnoDeptName；Reports的函数依赖是Sno,CnameGrade；Departments的函数依赖是DeptNameDeptHead。,4.1.3 异常问题的解决(3),关系模式的分解：用若干属性较少的关系模式代替原有关系模式的过程。比如用Students,Reports,Departments就是关系模式StudyInfo的一个分解。表4.1表示的关系StudyInfo就可以用表4.2表4.4对应的关系来表示。从表4.2表4.4可以看

10、出，没有分解之前存在的插入异常和删除异常等问题已经基本消除，且数据冗余程度大大降低。,4.1.3 异常问题的解决(3),表4.2 关系Students,4.1.3 异常问题的解决(3),表4.3 关系Reports,4.1.3 异常问题的解决(3),表4.4 关系Departments,4.1.3 异常问题的解决(4),前面通过实例说明，解决关系模式异常问题的方法是对关系模式进行分解。但分解的理论问题还没有解决：怎样判定关系模式好或不好?(关系模式的标准问题)怎样判定一个关系模式的分解是好(有益)的?(分解的标准问题)怎样将一个关系模式分解为一组好的关系模式?(分解方法问题)这就是规范化理论，

11、它正是用来改造关系模式，通过分解关系模式来消除其中不合适的数据依赖，以解决插入异常、删除异常、更新异常和数据冗余问题。这些就是后面几节所涉及的内容。,4.2 关系模式的函数依赖,函数依赖的一般概念,候选键与主键,函数依赖的推理规则,再论关系与关系模式,4.2.1 再论关系与关系模式,关系：元组的集合，笛卡尔积的一个子集，其实质是一张二维表，表的每一行为一个元组。关系模式：对元组中数据组织方式的结构性描述，其实质是删去所有元组后的空表格。关系与关系模式的联系：关系模式是相对稳定的、静态的，而关系却是动态变化的，不稳定的，且关系的每一次变化结果，都是关系模式对应的一个新的具体关系。注意：关系模式R

12、(U)对应的具体关系通常用小写字母r来表示。,4.2.2 函数依赖的一般概念(1),定义4.1 设R(U)是属性集U=A1,A2,An上的关系模式，X和Y是U的子集。若对R(U)的任一具体关系r中的任意两个元组t1和t2，只要t1X=t2X 就有t1Y=t2Y。则称“X函数确定Y”或“Y函数依赖于X”(Founctional Dependence)，记作XY。类似于y=f(x)其中t1X和t1Y分别表示元组t1在属性X和Y上的取值。“X函数确定Y”的含义是：在关系模式R(U)的任意一个具体关系r中，不可能存在这样的两个元组，它们在X上的属性值相等，而在Y上的属性值不等。注意：函数依赖不是指关系

13、模式R(U)的某个或某些具体关系满足的约束条件，而是指R(U)的一切具体关系r都要满足的约束条件。,4.2.2 函数依赖的一般概念(2),例4.3 设有一个描述学生信息的关系模式:R(Sname,Sex,Birthday,Phone)，其属性名分别代表学生的姓名、性别、出生日期和电话号码属性。它的一个具体关系r如表4.5所示。,4.2.2 函数依赖的一般概念(3),如果仅从关系模式R(U)的一个具体关系r出发，由于r没有相同姓名的元组(学生)，所以我们就会得出：对于关系模式R有SnameSex，SameBirthday，SnamePhone的结论。但这个结论是不正确的。比如，对关系模式R的另外

14、一个具体关系r1(表4.6)，这时，从关系r得出的函数依赖就不成立了。所以，关系模式中的函数依赖是对这个关系模式的任何可能的具体关系都成立的函数依赖。,4.2.2 函数依赖的一般概念(4),表4.6 关系r1,从例子可知，函数依赖与属性的语义有关。我们要根据属性的语义来确定一个函数依赖。例如SnameBirthday这个函数依赖，只有当关系中没有同姓名学生的条件下才成立。如果关系中允许出现相同姓名的学生，则出生日期就不再函数依赖于姓名了，即 SnameBirthday 数据库设计者应在定义数据库模式时，指明属性之间的函数依赖(主键)，使数据库管理系统根据设计者的意图来维护数据库的完整性。因此，

15、设计者可以对现实世界中的一些数据依赖作强制性规定.,4.2.2 函数依赖的一般概念(5),4.2.2 函数依赖的一般概念(6),例如，为了使SnameBirthday这个函数依赖成立，我们在创建 基本表(Create Table)时，通过指定Sname为主键的方法强制规定关系中不允许同名同姓的人存在。这样当输入某个元组时，这个元组在Sname上的属性值必须满足以上规定。若发现新输入元组在Sname上的值与关系中已有元组在Sname上的值相同，则数据库管理系统就拒绝接受该元组。解决的办法是通过人工方式是同名者为不同名者。比如有两个张华，可改为“张华”，“张华b”等。,在定义4.1的基础上补充以下

16、常用术语和记号：若XY，则称X为这个函数依赖的决定(Determinant)因素，简称X是决定因素。若XY且YX，则记作XY。(3)若Y不函数依赖于X，则记作。例:Student(Sno,Sname,Ssex,Sage,Sdept)假设不允许重名，则有:Sno Ssex，Sno Sage,Sno Sdept，Sno Sname，Sname Ssex，Sname Sage，Sname Sdept但Ssex Sage,4.2.2 函数依赖的一般概念(7),若XY，且Y X，则称XY是平凡函数依赖。若XY，且（也就是Y中至少有一个属性不在X中），则称XY是非平凡函数依赖。例：在关系SC(Sno,Cn

17、o,Grade)中，非平凡函数依赖：(Sno,Cno)Grade 平凡函数依赖：(Sno,Cno)Sno(Sno,Cno)Cno对于任一关系模式，平凡函数依赖都是必然成立的，但它不反映新的语义。所以在后面的讨论中，若没有特别声明，“XY”都表示非平凡函数依赖。,4.2.2 函数依赖的一般概念(8),4.2.2 函数依赖的一般概念(8),定义4.2 设R(U)是属性集U=A1,A2,An上的关系模式。X和Y是U的子集。如果XY，且对于 X的任何一个真子集X，都有，则称Y对X完全函数依赖(Full Founctional Dependence)或者X完全决定Y，记作:XY。如果XY，但Y不是完全函

18、数依赖于X，则称Y对X部分函数依赖(Partial Founctional Dependence)，记作：XY。例:在关系SC(Sno,Cno,Grade，Cname)中，由于：Sno Grade，Cno Grade，因此：(Sno,Cno)Grade(Sno,Cno)Cname,f,p,p,f,定义4.3 对于关系模式R(U)，设X、Y和Z都是U的子集。如果XY，YZ，且，,则称Z对X传递函数依赖(Transitive Functional Dependence)，记作:XZ。在传递函数依赖的定义中加上条件 是必要的，因为如果YX，则XY，即说明X与Y之间是一一对应的，这样导致Z对X的函数依

19、赖是直接依赖，而不是传递函数依赖。定义4.3中的条件 主要是强调XY和YZ都不是平凡函数依赖，否则同样Z对X是直接函数依赖，而不是传递函数依赖。例:在关系Std(Sno,Sdept,Mname)中，有：Sno Sdept，Sdept Mname Mname传递函数依赖于Sno 即：Mname Sno,4.2.2 函数依赖的一般概念(9),t,t,例4.4 关系模式StudyInfo(Sno,Sname,DeptName,DeptHead,Cname,Grade)有如下的一些函数依赖：SnoSname,Sno,CnameGrade，SnoDeptName,DeptNameDeptHead。由最后

20、两个函数依赖还可得出DeptHead传递函数依赖Sno，即 SnoDeptHead。如果没有同姓名的学生，还有SnoSname等。但显然有，。U=(Sno,Sname,DeptName,DeptHead,Cname,Grade)K=Sno,Cname 则KU,4.2.2 函数依赖的一般概念(10),t,t,f,4.2.3 候选键与主键(1),函数依赖的概念可更严格地定义关系模式的候选键与主键。定义4.4 对关系模式R(U)，设KU。如果，则称K为R(U)的候选键或候选关键字(Candidate Key)。通常在R(U)的所有候选键中选定一个作为主键(Primary Key)。主键也称为主码或主

21、关键字。候选键是能够唯一确定关系中任何一个元组(实体)的最少属性集合，主键也是候选键，它是候选键中任意选定的一个。在最简单的情况，单个属性是候选键。最极端的情况是，关系模式的整个属性全体是候选键，也是主键，这时称为全键或全码(All-key)。,4.2.3 候选键与主键(2),例4.5 设有关系模式R(Teacher，Course，Sname)，其属性Teacher，Course，Sname 分别表示教师，课程和学生。由于一个教师可以讲授多门课程，某一课程可由多个教师讲授。学生也可以选修不同教师讲授的不同课程，因此，这个关系模式的候选键只有一个，就是关系模式的全部属性(Teacher，Cour

22、se，Sname)，即全键(All-key)，它也是该关系模式的主键。为了便于区别候选键中的属性与其它属性，我们可以得到如下定义。,4.2.3 候选键与主键(3),定义4.5 对关系模式R(U)，包含在任何一个候选键中的属性称为主属性(Primary Attribute)，不包含在任何候选键中的属性称为非主属性(Nonprimary Attribute)或非码属性(Non-key Attribtute)。例4.6 在关系模式StudyInfo(Sno，Sname，DeptName，DeptHead，Cname，Grade)中，Sno,Cname是其唯一候选键，因此，Sno和Cname都是主属性

23、，而Sname，DeptName、DeptHead，Grade都是非主属性。定义4.6 对关系模式R(U)，设XU。若X不是R(U)的主键，但X是另一个关系模式的主键，则称X是R(U)的外键或外部关键字(Foreign key)。,4.2.3 候选键与主键(4),例4.7 在Reports(Sno,Cname,Grade)中，Sno不是关系模式Reports的主键，但Sno是关系模式Students(Sno,Sname,DeptName)中的主键。因此，Sno是关系模式Reports(Sno,Cname,Grade)的外键。主键与外键提供了一个表示两个关系中元组(实体)之间联系的手段。在数据设

24、计中，经常人为地增加外键来表示两个关系中元组之间的联系。当两个关系进行连接操作时就是因为有外键在起作用。比如，我们需要查看每个学生的姓名、选课名称和成绩时，就涉及到Students(Sno,Sname,DeptName)和Reports(Sno,Cname,Grade)对应关系的连接操作，这时，只要使用第1章介绍的如下SQL命令即可。SELECT Sname,Cname,Grade FROM Students,Reports WHERE Students.Sno=Reports.Sno。,4.2.4 函数依赖的推理规则,在讨论函数依赖时会遇到这样的问题：已知关系模式R(U,F)的函数依赖集F=

25、AB，BC。问AC是否成立?其中属性集U=A,B,C。这是本节后面将讨论的有关问题，其内容安排如下：函数依赖的逻辑蕴涵 Armstrong公理系统 函数依赖推理规则的完备性 闭包的计算 函数依赖集的等价和覆盖,函数依赖的逻辑蕴涵(1),在介绍函数依赖的推理规则之前，先介绍两个函数依赖的逻辑蕴涵和闭包概念。定义4.7 对于满足函数依赖集F的关系模式R(U,F)的任意一个具体关系r，若函数依赖XY都成立(即对于r中的任意两个元组t，s，若tX=sX，则有tY=sY)，则称F逻辑蕴涵XY，记为FXY。如F=AB，BC。FAC。(后面介绍)定义4.8 被函数依赖集F逻辑蕴涵的函数依赖所构成的集合，称为

26、F的闭包(Closure)，记作F+。即：F+=XY|FXY。,函数依赖的逻辑蕴涵(2),通常，FF+。若F=F+，称F是函数依赖完备集。然而，对于给定的函数依赖集F和属性集X，Y，仅有定义4.7和定义4.8还难于回答F是否逻辑蕴涵XY的问题。当然，我们可以先计算F+，然后检查XY是否属于F+即可。但我们还没有学到计算一个函数依赖集F的闭包F+的方法。这些问题需要学习了Armstrong公理系统和函数依赖的推理规则等知识以后才能够解决。,Armstrong公理系统,通俗说，Armstrong公理系统是函数依赖基本推理规则的集合，又称Armstrong推理规则系统。Armstrong公理系统：设

27、有关系模式R(U,F)，F是只涉及到U中属性的函数依赖集。若X，Y，Z，W均是U的子集，则有以下推理规则：自反律(Reflexivity Rule)：如果YX U，则XY成立，即FXY。增广律(Augmentation Rule)：如果XY成立,则XZYZ 成立(其中XZ是XZ的简单记法，其它类同)，即若FXY，则FXZYZ。传递律(Transitivity rule)：如果XY，YZ成立，则X Z成立，即若FXY，FYZ，则F XZ。,Armstrong公理系统(1),定理4.1 Armstrong公理系统中的推理规则，是正确的，即若XY由Armstrong公理导出，则XY属于F+。证明从略

28、。,Armstrong公理系统(2),定理4.2 函数依赖的如下五个推理规则是正确的。合并律(Union Rule)：如果XY和XZ成立，那么XYZ成立，即若FXY，FXZ，则F XYZ。伪传递律(Pseudotransivity Rule)：如果XY和WYZ成立，那么WXZ成立，即若FXY，FWYZ，则FWXZ。分解律(Decomposition Rule)：如果XY和ZY成立，那么XZ成立，即若FXY，ZY，则F XZ。(4)复合性(composition）：如果XY和WZ成立，那么XW YZ成立，即若FXY，FWZ，则F XW YZ。(5)如果XY和WZ成立,那么X(W-Y)YZ成立，即

29、若FXY，FWZ，则F X(W-Y)YZ。推论4.1 对关系模式R(U)，设XU，A1,A2,AmU，则XA1,A2,Am成立的充分必要条件是XAi(i=1,2,m)成立。,Armstrong公理系统(3),定义4.9 设F是属性集合U上的一个函数依赖集，XU，称 为属性集X关于F的闭包 在以后的讨论中，如果只涉及一个函数依赖集F，则属性集X关于F的闭包常简记为X+。值得注意的是，定义4.9中的A是U中的单个属性，因此XX+U。,Armstrong公理系统(4),例4.8 设关系模式R(U,F)，其中UA,B,C，函数依赖集FAB,BC。则有：A+A,B,C B+B,C C+C定理4.3 设F

30、是属性集U上的函数依赖集，X，Y是U的子集，则XY能由F根据Armstrong公理导出的充分必要条件是 Y X+。用途：判断一个函数依赖XY是否在F+中，只要判断XY能否从F根据Armstrong公理导出，即判断YX+是否成立即可。,函数依赖推理规则的完备性*(1),Armstrong公理的有效性：由F出发根据Armstrong公理导出的每一个函数依赖XY一定在F+中；Armstrong公理的完备性：F+中的每一个函数依赖XY，必定可以由F出发根据Armstong公理导出。,函数依赖推理规则的完备性*(2),从Armstong公理系统的完备性可以得到两个重要结论：对属性集X+中的每个属性A，都

31、有XA被F逻辑蕴涵，即X+是所有由F逻辑蕴含XA的属性A的集合。F+是由F根据Armstrong公理导出的函数依赖的集合。从Armstrong公理的完备性和有效性可知，“导出”与“蕴含”其实是两个完全等价的概念。因此可以得到函数依赖集F的闭包的一个计算公式：F+=XY|XY由F根据Armstrong公理导出 原定义为：F+=XY|FXY,闭包的计算(1),为了判断函数依赖XY是否在F+中，只要计算出F+即可。因为F+是由F根据Armstrong公理导出的函数依赖的集合。因此，原则上说，只要按照Armstrong公理系统中的推理规则就可以计算出F+。但是，闭包F+的计算是一件很麻烦的事情，因为计

32、算F+的问题是一个NP完全问题，即若U=A1,A2,An，F=X1Y1,X2Y2,XmYm，则计算F+需要的o(m!*2n)个函数依赖，因此，当 n、m比较大时，实际计算F+是不可行的。即使F的元素不多时，F+中的元素也可能很多。此外，闭包F+中也存在许多冗余信息。下面的示例给予说明。,闭包的计算(2),例4.9 设有关系模式R(U,F)，其中U=A,B,C，函数依赖集FAB，BC，则利用Armstrong公理系统中的推理规则可以求得F的闭包F+为如下的集合：,A,AB,AC,ABC,B,C,AA,ABA,ACA,ABCA,BB,CC,AB,ABB,ACB,ABCB,BC,AC,ABC,ACC

33、,ABCC,BBC,AAB,ABAB,ACAB,ABCAB,BC,AAC,ABAC,ACAC,ABCAC,BCB,ABC,ABBC,ACBC,ABCBC,BCC,AABC,ABABC,ACABC,ABCABC,BCBC,注意，以上集合中ABCBC等是A,B,CB,C的简写形式。,闭包的计算(3),其实，判断一个函数依赖XY是否在F+中，完全不必计算闭包F+，因为，由定理4.3可知，只要判断XY能否从F根据Armstrong公理导出，即判断YX+是否成立即可。这样就把一个需要计算F+才能解决的问题简化为计算X+就能解决的问题。而计算X+并不太难，它所花费的时间与F中的全部函数依赖的长度成正比。下

34、面介绍一个计算X+的算法。,闭包的计算(4),算法4.1 求属性集XU关于函数依赖集F的闭包X+。输入：有限的属性集合U、它上面的函数依赖集合F和U的一个子集X。输出：X关于F的闭包X+。计算方法和计算步骤：设置初始值：令X(0)，X(1)X，F=；如果X(0)X(1)，令X(0)X(1)，否则转；构造函数依赖集F=YZ|(YZ)F且YX(1)，令 F=FF 对F中的每一个函数依赖YZ,令X(1)=X(1)Z,转 输出X(1)，它就是X+。,闭包的计算(5),下面举例说明这个算法的使用方法。例4.10 设有关系模式R(A,B,C,D,E)，其属性集上函数依赖：F=ABC,BD,CE,ECB,A

35、CB，这里的ABC是A,BC的简写。令X=A,B，求X+。解：计算过程是根据循环次数介绍的。由算法4.1 第一次：X(0)=，X(1)=A,B，F=；由于X(0)X(1)，令X(0)X(1)=A,B；函数依赖集F=ABC,BD，令F=F-F=CE,ECB,ACB，将F中的每一个函数依赖的右端属性C,D并入X(1)中，即令X(1)=A,BC,D=A,B,C,D；,闭包的计算(6),第二次：由于X(0)X(1)，令X(0)X(1)=A,B,C,D；函数依赖集F=CE,ACB，令F=F-F=ECB，将F中的每一个函数依赖的右端属性E,B并入X(1)中，即令X(1)=A,B,C,D E,B=A,B,C

36、,D,E；第三次：由于X(0)X(1)，令X(0)X(1)=A,B,C,D,E；函数依赖集F=ECB，令F=F-F=将F中的每一个函数依赖的右端属性B并入X(1)中，即令X(1)=A,B,C,D,E B=A,B,C,D,E；第四次：由于X(0)=X(1)，转 输出X(1)=A,B,C,D,E=X+。由此可知：A,BU=A,B,C,D,E，由于AU，BU，所以A,B是侯选键。例属性集U为ABCD，FD集为 AB,BC,DB。则用上述算法，可求出A+=ABC，(AD)+=ABCD,(BD)+=BCD，等等。,快速求解候选键的一些方法,对于给定的关系R和函数依赖集F，可将属性分为四类：L类,仅出现在

37、F的函数依赖左边的属性；R类,仅出现在F的函数依赖右边的属性；N类,在F的函数依赖两边都不出现的属性；LR类,在F的函数依赖两边都出现的属性。若X是L类，则X必为R的任一候选键成员，若X+包含所有属性则X必为R的唯一候选键。如R(ABCD)，F=DB,BD,ADB,ACD，A,C是L类，又(AC)+=ACBD,因此，AC是R的唯一候选键。若X是R类，则X不在任何候选键中。若X是N类，则X必为R的任一候选键成员；若X是L类和N类组成，且若X+包含所有属性则X必为R的唯一候选键。如R(ABCDEP)，F=AD,ED,DB,BCD,DCA，C,E是L类，P是N类,又(CEP)+=ACBDEP,因此，

38、CEP是R的唯一候选键。,返回,5.函数依赖集的等价和覆盖*定义4.10 对关系模式R(U)上的两个函数依赖集F和G，如果满足F+G+，则称F和G是等价的。如果F和G是等价的，则称F覆盖G(同时G也覆盖F)。定理4.5 F+G+充分必要条件是FG+,GF+。定理4.6 每个函数依赖集F都可以被一个右部只有单属性的函数依赖集G所覆盖。,4.2.4 函数依赖的推理规则,定理4.7 每个函数依赖集F都有最小覆盖。,4.2.4 函数依赖的推理规则(7),定义4.11 如果函数依赖集合F满足：F中每一个函数依赖的右部都是单属性，即全是X A的形式，其中XU，AU；具体做法：分解成单属性 对F中没有冗余的

39、函数依赖，对任一函数依赖X A，有FXA与F不等价；具体做法：从第一个依赖开始，从F中去掉它（假设该依赖为XA），然后在剩下的依赖中求X+,看X+是否包含A,若是，则去掉XA；若不包含A，则不能去掉XA；这样依次做下去。对F中左边没有冗余属性，对任一函数依赖X A，若Z X，则(FXA)ZA与F不等价。具体做法：一个一个地检查F中左边是非单属性的依赖，例如XZA,现在要判断Z是否为多余的，则以XA代替XZA是否等价？只要在F中求X+,若X+包含A,则Z是多余的属性；否则Z不是多余的属性，依次判断其它属性即可消除各依赖左边的多余属性。则称F为最小函数依赖集，记为Fmin。如果函数依赖集F和G等价

40、，并且 G是最小函数依赖集，那么称G是F的一个最小覆盖。,FD集的最小依赖集举例,例 设F是关系模式R（ABC）的FD集，F=ABC，BC，AB，ABC，试求Fmin。先把F中的FD写成右边是单属性形式：F=AB，AC，BC，AB，ABC 显然多了一个AB，可删去。得F=AB，AC，BC，ABC F中AC可从AB和BC推出，因此AC是冗余的，可删去。得F=AB，BC，ABC F中ABC可从AB和BC推出，因此ABC也可删去。最后得F=AB，BC，即所求的Fmin。注意：每一个FD都有一个Fmin，但是检查F中函数依赖的顺序不同，则Fmin可能不相同，但它们是等价的。,返回,4.3 关系模式的规

41、范化,4.3.1 范式及其类型4.3.2 第一范式(1NF)4.3.3 第二范式(2NF)4.3.4 第三范式(3NF)4.3.5 BC范式(BCNF)4.3.6 多值依赖4.3.7 第四范式(3NF)4.3.8 关系模式规范化步骤,1.关系模式主要有六个范式级别：第一范式(简称1NF)，第二范式(2NF)，第三范式(3NF)，BC范式(BCNF)，第四范式(4NF)和第五范式(5NF)。各范式之间的关系为 1NF2NF3NFBCNF 4NF5NF。2.关系模式的规范化：将一个低级别范式的关系模式，通过模式分解转换为若干个高一级范式的关系模式的过程。,4.3.1 范式及其类型,定义4.12 如

42、果一个关系模式R(U)的所有属性都是不可再分的基本数据项，则称R(U)为第一范式，即R(U)1NF。以上定义中基本数据项的不可再分性，取决于这个属性在实际问题中的重要程度，并由数据库开发人员规定。比如：(a)R1(Sno,Sname,Birthday,Address)()(b)R2(Sno,Sname,Birthday,Privince,City,Street,Number)()(c)R3(Sno,Sname,Birthday,Address(Privince,City,Street,Number)(X),4.3.2 第一范式(1NF),在关系数据库中，所有关系模式必须是第一范式的。第一范式通

43、常存在数据冗余过多、删除异常和插入异常等问题。例4.12 在例4.1中给出的关系模式StudyInfo(Sno，Sname，DeptName,DeptHead,Cname,Grade)就是1NF的。前面已分析过，它存在的问题。,4.3.2 第一范式(1NF),定义4.13 若R(U)1NF，且每一个非主属性完全函数依赖于某个候选键，称R(U)为第二范式，即R(U)2NF。例4.13 我们知道，关系模式StudyInfo(Sno，Sname，DeptName,DeptHead,Cname,Grade)是第一范式。下面将证明，它不是第二范式。,4.3.3 第二范式(2NF),StudyInfo的唯

44、一候选键是Sno,Cname，也其是主键。所以，Sname，DeptName,DeptHead,Grade等都是非主属性。Sno,Cname Sno,Cname,DeptName,DeptHead,Cname,Grade；所以Sno,CnameSname，Sno,CnameDeptName 但根据问题的实际语义有：Sno,Cname Sname，Sno,Cname DeptName,4.3.3 第二范式(2NF),即非主属性Sname和DeptName是部分函数依赖于候选键Sno,Cname。由2NF的定义可知，这里的关系模式StudyInfo不是2NF的。关系模式StudyInfo的以上函数

45、依赖可由下图表示。,4.3.3 第二范式(2NF),从上面例子可发现，关系模式StudyInfo中的非主属性可以分为两种：(1)Grade这样的属性，它对主键是完全函数依赖的。(2)DeptName、DeptHead等对主键是部分函数依赖。按照这种思路把关系模式StudyInfo分解为如下两个关系模式,且都是2NF。StudentDept(Sno,Sname,DeptName,DeptHead)；Reports(Sno,Cname,Grade)；,4.3.3 第二范式(2NF),4.3.3 第二范式(2NF),因此，本章第1节表4.1 关系StudyInfo就分解为表4.8所示的Reports

46、和表4.9所示StudentDept的两个关系.,4.8 关系Reports,4.3.3 第二范式(2NF)(3),分解成2NF模式集算法：设关系模式R(U),主键是W,R上还存在FD XZ,且Z是非主属性和X W,那么 WZ。则应把R分解为两个模式：(1)R1(XZ),主键是X；(2)R2(Y),其中Y=U-Z,主键仍是W,外键是X。如果R1和R2还不是2NF，则重复上述过程，直到每一个关系都是2NF为止。,p,4.3.3 第二范式(2NF),表4.9关系StudentDept,分解以后，数据冗余度已得到改善，但插入异常、删除异常等问题仍然存在。,4.3.4 第三范式(3NF),定义4.14

47、 设关系模式R(U)2NF，且每一个非主属性不传递函数依赖于R(U)的候选键，则称R(U)为第三范式，即R(U)3NF。由定义可知，若R(U)3NF，则关系模式R(U)的每一个非主属性既不部分依赖于候选键也不传递函数依赖于候选键。例4.14 StudentDept(Sno,Sname,DeptName,DeptHead)已是2NF，但不是3NF。因为Sno是唯一候选键，也就是主键，所以有DeptName,DeptHead均是非主属性，因为SnoDeptName且DeptNameDeptHead，即非主属性DeptHead传递函数依赖于候选键Sno。,4.3.4 第三范式(3NF),一个关系模式

48、R(U)若仅是2NF但不是3NF(如关系模式StudentDept)仍然存在有关的异常等问题。解决的办法仍是模式分解。,至此，例4.1给出的关系模式StudyInfo已被分解成如下三个3NF的关系模式，且对应关系StudyInfo也分解成三个关系。Students(Sno,Sname,DeptName)；Reports(Sno,Cname,Grade)；Department(DeptName,DeptHead)。,4.3.4 第三范式(3NF),分解成3NF模式集算法：设关系模式R(U),主键是W,R上还存在FD XZ,且Z是非主属性,X不是候选键,那么 WZ。则应把R分解为两个模式：(1)R

49、1(XZ),主键是X；(2)R2(Y),其中Y=U-Z,主键仍是W,外键是X。如果R1和R2还不是3NF，则重复上述过程，直到每一个关系都是3NF为止。,t,4.3.5 BC范式(BCNF),在3NF模式中，并未排除主属性对候选键的传递依赖和部分函数依赖。如下图所示，因此有必要提出更高一级的范式,BCNF(Boyce Codd Normal Form)由Boyce与Codd提出的，比上述的3NF又有进一步的要求。通常认为BCNF是修正的第三范式，有时也称为第三范式，但它的定义却建立在1NF基础上。,4.3.5 BC范式(BCNF),定义4.15 若关系模式R(U)1NF，对于R(U)的任意一个

50、函数依赖XY，若YX，则X必含有候选键，那么称R(U)为BC范式，即R(U)BCNF等价于：在满足1NF的关系模式R(U)中，若每一个非平凡函数依赖的决定因素都包含有候选键，则R(U)BCNF。定义4.15 若关系模式R(U)1NF，且R(U)的每个属性都不传递依赖于R的候选键，则称R(U)为BC范式，即R(U)BCNF。,4.3.5 BC范式(BCNF),若关系模式R(U)BCNF，则下结论成立。R(U)的所有非主属性都完全函数依赖于每一个候选键，因此R(U)2NF。R(U)的所有主属性都完全函数依赖于不包含它的候选键。R(U)中没有属性完全函数依赖于任何一组非候选键属性。定理4.8 若R(