厦门大学计算机科学系ppt课件市公开课获奖课件省名师优质课赛课一等奖课件.ppt

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,数据库系统原理,厦门大学计算机科学系 林子雨,ziyulin 2017,版,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考!,数据库系统原理,厦门大学计算机科学系 林子雨,ziyulin 2017,版,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,An Introduction to Database System,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考!,数据库系统原理,厦门大学计算机科学系 林子雨,ziyulin 2017,版,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,An Introduction to Database System,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考!,厦门大学计算机科学系,林子雨,厦门大学计算机科学系,E-mail:ziyulin,主页：,关系数据理论（）,厦门大学计算机科学系本科生课程,数据库系统原理,1/182,6.,1 问题提出,6.2,规范化,6.3,数据依赖公理系统,6.4,模式分解,第6章 关系数据理论,2/182,关系数据库逻辑设计,针对详细问题，怎样结构一个适合于它数据模式,数据库逻辑设计工具关系数据库规范化理论,6.1 问题提出,3/182,一、概念回顾,二、关系模式形式化定义,三、什么是数据依赖,四、关系模式简化定义,五、数据依赖对关系模式影响,6.1 问题提出,4/182,关系,：描述实体、属性、实体间联络。,从形式上看，它是一张二维表，是所包括属性笛卡尔积一个子集。,关系模式,：用来定义关系。,关系数据库,：基于关系模型数据库，利用关系来描述现实世界。,从形式上看，它由一组关系组成。,关系数据库模式,：定义这组关系关系模式全体。,6.1 问题提出,概念回顾,5/182,关系模式由五部分组成，即它是一个五元组：,R(U,D,DOM,F),R,：关系名,U,：组成该关系属性名集合,D,：属性组,U,中属性所来自域,DOM,：属性向域映象集合,F,：属性间数据依赖关系集合,6.1 问题提出,关系模式形式化定义,6/182,1.,完整性约束表现形式,限定属性取值范围：比如学生成绩必须在,0-100,之间,定义属性,值,间相互关连（主要表达于值,相等是否,）,这就是数据依赖，它是数据库模式设计关键,2.,数据依赖,是经过一个关系中属性间值相等是否表达出来数据间相互关系,是现实世界属性间相互联络抽象,是数据内在性质,是,语义,表达,3.,数据依赖类型,函数依赖（,Functional Dependency,，简记为,FD,）,多值依赖（,Multivalued Dependency,，简记为,MVD,）,其它,6.1 问题提出,什么是数据依赖,7/182,关系模式,R,（,U,D,DOM,F,）,简化为一个三元组：,R,（,U,F,）,当且仅当,U,上一个关系,r,满足,F,时，,r,称为关系,模式,R,（,U,F,）一个,关系,6.1 问题提出,关系模式简化表示,8/182,例：描述学校数据库：,学生学号（,Sno,）、所在系（,Sdept,）,系主任姓名（,Mname,）、课程名（,Cname,）,成绩（,Grade,）,6.1 问题提出,数据依赖对关系模式影响,Sno,Sdept,Mname,Cname,Grade,单一,关系模式：,Student,U,9/182,学校数据库语义：,一个系有若干学生，一个学生只属于一个系；,一个系只有一名主任；,一个学生能够选修多门课程，每门课程有若干学生选修；,每个学生所学每门课程都有一个成绩。,6.1 问题提出,数据依赖对关系模式影响,U,Sno,Sdept,Mname,Cname,Grade,属性组,U,上一组函数依赖,F,：,F,Sno Sdept,Sdept Mname,(Sno,Cname)Grade,10/182,6.1 问题提出,数据依赖对关系模式影响,Sno,Cname,Sdept,Mname,Grade,11/182,6.1 问题提出,关系模式,Student,中存在问题,学 号,Sno,系主任,Mname,课程名,Cname,成绩,Grade,所 在 系,Sdept,95001,李勇,高数,80,IS,95002,李勇,高数,73,IS,95003,王敏,高数,91,MA,95004,李勇,外语,67,IS,12/182,6.1 问题提出,关系模式,Student,中存在问题,数据冗余太大,浪费大量存放空间,例：每一个系主任姓名重复出现,更新异常（,Update Anomalies,）,数据冗余,，,更新数据时，维护数据完整性代价大。,例：某系更换系主任后，系统必须修改与该系学生相关每一个元组,插入异常（,Insertion Anomalies,）,该插数据插不进去,例，假如一个系刚成立，尚无学生，我们就无法把这个系及其系主任信息存入数据库。,删除异常（,Deletion Anomalies,）,不该删除数据不得不删,例，假如某个系学生全部毕业了，我们在删除该系学生信息同时，把这个系及其系主任信息也丢掉了。,13/182,6.1,问题提出,结论：,Student,关系模式不是一个好模式。,“,好,”,模式：,不会发生插入异常、删除异常、更新异常，,数据冗余应尽可能少。,原因：,由存在于模式中,一些数据依赖,引发,处理方法：,经过,分解,关系模式来消除其中不适当数据依赖。,数据依赖对关系模式影响,14/182,6.,1 问题提出,6.2,规范化,6.3,数据依赖公理系统,6.4,模式分解,第6章 关系数据理论,15/182,6.2,规范化,规范化理论,正是用来改造关系模式，经过分解关系模式来消除其中不适当数据依赖，以处理插入异常、删除异常、更新异常和数据冗余问题。,16/182,6.2.1,函数依赖,一、函数依赖,二、平凡函数依赖与非平凡函数依赖,三、完全函数依赖与部分函数依赖,四、传递函数依赖,17/182,6.2.1,函数依赖,定义,6.,1,设,R(U),是一个属性集,U,上关系模式，,X,和,Y,是,U,子集。,若对于,R(U),任意,一个可能关系,r,，,r,中不可能存在两个元组在,X,上属性值相等，而在,Y,上属性值不等，则称,“,X,函数确定,Y,”,或,“,Y,函数依赖于,X,”,，记作,XY,。,X,称为这个函数依赖,决定属性集,(Determinant),。,Y=f(x),一、函数依赖,18/182,6.2.1,函数依赖,1.函数依赖不是指关系模式R某个或某些关系实例满足约束条件，而是指R全部关系实例均要满足约束条件。,2.函数依赖是语义范畴概念。只能根据数据语义来确定函数依赖。,例如“姓名年龄”这个函数依赖只有在不允许有同名人条件下成立,3.数据库设计者可以对现实世界作强制规定。例如规定不允许同名人出现，函数依赖“姓名年龄”成立。所插入元组必须满足规定函数依赖，若发现有同名人存在，则拒绝装入该元组。,说明：,19/182,例,:Student(Sno,Sname,Ssex,Sage,Sdept),假设不允许重名，则有,:,Sno Ssex,，,Sno Sage,Sno Sdept,，,Sno,Sname,Sname Ssex,，,Sname Sage,Sname Sdept,但,Ssex Sage,若,XY,，而且,YX,则记为,X,Y,。,若,Y,不函数依赖于,X,则记为,XY,。,6.2.1,函数依赖,20/182,6.2.1,函数依赖,在关系模式,R(U),中，对于,U,子集,X,和,Y,，,假如,XY,，但,Y,X,，则称,XY,是,非平凡函数依赖,若,XY,，但,Y,X,则称,XY,是,平凡函数依赖,例：在关系,SC(Sno,Cno,Grade),中，,非平凡函数依赖：,(Sno,Cno),Grade,平凡函数依赖：,(Sno,Cno),Sno,(Sno,Cno)Cno,于任一关系模式，平凡函数依赖都是必定成立，它不反应新语义，所以若不尤其申明，我们总是讨论非平凡函数依赖。,二、,平凡函数依赖与非平凡函数依赖,21/182,6.2.1,函数依赖,定义,6.2,在关系模式,R(U),中，假如,XY,，而且对于,X,任何一个真子集,X,，都有,X,Y,则称,Y,完全函数依赖于,X,，记作,X,Y,。,若,XY,，但,Y,不完全函数依赖于,X,，则称,Y,部分函数依赖,于,X,，记作,X,P,Y,。,三、完全函数依赖与部分函数依赖,例,:,在关系,SC(Sno,Cno,Grade),中，,因为：,Sno Grade,，,Cno Grade,，,所以：,(Sno,Cno),Grade,22/182,6.2.2,码,定义,6.4,设,K,为关系模式,R,中属性或属性组合。若,K,U,，则,K,称为,R,一个,侯选码,（,Candidate Key,）。若关系模式,R,有多个候选码，则选定其中一个做为,主码,（,Primary key,）。,主属性与非主属性,ALL KEY,23/182,6.2.2,码,外部码,定义,6.5,关系模式,R,中属性或属性组,X,并非,R,码，但,X,是另一个关系模式码，则称,X,是,R,外部码（,Foreign key,）,也称外码。,主码又和外部码一起提供了表示关系间联络伎俩。,24/182,6.2.3,范式,范式是符合某一个级别关系模式集合。,关系数据库中关系必须满足一定要求。满足不一样程度要求为不一样范式。,范式种类：,第一范式,(1NF),第二范式,(2NF),第三范式,(3NF),BC,范式,(BCNF),第四范式,(4NF),第五范式,(5NF),25/182,6.2.3,范式,各种范式之间存在联络：,某一关系模式,R,为第,n,范式，可简记为,RnNF,。,26/182,6.2.4 2NF,1NF,定义,假如一个关系模式,R,全部属性都是,不可分基本数据项,，则,R1NF,。,第一范式是对关系模式最起码要求。不满足第一范式数据库模式不能称为关系数据库。,不过满足第一范式关系模式并不一定是一个好关系模式。,27/182,6.2.4 2NF,例,:,关系模式,SLC(Sno,Sdept,Sloc,Cno,Grade),Sloc,为学生住处，假设每个系学生住在同一个地方。,函数依赖包含：,(Sno,Cno),Grade,Sno Sdept,(Sno,Cno)Sdept (,?,),Sno Sloc,(Sno,Cno),Sloc,Sdept Sloc,f,p,p,28/182,6.2.4 2NF,例,:,关系模式,SLC(Sno,Sdept,Sloc,Cno,Grade),Sloc,为学生住处，假设每个系学生住在同一个地方。,函数依赖包含：,(Sno,Cno),Grade,Sno Sdept,(Sno,Cno)Sdept,Sno Sloc,(Sno,Cno),Sloc,Sdept Sloc,f,p,p,29/182,6.2.4 2NF,SLC,码为,(Sno,Cno),SLC,满足第一范式,非主属性,Sdept,和,Sloc,部分函数依赖于码,(Sno,Cno),Sno,Cno,Grade,Sdept,Sloc,SLC,30/182,课堂练习,已知学生关系模式,S(Sno,Sname,SD,Sdname,Course,Grade),其中，,Sno,是学号，,Sname,是姓名，,SD,是系名，,Sdname,是系主任名，,Course,是课程，,Grade,是成绩,（,1,）写出关系模式,S,基本函数依赖和主码；（做本题）,（,2,）原关系模式是第几范式？怎样分解成高一级范式？,（,3,）将关系模式分解成,3NF,，并说明为何？,31/182,6.2.4 2NF,SLC,不是一个好关系模式,(1),插入异常,假设,Sno,95102,，,Sdept,IS,，,Sloc,N,学生还未选课，因课程号是主属性，所以该学生信息无法插入,SLC,。,(2),删除异常,假定某个学生原来只选修了,3,号课程这一门课。现在因身体不适，他连,3,号课程也不选修了。因课程号是主属性，此操作将造成该学生信息整个元组都要删除。,SLC(Sno,Sdept,Sloc,Cno,Grade),32/182,6.2.4 2NF,(3),数据冗余度大,假如一个学生选修了,10,门课程，那么他,Sdept,和,Sloc,值就要重复存放了,10,次。,(4),修改复杂,比如学生转系，在修改此学生元组,Sdept,值同时，还可能需要修改住处（,Sloc,）。假如这个学生选修了,K,门课，则必须无遗漏地修改,K,个元组中全部,Sdept,、,Sloc,信息。,SLC(Sno,Sdept,Sloc,Cno,Grade),33/182,6.2.4 2NF,原因,Sdept,、,Sloc,部分函数依赖于码。,处理方法,SLC,分解为两个关系模式，以消除这些部分函数依赖,SC,（,Sno,，,Cno,，,Grade,）,SL,（,Sno,，,Sdept,，,Sloc,）,34/182,6.2.4 2NF,函数依赖图,：,Sno,Cno,Grade,SC,SL,Sno,Sdept,Sloc,1NF,2NF,35/182,6.2.4 2NF,采取投影分解法将一个,1NF,关系分解为多个,2NF,关系，能够在一定程度上减轻原,1NF,关系中存在插入异常、删除异常、数据冗余度大、修改复杂等问题。,将一个,1NF,关系分解为多个,2NF,关系，并不能完全消除关系模式中各种异常情况和数据冗余。,36/182,6.2.4 2NF,2NF,定义,定义,6.6,若关系模式,R1NF,，而且每一个,非主,属性都,完全,函数依赖于,R,码，则,R2NF,。,例：,SLC(Sno,Sdept,Sloc,Cno,Grade)1NF,SLC(Sno,Sdept,Sloc,Cno,Grade)2NF,SC,（,Sno,，,Cno,，,Grade,）,2NF,SL,（,Sno,，,Sdept,，,Sloc,）,2NF,Sno,Cno,Grade,SC,37/182,课堂练习,已知学生关系模式,S(Sno,Sname,SD,Sdname,Course,Grade),其中，,Sno,是学号，,Sname,是姓名，,SD,是系名，,Sdname,是系主任名，,Course,是课程，,Grade,是成绩,（,1,）写出关系模式,S,基本函数依赖和主码；,（,2,）原关系模式是第几范式？怎样分解成高一级范式？（做本题）,（,3,）将关系模式分解成,3NF,，并说明为何？,38/182,6.2.4 2NF,定义,6.3,在关系模式,R(U),中，假如,XY,，,YZ,，且,Y,X,，,YX,，则称,Z,传递函数依赖,于,X,。,注,:,假如,YX,，即,XY,，则,Z,直接依赖,于,X,。,例,:,在关系,Std(Sno,Sdept,Mname),中，有：,Sno Sdept,，,Sdept Mname,Mname,传递函数依赖于,Sno,四、传递函数依赖,39/182,6.2.5 3NF,例：,2NF,关系模式,SL(Sno,Sdept,Sloc),中,函数依赖：,SnoSdept,SdeptSloc,SnoSloc,Sloc,传递函数依赖于,Sno,，即,SL,中存在非主属性对码传递函数依赖。,SL,Sno,Sdept,Sloc,40/182,6.2.5 3NF,处理方法,采取投影分解法，把,SL,分解为两个关系模式，以消除传递函数依赖：,SD,（,Sno,，,Sdept,）,DL,（,Sdept,，,Sloc,）,SD,码为,Sno,，,DL,码为,Sdept,。,41/182,6.2.5 3NF,SD,码为,Sno,，,DL,码为,Sdept,。,Sno,Sdept,SD,Sdept,Sloc,DL,2NF,3NF,42/182,6.2.5 3NF,3NF,定义,定义,6.8,关系模式,R,中若不存在这么码,X,、属性组,Y,及,非主属性,Z,（,Z,Y,）,使得,X,Y,，,Y,X,，,Y,Z,，成立，则称,R,3NF,。,例，,SL(Sno,Sdept,Sloc)2NF,SL(Sno,Sdept,Sloc)3NF,SD,（,Sno,，,Sdept,）,3NF,DL,（,Sdept,，,Sloc,）,3NF,43/182,6.2.5 3NF,若,R3NF,，则,R,每一个,非主属性,既不部分函数依赖于候选码也不传递函数依赖于候选码。,假如,R3NF,，则,R,也是,2NF,。,采取投影分解法将一个,2NF,关系分解为多个,3NF,关系，能够在一定程度上处理原,2NF,关系中存在插入异常、删除异常、数据冗余度大、修改复杂等问题。,将一个,2NF,关系分解为多个,3NF,关系后，并不能完全消除关系模式中各种异常情况和数据冗余。,44/182,课堂练习,已知学生关系模式,S(Sno,Sname,SD,Sdname,Course,Grade),其中，,Sno,是学号，,Sname,是姓名，,SD,是系名，,Sdname,是系主任名，,Course,是课程，,Grade,是成绩,（,1,）写出关系模式,S,基本函数依赖和主码；,（,2,）原关系模式是第几范式？怎样分解成高一级范式？,（,3,）将关系模式分解成,3NF,，并说明为何？（做本题）,45/182,6.2.6 BCNF,定义,6.9,设关系模式,R,1NF,，假如对于,R,每个函数依赖,XY,，若,Y,不属于,X,，则,X,必含有码，那么,RBCNF,。,若,RBCNF,每一个决定属性集（原因）都包含（候选）码,R,中全部属性（主，非 主属性）都完全函数依赖于码,没有任何属性完全函数依赖于非码任何一组属性,R3NF(,?,),若,R3NF,则,R,不一定,BCNF,即在第三范式基础上，数据库表中不存在任何属性对任一候选码传递函数依赖和部分函数依赖,46/182,6.2.6 BCNF,证实题：,若关系模式,R,BCNF,，则,R,2NF,。,47/182,6.2.6 BCNF,例子：关系模式,C(Cno,Cname,Pcno),，它只有一个码,Cno,，这里没有任何属性对,Cno,部分依赖或传递依赖，所以，,C,3NF,同时，,C,中,Cno,是唯一决定原因，,C,同时又是码，依据定义，,C,BCNF,48/182,6.2.6 BCNF,例子：关系模式,SJP,（,S,J,P,）中，,S,是学生，,J,表示课程，,P,表示名次，每一个学生选修每门课程成绩有一定名次，每门课程中每一名次只有一个学生（即没有并列名次），能够得到以下依赖：,（,S,，,J,）,P;(J,P),S,所以,(S,J),和,(J,P),都能够作为候选码，这个关系模式中没有属性对码传递依赖或部分依赖，所以，,SJP,3NF,，而且除,(S,J),和,(J,P),以外没有其它决定原因，所以,SJP,BCNF,49/182,6.2.6 BCNF,例：在关系模式,STJ,（,S,，,T,，,J,）中，,S,表示学生，,T,表示教师，,J,表示课程。,每一教师只教一门课。每门课由若干教师教，某一学生选定某门课，就确定了一个固定教师。某个学生选修某个教师课就确定了所选课名称：,TJ,，,(S,，,J)T,，,(S,，,T)J,50/182,6.2.6 BCNF,S,J,T,S,T,J,STJ,51/182,6.2.6 BCNF,STJ3NF,(S,，,J),和,(S,，,T),都能够作为候选码,S,、,T,、,J,都是主属性,STJBCNF,TJ,，,T,是决定属性集，,T,不是候选码,52/182,6.2.6 BCNF,处理方法：将,STJ,分解为二个关系模式：,SJ(,S,，,J,)BCNF,，,TJ(,T,，,J)BCNF,没有,任何属性,对码部分函数依赖和传递函数依赖,S,J,ST,T,J,TJ,53/182,课堂作业,有一个配件管理表,WPE(WNO,PNO,ENO,QNT),，其中，,WNO,表示仓库号，,PNO,表示配件号，,ENO,表示职员号，,QNT,表示数量。有以下约束要求：,（,1,）一个仓库有多名职员,（,2,）一个职员仅在一个仓库工作,（,3,）每个仓库里一个型号配件由一个职员负责，但一个人能够管理几个配件；,（,4,）同一个型号配件能够分别放在几个仓库中,（,5,）一个仓库存放某种配件数量是一定,（,6,）一个职员管理某种配件数量是一定,问题,：,（,1,）请写出表中函数依赖关系,（,2,）判断该表是否是,3NF,？,（,3,）判断该表是否是,BCNF,？,54/182,课堂作业答案,函数依赖关系：,ENO,WNO,(WNO,PNO)QNT,(WNO,PNO)ENO,(ENO,PNO)QNT,55/182,课堂作业答案,候选码包含：,(WNO,PNO),和,(ENO,PNO),ENO,PNO,WNO,都是主属性，,QNT,是非主属性,全部非主属性都是直接依赖于候选码，所以是,3NF,关于主属性：,(WNO,PNO)ENO,；,ENO,WNO,，得到传递依赖,(WNO,PNO)WNO,，所以不是,BCNF,56/182,课堂作业答案,能够继续分拆成两个表,管理表,EP,（,ENO,PNO,QNT,）,工作表,EW,（,ENO,WNO,）,两个表属于,BCNF,57/182,多值依赖与第四范式（,4NF,）,例,:,学校中某一门课程由多个教师讲授，他们使用相同一套参考书。每个教师能够讲多门课程，每种参考书可供多门课使用。,关系模式,Teaching(C,T,B),课程,C,、教师,T,和 参考书,B,58/182,表,6.1,59/182,普通物理学,光学原理,物理习题集,普通物理学,光学原理,物理习题集,数学分析,微分方程,高等代数,数学分析,微分方程,高等代数,李 勇,李 勇,李 勇,王 军,王 军,王 军,李 勇,李 勇,李 勇,张 平,张 平,张 平,物 理,物 理,物 理,物 理,物 理,物 理,数 学,数 学,数 学,数 学,数 学,数 学,参考书,B,教员,T,课程,C,用二维表表示,Teaching,60/182,多值依赖与第四范式（续）,TeachingBCNF:,Teach,含有唯一候选码,(C,，,T,，,B),，即全码,Teaching,模式中存在问题,(1),数据冗余度大：有多少名任课教师，参考书就要存放多少次,(2),插入操作复杂：当某一课程增加一名任课教师时，该课程有多少本参考书，就必须插入多少个元组,比如物理课增加一名教师刘关，需要插入两个元组：,（物理，刘关，普通物理学）,（物理，刘关，光学原理）,61/182,多值依赖与第四范式（续）,(3),删除操作复杂：某一门课要去掉一本参考书，该课程有多少名教师，就必须删除多少个元组,(4),修改操作复杂：某一门课要修改一本参考书，该课程有多少名教师，就必须修改多少个元组,产生原因,存在多值依赖,62/182,6.2.7,多值依赖,定义,6.10,设,R(U),是一个属性集,U,上一个关系模式，,X,、,Y,和,Z,是,U,子集，而且,Z,U,X,Y,，,多值依赖,XY,成立当且仅当对,R,任一关系,r,，,r,在（,X,，,Z,）上每个值对应一组,Y,值，这组值仅仅决定于,X,值而与,Z,值无关,例,Teaching,（,C,T,B,）,对于,C,每一个值，,B,有一组值与之对应，而不论,T,取何值,63/182,6.2.7,多值依赖,在,R,（,U,）任一关系,r,中，假如存在元组,t,，,s,使得,t,X,=,s,X,，那么就必定存在元组,w,，,v,r,，（,w,，,v,能够与,s,，,t,相同），使得,w,X,=,v,X,=,t,X,，而,w,Y,=,t,Y,，,w,Z,=,s,Z,，,v,Y,=,s,Y,，,v,Z,=,t,Z,（即交换,s,，,t,元组,Y,值所得两个新元组必在,r,中），则,Y,多值依赖于,X,，记为,X,Y,。这里，,X,，,Y,是,U,子集，,Z,=,U-X,-,Y,。,64/182,6.2.7,多值依赖,t x y1 z2,s x y2 z1,w x y1 z1,v x y2 z2,X,Y,Z,65/182,6.2.7,多值依赖,平凡多值依赖和非平凡多值依赖,若,XY,，而,Z,，则称,XY,为,平凡多值依赖,不然称,XY,为,非平凡多值依赖,66/182,6.2.8 4NF,定义,6.10,关系模式,R1NF,，假如对于,R,每个非平凡多值依赖,XY,（,Y,X,），,X,都含有候选码，则,R4NF,。,假如,R 4NF,，则,R BCNF,不允许,有非平凡且非函数依赖,多值依赖,允许,是,函数依赖,（是非平凡多值依赖）,67/182,6.2.8 4NF,例：,Teach(C,T,B)4NF,存在非平凡多值依赖,CT,，且,C,不是候选码,用投影分解法把,Teach,分解为以下两个关系模式：,CT(C,T)4NF,CB(C,B)4NF,CT,，,CB,是平凡多值依赖,68/182,6.2.9,规范化,关系数据库规范化理论是数据库逻辑设计工具。,一个关系只要其分量都是不可分数据项，它就是规范化关系，但这只是最基本规范化。,规范化程度能够有多个不一样级别,69/182,6.2.9,规范化,规范化程度过低关系不一定能够很好地描述现实世界，可能会存在插入异常、删除异常、修改复杂、数据冗余等问题,一个低一级范式关系模式，经过模式分解能够转换为若干个高一级范式关系模式集合，这种过程就叫,关系模式规范化,70/182,6.2.9,规范化,关系模式规范化基本步骤,1NF,消除非主属性对码部分函数依赖,消除决定属性,2NF,集非码非平 消除非主属性对码传递函数依赖,凡函数依赖,3NF,消除主属性对码部分和传递函数依赖,BCNF,消除非平凡且非函数依赖多值依赖,4NF,71/182,6.2.9,规范化,消除不适当数据依赖,将各关系模式到达某种程度,“,分离,”,采取,“,一事一地,”,模式设计标准,让一个关系描述一个概念、一个实体或者实体间一个联络。若多于一个概念就把它,“,分离,”,出去,所谓规范化实质上是概念单一化,不能一味追求规范化程度高,规范化基本思想,72/182,6.2.9,规范化,在设计数据库模式结构时，必须对现实世界实际情况和用户应用需求作深入分析，确定一个适当、能够反应现实世界模式,上面规范化步骤能够在其中任何一步终止,73/182,第六章 关系数据理论,6.1,数据依赖,6.2,规范化,6.3,数据依赖公理系统,6.4,模式分解,74/182,6.3,数据依赖公理系统,逻辑蕴含,定义,6.11,对于满足一组,函数依赖,F,关系模式,R,，函数依赖,XY,都成立,即,r,中任意两元组,t,s,，若,tX=sX,，则,tY=sY,，则称,F,逻辑蕴含,X Y,75/182,Armstrong,公理系统,一套推理规则，是模式分解算法理论基础,用途,求给定关系模式码,从一组函数依赖求得蕴含函数依赖,76/182,1.Armstrong,公理系统,关系模式,R,来说有以下推理规则：,A1.,自反律,（,Reflexivity,）：若,Y,X,U,，则,X,Y,为,F,所蕴含。,A2.,增广律（,Augmentation,）：若,XY,为,F,所蕴含，且,Z,U,，则,XZYZ,为,F,所蕴含。,A3.,传递律,（,Transitivity,）：若,X,Y,及,Y,Z,为,F,所蕴含，则,X,Z,为,F,所蕴含。,77/182,定理,6.l Armstrong,推理规则是正确,（,1,）自反律,:,若,Y,X,U,，则,X,Y,为,F,所蕴含,证,:,设,Y,X,U,对,R,任一关系,r,中任意两个元组,t,，,s,：,若,t,X,=,s,X,，因为,Y,X,，有,t,Y,=,s,Y,，,所以,X,Y,成立,.,自反律得证,定理,6.l Armstrong,推理规则是正确,78/182,定理,6.l,(2),增广律,:,若,X,Y,为,F,所蕴含，且,Z,U,，则,X,Z,YZ,为,F,所蕴含。,证：,设,X,Y,为,F,所蕴含，且,Z,U,。,设,R,任一关系,r,中任意两个元组,t,，,s,；,若,t,XZ,=,s,XZ,，则有,t,X,=,s,X,和,t,Z,=,s,Z,；,由,X,Y,，于是有,t,Y,=,s,Y,，所以,t,YZ,=,s,YZ,，所以,XZ,YZ,为,F,所蕴含,.,增广律得证。,79/182,定理,6.l,(3),传递律：若,X,Y,及,Y,Z,为,F,所蕴含，则,X,Z,为,F,所蕴含。,证：,设,X,Y,及,Y,Z,为,F,所蕴含。,对,R,任一关系,r,中任意两个元组,t,，,s,。,若,t,X,=,s,X,，因为,X,Y,，有,t,Y,=,s,Y,；,再由,Y,Z,，当,t,Y,=,s,Y,时，一定有,t,Z,=,s,Z,所以,X,Z,为,F,所蕴含,.,传递律得证。,80/182,2.,导出规则,1.,依据,A1,，,A2,，,A3,这三条推理规则能够得到下面三条推理规则：,合并规则,：由,X,Y,，,X,Z,，有,X,YZ,。,（,A2,，,A3,）,伪传递规则,：由,X,Y,，,WY,Z,，有,XW,Z,。,（,A2,，,A3,）,分解规则,：由,X,Y,及,Z,Y,，有,X,Z,。,（,A1,，,A3,）,81/182,导出规则,2.,依据合并规则和分解规则，可得引理,6.1,引理,6.l,X,A,1,A,2,A,k,成立充分必要条件是,X,A,i,成立（,i,=l,，,2,，,，,k,）。,82/182,3.,函数依赖闭包,定义,6.12,在关系模式,R,中为,F,所逻辑蕴含函数依赖全体叫作,F,闭包,，记为,F,+,。,83/182,3.函数依赖闭包,人们把自反律、传递律和增广律称为Armstrong公理系统,84/182,Armstrong公理系统,有效性,：由,F,出发依据,Armstrong,公理推导出来每一个函数依赖一定在,F,+,中,/*Armstrong,正确,完备性,：,F,+,中每一个函数依赖，必定能够由,F,出发依据,Armstrong,公理推导出来,/*Armstrong,公理够用，完全,85/182,Armstrong公理系统,要证实完备性，就首先要处理怎样判定一个函数依赖是否属于由F依据Armstrong公理系统推导出来函数依赖集合,假如能够求出这个集合，问题就处理了,不过，这个是一个NP完全问题,86/182,F,闭包,F,+,计算是,NP,完全问题，,X A1A2.An,F,+,=,X ,Y ,Z ,XY ,XZ ,YZ ,XYZ ,X X,Y Y,Z Z,XY X,XZ X,YZ Y,XYZ X,X Y,Y Z,XY Y,XZ Y,YZ Z,XYZ Y,X Z,Y YZ,XY Z,XZ Z,YZ YZ,XYZ Z,X XY,XY XY,XZ XY,XYZ XY,X XZ,XY YZ,XZ XZ,XYZ YZ,X YZ,XY XZ,XZ XY,XYZ XZ,X ZYZ,XY XYZ,XZ XYZ,XYZ XYZ,F,=X Y,Y Z,87/182,3.,函数依赖闭包,定义,6.13,设,F,为属性集,U,上一组函数依赖，,X,U,，,X,F,+,=,AX,A,能由,F,依据,Armstrong,公理导出,，,X,F,+,称为属性集,X,关于函数依赖集,F,闭包,为了证实,Armstrong,公理系统完备性，需要引入以下概念：,88/182,关于闭包引理,引理,6.2,设,F,为属性集,U,上一组函数依赖，,X,，,Y,U,，,X,Y,能由,F,依据,Armstrong,公理导出充分必要条件是,Y,X,F,+,用途,将判定,X,Y,是否能由,F,依据,Armstrong,公理导出问题，就转化为求出,X,F,+,，判定,Y,是否为,X,F,+,子集问题（不再是,NP,完全问题）,依据引理,6.1,能够深入得到：,89/182,U=A,B,C,D;F=A B,BC D;,A,+,=,C,+,=,(AC),+,=,实例,AB.,C.,ABCD,90/182,求闭包算法,算法,6.l,求属性集,X,（,X,U,）关于,U,上函数依赖集,F,闭包,X,F,+,输入：,X,，,F,输出：,X,F,+,步骤：,91/182,算法,6.l,（,1,）令,X,（,0,）,=,X,，,i,=0,（,2,）求,B,，这里,B,=,A,|(,V)(,W,)(,V,W,F,V,X,（,i,）,A,W),；,（,3,）,X,（,i+1,）,=,B,X,（,i,）,（,4,）判断,X,（,i+1,）,=,X,（,i,）,吗,?,（,5,）若相等或,X,（,i,）,=,U,则,X,（,i,）,就是,X,F,+,算法终止。,（,6,）若否，则,i,=,i,+l,，返回第（,2,）步。,92/182,算法,6.l,对于算法,6.l,，令,a,i,=|,X,（,i,）,|,，,a,i,形成一个步长大于,1,严格递增序列，序列上界是,|,U,|,，所以该算法最多,|,U,|-,|X,|,次循环就会终止。,93/182,函数依赖闭包,例,1,已知关系模式,R,，其中,U,=,A,，,B,，,C,，,D,，,E,；,F,=,AB,C,，,B,D,，,C,E,，,EC,B,，,AC,B,。,求（,AB,）,F,+,。,解 设,X,（,0,）,=,AB,；,(1),计算,X,（,1,）,:,逐一扫描,F,集合中各个函数依赖，,找左部为,A,，,B,或,AB,函数依赖。,得到两个：,AB,C,，,B,D,。,于是,X,（,1,）,=,AB,CD,=,ABCD,。,94/182,函数依赖闭包,(2),因为,X,（,0,）,X,（,1,）,，所以再找出左部为,ABCD,子集那些函数依赖，又得到,AB,C,，,B,D,，,C,E,，,AC,B,，,于是,X,（,2,）,=,X,（,1,）,BCDE,=,ABCDE,。,(3),因为,X,（,2,）,=U,，算法终止,所以（,AB,）,F,+,=,ABCDE,。,95/182,课堂练习,例：设相关系模式,R(U,F),，其中,U=A,B,C,D,E,I,F=A,D,AB,E,BI,E,CD,I,E,C,请计算,（,AE,）,F,+,96/182,4.Armstrong,公理系统有效性与完备性,建立公理系统体系,目标,：从已知,f,推导出未知,f,明确：,1.,公理系统推导出来,f,正确？,2.,F,+,中每一个,f,都能推导出来？,f,不能由,F,导出,f,F,+,F,+,f,F,97/182,4.Armstrong,公理系统有效性与完备性,有效性,：由,F,出发依据,Armstrong,公理推导出来每一个函数依赖一定在,F,+,中,/*Armstrong,正确,完备性,：,F,+,中每一个函数依赖，必定能够由,F,出发依据,Armstrong,公理推导出来,/*Armstrong,公理够用，完全,完备性,：全部不能用,Armstrong,公理推导出来,f,都不为真,若,f,不能用,Armstrong,公理推导出来，,f,F,+,98/182,有效性与完备性证实,证实：,有效性,依据定理,6.1,能够得证,定理,6.l Armstrong,推理规则是正确,Armstrong,公理系统推理规则,关系模式,R,来说有以下推理规则：,A1.,自反律,（,Reflexivity,）：若,Y,X,U,，则,X,Y,为,F,所蕴含。,A2