第5章 关系数据库规范化理论

書式設定, 書式設定,第 2 ,第 3 ,第 4 ,第 5 ,*,软件学院自评报告,软件学院自评报告,第五章,关系数据库规范化理论,1,5.1,关系规范化的必要性,5.2,函数依赖,5.3,范式,5.4,关系模式的规范化,第五章 关系数据库规范化理论,2,5.1,关系规范化的必要性,每个关系由哪些属性组成？,1.,关系数据库逻辑设计问题,构造几个关系？,关系数据库,关系,属性,3,5.1,关系规范化的必要性,例：教学管理系统，需要存储下列信息,学号,姓名,系名,系主任名,课程名,成绩,Sno, Sname, Sdept, Mname, Cname, Score,设计一个关系模式：,SLC=Sno,Sname,Sdept,Mname,Cname,Score,4,5.1,关系规范化的必要性,SLC,中的样本数据,Sno,Sname,Sdept,Mname,Cname,Score,02001,王飞,电子系,赵千,数字电路,98,02001,王飞,电子系,赵千,模拟电路,87,02001,王飞,电子系,赵千,高等数学,82,02002,李力,电子系,赵千,数字电路,82,02002,李力,电子系,赵千,模拟电路,71,02002,李力,电子系,赵千,高等数学,64,02003,刘强,计科系,王杰,C+,语言,93,02003,刘强,计科系,王杰,操作系统,87,02003,刘强,计科系,王杰,编译原理,76,02004,孙一,数学系,宋扬,高等数学,83,5,5.1,关系规范化的必要性,该关系模式存在四个主要问题：,（,1,）数据冗余度大,浪费空间，产生数据的不一致性,（,2,）插入异常,（,3,）删除异常,（,4,）更新异常,6,5.1,关系规范化的必要性,思考,：为什么会产生上述,问题,？,与数据间的依赖有关,关于分离度,高,低,：查询效率低，信息丢失,：会产生四个问题,解决方法：,关系分解，实现信息的某种程度上的分离,S,（,Sno,Sname,Sdept,）,D,（,Sdept,Mname,）,SC,（,Sno,Cname,Score,）,解决问题，说明是一个,好的关系数据库模式,。,P113,7,5.1,关系规范化的必要性,2.,规范化理论研究的内容,（,1,）函数依赖,核心,模式分解和设计的基础,（,2,）范式,模式分解的标准,（,3,）模式设计,8,数据依赖,函数依赖,键的形式化定义,候选键的求解理论和算法,5.2,函数依赖,9,5.2.1,数据依赖,关系模式回顾,R,（,U, D, DOM, F,）,F,：属性,U,上数据的依赖关系集合,记作：,R(U,，,F),10,5.2.1,数据依赖,定义,5.1,数据依赖,是通过一个关系中属性间值的相等与否,体现出来的数据间的相互关系，是现实世界属性间,相互联系的抽象，是数据内在的性质，是语义的体现。,数据依赖共有三种：,（,1,）函数依赖（,Functional Dependency,，,FD,）,（,2,）多值依赖（,Multivalued Dependency,，,MVD,）,（,3,）连接依赖（,Join Dependency,，,JD,）,11,5.2.2,函数依赖,定义,5.2,函数依赖,设,R(U),是一个关系模式，,U,是,R,的属性集合。,X,Y,为,U,的子集。,如果,R(U),的所有关系,r,都存在着：,对于,X,的每一个值，,Y,都有唯一值与之对应，,则称,X,函数决定,Y,或,Y,函数依赖于,X,。,记作,XY,。其中,X,叫作决定属性集，,Y,叫作被决定属性集。,若,Y,不函数依赖于,X,，记作：,X,Y,。,若,XY,，,YX,，记作：,X Y,注：,函数依赖是属性间的一种联系,12,5.2.2,函数依赖,设有关系模式,SLC1(SNo,SName,SDept,MName,SLoc,CName,Score),U = SNo,SName,SDept,MName,SLoc,CName,Score, 根据学号可以确定学生的姓名；, 一个系有若干学生，但一个学生只属于一个系；, 一个系只有一名主任；, 根据学生所在的系可以确定学生的住处；, 一个学生可以选修多门课程，每门课程有若干学生选修；, 每个学生所学的每门课程都有一个成绩。,根据如下描述写出依赖关系：,SNoSName,SNoSDept,SDeptMName,SDeptSLoc,(SNo,CName)Score,F=SNoSName, SNoSDept, SDeptMName, SDeptSLoc,(SNo,CName)Score,13,5.2.2,函数依赖,注意：,P115,（,1,）属性间的函数依赖 指,R,的一切关系子集都要满足定义中的限定；,（,2,）函数依赖 是语义范畴的概念；,（,3,）数据库设计者可以对现实世界做强制的规定。,14,5.2.2,函数依赖,定义,5.3,平凡函数依赖与非平凡函数依赖,在关系模式,R(U,F),中，对于,U,的子集,X,、,Y,，,如果,XY,但,Y X,，则称,XY,是非平凡函数依赖；,如果,Y X,，则称,XY,是平凡函数依赖。,若不特别声明，本书中讨论的是,非平凡函数依赖,。,例,：（,SNo,CName,）,Score,Score,SNo,CName,（,SNo,CName,）,CName,CName,SNo,CName,非平凡函数依赖,平凡函数依赖,15,5.2.2,函数依赖,定义,5.4,完全,/,部分函数依赖,在,R(U,F),中,如果,XY,，对于,X,的任一真子集,X,，都有,X,Y,则称,Y,对,X,完全函数依赖,记为,否则,称,Y,对,X,是部分函数依赖,记作,例,：（,SNo,CName,）,SName,SNoSName,(SNo,CName)Score,SnoScore,CnameScore,16,5.2.2,函数依赖,定义,5.5,传递函数依赖,在,R(U,F),中,如果,XY,，,Y,Z,且,Y X,Z Y,Y,X,则称,Z,对,X,是传递函数依赖,记为,若有,YX,则,X Y,那么,例,：,SNoSDept,SDeptMName,17,5.2.3,键的形式化定义,定义,5.6,设,K,是关系模式,R(U,F),中的属性或属性组。若,则,K,为,R,的,候选键,（,Candidate Key,），简称为,键,。,定义,5.7,主键,定义,5.8,主属性,定义,5.9,非主属性,定义,5.10,单键,定义,5.11,全键,例,： （演奏者，作品，听众）,定义,5.12,外键,R,（,A,，,B,，,C,，,F,）,S,（,Ks,，,D,，,E,）,R,的外键,参照关系,被参照关系,18,5.2.4,候选键的求解理论和算法,思考：,学生关系模式,S,（,Sno,Sname,Sdept,），已知：, 根据学号可以确定学生的姓名；, 一个系有若干学生，但一个学生只属于一个系；,若用,S(U,F),描述这个关系模式，,U=?,，,F=?,U = ,Sno,Sname,Sdept,F = ,SNoSName,SNoSDept,它的候选键是什么？,19,5.2.4,候选键的求解理论和算法,思考：设有关系模式,R(A,B,C,D),其函数依赖集,F=DB,BD,ADB,ACD,求,R,的所有候选键。,20,5.2.4,候选键的求解理论和算法,定义,5.13,闭包,(Closure),对于给定的关系模式,R(U,F),，,F,的闭包是由,F,所逻辑蕴含的所有的函数依赖的集合，,记作,。,例：,U=A,B,C,D,F=DB,BD,ADB,ACD,= ,A,C,D,B,=,D,B,注意：,若,K,为候选键，则,21,5.2.4,候选键的求解理论和算法,思考：设有关系模式,R(A,B,C,D),其函数依赖集,F=DB,BD,ADB,ACD,求,R,的所有候选键。,=,D,B,= B, D ,= A ,= C ,= A, B, D ,= A, C, D, B ,= A, D, B ,CK,：,AC,22,5.2.4,候选键的求解理论和算法,对于给定的关系模式,R(U),和函数依赖集,F,，可将其属性分为,4,类：,L,类 仅出现在的函数依赖,左部,的属性；,R,类 仅出现在的函数依赖,右部,的属性；,N,类 在的函数依赖,左右两边均未出现,的属性；,LR,类 在的函数依赖,左右两边均出现,的属性。,23,5.2.4,候选键的求解理论和算法,定理,5.1,对于给定的关系模式,R(U),及其函数依赖集,F,，,若,X(X,R),是,L,类属性，则,X,必为,R,的任一侯选键的成员,。,推论,5.1,对于给定的关系模式,R(U),及其函数依赖集,F,，,若,X(X,R),是,L,类属性，且,包含了,R,的全部属性,，,则,X,必为,R,的的唯一侯选键,。,24,5.2.4,候选键的求解理论和算法,【,例,5.1】,：设有关系模式,R(A,B,C,D),其函数依赖集,F=DB,BD,ADB,ACD,求,R,的所有候选键。,L,：,解：,A, C,R,：,none,N,：,none,LR,：,B, D,= A, C, D, B ,CK,：,AC,= U,25,5.2.4,候选键的求解理论和算法,定理,5.2,对于给定的关系模式,R(U),及其函数依赖集,F,，,若,X(X,R),是,R,类属性，则,X,不在任何侯选键中,。,定理,5.3,对于给定的关系模式,R(U),及其函数依赖集,F,，,若,X(X,R),是,N,类属性，则,X,必为,R,的任一侯选键的成员,。,推论,5.2,对于给定的关系模式,R(U),及其函数依赖集,F,，,若,X,是,N,类和,L,类,组成的属性集，且,包含了,R,的全部属性,，,则,X,必为,R,的的唯一侯选键,。,26,5.2.4,候选键的求解理论和算法,【,例,5.2】,：设有关系模式,R(A,B,C,D,E,P),其函数依赖集,F=AD,ED,DB,BCD,DCA,求,R,的所有候选键。,L,：,解：,C, E,R,：,none,N,：,P,LR,：,A, B, D,CK,：,CEP,= ,C,E,P,D,B,= U,A,27,5.2.4,候选键的求解理论和算法,【,练习,1】,：设有关系模式,R(A,B,C,D,E,P),其函数依赖集,F=AB,CP,EA,CED,求,R,的所有候选键。,L,：,解：,C, E,R,：,P, D, B,N,：,none,LR,：,A,CK,：,CE,= ,C,E,P,A,B,= U,D,28,5.2.4,候选键的求解理论和算法,【,练习,2】,：设有关系模式,R(A,B,C),其函数依赖集,F=ABC,CA,求,R,的所有候选键。,L,：,解：,B,R,：,none,N,：,none,LR,：,A, C,CK,：,AB, BC,=,B, U,= ,A,B,C,= U,= ,B,C,A,= U,29,5.2.4,候选键的求解理论和算法,【,练习,3】,：设有关系模式,R(A,B,C,D,E),其函数依赖集,F=ABC,CDE,BD,EA,求,R,的所有候选键。,L,：,解：,none,N,：,none,LR,：,A, B, C, D, E,= ,B,R,：,none,= ,A,B,C,= U,D,E,D,= C ,= D ,= ,E,A,B,= U,C,D,= ,B,C,D,= U,E,A,= ,B,D,= ,C,D,E,A,B,= U,CK,：,A, E, BC, CD,30,回顾,规范化理论研究的内容,（,1,）函数依赖,核心,模式分解和设计的基础,（,2,）范式,模式分解的标准,（,3,）模式设计,31,5.3,范式,范式定义,第一范式（,1NF,）,第二范式（,2NF,）,第三范式（,3NF,）,改进的,3NF,（,BCNF,）,多值依赖与第四范式（,4NF,）,32,5.3.1,范式的定义,范式（,NF,）,是符合某一种级别的关系模式的集合。,满足不同程度要求的为不同范式。,范式的概念最早由,E.F.Codd,提出：,1971,年,1NF,，,2NF,，,3NF,1974,年,BCNF,1976,年,4NF,，,5NF,5NF,3NF,BCNF,2NF,4NF,1NF,若,R(U,F),符合,x,范式的要求，则称,R,为,x,范式，记作：,RxNF,33,5.3.2,第一范式（,1NF,）,定义,5.14,第一范式（,1NF,）,如果一个关系模式,R(U,F),的所有属性都是,不可分的,基本数据项,，则,R1NF,。,例：,SLC2(SNo,SDept,SLoc,CName,Score),满足,1NF,的数据库模式不一定是一个,好的,关系模式；,不满足,1NF,的数据库模式不能称为关系数据库模式,。,1NF,34,5.3.3,第二范式（,2NF,）,定义,5.15,第二范式（,2NF,）,满足第一范式的关系模式,R(U,F),，如果所有的,非主属性,都,完全依赖,于,键,，,则称,R,属于第二范式,记为,R(U,F),2NF.,例：,SLC2(SNo,SDept,SLoc,CName,Score)1NF,(,SNo,CName)SDept,SnoSDept,SLC2(SNo,SDept,SLoc,CName,Score)2NF,35,5.3.3,第二范式（,2NF,）,例：,SLC2(SNo,SDept,SLoc,CName,Score)1NF,SC2(SNo,CName,Score),2NF,SL2(SNo,SDept,SLoc),2NF,(SNo,CName)Score,SnoScore,CnameScore,SNoSDept,SNoSLoc,SDeptSLoc,36,5.3.4,第三范式（,3NF,）,定义,5.16,第三范式（,3NF,）,若,R(U,F),2NF,，,且它的任何一个,非主属性,都不,传递依赖,于,键,，,则称关系,R,属于第三范式,记为,R(U,F),3NF,。,例：,SL2(,SNo,SDept,SLoc)2NF,SD2(,SNo,SDept),3NF,DL2(,SDept,SLoc),3NF,在关系数据库模型设计中目前一般采用第三范式。,SNoSDept,SDeptSLoc,SL2(SNo,SDept,SLoc)3NF,37,5.3.5 BCNF,定义,5.17,改进的,3NF-BCNF,设关系模式,R(U,F),1NF,，,若,XY,且,Y X,时,X,必包含键,，则称,R(U,F),BCNF,。,一个满足,BCNF,的关系模式必然有：,R,中所有非主属性对每一个键都是完全函数依赖；,R,中所有主属性对每一个不包含它的键，都是完全函数依赖；,R,中没有任何属性完全函数依赖于非键的任何一组属性。,38,5.4,关系模式的规范化,SLC2(SNo,SDept,SLoc,CName,Score,)1NF,SC2,(,SNo,CName,Score)3NF,SL2,(,SNo,SDept,SLoc)2NF,SD2,(,SNo,SDept)3NF,DL2,(,SDept,SLoc)3NF,一个低一级的范式的关系模式，,通过模式分解转换为若干个高一级范式的关系模式集合，,这种分解过程叫做,关系模式的规范化,39,5.4.1,关系模式规范化的目的和基本思想,规范化的目的：,基本思想：,解决关系模式中存在的数据冗余、插入和删除异常、更新异常的问题,逐步消除数据依赖中不合适的部分，使模式中的各个关系模式达到某种程度的“分离”，即采用“一事一地”的模式设计原则。,40,5.4.2,关系模式规范化的步骤,1NF,消除,非主属性,对,键,的,部分函数依赖,消除,非主属性,对,键,的,传递函数依赖,消除,主属性,对,键,的,部分和传递函数依赖,2NF,3NF,BCNF,基本原则：,由低到高，逐步规范,权衡利弊，适可而止,通常以满足第三范式为基本要求。,41,范式的判定,【,练习,1】,：设有关系模式,R(A,B,C,D,E,P),其函数依赖集,F=AB,CP,EA,CED,判断,R,属于第几范式。,L,：,解：,C, E,R,：,B, D, P,N,：,none,LR,：,A,CK,：,CE,= ,C,E,P,A,B,= U,D,R1NF,主属性：,C, E,非主属性：,A, B, D, P,又,(C,E)P,CP,R2NF,R1NF,42,范式的判定,【,练习,2】,：设有关系模式,R(A,B,C,D),其函数依赖集,F=AC,CA,BA,DC,判断,R,属于第几范式。,L,：,解：,B, D,R,：,none,N,：,none,LR,：,A, C,CK,: BD,= ,B,D,A,C,= U,R1NF,主属性：,B, D,非主属性：,A, C,又,(B,D)A,BA,R2NF,R1NF,43,范式的判定,【,练习,3】,：设有关系模式,R(A,B,C,D),其函数依赖集,F=BC,CD,DA,判断,R,属于第几范式。,L,：,解：,B,R,：,A,N,：,none,LR,：,C, D,CK,: B,= ,B,C,D,A,= U,R1NF,主属性：,B,非主属性：,A, C, D,R2NF,又因为候选键只有一个属性，,所以所有非主属性都完全依赖于键 ,R2NF,又,BC,CD,R3NF,44,范式的判定,【,练习,4】,：设有关系模式,R(A,B,C),其函数依赖集,F=ABC,CA,判断,R,属于第几范式。,解：,CK,: AB, BC,R1NF,主属性：,A, B, C,非主属性：,none,R3NF,又因为所有属性都是主属性,又,R3NF,RBCNF,45,范式的判定,【,练习,5】,：设有关系模式,R(A,B,C,D,E),其函数依赖集,F=ABC,BD, CE, ECB, ACB,判断,R,属于第几范式。,L,：,解：,A,R,：,D,N,：,none,LR,：,B, C, E,= ,A,= U,= ,A,B,C,D,E,= U,= ,A,C,E,B,D,= U,= ,A,E,= U,CK,: AB, AC,R1NF,主属性：,A, B, C,非主属性：,D, E,又,(A,B)D,BD,R2NF,R1NF,46,复习,1NF,消除,非主属性,对,键,的,部分函数依赖,消除,非主属性,对,键,的,传递函数依赖,消除,主属性,对,键,的,部分和传递函数依赖,2NF,3NF,BCNF,基本原则：,由低到高，逐步规范,权衡利弊，适可而止,通常以满足第三范式为基本要求。,47,5.4.3,关系模式规范化的要求,定义,5.20,关系模式,R,的一个分解是指,其中,并且没有,1i, jn,是,F,在 上的投影。,等价的常用标准有三个：,（,1,）分解要具有无损连接性；,（,2,）分解要保持函数依赖；,（,3,）分解既要保持函数依赖又要具有无损连接性。,48,5.4.3,关系模式规范化的要求,1.,无损连接分解,定义,5.21,无损连接性（,Lossless Join,）,设关系模式,R,被分解为若干个关系模式,其中,，且不存在,是,F,在 上的投影，如果,R,与,自然连接的结果相等，则称关系模式,R,的分解,具有无损连接性。,49,5.4.3,关系模式规范化的要求,例如，对于关系模式,SL2(,SNo,SDept,SLoc),SNo,SDept,SLoc,02001,电子系,10-201,02002,电子系,10-201,02003,计科系,11-305,02004,数学系,12-823,SN2,02001,02002,02003,02004,SDept,电子系,计科系,数学系,SLoc,10-201,11-305,12-823,50,5.4.3,关系模式规范化的要求,例如，对于关系模式,SL2(,SNo,SDept,SLoc),SNo,SDept,02001,电子系,02002,电子系,02003,计科系,02004,数学系,SDept,电子系,10-201,计科系,11-305,数学系,12-823,SLoc,ND2,DL2,SNo,SDept,SLoc,02001,电子系,10-201,02002,电子系,10-201,02003,计科系,11-305,02004,数学系,12-823,ND2 DL2,51,5.4.3,关系模式规范化的要求,关系模式,R,被分解为,中有如下函数依赖中的一个，则此分解为无损连接分解：,，若,（,1,）,（,2),即,R,分解成 和 后，如果它们的公共属性集是,或者 的主键，那么分解是无损的。,52,5.4.3,关系模式规范化的要求,2.,依赖保持的分解,定义,5.22,函数依赖保持性（,Preserve Dependency,）,设关系模式,R,的一个分解为,其中,，且不存在,是,F,在 上的投影，,若,则称关系模式,R,的分解具有函数依赖保持性。,53,5.4.3,关系模式规范化的要求,如果一个分解具有无损分解，则它能够保证不丢失信息；,如果一个分解保持了函数依赖，则它可以减轻或解决各种异常情况。,具有无损连接性的分解不一定保持函数依赖，保持函数依赖的分解不一定具有无损连接性。,54,习题,1.,设工厂里有一个记录职工每天日产量的关系模式：,R,（,ENo,，,Date,，,Output,，,PNo,，,PDirector,）,。,其中，,ENo,表示职工号，,Date,表示日期，,Output,表示职工日产量，,PNo,表示车间号，,PDirector,表示车间主任,如果规定：,每个职工每天只有一个日产量；,每个职工只能隶属于一个车间，一个车间有多个职工；,每个车间只有一个车间主任。,（,1,）根据上述规定，写出关系模式,R,的基本函数依赖；,（,2,）试写出关系模式,R,的候选键，并写出求解过程；,（,3,）试问关系模式,R,最高已经达到第几范式？为什么？,（,4,）若不满足第三范式，请将其分解使其满足三范式。,55,R,（,ENo,，,Date,，,Output,，,PNo,，,PDirector,）,如果规定：,每个职工每天只有一个日产量；,每个职工只能隶属于一个车间，一个车间有多个职工；,每个车间只有一个车间主任。,解,：,(1)F=(,ENo,Date)Output,ENoPNo,PNoPDirector,(2),L:ENo,Date,R:Output,PDirector,N:none,LR:PNo,(,ENo,Date,),+=,ENo,Date,Output,PNo,PDirector,CK:,（,ENo,Date,）,56,R,（,ENo,，,Date,，,Output,，,PNo,，,PDirector,）,如果规定：,每个职工每天只有一个日产量；,每个职工只能隶属于一个车间，一个车间有多个职工；,每个车间只有一个车间主任。,解,：,(3),主属性：,ENo,Date,非主属性：,Output,PDirector,PNo,(,ENo,Date,),PNo,ENo,PNo,R1NF,R1NF,R2NF,57,R,（,ENo,，,Date,，,Output,，,PNo,，,PDirector,）,解,：,F=(,ENo,Date)Output,ENoPNo,PNoPDirector,ED,（,ENo,，,Date,，,output,）,P,（,PNo,，,PDirector,）,EPD,（,ENo,，,PNo,，,PDirector,）,3NF,2NF,EP(ENo,PNo,),PD(PNo,PDirector,),3NF,3NF,（,4,）,ED,（,ENo,，,Date,，,output,）,EP,（,ENo,，,PNo,）,PD,（,PNo,，,PDirector,）,58,习题,2.,现有关系模式如下：,R,（,Sno,，,Cno,，,Grade,，,Tname,，,Taddr,）,其属性分别表示学生的学号、选修课程的编号、成绩、,任课教师名、教师地址等意义。,现规定：,每个学生每学一门课程只有一个成绩；,每门课可以有多位教师任教，一位教师只能教一门课；,每位教师只有一个地址，一个地址可以居住多位教师,（此外不允许教师同名同姓）。,1,、根据上述规定，写出关系模式,R,的基本函数依赖；,2,、试写出关系模式,R,的候选键，并写出求解过程；,3,、试问关系模式,R,最高已经达到第几范式？为什么？,59,R,（,Sno,，,Cno,，,Grade,，,Tname,，,Taddr,）,如果规定：,每个学生每学一门课程只有一个成绩；,每门课可以有多位教师任教，一位教师只能教一门课；,每位教师只有一个地址，一个地址可以居住多位教师,解,：,(1)F=(,Sno,Cno)Grade,TnameCno,TnameTaddr,(2),L:Sno,Tname,R:Grade,Taddr,N:none,LR:Cno,(,Sno,Tname,),+=,Sno,Tname,Grade,Cno,Taddr,CK:,（,Sno,Tname,）,60,R,（,Sno,，,Cno,，,Grade,，,Tname,，,Taddr,）,如果规定：,每个职工每天只有一个日产量；,每个职工只能隶属于一个车间，一个车间有多个职工；,每个车间只有一个车间主任。,解,：,(3),主属性：,Sno,Tname,非主属性：,Grade,Cno,Taddr,(,Sno,Tname,),Cno,Tname,Cno,R1NF,R1NF,R2NF,61,解,：,F=(,Sno,Cno)Grade,TnameCno,TnameTaddr,SC,（,Sno,Cno,Grade,）,T,（,Tname,Taddr,）,CT,（,Tname,Cno,Taddr,）,3NF,3NF,（,4,）,SC,（,Sno,Cno,Grade,）,CT,（,Tname,Cno,Taddr,）,R,（,Sno,，,Cno,，,Grade,，,Tname,，,Taddr,）,62,