数据库系统概论(第五版)PPT第6章

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,中国人民大学,数据库系统概论,An Introduction to Database System,数据库系统概论,An Introduction to Database System,第六章 关系数据理论,xx,大学信息学院,基于某个数据库管理系统设计数据库，如何基于数据库系统编程,第,6,章 关系数据理论,第,7,章 数据库设计,第,8,章 数据库编程,第二篇 设计与应用开发篇,第六章 关系数据理论,6.1,问题的提出,6.2,规范化,6.3,数据依赖的公理系统,*6.4,模式的分解,6.5 小结,6.1,问题的提出,关系数据库逻辑设计,针对具体问题，如何构造一个适合于它的数据模式,数据库逻辑设计的工具关系数据库的规范化理论,*,问题的提出（续）,关系模式由五部分组成，是一个五元组：,R(U, D, DOM, F),关系名,R,是符号化的元组语义,U,为一组属性,D,为属性组,U,中的属性所来自的域,DOM,为属性到域的映射,F,为属性组,U,上的一组数据依赖,问题的提出（续）,由于,D,、,DOM,与模式设计关系不大，因此在本章中把关系模式看作一个三元组：,R,当且仅当,U,上的一个关系,r,满足,F,时，,r,称为关系模式,R,的一个关系,作为二维表，关系要符合一个最基本的条件：每个分量必须是不可分开的数据项。满足了这个条件的关系模式就属于第一范式（,1NF,）,*,问题的提出（续）,数据依赖,是一个关系内部属性与属性之间的一种约束关系,通过属性间值的相等与否体现出来的数据间相互联系,是现实世界属性间相互联系的抽象,是数据内在的性质,是语义的体现,*,问题的提出（续）,数据依赖的主要类型,函数依赖（,Functional Dependency,，简记为,FD,）,多值依赖（,Multi-Valued Dependency,，简记为,MVD,）,*,问题的提出（续）,函数依赖普遍存在于现实生活中,描述一个学生关系，可以有学号、姓名、系名等属性。,一个学号只对应一个学生，一个学生只在一个系中学习,“,学号,”,值确定后，学生的姓名及所在系的值就被唯一确定。,Sname=f(Sno),，,Sdept=f(Sno),即,Sno,函数决定,Sname,Sno,函数决定,Sdept,记作,Sno,Sname,，,Sno,Sdept,*,问题的提出（续）,例,6.1,建立一个描述学校教务的数据库。涉及的对象包括：,学生的学号（,Sno,）,所在系（,Sdept,）,系主任姓名（,Mname,）,课程号（,Cno,）,成绩（,Grade,）,*,问题的提出（续）,假设学校教务的数据库模式用一个单一的关系模式,Student,来表示，则该关系模式的属性集合为：,U,Sno, Sdept, Mname, Cno, Grade,现实世界的已知事实（语义）：,一个系有若干学生， 但一个学生只属于一个系；,一个系只有一名（正职）负责人；,一个学生可以选修多门课程，每门课程有若干学生选修；,每个学生学习每一门课程有一个成绩。,*,问题的提出（续）,由此可得到属性组,U,上的一组函数依赖,F,：,F=SnoSdept, Sdept Mname, (Sno, Cno) Grade,Sno,Cno,Sdept,M,nam,e,Grade,*,问题的提出（续）,关系模式,Student,中存在的问题：,（,1,）数据冗余,浪费大量的存储空间,每一个系主任的姓名重复出现，重复次数与该系所有学生的所有课程成绩出现次数相同。,*,问题的提出（续）,（,2,）更新异常（,Update Anomalies,）,数据冗余,，,更新数据时，维护数据完整性代价大。,某系更换系主任后，必须修改与该系学生有关的每一个元组。,*,问题的提出（续）,（,3,）插入异常（,Insertion Anomalies,）,如果一个系刚成立，尚无学生，则无法把这个系及其系主任的信息存入数据库。,*,问题的提出（续）,（,4,）删除异常（,Deletion Anomalies,）,如果某个系的学生全部毕业了， 则在删除该系学生信息的同时，把这个系及其系主任的信息也丢掉了。,*,问题的提出（续）,结论,Student,关系模式不是一个好的模式。,一个,“,好,”,的模式应当不会发生插入异常、删除异常和更新异常，数据冗余应尽可能少。,原因,由存在于模式中的某些数据依赖引起的。,解决方法,用规范化理论改造关系模式来消除其中不合适的数据依赖,*,问题的提出（续）,把这个单一的模式分成三个关系模式：,S(Sno,Sdept,Sno Sdept);,SC(Sno,Cno,Grade,(Sno,Cno) Grade);,DEPT(Sdept,Mname,Sdept Mname);,这三个模式都不会发生插入异常、删除异常的问题，数据的冗余也得到了控制。,第六章 关系数据理论,6.1,问题的提出,6.2,规范化,6.3,数据依赖的公理系统,*6.4,模式的分解,6.5 小结,6.2,规范化,6.2.1,函数依赖,6.2.2,码,6.2.3,范式,6.2.4 2NF,6.2.5 3NF,6.2.6 BCNF,6.2.7,多值依赖,6.2.8 4NF,6.2.9,规范化小结,6.2.1,函数依赖,1.,函数依赖,2.,平凡函数依赖与非平凡函数依赖,3.,完全函数依赖与部分函数依赖,4.,传递函数依赖,*,1.,函数依赖,定义,6.1,设,R(U),是一个属性集,U,上的关系模式，,X,和,Y,是,U,的子集。若对于,R(U),的任意一个可能的关系,r,，,r,中不可能存在两个元组在,X,上的属性值相等， 而在,Y,上的属性值不等， 则称“,X,函数确定,Y,”,或“,Y,函数依赖于,X,”,，记作,X,Y,。,函数依赖（续）,例,Student(Sno, Sname, Ssex, Sage, Sdept),假设不允许重名，则有,:,Sno Ssex,，,Sno Sage,Sno Sdept,，,Sno Sname,Sname Ssex,，,Sname Sage,Sname Sdept,但,Ssex,Sage, Ssex,Sdept,若,XY,，并且,YX,则记为,XY,。,若,Y,不函数依赖于,X,则记为,X,Y,。,函数依赖（续）,Sno,Sname,Ssex,Sage,Sdept,S1,张三,男,20,计算机系,S1,李四,女,21,自动化系,S3,王五,男,20,计算机系,S4,赵六,男,21,计算机系,S5,田七,男,20,计算机系,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,违背了,Sno Sname,函数依赖（续）,由下面的关系表,能否得出,Sno Sname,Sno,Sname,Ssex,Sage,Sdept,S1,张三,男,20,计算机系,S2,李四,女,21,自动化系,S3,王五,男,20,计算机系,S4,赵六,男,21,计算机系,S5,田七,男,20,计算机系,.,.,.,.,.,.,.,.,.,.,.,.,.,.,.,函数依赖不是指关系模式,R,的某个或某些关系实例满足的约束条件，而是指,R,的所有关系实例均要满足的约束条件。,*,函数依赖（续）,函数依赖是语义范畴的概念，只能根据数据的语义来确定一个函数依赖。,例如“姓名年龄”这个函数依赖只有在不允许有同名人的条件下成立,*,2.,平凡函数依赖与非平凡函数依赖,X,Y,，但,Y,X,则称,X,Y,是,非平凡的函数依赖,。,X,Y,，但,Y,X,则称,X,Y,是,平凡的函数依赖,。,对于任一关系模式，平凡函数依赖都是必然成立的，它不反映新的语义。,若不特别声明， 我们总是讨论非平凡函数依赖。,*,平凡函数依赖与非平凡函数依赖（续）,若,X,Y,，则,X,称为这个函数依赖的,决定因素,（,Determinant,）。,若,X,Y,，,Y,X,，则记作,X,Y,。,若,Y,不函数依赖于,X,，则记作,X,Y,。,*,3.,完全函数依赖与部分函数依赖,定义,6.2,在,R(U),中，如果,X,Y,，并且对于,X,的任何一个真子集,X, 都有,X,Y,则称,Y,对,X,完全函数依赖,，记作,X,Y,。,若,X,Y,，但,Y,不完全函数依赖于,X,，则称,Y,对,X,部分函数依赖,，记作,X,Y,F,P,*,完全函数依赖与部分函数依赖（续）,例,在关系,SC(Sno, Cno, Grade),中，有：,由于：,Sno Grade,，,Cno Grade,，,因此：,(Sno, Cno) ,Grade,(Sno, Cno)Sno,(Sno, Cno) Cno,F,P,P,*,4.,传递函数依赖,定义,6.3,在,R(U),中，如果,X,Y,(,Y,X,),，,Y,X,，,Y,Z,，,Z,Y,则称,Z,对,X,传递函数依赖,(transitive functional dependency),。记为：,X,Z,。,注,:,如果,Y,X,即,X,Y,，则,Z,直接依赖于,X,，而不是传递函数依赖。,例,在关系,Std(Sno, Sdept, Mname),中，有：,Sno Sdept,，,Sdept Mname,，,Mname,传递函数依赖于,Sno,传递,6.2,规范化,6.2.1,函数依赖,6.2.2,码,6.2.3,范式,6.2.4 2NF,6.2.5 3NF,6.2.6 BCNF,6.2.7,多值依赖,6.2.8 4NF,6.2.9,规范化小结,*,码,定义,6.4,设,K,为,R,中的属性或属性组合。若,K,U,，则,K,称为,R,的一个,候选码,(Candidate Key),。,如果,U,部分函数依赖于,K,，即,K,U,则,K,称为超码 （,Surpkey,）。候选码是最小的超码，即,K,的任意一个真子集都不是候选码。,若关系模式,R,有多个候选码，则选定其中的一个做为,主码,(Primary key),。,F,P,*,码（续）,主属性与非主属性,包含在任何一个候选码中的属性 ，称为主属性 （,Prime attribute,）,不包含在任何码中的属性称为非主属性（,Nonprime attribute,）或非码属性（,Non-key attribute,）,全码：整个属性组是码，称为全码（,All-key,）,*,码（续）,例,6.2,S(Sno, Sdept, Sage),，单个属性,Sno,是码,SC(Sno, Cno, Grade),中，,(Sno, Cno),是码,例,6.3 R(P,W,A),P,：演奏者,W,：作品,A,：听众,一个演奏者可以演奏多个作品,某一作品可被多个演奏者演奏,听众可以欣赏不同演奏者的不同作品,码为,(P,W,A),，即,All-Key,*,码（续）,定义,6.5,关系模式,R,中属性或属性组,X,并非,R,的码，但,X,是另一个关系模式的码，则称,X,是,R,的,外部码,（,Foreign key,）也称,外码,。,SC(Sno,Cno,Grade),中，,Sno,不是码,Sno,是,S(Sno,Sdept,Sage),的码，则,Sno,是,SC,的外码,主码与外部码一起提供了表示关系间联系的手段,6.2,规范化,6.2.1,函数依赖,6.2.2,码,6.2.3,范式,6.2.4 2NF,6.2.5 3NF,6.2.6 BCNF,6.2.7,多值依赖,6.2.8 4NF,6.2.9,规范化小结,*,6.2.3,范式,范式是符合某一种级别的关系模式的集合。,关系数据库中的关系必须满足一定的要求。满足 不同程度要求的为不同范式。,范式的种类：,第一范式,(1NF),第二范式,(2NF),第三范式,(3NF),BC,范式,(BCNF),第四范式,(4NF),第五范式,(5NF),*,范式（续）,各种范式之间存在联系：,某一关系模式,R,为第,n,范式，可简记为,RnNF,。,一个低一级范式的关系模式，通过模式分解（,schema decomposition,）可以转换为若干个高一级范式的关系模式的集合，这种过程就叫,规范化,（,normalization,）。,6.2,规范化,6.2.1,函数依赖,6.2.2,码,6.2.3,范式,6.2.4 2NF,6.2.5 3NF,6.2.6 BCNF,6.2.7,多值依赖,6.2.8 4NF,6.2.9,规范化小结,*,2NF,定义,6.6,若关系模式,R,1NF,，并且每一个非主属性都完全函数依赖于任何一个候选码，则,R,2NF,例,6.4,S-L-C(Sno,Sdept,Sloc,Cno,Grade),，,Sloc,为学生的住处，并且每个系的学生住在同一个地方。,S-L-C,的码为,(Sno,Cno),。,函数依赖有,(Sno,Cno),Grade,SnoSdept, (Sno,Cno),Sdept,SnoSloc, (Sno,Cno),Sloc,Sdept,Sloc,F,P,P,*,2NF,（续）,Sno,Cno,Grade,Sdept,Sloc,关系模式,S-L-C,不属于,2NF,非主属性,Sdept,、,Sloc,并不完全依赖于码,*,2NF,（续）,一个关系模式不属于,2NF,，会产生以下问题：,插入异常,如果插入一个新学生，但该生未选课，即该生无,Cno,，由于插入元组时，必须给定码值，因此插入失败。,删除异常,如果,S4,只选了一门课,C3,，现在他不再选这门课，则删除,C3,后，整个元组的其他信息也被删除了。,修改复杂,如果一个学生选了多门课，则,Sdept,，,Sloc,被存储了多次。如果该生转系，则需要修改所有相关的,Sdept,和,Sloc,，造成修改的复杂化。,*,2NF,（续）,出现这种问题的原因,例子中有两类非主属性：,一类如,Grade,，它对码完全函数依赖,另一类如,Sdept,、,Sloc,，它们对码不是完全函数依赖,解决方法：,用投影分解把关系模式,S-L-C,分解成两个关系模式,SC(Sno,Cno,Grade),S-L(Sno,Sdept,Sloc),2NF,（续）,SC,的码为,(Sno,Cno),SL,的码为,Sno,，这样使得非主属性对码都是完全函数依赖了,Sno,Cno,Grade,Sno,Sdept,Sloc,图,6.4 SC,中的函数依赖,图,6.5 S-L,中的函数依赖,6.2,规范化,6.2.1,函数依赖,6.2.2,码,6.2.3,范式,6.2.4 2NF,6.2.5 3NF,6.2.6 BCNF,6.2.7,多值依赖,6.2.8 4NF,6.2.9,规范化小结,*,6.2.,5,3NF,定义,6.7,设关系模式,R,1NF,若,R,中不存在这样的码,X,、属性组,Y,及非主属性,Z,（,Z,Y,）,使得,X,Y,，,Y,Z,成立，,Y,X,不成立，则称,R, 3NF,。,SC,没有传递依赖，因此,SC 3NF,S-L,中,Sno Sdept( Sdept, Sno,), SdeptSloc,，可得,Sno Sloc,。,解决的办法是将,S-L,分解成,S-D(Sno,Sdept),3NF,D-L(Sdept,Sloc),3NF,传递,6.2,规范化,6.2.1,函数依赖,6.2.2,码,6.2.3,范式,6.2.4 2NF,6.2.5 3NF,6.2.6 BCNF,6.2.7,多值依赖,6.2.8 4NF,6.2.9,规范化小结,*,BCNF,BCNF,（,Boyce Codd Normal Form,）由,Boyce,和,Codd,提出，比,3NF,更进了一步。通常认为,BCNF,是修正的第三范式，有时也称为扩充的第三范式。,定义,6.8,设关系模式,R,1NF,，若,X,Y,且,Y,X,时,X,必含有码，则,R,BCNF,。,换言之，在关系模式,R,中，如果每一个决定属性集都包含候选码，则,RBCNF,。,*,BCNF,（续）,BCNF,的关系模式所具有的性质,所有非主属性都完全函数依赖于每个候选码,所有主属性都完全函数依赖于每个不包含它的候选码,没有任何属性完全函数依赖于非码的任何一组属性,如果一个关系数据库中的所有关系模式都属于,BCNF,，那么在函数依赖范畴内，它已实现了模式的彻底分解，达到了最高的规范化程度，消除了插入异常和删除异常。,例6.,5,考察关系模式,C(Cno,Cname,Pcno),它只有一个码,Cno,，没有任何属性对,Cno,部分依赖或传递依赖，所以,C3NF,。,同时,C,中,Cno,是唯一的决定因素，所以,CBCNF,。,对于关系模式,SC(Sno,Cno,Grade),可作同样分析。,BCNF,（续）,例,6,.6 关系模式,S(Sno,Sname,Sdept,Sage),，,假定,Sname,也具有唯一性，那么,S,就有两个码，这两个码都由单个属性组成，彼此不相交。,其他属性不存在对码的传递依赖与部分依赖，所以,S3NF,。,同时,S,中除,Sno,，,Sname,外没有其他决定因素，所以,S,也属于,BCNF,。,BCNF,（续）,例6.,7, 关系模式,SJP(S,J,P),中，,S,是学生，,J,表示,课程，,P,表示名次。每一个学生选修每门课程的,成绩有一定的名次，每门课程中每一名次只有一,个学生（即没有并列名次）。,由语义可得到函数依赖：,(S,J),P,；,(J,P),S,(S,J),与,(J,P),都可以作为候选码。,关系模式中没有属性对码传递依赖或部分依赖，所以,SJP3NF,。,除,(S,J),与,(J,P),以外没有其他决定因素，所以,SJPBCNF,。,BCNF,（续）,BCNF,（续）,例6.,8, 关系模式,STJ(S,T,J),中，,S,表示学生，,T,表,示教师，,J,表示课程。每一教师只教一门课。每,门课有若干教师，某一学生选定某门课，就对应,一个固定的教师。,由语义可得到函数依赖：,(S,J)T,；,(S,T)J,；,TJ,因为没有任何非主属性对码传递依赖或部分依赖，,STJ 3NF,。,因为,T,是决定因素，而,T,不包含码，所以,STJ BCNF,关系。,图,6.6 STJ,中的函数依赖,BCNF,（续）,对于不是,BCNF,的关系模式，仍然存在不合适的地方。,非,BCNF,的关系模式也可以通过分解成为,BCNF,。例如,STJ,可分解为,ST(S,T),与,TJ(T,J),，它们都是,BCNF,。,BCNF,（续）,3NF,和,BCNF,是在函数依赖的条件下对模式分解所能达到的分离程度的测度。,一个模式中的关系模式如果都属于,BCNF,，那么在函数依赖范畴内，它已实现了彻底的分离，已消除了插入和删除的异常。,3NF,的“不彻底”性表现在可能存在主属性对码的部分依赖和传递依赖。,6.2,规范化,6.2.1,函数依赖,6.2.2,码,6.2.3,范式,6.2.4 2NF,6.2.5 3NF,6.2.6 BCNF,6.2.7,多值依赖,6.2.8 4NF,6.2.9,规范化小结,*,6.2.7,多值依赖,例6.9设学校中某一门课程由多个教师讲授，他们,使用相同的一套参考书。,每个教员可以讲授多门课,程，每种参考书可以供多门课程使用,用关系模式,Teaching(C,T,B),来表示课程,C,、教师,T,和参,考书,B,之间的关系。,多值依赖（续）,表,6.3,非规范化关系示例,课程,C,教员,T,参考书,B,物理,数学,计算数学,李 勇,王 军,李 勇,张 平,张 平,周 峰,普通物理学,光学原理,物理习题集,数学分析,微分方程,高等代数,数学分析,*,多值依赖（续）,表,6.4,规范化,的二维表,Teaching,课程,C,教员,T,参考书,B,物 理,李 勇,普通物理学,物 理,李 勇,光学原理,物 理,李 勇,物理习题集,物 理,王 军,普通物理学,物 理,王 军,光学原理,物 理,王 军,物理习题集,数 学,李 勇,普通物理学,数 学,李 勇,光学原理,数 学,李 勇,物理习题集,数 学,张 平,普通物理学,数 学,张 平,光学原理,数 学,张 平,物理习题集,*,多值依赖（续）,Teaching,具有唯一候选码,(C,T,B),， 即全码。,TeachingBCNF,*,多值依赖（续）,课程,C,教员,T,参考书,B,物 理,李 勇,普通物理学,物 理,李 勇,光学原理,物 理,李 勇,物理习题集,物 理,王 军,普通物理学,物 理,王 军,光学原理,物 理,王 军,物理习题集,数 学,李 勇,普通物理学,数 学,李 勇,光学原理,数 学,李 勇,物理习题集,数 学,张 平,普通物理学,数 学,张 平,光学原理,数 学,张 平,物理习题集,(1),数据冗余度大：有多少名任课教师，参考书就要存储多少次。,*,多值依赖（续）,课程,C,教员,T,参考书,B,物 理,李 勇,普通物理学,物 理,李 勇,光学原理,物 理,李 勇,物理习题集,物 理,王 军,普通物理学,物 理,王 军,光学原理,物 理,王 军,物理习题集,数 学,李 勇,普通物理学,数 学,李 勇,光学原理,数 学,李 勇,物理习题集,数 学,张 平,普通物理学,数 学,张 平,光学原理,数 学,张 平,物理习题集,(2),增加操作复杂：当某一课程增加一名任课教师时，该课程有多少本参照书，就必须插入多少个元组。,*,多值依赖（续）,课程,C,教员,T,参考书,B,物 理,李 勇,普通物理学,物 理,李 勇,光学原理,物 理,李 勇,物理习题集,物 理,王 军,普通物理学,物 理,王 军,光学原理,物 理,王 军,物理习题集,数 学,李 勇,普通物理学,数 学,李 勇,光学原理,数 学,李 勇,物理习题集,数 学,张 平,普通物理学,数 学,张 平,光学原理,数 学,张 平,物理习题集,(3),删除操作复杂：某一门课要去掉一本参考书，该课程有多少名教师，就必须删除多少个元组。,*,多值依赖（续）,课程,C,教员,T,参考书,B,物 理,李 勇,普通物理学,物 理,李 勇,光学原理,物 理,李 勇,物理习题集,物 理,王 军,普通物理学,物 理,王 军,光学原理,物 理,王 军,物理习题集,数 学,李 勇,普通物理学,数 学,李 勇,光学原理,数 学,李 勇,物理习题集,数 学,张 平,普通物理学,数 学,张 平,光学原理,数 学,张 平,物理习题集,(4),修改操作复杂：某一门课要修改一本参考书，该课程有多少名教师，就必须修改多少个元组。,产生原因,:,存在多值依赖,*,多值依赖（续）,定义,6.9,设,R(U),是属性集,U,上的一个关系模式。,X,Y,Z,是,U,的子集，并且,Z,=,U,-,X,-,Y,。关系模式,R(U),中多值依赖,X,Y,成立，当且仅当对,R(U),的任一关系,r,，给定的一对,(,x,z,),值，有一组,Y,的值，这组值仅仅决定于,x,值而与,z,值无关。,例,Teaching,（,C, T, B,）,对于,C,的每一个值，,T,有一组值与之对应，而不论,B,取何值。因此,T,多值依赖于,C,，即,CT,。,多值依赖（续）,多值依赖的另一个等价的定义,在,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,。,*,多值依赖（续）,平凡多值依赖和非平凡的多值依赖,若,XY,，而,Z,，即,Z,为空，,则称,XY,为,平凡的多值依赖,。,否则称,XY,为,非平凡的多值依赖,。,多值依赖（续）,W,S,C,W1,S1,C1,W1,S1,C2,W1,S1,C3,W1,S2,C1,W1,S2,C2,W1,S2,C3,W2,S3,C4,W2,S3,C5,W2,S4,C4,W2,S4,C5,例6.,10,关系模式,WSC(W,S,C),中，,W,表示仓库，,S,表示保管,员，,C,表示商品。假设每个仓库有若干个保管员，有若干种,商品。每个保管员保管所在仓库的所有商品，每种商品被所,有保管员保管。,多值依赖（续）,按照语义对于,W,的每一个值,W,i,，,S,有一个完整的集合与之对应而不问,C,取何值。所以,W,S,。,如图,6.7,所示,对应,W,的某一个值,W,i,的全部,S,值记作,S,Wi,（表示此仓库工作的全部保管员）,全部,C,值记作,C,Wi,（表示在此仓库中存放的所有商品）,应当有,S,Wi,中的每一个值和,C,Wi,中的每一个,C,值对应,于是,S,Wi,与,C,Wi,之间正好形成一个完全二分图，因而,W,S,。,多值依赖（续）,由于C与S的完全对称性，必然有WC成立。,图,6.7 W,S,且,W,C,多值依赖（续）,多值依赖的性质,（,1,）多值依赖具有对称性。,即若,X,Y,，则,X,Z,，其中,Z,U,X,Y,多值依赖的对称性可以用完全二分图直观地表示出来。,从例,6.10, 容易看出，因为每个保管员保管所有商品，同时每种商品被所有保管员保管，显然若,W,S,，必然有,W,C,。,*,多值依赖（续）,（,2,）多值依赖具有传递性。即若,X,Y,，,Y,Z,， 则,X,Z,-,Y,。,（,3,）函数依赖是多值依赖的特殊情况。即若,X,Y,，则,X,Y,。,（,4,）若,X,Y,，,X,Z,，则,X,YZ,。,（,5,）若,X,Y,，,X,Z,，则,X,Y,Z,。,（,6,）若,X,Y,，,X,Z,，则,X,Y,-,Z,，,X,Z,-,Y,。,*,多值依赖（续）,多值依赖与函数依赖的区别,（,1,）多值依赖的有效性与属性集的范围有关,若,X,Y,在,U,上成立，则在,W,（,XY,W,U,）上一定成立；反之则不然，即,X,Y,在,W,（,W,U,）上成立，在,U,上并不一定成立。,原因：多值依赖的定义中不仅涉及属性组,X,和,Y,，而且涉及,U,中其余属性,Z,。,*,多值依赖（续）,多值依赖的有效性与属性集的范围有关（续）,一般地，在,R,(,U,)上若有,X,Y,在,W,(,W,U,)上成立，则称,X,Y,为,R,(,U,),的嵌入型多值依赖。,函数依赖,X,Y,的有效性仅决定于,X,、,Y,这两个属性集的值,只要在,R,(,U,)的任何一个关系,r,中，元组在,X,和,Y,上的值满足定义,6.l,，则函数依赖,X,Y,在任何属性集,W,(,XY,W,U,)上成立。,*,多值依赖（续）,（,2,）若函数依赖,X,Y,在,R,(,U,),上成立，则对于任何,Y,Y,均有,X,Y,成立。多值依赖,X,Y,若在,R,(,U,),上成立，不能断言对于任何,Y,Y,有,X,Y,成立。,*,多值依赖（续）,例如，关系,R(A,B,C,D),，,A,BC,成立，当然也有,A,D,成立。有,R,的一个关系实例，在此实例上,A,B,是不成立的。,A,B,C,D,a,1,b,1,c,1,d,1,a,1,b,1,c,1,d,2,a,1,b,2,c,2,d,1,a,1,b,2,c,2,d,2,表,6.6 R,的一个实例,6.2,规范化,6.2.1,函数依赖,6.2.2,码,6.2.3,范式,6.2.4 2NF,6.2.5 3NF,6.2.6 BCNF,6.2.7,多值依赖,6.2.8 4NF,6.2.9,规范化小结,*,6.2.8,4NF,定义,6.10,关系模式,R,1NF,，如果对于,R,的每个非平凡多值依赖,X,Y,（,Y,X,），,X,都含有码，则,R,4NF,。,4NF,就是限制关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖。,4NF,所允许的非平凡多值依赖实际上是函数依赖。,*,4NF,（续）,如果一个关系模式是,4NF,， 则必为,BCNF,。,在,例6.10,的,WSC,中，,W S, WC,他们都是非平凡多值依赖。而,W,不是码，关系模式,WSC,的码是,(W,S,C),，即,All-key,，因此,WSC,4NF,。,可以把,WSC,分解成,WS(W,S),WC(W,C),，,WS,4NF,，,WC,4NF,。,6.2,规范化,6.2.1,函数依赖,6.2.2,码,6.2.3,范式,6.2.4 2NF,6.2.5 3NF,6.2.6 BCNF,6.2.7,多值依赖,6.2.8 4NF,6.2.9,规范化小结,*,6.2.9 规范化小结,在关系数据库中，对关系模式的基本要求是满足第一范式。,规范化程度过低的关系不一定能够很好地描述现实世界,可能存在插入异常、删除异常、修改复杂、数据冗余等问题,解决方法就是对其进行规范化，转换成高级范式。,*,规范化小结（续）,一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式集合，这种过程就叫关系模式的规范化。,关系数据库的规范化理论是数据库逻辑设计的工具。,*,规范化小结（续）,规范化的基本思想,是逐步消除数据依赖中不合适的部分，使模式中的各关系模式达到某种程度的“分离”。,即采用“一事一地”的模式设计原则,让一个关系描述一个概念、一个实体或者实体间的一种联系。,若多于一个概念就把它“分离”出去。,因此 规范化实质上是概念的单一化。,*,规范化小结（续）,关系模式规范化的基本步骤,1NF,消除非主属性对码的部分函数依赖,消除决定因素,2NF,非码的非平凡 消除非主属性对码的传递函数依赖,函数依赖,3NF,消除主属性对码的部分和传递函数依赖,BCNF,消除非平凡且非函数依赖的多值依赖,4NF,图,6.8,规范化过程,*,规范化小结（续）,不能说规范化程度越高的关系模式就越好。,必须对现实世界的实际情况和用户应用需求作进一步分析，确定一个合适的、能够反映现实世界的模式。,上面的规范化步骤可以在其中任何一步终止。,第六章 关系数据理论,6.1,问题的提出,6.2,规范化,6.3,数据依赖的公理系统,*6.4,模式的分解,6.5 小结,*,6.3,数据依赖的公理系统,定义,6.11,对于满足一组,函数依赖,F,的关系模式,R,，其任何一个关系,r,，若函数依赖,X,Y,都成立（即,r,中任意两元组,t,、,s,，若,t,X,=,s,X,，则,t,Y,=,s,Y,），则称,F,逻辑蕴涵,X,Y,。,*,数据依赖的公理系统（续）,Armstrong,公理系统,一套推理规则，是模式分解算法的理论基础,用途,求给定关系模式的码,从一组函数依赖求得蕴涵的函数依赖,*,数据依赖的公理系统（续）,Armstrong,公理系统 设,U,为属性集总体，,F,是,U,上的一组函数依赖， 于是有关系模式,R,。对,R,来说有以下的推理规则：,A,1 自反律（,reflexivity,rule,）：若,Y,X,U,，则,X,Y,为,F,所蕴涵。,A2,增广律（,augmentation,rule,）：若,X,Y,为,F,所蕴涵，且,Z,U,，则,XZ,YZ,为,F,所蕴涵。,A3,传递律（,transitivity,rule,）：若,X,Y,及,Y,Z,为,F,所蕴涵，则,X,Z,为,F,所蕴涵。,注意：由自反律所得到的函数依赖均是平凡的函数依赖,自反律的使用并不依赖于,F,。,*,数据依赖的公理系统（续）,定理,6.1 Armstrong,推理规则是正确的。,证明,A1 自反律,设,Y,X,U,。,对,R,的任一关系,r,中的任意两个元组,t,、,s,：,若,t,X,=,s,X,，由于,Y,X,，有,t,Y,=,s,Y,，,所以,X,Y,成立，,自反律得证。,*,数据依赖的公理系统（续）,A2 增广律,设,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,所蕴涵，,增广律得证。,*,数据依赖的公理系统（续）,A3 传递律,设,X,Y,及,Y,Z,为,F,所蕴涵。,对,R,的任一关系,r,中的任意两个元组,t,、,s,：,若,t,X,=,s,X,，由于,X,Y,，有,t,Y,=,s,Y,；,再由,Y,Z,，有,t,Z,=,s,Z,，,所以,X,Z,为,F,所蕴涵，,传递律得证。,*,数据依赖的公理系统（续）,根据,A1,，,A2,，,A3,这三条推理规则可以得到下面三条推理规则：,合并规则（,union rule,）：,由,X,Y,，,X,Z,，有,X,YZ,。,伪传递规则（,pseudo transitivity rule,）：,由,X,Y,，,WY,Z,，有,XW,Z,。,分解规则（,decomposition rule,）：,由,X,Y,及,Z,Y,，有,X,Z,。,*,数据依赖的公理系统（续）,根据合并规则和分解规则，可得引理,6.1,引理,6.,1,X,A,1,A,2,A,k,成立的充分必要条件是,X,A,i,成立（,i,=,1，,2,，,，,k,）。,*,数据依赖的公理系统（续）,定义,6.,1,2,在关系模式,R,中为,F,所逻辑蕴涵的函数依赖的全体叫作,F,的闭包，记为,F,+,。,定义,6.13,设,F,为属性集,U,上的一组函数依赖，,X,、,Y,U,，,X,F,+,=,A,|,X,A,能由,F,根据,Armstrong,公理导出,，,X,F,+,称为属性集,X,关于函数依赖集,F,的闭包。,*,数据依赖的公理系统（续）,引理,6.2,设,F,为属性集,U,上的一组函数依赖，,X,、,Y,U,，,X,Y,能由,F,根据,Armstrong,公理导出的充分必要条件是,Y,X,F,+,。,引理,6.2,的用途,判定,X,Y,是否能由,F,根据,Armstrong,公理导出的问题，就,转化为求出,X,F,+,，判定,Y,是否为,X,F,+,的子集的问题。,*,数据依赖的公理系统（续）,求闭包的算法,算法,6.,1,求属性集,X,（,X,U,）关于,U,上的函数依赖集,F,的闭包,X,F,+,输入：,X,，,F,输出：,X,F,+,步骤：,迭代,*,数据依赖的公理系统（续）,令,X,(,0,),=,X,，,i,=0,求,B,，这里,B,=,A,|(,V,)(,W,)(,V,W,F,V,X,(,i,),A,W,),。,X,(,i,+1,),=,B,X,(,i,),。,判断,X,(,i,+1,),=,X,(,i,),。,若,X,(,i,+1,),与,X,(,i,),相等或,X,(,i,),=,U,，则,X,(,i,),就是,X,F,+,，,算法终止。,若否，则,i,=,i,+,1，返回第,步。,对,X,(i,),中的每个元素，依次检查相应的函数依赖,将依赖它的属性加入,B,*,数据依赖的公理系统（续）,例,6.11,已知关系模式,R,，其中,U,=,A,B,C,D,E,；,F,=,AB,C,B,D,C,E,EC,B,AC,B,。,求(,AB,),F,+,。,*,数据依赖的公理系统（续）,解 ：由算法,6.1,，设,X,(,0,),=,AB,。,计算,X,(,1,),：逐一的扫描,F,集合中各个函数依赖，找左部为,A,、,B,或,AB,的函数依赖。得到两个：,AB,C,，,B,D,。于,是,X,(,1,),=,AB,CD,=,ABCD,。,因为,X,(,0,),X,(,1,),，所以再找出左部为,ABCD,子集的那些函数,依赖，又得到,C,E,，,AC,B,，于是,X,(,2,),=,X,(,1,),BE,=,ABCDE,。,因为,X,(,2,),已等于全部属性集合，所以(,AB,),F,+,=,ABCDE,。,参见爱课程网数据库系统概论,6.3,节,动画,求闭包,*,数据依赖的公理系统（续）,有效性与完备性的含义,有效性：由,F,出发根据,Armstrong,公理推导出来的每一个函数依赖一定在,F,+,中,完备性：,F,+,中的每一个函数依赖，必定可以由,F,出发根据,Armstrong,公理推导出来,*,定理,6.2,Armstrong,公理系统是有效的、完备的。,证明：,1.,有效性,有效性实际上是“正确性”,可由定理,6.1,得证,数据依赖的公理系统（续）,*,2.,完备性,只需证明逆否命题：若函数依赖,X,Y,不能由,F,从,Armstrong,公理导出，那么它必然不为,F,所蕴,涵,分三步证明：,（,1,）,若,V,W,成立，且,V,X,F,+,，则,W,X,F,+,证：因为,V,X,F,+,，所以有,X,V,成立；,因为,X,V,，,V,W,，于是,X,W,成立；,所以,W,X,F,+,。,数据依赖的公理系统（续）,*,（,2,）构造一张二维表,r,，它由下列两个元组构成，可以证明,r,必是,R,的一个关系，即,F,中的全部函数依赖在,r,上成立。,X,F,+,U,-,X,F,+,11.1 00.0,11.1 11.1,若,r,不是,R,的关系，则必由于,F,中有某一个函数依赖,V,W,在,r,上 不成立所致。由,r,的构成可知，,V,必定是,X,F,+,的子集，而,W,不是,X,F,+,的子集，可是由第（,1,）步，,W,X,F,+,，矛盾。,所以,r,必是,R,的一个关系。,数据依赖的公理系统（续）,*,（,3,）若,X,Y,不能由,F,从,Armstrong,公理导出，则,Y,不是,X,F,+,的子集。（引理,6.2,）,因此必有,Y,的子集,Y,满足,Y,U,-,X,F,+,，,则,X,Y,在,r,中不成立，,即,X,Y,必不为,R,蕴涵。,数据依赖的公理系统（续）,*,Armstrong,公理的完备性及有效性说明,:,“,导出,”与,“,蕴涵,”,是两个完全等价的概念,F,+,：为,F,所逻辑蕴涵的函数依赖的全体（定义,6.12,）,F,+,：可以说成由,F,出发借助,Armstrong,公理导出的函数依赖的集合,数据依赖的公理系统（续）,*,定义,6.14,如果,G,+,=,F,+,，就说函数依赖集,F,覆盖,G,（,F,是,G,的覆盖，或,G,是,F,的覆盖），或,F,与,G,等价。,两个函数依赖集等价是指它们的闭包等价,数据依赖的公理系统（续）,函数依赖集等价的充要条件,引理,6.3,F,+,=,G,+,的充分必要条件是,F,G,+,和,G,F,+,。,证,:,必要性显然，只证充分性。,（,1,）若,F,G,+,，则,X,F,+,X,G,+,+,。,（,2,）任取,X,Y,F,+,则有,Y,X,F,+,X,G,+,+,。,所以,X,Y,(,G,+,),+,=,G,+,。即,F,+,G,+,。,（,3,）同理可证,G,+,F,+,，所以,F,+,=,G,+,。,引理,6.3,给出了判断两个函数依赖集等价的可行算法,如何判定,F,G,+,？,只需逐一对,F,中的函数依赖,X,Y,考察,Y,是否属于,X,G,+,+,数据依赖的公理系统（续）,*,定义,6.15,如果函数依赖集,F,满足下列条件，则称,F,为一个极小函数依赖集，亦称为最小依赖集或最小覆盖。,（,1,）,F,中任一函数依赖的右部仅含有一个属性。,（,2,）,F,中不存在这样的函数依赖,X,A,，,使得,F,与,F,-,X,A,等价。,（,3,）,F,中不存在这样的函数依赖,X,A,，,X,有真,子集,Z,使得,F,-,X,A,Z,A,与,F,等价。,即,F,中的函数依赖均不能由,F,中其他函数依赖导出,F,中各函数依赖左部均为最小属性集（不存在冗余属性）,数据依赖的公理系统（续）,*,例,6.12,考察,6.1,节中的关系模式,S,，其中：,U,=S,no,S,dept,M,name,C,no,G,rade,，,F,=S,no,S,dept,S,dept,M,name,(S,no,C,no,),Gr,ade,F,是最小覆盖,F,=S,no,S,dept,S,no,M,name,S,dept,M,name,(S,no,C,no,)G,rade,(Sn,o,S,dept,)S,dept,F,不是最小覆盖,因为：,F,- S,no,M,name,与,F,等价,F,- (S,no,S,dept,)S,dept,也与,F,等价,参见爱课程网数据库系统概论,6.2,节,动画,最小覆盖集难点解析,数据依赖的公理系统（续）,*,数据依赖的公理系统（续）,定理,6.3,每一个函数依赖集,F,均等价于一个极小函数依赖集,F,m,。此,F,m,称为,F,的最小依赖集。,证：构造性证明，分三步对,F,进行“极小化处理”，找出,F,的一个最小依赖集。,（,1,）逐一检查,F,中各函数依赖,FD,i,：,X,Y,，,若,Y,=,A,1,A,2,A,k,，,k,2,，,则用,X,A,j,|,j,=1,2,k,来取代,X,Y,。,引理,6.1,保证了,F,变换前后的等价性。,*,数据依赖的公理系统（续）,（,2,）逐一检查,F,中各函数依赖,FD,i,：,X,A,，,令,G,=,F,-,X,A,，,若,A,X,G,+,，则从,F,中去掉此函数依赖。,由于,F,与,G,等价的充要条件是,A,X,G,+,因此,F,变换前后是等价的。,*,数据依赖的公理系统（续）,（,3,）逐一取出,F,中各函数依赖,FD,i,：,X,A,，,设,X,=,B,1,B,2,B,m,，,m,2,，,逐一考查,B,i,（,i,=1,，,2,，,，,m,），,若,A,(,X-B,i,),F,+,，则以,X,-,B,i,取代,X,。,由于,F,与,F,-,X,A,Z,A,等价的充要条件是,A,Z,F,+,，其中,Z,=,X,-,B,i,，,因此,F,变换前后是等价的。,最后剩下的,F,就一定是极小依赖集。,因为对,F,的,每一次“改造”都,保证了改造前后的两个函数,依赖集等价，因此剩下的,F,与原来的,F,等价。,证毕,*,数据依赖的公理系统（续）,定理,6.3,的证明过程,是求,F,极小依赖集的过程,也是检验,F,是否为极小依赖集的一个算法,若改造后的,F,与原来的,F,相同，说明,F,就是一个最小依赖集,*,数据依赖的公理系统（续）,例,6.13,F,=,A,B,B,A,B,C,A,C,C,A,F,的最小依赖集：,F,m1,= ,A,B,B,C,C,A,*,数据依赖的公理系统（续）,F,的最小依赖集,F,m,不一定是唯一的，它与对各函数依赖,FD,i,及,X,A,中,X,各属性的处置顺序有关。,*,数据依