第4章 关系数据模式的规范化理论

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Copyright2006,College of,ITSoft,(HZIEE),63,Version No: 1.0,Copyright2006,College of,ITSoft,(HZIEE),Version No: 1.0,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第,4,章 关系数据模式的规范化理论,4.1,问题的提出,4.2,函数依赖,4.3,范式和规范化,什么是数据库设计,?,怎么设计？,现实世界,数据,/,关系,机器世界,4.1,问题的提出,是不是从信息世界的模型中简单地转化为机器世界的数据就可以了呢,?,实体,关系表,属性,数据项,4.1,问题的提出,4.1,问题的提出,如果要设计一个教学管理数据库，希望从数据库中得到学生学号,(,sno,),、学生姓名,(name),、性别,(sex),、学生学习的课程号,(,cno,),、课程名,(,cname,),和该门课程的成绩,(grade),。,如何设计该关系模式？,主码是什么,?,(,学号,姓名,性别,课程号,课程名,成绩,),(SNO,NAME,SEX,CNO,CNAME,GRADE),4.1,问题的提出,问题,1,：数据冗余,SNO,NAME,SEX,CNO,CNAME,GRADE,S0102,王华,男,C108,C,语言,84,S0102,王华,男,C206,数据库,92,S0108,李丽,女,C206,数据库,86,S0108,李丽,女,C207,数学,86,4.1,问题的提出,问题,2,：不一致性,SNO,NAME,SEX,CNO,CNAME,GRADE,S0102,王华,男,C108,C,语言,84,S0102,张三,男,C206,数据库,92,S0108,李丽,女,C206,数据库,86,S0108,李丽,女,C207,数学,86,4.1,问题的提出,问题,3,：插入异常,SNO,NAME,SEX,CNO,CNAME,GRADE,S0102,王华,男,C108,C,语言,84,S0102,王华,男,C206,数据库,92,S0108,李丽,女,C206,数据库,86,S0108,李丽,女,C207,数学,86,（,S0010,，李四，男，,null,，,null,，,null,）,4.1,问题的提出,问题,4,：删除异常（当某学号只有一条记录，并做删除操作时）,SNO,NAME,SEX,CNO,CNAME,GRADE,S0102,王华,男,C108,C,语言,84,S0103,张三,男,C206,数据库,92,S0108,李丽,女,C206,数据库,86,S0108,李丽,女,C207,数学,86,4.1,问题的提出,解决方案,S1,（,S,NO,，,NAME,，,SEX,）,S2,（,CNO,，,CNAME,）,S3,（,S,NO,，,CNO,，,GRADE,）,4.2,函数依赖,定义,1,设,R(U),是属性集,U,上的关系模式，,X,，,Y,是,U,的子集。若对于,R(U),任意一个可能的关系,r,，,r,中不可能存在两个元组在,X,上的属性值相等，而在,Y,上的属性值不等，则称,X,函数确定,Y,或,Y,函数依赖于,X,，记作,X-Y,4.2,函数依赖,例子,职工号,-,姓名,S1:SNO,- NAME ;SNO- SEX,S2:(SNO,CNO) - GRADE,S3: CNO,- CNAME,4.2,函数依赖,定义,2,设,X-Y,是一个函数依赖，若,则称,X-Y,是一个平凡函数依赖。,设,X-Y,是一个函数依赖，若,则称,X-Y,是一个非平凡函数依赖。,4.2,函数依赖,例子,在,S2,中有,(SNO,CNO) -SNO,(SNO,CNO) -CNO,所以这些都是平凡函数依赖关系,(SNO,CNO) - GRADE,这个是非平凡函数依赖关系,4.2,函数依赖,定义,3,设,X-Y,是一个函数依赖，并且对于任何,则称,XY,是一个完全函数依赖。即,Y,函数依赖,于整个,X,，记,4.2,函数依赖,举例：,在关系,S (SNO,NAME,SEX,CNO,CNAME,GRADE),中：,(SNO,CNO) - GRADE,但,SNO - GRADE,；,(CNO) - GRADE,都不成立,所以,(SNO,CNO) - GRADE,是完全函数依赖关系。,4.2,函数依赖,定义,4,设,X-Y,是一个函数依赖,但不是完全函数依赖,则称,X-Y,是一个部分函数依赖,或称,Y,函数依赖于,X,的某个真子集,记,4.2,函数依赖,在关系,S (SNO,NAME,SEX,CNO,CNAME, GRADE),中：,(SNO,CNO)-NAME,而对于每个学生都有唯一的,SNO,值,所以,SNO-NAME,而,CNO-NAME,因此，,(SNO,CNO)-NAME,是部分函数依赖,(SNO,CNO) NAME,p,4.2,函数依赖,设,R(U),是一个关系模式,则称,Z,传递函数依赖于,X,记,4.2,函数依赖,例子： 班级,(,班号,专业名,系名,人数,入学年份,),班号,-,专业名,专业名,-,系名,班号,-,人数,班号,-,入学年份,班号,-,专业名,专业名,-,系名,4.2,函数依赖,函数依赖与属性关系,属性之间有,3,种关系,但并不是每一种关系中都存在函数依赖。,函数依赖与属性关系,设,R(U),是属性集,U,上的关系模式,X,Y,是,U,的子集,:,若,X,和,Y,之间是,1:1,关系,则存在函数依赖,X-Y,Y-X;,若,X,和,Y,之间是,1:n,关系,则存在函数依赖,X-Y;,若,X,和,Y,之间是,m:n,关系,则,X,Y,间不存在函数依赖,.,函数依赖与属性关系,分析下列关系中各种函数的依赖关系,:,学生,(,学号,姓名,出生年月,系名,班号,宿舍区,),Armstrong,公理,背景,为了从一组函数依赖中求得逻辑蕴涵的函数依赖,例如已知函数依赖集,F,要问是否逻辑蕴涵,X-Y,就需要一套推理规则,.,Armstrong,公理,设,A,B,C,D,是给定关系模式,R,的属性集的任意子集,并把,A,和,B,的并集称为,AB,则其推理规则可归结为,3,条,:,自反律,:,如果,这是一个平凡函数依赖,增广律,:,如果,传递律,:,如果,Armstrong,公理,推论,自合规则,:A-A,分解规则,:A-BC,则,A-B,且,A-C,合并规则,: A-B,且,A-C,则,A-BC,复合规则,: A-B,且,C-D,成立,则,AC-BD,4.2,函数依赖,4.2.6,闭包及其计算,定义,6,：设,F,是关系模式,R,的一个函数依赖集，,X,，,Y,是,R,的属性子集，如果从,F,中的函数依赖能够推出,XY,，则称,F,逻辑蕴涵,XY,。,定义,7,：被,F,逻辑蕴涵的函数依赖的全体构成的集合，称为,F,的闭包，记为,F,+,。,练习,1,：设有关系模式,R(A,B,C,D,E),，,F = AC,BC E,D C, E A,，试求,F,的闭包,F,+,。,4.2,函数依赖,定义,8,：设,F,是属性集,U,上的一组函数依赖，,X U,，则属性集,X,关于,F,的闭包,X,+,定义为,X,+,=A|AU,且,XA,在,F,+,中,，即,X=A|XAF,+,。,算法,4.1,result=,X,do,if,F,中有某个函数依赖,Y,Z,满足,Y,result,then result=,result,Z,while (result,有所改变,);,X,F,+,算法,:,设,i=0,令,X,(0),= X,计算,A=B|,一切,W,X,(i,),且,W B F,+,令,X,(i+1),=,X,(i),A,判断,X,(i+1),=,X,(i,),是否成立，,成立，转，,不成立，,i = i + 1,，转, 算法结束，,X,F,+,=,X,(i,),4.2,函数依赖,随堂练习,练习,1,：设有关系模式,R(A,B,C,D,E),，,F = AB,C E,D AC,，试求,D,关于,F,的闭包。,练习,2,：设有关系模式,R(A,B,C,D,E),，,F = ABC,BD,CE,EC,AC,，试求,BC,关于,F,的闭包,(BC),F,+,。,4.2,函数依赖,关键码的定义,如果,X,U,在,R,上成立（即,X,U,在,F,+,中），那么称,X,是,R,的一个超键。,如果,X,U,在,R,上成立，但对,X,的任一真子集,X,都有,X,U,不成立（即,X,U,不在,F,+,中，或者,X,U,），那么称,X,是,R,上的一个候选键。,快速求解候选键的一个充分条件,对于给定的关系模式,R,(,A,1,，,An,),和函数依赖集,F,，可将其属性分为以下四类：,f,L,类,R,类,N,类,LR,类,定理,4.4,对于给定的关系模式,R,及其函数依赖集,F,（,1,）若,X,（,X,R,）是,L,类属性，则,X,必为,R,的任一候选键的成员。,（,2,）若,X,（,X,R,）是,L,类属性，且,X,+,包含了,R,的全部属性，则,X,必为,R,的惟一候选键。,（,3,）若,X,（,X,R,）是,R,类属性，则,X,不在任何候选键中。,（,4,）若,X,（,X,R,）是,N,类属性，则,X,包含在,R,的任一候选键中。,（,5,）若,X,（,X,R,）是,R,的,N,类和,L,类属性组成的属性集，且,X,+,包含了,R,的全部属性，则,X,是,R,的惟一候选键。,随堂练习,练习,1,：设有关系模式,R(A,B,C,D,E),，,F = AB,CG,EA,，,CE D,，求,R,的所有候选键。,练习,2,：设有关系模式,R(A,B,C,D,E,P),，,F = AD,ED,DB,BCD,DCA,，求,R,的所有候选键。,练习,3,：设有关系模式,R(A,B,C,D,E),，,F = ABC,CDE,BD,EA,，求,R,的所有候选键。,多属性函数依赖集候选键的求解算法,（,1,）属性分类（,L,、,R,、,N,和,LR,）,（,2,）若,X,+,包含了,R,的全部属性，转（,5,）；否则，转（,3,）。,（,3,）在,Y,中取一个属性,A,，求,(,XA,),+,，若它包含了,R,的全部属性，则转（,4,）；否则，调换一属性反复进行这一过程，直到试完所有,Y,中的属性。,（,4,）如果已找出所有候选键，则转（,5,）；否则在,Y,中依次取两个、三个、,，求它们的属性集的闭包，直到其闭包包含,R,的全部属性。,（,5,）停止，输出结果。,令,X,代表,L,和,N,类，,Y,代表,LR,类,随堂练习,关系模式R(A,B,C,D,E,F)，,其函数依赖集F=ABE,ACF,ADB,BC,CD ,，试求,R,的所有候选键。,4.4,范式和规范化,要想设计一个好的关系,必须使关系满足一定的约束条件,此约束条件已经形成了规范,分成几个等级,一级比一级要求得严格。,4.4,范式和规范化,满足最低要求的关系称为第一范式,在此基础上又满足某条件,达到第二范式,如此类推,直到第五范式,.,4.4,范式和规范化,一个较低范式关系,可以通过关系的无损分解转换为若干较高范式关系的集合,这一过程叫做,关系规范化,.,4.4,范式和规范化,一般情况下,第一范式和第二范式的关系存在许多缺点,实际的关系数据库一般使用第三范式以上的关系,.,4.4.1,范式,范式是符合某一种级别的关系模式的集合。,关系数据库中的关系必须满足一定的要求。满足不同程度要求的为不同范式。,范式的种类：,第一范式,(1NF),第二范式,(2NF),第三范式,(3NF),BC,范式,(BCNF),第四范式,(4NF),第五范式,(5NF),范式（续）,各种范式之间存在联系：,某一关系模式,R,为第,n,范式，可简记为,RnNF,。,4.4,范式和规范化,候选码定义,设,K,为关系模式,R(U,，,F),中的属性或属性组合，若,K U,，则,k,称为,R,的一个候选码。,若关系模式,R,中有多个候选码，则选定其中一个作为主码。,组成候选码的属性称为主属性，不参加任何候选码的属性成为非主属性。,f,第一范式,4.4.2,范式的判定条件与规范化,1.,第一范式（,1NF,）,定义：设,R,是一个关系模式，,R,属于第一范式当且仅当,R,中每一个属性,A,的值域只包含原子项，即不可分割的数据项。,第一范式（续）,例,:,关系模式,SLC(Sno,Sdept,Sloc,Cno, Grade),Sloc,为学生住处，假设每个系的学生住在同一个地方。,函数依赖包括：,(,Sno,Cno,),f,Grade,Sno,Sdept,(,Sno,Cno,),P,Sdept,Sno,Sloc,(,Sno,Cno,),P,Sloc,Sdept,Sloc,第一范式（续）,SLC,的码为,(,Sno,Cno,),Sno,Cno,Grade,Sdept,Sloc,SLC,第一范式（续）,结论,:,1. SLC,满足第一范式。,2.,非主属性,Sdept,和,Sloc,部分函数依赖于码,(,Sno,Cno,),。,sno,cno,sdept,sloc,grade,第一范式（续）,第一范式存在的问题,插入异常：若插入一个学生，但未选课，这样的元祖不能插入。,删除异常：如果某个学生只选修了一门课，如果他不选该课程了，则在删除课程号的同时会把该学生也一起删除。,数据冗余大：如果一个学生选修了,10,门课程，则他的,DEPT,和,SLOC,值就要重复存储,10,次。,修改复杂：如果要修改,DEPT,和,SLOC,的值，则必须修改,10,次。,第一范式（续）,原因,Sdept,、,Sloc,部分函数依赖于码。,解决方法,采用投影分解法，把,SLC,分解为两个关系模式，以消除这些部分函数依赖。,SC,（,Sno,，,Cno,，,Grade,）,SL,（,Sno,，,Sdept,，,Sloc,）,第一范式（续）,Sno,Cno,Grade,Sdept,Sloc,SLC,第一范式（续）,函数依赖图,：,Sno,Cno,Grade,SC,SL,Sno,Sdept,Sloc,第二范式,2.,第二范式（,2NF,）,定义：设,R,是一个关系模式，,R,属于第二范式当且仅当,R,是,1NF,，且每个非主属性都完全函数依赖于主码。,第二范式（续）,例：,2NF,关系模式,SL(Sno,Sdept,Sloc,),中,函数依赖：,SnoSdept,SdeptSloc,SnoSloc,SL,Sno,Sdept,Sloc,Sloc,传递函数依赖于,Sno,，即,SL,中存在非主属性对码的传递函数依赖。,第二范式（续）,第二范式存在的问题,删除异常：如果某个系的学生全部毕业了，在删除该系学生信息的同时，把这个系的信息也丢掉了。,数据冗余大：每一个系的学生都住在同一个地方，系的住处重复了多次。,修改复杂：当学校调整学生住处，如信息系的学生全部迁到另一地方，修改时必须同时修改该系的所有学生的,SLOC,属性值。,原因是还存在,sloc,对,sno,的传递函数依赖,第二范式（续）,原因,Sloc,传递函数依赖于,Sno,解决方法,采用投影分解法，把,SL,分解为两个关系模式，以消除传递函数依赖：,SD,（,Sno,，,Sdept,）,DL,（,Sdept,，,Sloc,）,SD,的码为,Sno,，,DL,的码为,Sdept,。,SL,Sno,Sdept,Sloc,第二范式（续）,SD,的码为,Sno,，,DL,的码为,Sdept,。,Sno,Sdept,SD,Sdept,Sloc,DL,第三范式,3.,第三范式（,3NF,）,定义：设,R,是一个关系模式，,R,属于第三范式当且仅当,R,是,2NF,，且每个非主属性都非传递函数依赖于主码。,第三范式（续）,例如：模型,SC(SNO,SNAME,CNO,GRADE),模型的候选码是：,(SNO,CNO),、,(SNAME,CNO),非主属性只有,GRADE,，对这两个候选码都是完全函数依赖，因此,SC3NF,。,存在的问题,删除异常：当学生退选了课程，元组被删除也失去学生学号和姓名的对应关系。,数据冗余：学生选课多时，姓名会被重复存储。,BC,范式,4. BC,范式（,BCNF,）,定义：对于关系模式,R,，对任何非平凡的函数依赖,X,Y,，,X,均包含码，则,R,属于,BCNF,。,BC,范式（续）,例：,假设仓库管理关系表为StorehouseManage(仓库ID, 存储物品ID, 管理员ID, 数量)，且有一个管理员只在一个仓库工作；一个仓库可以存储多种物品。这个数据库表中存在如下决定关系：,(仓库ID, 存储物品ID) (管理员ID, 数量),(管理员ID, 存储物品ID) (仓库ID, 数量),候选键：,(仓库ID, 存储物品ID),、,(管理员ID, 存储物品ID),BC,范式（续）,它会出现如下异常情况：,(1) 删除异常：,当仓库被清空后，所有存储物品ID和数量信息被删除的同时，仓库ID和管理员ID信息也被删除了。,(2) 插入异常：,当仓库没有存储任何物品时，无法给仓库分配管理员。,(3) 更新异常：,如果仓库换了管理员，则表中所有行的管理员ID都要修改。,BC,范式（续）,由于存在如下决定关系：,(仓库ID) (管理员ID),(管理员ID) (仓库ID),即存在关键字段决定关键字段的情况，所以其不符合BCNF范式。,把仓库管理关系表分解为二个关系表：,仓库管理：StorehouseManage(仓库ID, 管理员ID)；,仓库：Storehouse(仓库ID, 存储物品ID, 数量)。,规范化步骤,消除非主属性对码的部分函数依赖,BCNF,2NF,3NF,1NF,消除非主属性对码的传递函数依赖,消除每一属性对码的部分和传递函数依赖,随堂练习,（,1,）在关系模式,R(U,F),中，如果,X Y,，存在,X,的真子集,X,1,，,使,X,1,Y,，称函数依赖,X Y,为（ ）,A.,平凡函数依赖,B.,部分函数依赖,C.,完全函数依赖,D.,传递函数依赖,（,2,）在关系模式,R(U,F),中，对任何非平凡的函数依赖,X Y,，,X,均包含键，则,R,最高可以达到（ ）,A.2NF,B.3NFC.BCNFD.4NF,随堂练习,（,3,）已知：关系模式,R(U,F), U=ABCDEG,F=A B,C G,E A,CE D,求：（,1,）,R,的候选码,（,2,）,R,最高属于哪级范式,（,4,）已知：关系模式,R(U,F), U=ABCDE,F=A BC,CD E,E A,B D,求：（,1,）,R,的候选码,（,2,）,R,最高属于哪级范式,