数据库原理第6章(最终稿)ppt课件

数据库系统概论AnIntroductiontoDatabaseSystem第六章关系数据理论,问题的提出,数据库设计数据库概念设计(ER模型)数据库逻辑设计数据库物理设计,问题?1.针对一个具体问题，应如何构造一个适合于它的数据模式，即应该构造几个关系，每个关系由哪些属性组成等2.设计的工具:规范化理论,例:职员部门数据库的两种可能设计,冗余数据多容易出现数据不一致,方案一,方案二,第六章关系数据理论,6.1问题的提出6.2规范化6.3数据依赖的公理系统*6.4模式的分解,概念回顾,关系：描述实体、属性、实体间的联系。从形式上看，它是一张二维表，是所涉及属性的笛卡尔积的一个子集。关系模式：关系的描述。关系数据库：基于关系模型的数据库，利用关系来描述现实世界。从形式上看，它由一组关系组成。关系数据库的模式：定义这组关系的关系模式的全体。,概念回顾(续),关系模式的形式化定义:R(U,D,DOM,F)R：关系名U：组成该关系的属性名集合D：属性组U中属性所来自的域DOM：属性向域的映象集合F：属性间数据的依赖关系集合可以将关系模式看成一个三元组：R(U,F),本章讨论:F,函数依赖FunctionalDependency简记为FD,多值依赖MultivaluedDependency简记为MVD,函数依赖的举例,例：描述学校的数据库：学生的学号（Sno）、所在系（Sdept）系主任姓名（Mname）、课程名（Cname）成绩（Grade）设计为关系模式：Student其中:USno,Sdept,Mname,Cname,GradeF是什么?,关系模式Student中存在的问题,数据冗余太大见教材P171页浪费大量的存储空间例：每一个系主任的姓名重复出现、学生姓名也重复更新异常（UpdateAnomalies）数据冗余，更新数据时，维护数据完整性代价大。例：某系更换系主任后，系统必须修改与该系学生有关的每一个元组,关系模式Student中存在的问题,插入异常（InsertionAnomalies）该插的数据插不进去例，如果一个系刚成立，尚无学生，我们就无法把这个系及其系主任的信息存入数据库。删除异常（DeletionAnomalies）不该删除的数据不得不删例，如果某个系的学生全部毕业了，我们在删除该系学生信息的同时，把这个系及其系主任的信息也丢掉了。,数据依赖对关系模式的影响,结论：Student关系模式不是一个好的模式。“好”的模式：不会发生插入异常、删除异常、更新异常，数据冗余应尽可能少。原因：由存在于模式中的某些数据依赖引起的解决方法：通过分解关系模式来消除其中不合适的数据依赖。,什么是函数依赖,1.非形式化定义:”函数”依赖表示为：X1X2X3XnY，类似于Y=f(X)即：取一组值，分别对应于属性X1X2X3Xn，结果对应于Y产生唯一值(或者是空值),是通过一个关系中属性间值的相等与否体现出来的数据间的相互关系是现实世界属性间相互联系的抽象是数据内在的性质是语义的体现,函数依赖的举例（续）,F是由如下的语义来体现：一个系有若干学生，一个学生只属于一个系；一个系只有一名主任；一个学生可以选修多门课程,每门课程有若干学生选修;每个学生所学的每门课程都有一个成绩。,例：描述学校的数据库：学生的学号（Sno）、所在系（Sdept）系主任姓名Mname）、课程名（Cname）、绩（Grade）设计为关系模式：Student其中:USno,Sdept,Mname,Cname,GradeF是什么?,函数依赖的举例（续）,属性组U上的一组函数依赖F：FSnoSdept,SdeptMname,(Sno,Cname)Grade,6.2规范化,规范化理论是用来改造关系模式，通过分解关系模式来消除其中不合适的数据依赖，以解决插入异常、删除异常、更新异常和数据冗余问题。,6.2.1函数依赖,一、函数依赖二、平凡函数依赖与非平凡函数依赖三、完全函数依赖与部分函数依赖四、传递函数依赖,一、函数依赖,定义6.1设R(U)是一个属性集U上的关系模式，X和Y是U的子集，r为R(U)的任意一个可能的关系。,t1,t2,A,t1,t2r当t1X=t2X时，必有t1Y=t2Y成立则称“X函数确定Y”或“Y函数依赖于X”。X称为这个函数依赖的决定属性集记作XY。,类似Y=f(X),XY的进一步解释,新关系X,Y(R)的元组在X分量上的值不重复,对于R的任意一个可能的关系r中的元组，由X上的分量可惟一确定Y上的分量,对于R的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等。,函数依赖（续）,说明：,1.函数依赖不是指关系模式R的某个或某些关系实例满足的约束条件，而是指R的所有关系实例均要满足的约束条件。2.函数依赖是语义范畴的概念，只能根据数据的语义来确定函数依赖。3.数据库设计者可以对现实世界作强制的规定。例如规定不允许同名人出现，函数依赖“姓名年龄”成立。所插入的元组必须满足规定的函数依赖，若发现有同名人存在，则拒绝装入该元组。,函数依赖的相关符号含义,若XY，并且YX,则记为XY。若Y不函数依赖于X,则记为XY。,函数依赖（续）,例:Student(Sno,Sname,Ssex,Sage,Sdept)假设不允许重名，则有:SnoSsex，SnoSage,SnoSdept，SnoSname,SnameSsex，SnameSage，SnameSdept但SsexSage,二、平凡函数依赖与非平凡函数依赖,在关系模式R(U)中，对于U的子集X和Y，如果XY，但YX，则称XY是非平凡的函数依赖若XY，但YX,则称XY是平凡的函数依赖例：在关系SC(Sno,Cno,Grade)中，非平凡函数依赖：(Sno,Cno)Grade平凡函数依赖：(Sno,Cno)Sno，(Sno,Cno)Cno,对于任一关系模式，平凡函数依赖都是必然成立的。仅需讨论非平凡函数依赖,三、完全函数依赖与部分函数依赖,定义6.2在关系模式R(U)中，如果XY，并且对于X的任何一个真子集X，都有XY,则称Y完全函数依赖于X，记作XFY。若XY，但Y不完全函数依赖于X，则称Y部分函数依赖于X，记作XPY。,完全函数依赖与部分函数依赖（续）,例:在关系SC(Sno,Cno,Grade)中，由于：SnoGrade，CnoGrade，因此：(Sno,Cno)FGrade,四、传递函数依赖,定义6.3在关系模式R(U)中，如果XY，YZ，且YX，YX，则称Z传递函数依赖于X。注:如果YX，即XY，则Z直接依赖于X。例:在关系Std(Sno,Sdept,Mname)中，有：SnoSdept，SdeptMnameMname传递函数依赖于Sno,6.2.2码,定义6.4设K为关系模式R中的属性或属性组合。若KFU，则K称为R的一个侯选码（CandidateKey）。若关系模式R有多个候选码，则选定其中的一个做为主码（Primarykey）。主属性与非主属性ALLKEY,外部码,定义6.5关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R的外部码（Foreignkey）也称外码主码又和外部码一起提供了表示关系间联系的手段。,6.2.3范式,范式是符合某一种级别的关系模式的集合。范式的种类：第一范式(1NF)第二范式(2NF)第三范式(3NF)BC范式(BCNF)第四范式(4NF)第五范式(5NF),6.2.3范式,各种范式之间存在联系：某一关系模式R为第n范式，可简记为RnNF。,6.2.41NF,1NF的定义如果一个关系模式R的所有属性值都是不可分的基本数据项，则R1NF。第一范式是对关系模式的最起码的要求。不满足第一范式的数据库模式不能称为关系数据库。但是满足第一范式的关系模式并不一定是一个好的关系模式。,例:关系模式SLC(Sno,Sdept,Sloc,Cno,Grade)Sloc为学生住处，假设每个系的学生住在同一个地方。函数依赖包括：(Sno,Cno)FGradeSnoSdept(Sno,Cno)PSdeptSnoSloc(Sno,Cno)PSlocSdeptSloc,SLC的一个实例,候选码？,SLC的候选码为(Sno,Cno)SLC满足第一范式。非主属性Sdept和Sloc部分函数依赖于码(Sno,Cno),SLC存在的问题,插入异常,删除异常,数据冗余度大,修改复杂,SLC不是一个好的关系模式,原因Sdept、Sloc部分函数依赖于码。解决方法SLC分解为两个关系模式，以消除这些部分函数依赖SC（Sno，Cno，Grade）SL（Sno，Sdept，Sloc）,原来的函数依赖图：,SLC的码为(Sno,Cno)SLC满足第一范式。非主属性Sdept和Sloc部分函数依赖于码(Sno,Cno),分解后的函数依赖图：,第二范式：2NF,2NF的定义定义6.6若关系模式R1NF，并且每一个非主属性都完全函数依赖于R的码，则R2NF。例：SLC(Sno,Sdept,Sloc,Cno,Grade)1NFSLC(Sno,Sdept,Sloc,Cno,Grade)2NFSC（Sno，Cno，Grade）2NFSL（Sno，Sdept，Sloc）2NF,第二范式（续）,采用投影分解法将一个1NF的关系分解为多个2NF的关系，可以在一定程度上减轻原1NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。将一个1NF关系分解为多个2NF的关系，并不能完全消除关系模式中的各种异常情况和数据冗余。,6.2.5第三范式：3NF,例：2NF关系模式SL(Sno,Sdept,Sloc)中（Sno，Sdept，Sloc）2NF函数依赖：SnoSdeptSdeptSlocSnoSlocSloc传递函数依赖于Sno，即SL中存在非主属性对码的传递函数依赖。,T,3NF,函数依赖图：,T,3NF,解决方法采用投影分解法，把SL分解为两个关系模式，以消除传递函数依赖：SD（Sno，Sdept）DL（Sdept，Sloc）SD的码为Sno，DL的码为Sdept。,3NF,SD的码为Sno，DL的码为Sdept。,3NF,3NF的定义定义6.8关系模式R中若不存在这样的码X、属性组Y及非主属性Z（ZY）,使得XY，YX，YZ，成立，则称R3NF。例，SL(Sno,Sdept,Sloc)2NFSL(Sno,Sdept,Sloc)3NFSD（Sno，Sdept）3NFDL（Sdept，Sloc）3NF,3NF,若R3NF，则R的每一个非主属性既不部分函数依赖于候选码也不传递函数依赖于候选码。若R中属性全部为主属性，则R3NF。如果R3NF，则R中非主属性之间无依赖性(3NF中消除了非关键字属性间的函数依赖)如果R3NF，则R也是2NF。(如何证明：如果R3NF，则R也是2NF),证明:若R3NF，则R2NF,反证法：假设R3NF，而R2NF,则R中存在非主属性Z（ZX）,部分函数依赖于码X，即：XZ,因此有属性组Y（YX）使得XY，YX，YZ，成立,显然这与R3NF的定义矛盾。假设不成立。,P,注意:3NF中不存在这样的码X、属性组Y及非主属性Z（ZY）,使得XY，YX，YZ，成立,6.2.6BC范式（BCNF）,定义6.9设关系模式R1NF，如果对于R的每个函数依赖XY，若Y不属于X，则X必含有候选码，那么RBCNF。,等价定义：每个非平凡的函数依赖的左边必须包含候选码,若RBCNF，则：每一个决定属性集（因素）都包含（候选）码R中的所有属性（主、非主属性）都完全函数依赖于码若R3NF则R不一定BCNF若RBCNF，则R3NF（如何证明?）,证明:若RBCNF，则R3NF,反证法：假设RBCNF，而R3NF,则R中存在传递函数依赖，即：XY(YX)、YZ（ZY）显然Y不是候选码（因为YX）因此，YZ（ZY）中左边不含码,这与RBCNF矛盾。假设不成立。,如何区别BCNF与3NF,3NF是放宽条件的BCNF：BCNF：对于任何非平凡的依赖XY，X必须包含候选码。3NF：对于任何非平凡的依赖XY，或者X包含候选码，或者Y是某个候选码的组成部分。,举例分析,例1：在关系模式STJ（S，T，J）中，S表示学生，T表示教师，J表示课程。每一教师只教一门课，每门课由若干教师教：TJ某一学生选定某门课，就确定了一个固定的教师：(S，J)T某个学生选修某个教师的课就确定了所选课的名称：(S，T)J所以：F=(S，J)T，(S，T)J，TJ,举例分析（续）,(S，J)和(S，T)都可以作为候选码,举例分析（续）,每个FD的左边或是候选码，或者每个FD的右边是候选码的组成部分STJ3NF但STJBCNF因为存在:TJ，T是决定属性集，T不是码，J属于候选码的组成部分。,F=(S，J)T，(S，T)J，TJ,举例分析（续）,解决方法：将STJ分解为二个关系模式：SJ(S，J)BCNF，TJ(T，J)BCNF,BCNF的相关结论,如果关系模式RBCNF，必定有R3NF如果R3NF，且R只有一个候选码，则R必属于BCNF。任何二元关系模式的最高范式属于BCNF如果R的码为全码（all-key）,则RBCNF若RBCNF，则在函数依赖的范畴内R已经实现了彻底的分离（消除了插、删、改异常，但尚不能消除冗余）,BCNF的关系模式所具有的性质,所有非主属性都完全函数依赖于每个候选码所有主属性都完全函数依赖于每个不包含它的候选码没有任何属性完全函数依赖于非码的任何一组属性,总结：怎样判断3NF和BCNF？,若R3NF，则R的每一个非主属性既不部分函数依赖于候选码也不传递函数依赖于候选码。若R中属性全部为主属性，则R3NF。3NF：对于任何非平凡的依赖XY，或者X包含候选码，或者Y是某个候选码的组成部分。,RBCNF：每一个决定属性集（因素）都包含（候选）码，即对于任何非平凡的依赖XY，X必须包含候选码。R中的所有属性（主、非主属性）都完全函数依赖于码。如果R3NF，且R只有一个候选码，则R必属于BCNF。任何二元关系模式的最高范式属于BCNF。如果R的码为全码（all-key）,则RBCNF。没有任何属性完全函数依赖于非码的任何一组属性,怎样判断3NF和BCNF：,分析下列关系的范式：,例2:R(Sno,ID,Sdept,Sage),1、码：Sno或ID2、非主属性对码不部分依赖，也不传递依赖R3NF3、在所有的函数依赖中，左部均含码RBCNF,分析下列关系的范式：,R(Sno,Cno,Pno)名次(假设同一同课程无并列名次),1、码：（Sno,Cno)或(Cno,Pno)2、在所有的函数依赖中，左部均含码RBCNF,分析下列关系的范式：,例3:Booking(title，cinema，city)订票（电影名，电影院，城市）,小结,cinemacity一个电影院只能建在一个城市中(title,city)cinema在同一个城市中预订的同一种电影票不会是两个不同的电影院的,1、码：(title,city)或(title,cinema)2、在所有的函数依赖中，或左部含码，或右部是码的组成部分R3NF，RBCNF,例4:学校中某一门课程由多个教师讲授，他们使用相同的一套参考书。关系模式Teaching(C,T,B)课程C、教师T和参考书B,表6.3,用二维表表示Teaching,多值依赖（续）,TeachingBCNF:Teach具有唯一候选码(C，T，B)，即全码Teaching模式中存在的问题(1)数据冗余度大：有多少名任课教师，参考书就要存储多少次,多值依赖（续）,(2)插入操作复杂：当某一课程增加一名任课教师时，该课程有多少本参照书，就必须插入多少个元组例如物理课增加一名教师刘明，需要插入三个元组：（物理，刘明，普通物理学）（物理，刘明，光学原理）（物理，刘明，物理习题集）,多值依赖与第四范式（续）,(3)删除操作复杂：某一门课要去掉一本参考书，该课程有多少名教师，就必须删除多少个元组(4)修改操作复杂：某一门课要修改一本参考书，该课程有多少名教师，就必须修改多少个元组产生原因:存在多值依赖,一、多值依赖,定义6.9(p179)设R(U)是一个属性集U上的一个关系模式，X、Y和Z是U的子集，并且ZUXY，多值依赖XY成立当且仅当对R的任一关系r，r在（X，Z）上的每个值对应一组Y的值，这组值仅仅决定于X值而与Z值无关例Teaching（C,T,B）对于每一门课程值（C），有一组教师值与之对应（T），而不论是什么参考书（B）。所以,CT,多值依赖另一定义（p179),在R（U）的任一关系r中，如果存在元组t，s使得tX=sX，那么就必然存在元组w，vr，（w，v可以与s，t相同），使得wX=vX=tX，而wY=tY，wZ=sZ，vY=sY，vZ=tZ（即交换s，t元组的Y值所得的两个新元组必在r中），则Y多值依赖于X，记为XY。这里，X，Y是U的子集，Z=U-X-Y。txy1z2sxy2z1wxy1z1vxy2z2,多值依赖XY的另一定义,ts(r(t)r(s)tX=sXw(r(w)w(X)=t(X)w(Y)=t(Y)w(Z)=s(Z),txy1z2sxy2z1wxy1z1vxy2z2,ts(r(t)r(s)tX=sXv(r(v)v(X)=s(X)v(Y)=s(Y)v(Z)=t(Z),XYZ,多值依赖直观的含义:,t,w,s,v,若R中有两个元组在X属性上取值相等，则交换这两个元组在Y属性上的取值得到的两个元组也必在R中,R,相等,思考：,课程、教师、时间、教室、学生、分数R（C，T，H，R，S，G）c1t1h1r2s1g1c1t1h2r3s1g1c1t1h3r2s1g1c1t1h1r2s2g2c1t1h2r3s2g2c1t1h3r2s2g2,语义：对于某教师所教的某门课（C，T）可有一组“时间教室”（H，R）与之对应，而与“学生成绩”无关,(C,T)(H,R)(C,T)(S,G),多值依赖（续）,平凡多值依赖和非平凡的多值依赖若XY，而Z，则称XY为平凡的多值依赖否则称XY为非平凡的多值依赖,多值依赖的性质,（1）多值依赖具有对称性若XY，则XZ，其中ZUXY多值依赖的对称性可以用完全二分图直观地表示出来。,多值依赖的对称性,XY,XZ,多值依赖的对称性,课程C教师T课程C参考书B,多值依赖的性质（P180）,2）多值依赖具有传递性若XY，YZ，则XZ-Y3）函数依赖是多值依赖的特殊情况:若XY，则XY。(复制规则)4）若XY，XZ，则XYZ。5）若XY，XZ，则XYZ。6）若XY,XZ,则XY-Z,XZ-Y。,多值依赖与函数依赖的联系与区别,联系：函数依赖是多值依赖的特殊情况XY：描述的是X与Y之间的一对一的联系XY：描述的是X与Y之间的一对多的联系但是，在XY中，若对于X的每一个值，Y仅有一个值与之对应时则XY变成XY。区别：XY在R上是否成立仅与X、Y有关XY在R上是否成立不仅与X、Y有关,而且与UXY有关XY在R上成立，则必有XY(其中YY)XY在R上成立，则不一定有XY(其中YY),6.2.8第四范式（4NF）,定义6.10关系模式R1NF，如果对于R的每个非平凡多值依赖XY（YX），X都含有候选码，则R4NF。如果R4NF，则RBCNF不允许有非平凡且非函数依赖的多值依赖允许的非平凡多值依赖实际上是函数依赖,第四范式（续）,例1：Teach(C,T,B)4NF存在非平凡的多值依赖CT，且C不是候选码用投影分解法把Teach分解为如下两个关系模式：CT(C,T)4NFCB(C,B)4NFCT，CB是平凡多值依赖,几条结论,当R中的依赖只含FD时，4NF就是BCNF4NF必定为BCNF，反之不然若一个R的码为全码，且无MFD，则R4NF若R的依赖集中所有的候选关键字都是决定因素，则R4NF。,6.2.9规范化小结,关系数据库的规范化理论是数据库逻辑设计的工具。一个关系只要其分量都是不可分的数据项，它就是规范化的关系，但这只是最基本的规范化。规范化程度可以有多个不同的级别,规范化（续）,规范化程度过低的关系不一定能够很好地描述现实世界，可能会存在插入异常、删除异常、修改复杂、数据冗余等问题一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式集合，这种过程就叫关系模式的规范化,规范化（续）,关系模式规范化的基本步骤1NF消除非主属性对码的部分函数依赖消除决定属性2NF集非码的非平消除非主属性对码的传递函数依赖凡函数依赖3NF消除主属性对码的部分和传递函数依赖BCNF消除非平凡且非函数依赖的多值依赖4NF,规范化的基本思想,消除不合适的数据依赖使各关系模式达到某种程度的“分离”采用“一事一地”的模式设计原则让一个关系描述一个概念、一个实体或者实体间的一种联系。若多于一个概念就把它“分离”出去所谓规范化实质上是概念的单一化,规范化（续）,不能说规范化程度越高的关系模式就越好在设计数据库模式结构时，必须对现实世界的实际情况和用户应用需求作进一步分析，确定一个合适的、能够反映现实世界的模式上面的规范化步骤可以在其中任何一步终止,第六章关系数据理论,6.1问题的提出6.2规范化6.3数据依赖的公理系统*6.4模式的分解,6.3数据依赖的公理系统,逻辑蕴含定义6.11对于满足一组函数依赖F的关系模式R，其任何一个关系r，若函数依赖XY都成立,则称F逻辑蕴含XY,Armstrong公理系统,一套推理规则（1974年）用途求给定关系模式的码从一组函数依赖求得蕴含的函数依赖,1.Armstrong公理系统,设有关系模式RAl.自反律（Reflexivity）：若YXU，则XY为F所蕴含。A2.增广律（Augmentation）：若XY为F所蕴含，且ZU，则XZYZ为F所蕴含。A3.传递律（Transitivity）：若XY及YZ为F所蕴含，则XZ为F所蕴含。注意：由自反律所得到的函数依赖均是平凡的函数依赖。,定理6.lArmstrong推理规则是正确的,（l）自反律:若YXU，则XY为F所蕴含证:设YXU对R的任一关系r中的任意两个元组t，s：若tX=sX，由于YX，有ty=sy，所以XY成立.自反律得证,定理6.l,(2)增广律:若XY为F所蕴含，且ZU，则XZYZ为F所蕴含。证：设XY为F所蕴含，且ZU。设R的任一关系r中任意的两个元组t，s；若tXZ=sXZ，则有tX=sX和tZ=sZ；由XY，于是有tY=sY，所以tYZ=sYZ，所以XZYZ为F所蕴含.增广律得证。,定理6.l,(3)传递律：若XY及YZ为F所蕴含，则XZ为F所蕴含。证：设XY及YZ为F所蕴含。对R的任一关系r中的任意两个元组t，s。若tX=sX，由于XY，有tY=sY；再由YZ，有tZ=sZ，所以XZ为F所蕴含.传递律得证。,2.导出规则,1.根据A1，A2，A3这三条推理规则可以得到下面三条推理规则：合并规则：由XY，XZ，有XYZ。（A2，A3）伪传递规则：由XY，WYZ，有XWZ。（A2，A3）分解规则：由XY及ZY，有XZ。（A1，A3）,导出规则,2.根据合并规则和分解规则，可得引理5.1引理6.lXA1A2Ak成立的充分必要条件是XAi成立（i=l，2，k）。,3.函数依赖闭包F+,定义6.l2在关系模式R中为F所逻辑蕴含的函数依赖的全体叫作F的闭包，记为F+。,求F的闭包举例：,设有F=XY,YZ,求F+F+=X,Y,Z,XY,XZ,YZ,XYZ,XX,YY,ZZ,XYX,XZX,YZY,XYZX,XY,YZ,XYY,XZY,YZZ,XYZY,XZ,YYZ,XYZ,XZZ,YZYZ,XYZZ,XXY,XYXY,XZXY,XYZXY,XXZ,XYYZ,XZXZ,XYZYZXYZ,XYXZ,XZXY,XYZXZ,XZYZ,XYXYZ,XZXYZ,XYZXYZ,共计42个，计算F+是NP完全问题，若有F=XA1A2An,F+2n,函数依赖的判定-属性闭包XF+,定义6.13设F为属性集U上的一组函数依赖，XU，XF+=A|XA能由F根据Armstrong公理导出，XF+称为属性集X关于函数依赖集F的闭包,函数依赖的判定-属性闭包XF+,引理6.2设F为属性集U上的一组函数依赖，X，YU，XY能由F根据Armstrong公理导出的充分必要条件是YXF+用途将判定XY是否能由F根据Armstrong公理导出的问题，就转化为求出XF+，判定Y是否为XF+的子集的问题,XYYXF+,如何求属性闭包XF+（P184）,算法6.1求属性集X（XU）关于U上的函数依赖集F的闭包XF+输入：X，F输出：XF+步骤：（1）令X（0）=X，i=0（2）求B，这里B=A|(V)(W)(VWFVX（i）AW)；（3）X（i+1）=BX（i）,A来自F中某个依赖的右部成员，而该依赖的左部是当前X（i）的子集,算法6.l,（4）判断X（i+1）=X（i）吗?（5）若相等或X（i）=U,则X（i）就是XF+,算法终止。（6）若否，则i=i+l，返回第（2）步。对于算法6.l，令ai=|X（i）|，ai形成一个步长大于1的严格递增的序列，序列的上界是|U|，因此该算法最多|U|-|X|次循环就会终止。,U=A,B,C,D;F=AB,BCD;A+=AB.C+=C.(AC)+=?,Example,AC,B,Example,AC,D,B,U=A,B,C,D;AB,BCD.(AC)+=ABCD.,求XF+举例:,例1已知关系模式R，其中U=A，B，C，D，E；F=ABC，BD，CE，ECB，ACB。求（AB）F+。解设X（0）=AB；(1)计算X（1）:逐一的扫描F集合中各个函数依赖，找左部为A，B或AB的函数依赖。得到两个：ABC，BD。于是X（1）=ABCD=ABCD。,求XF+举例:,(2)因为X（0）X（1），所以再找出左部为ABCD子集的那些函数依赖，又得到ABC，BD，CE，ACB，于是X（2）=X（1）BCDE=ABCDE。(3)因为X（2）=U，算法终止所以（AB）F+=ABCDE。,输入:R的U及R上的F输出:R的所有候选码Key(1)将R的所有属性分为L、R、N、LR四类并令X代表L、N两类，Y代表LR类(2)求X+，若X+=U，则X是惟一Key，转(4)(3)从Y中取一个属性A，求(XA)+，若(XA)+=U，则XA是Key，否则，从Y中取二个属性，重复(3)(4)停止，输出所有Key,设有关系模式：R其中U为R的属性集，即：U=A1，A2，AnF为R的函数依赖集。求候选码=？,练习,设有关系模式R(A,B,C,D),其上的函数依赖集为：F=AC,CA,BAC,DAC1、计算(AD)F+2、求R的候选码,4.Armstrong公理系统的有效性与完备性,有效性：由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F+中/*Armstrong正确完备性：F+中的每一个函数依赖f，必定可以由F出发根据Armstrong公理推导出来/*Armstrong公理够用，完全完备性的逆否命题:若f不能用Armstrong公理推导出来，则fF+,5.函数依赖集等价(p186),定义6.14如果G+=F+，就说函数依赖集F覆盖G（F是G的覆盖，或G是F的覆盖），或F与G等价。讨论函数依赖集等价的意义：一个大的FD集如何用一个等价的小的FD集代替,函数依赖集等价的充要条件,引理6.3F+=G+的充分必要条件是FG+，和GF+证:必要性显然，只证充分性。（1）若FG+，则XF+XG+。（2）任取XYF+则有YXF+XG+。所以XY(G+）+=G+。即F+G+。（3）同理可证G+F+，所以F+=G+。,6.最小依赖集,定义6.15如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖或正则覆盖。(1)F中任一函数依赖的右部仅含有一个属性。(2)F中不存在这样的函数依赖XA，使得F与F-XA等价。(3)F中不存在这样的函数依赖XA，X有真子集Z使得F-XAZA与F等价。,最小依赖集,例2对于6.l节中的关系模式S，其中：U=SNO，SDEPT，MN，CNAME，G，F=SNOSDEPT，SDEPTMN，（SNO，CNAME）G设F=SNOSDEPT，SNOMN，SDEPTMN，(SNO，CNAME)G，(SNO，SDEPT)SDEPTF是最小覆盖，而F不是。因为：F-SNOMN与F等价F-(SNO，SDEPT)SDEPT也与F等价F-(SNO，SDEPT)SDEPTSNOSDEPT也与F等价,7.极小化过程,定理6.3每一个函数依赖集F均等价于一个极小函数依赖集Fm。此Fm称为F的最小依赖集证:构造性证明，依据定义分三步对F进行“极小化处理”，找出F的一个最小依赖集。(1)逐一检查F中各函数依赖FDi：XY，若Y=A1A2Ak，k2，则用XAj|j=1，2，k来取代XY。引理6.1保证了F变换前后的等价性。,极小化过程,(2)逐一检查F中各函数依赖FDi：XA，令G=F-XA，若AXG+，则从F中去掉此函数依赖。由于F与G=F-XA等价的充要条件是AXG+因此F变换前后是等价的。,极小化过程,(3)逐一取出F中各函数依赖FDi：XA，设X=B1B2Bm，逐一考查Bi（i=l，2，m），若A（X-Bi）F+，则以X-Bi取代X。由于F与F-XAZA等价的充要条件是AZF+，其中Z=X-Bi因此F变换前后是等价的。,极小化过程,由定义，最后剩下的F就一定是极小依赖集。因为对F的每一次“改造”都保证了改造前后的两个函数依赖集等价，因此剩下的F与原来的F等价。证毕定理6.3的证明过程也是求F极小依赖集的过程,极小化步骤(记忆)：,第一步：使每一个FD的右部属性单一化(采用分解规则)第二步：消除多余FDXA多余？，只看AXG+？(令G=F-XA)第三步：消除每一个FD的左部多余属性对于B1B2BmA，Bi多余？只看A(X-Bi)F+?(令X=B1B2Bm),极小化过程,例3F=AB，BA，BC，AC，CAFm1、Fm2都是F的最小依赖集：Fm1=AB，BC，CAFm2=AB，BA，AC，CAF的最小依赖集Fm不一定是唯一的它与对各函数依赖FDi及XA中X各属性的处置顺序有关,极小化过程,极小化过程(定理6.3的证明)也是检验F是否为极小依赖集的一个算法若改造后的F与原来的F相同，说明F本身就是一个最小依赖集,极小化过程,练习F=AB,AC,BC,ABC求F的最小依赖集,F=AB,BC,第六章关系数据理论,6.1数据依赖6.2规范化6.3数据依赖的公理系统6.4模式的分解,6.4模式的分解(选学内容),把低一级的关系模式分解为若干个高一级的关系模式的方法并不是唯一的只有能够保证分解后的关系模式与原关系模式等价，分解方法才有意义,关系模式分解的标准,三种模式分解的等价定义分解具有无损连接性分解要保持函数依赖分解既要保持函数依赖，又要具有无损连接性,模式的分解（续）,定义6.16关系模式R的一个分解：=R1，R2，RnU=U1U2Un，且不存在UiUj，Fi为F在Ui上的投影定义6.17函数依赖集合XY|XYF+XYUi的一个覆盖Fi叫作F在属性Ui上的投影,模式的分解（续）,例:SL（Sno，Sdept，Sloc）F=SnoSdept,SdeptSloc,SnoSlocSL2NF存在插入异常、删除异常、冗余度大和修改复杂等问题分解方法可以有多种,模式的分解（续）,SLSnoSdeptSloc95001CSA95002ISB95003MAC95004ISB95005PHB,模式的分解（续）,1.SL分解为下面三个关系模式：SN(Sno)SD(Sdept)SO(Sloc),分解后的关系为：,SNSDSOSnoSdeptSloc95001CSA95002ISB95003MAC95004PH95005,模式的分解（续）,分解后的数据库丢失了许多信息例如无法查询95001学生所在系或所在宿舍。如果分解后的关系可以通过自然连接恢复为原来的关系，那么这种分解就没有丢失信息,模式的分解（续）,2.SL分解为下面二个关系模式：NL(Sno,Sloc)DL(Sdept,Sloc)分解后的关系为：NLDLSnoSlocSdeptSloc95001ACSA95002BISB95003CMAC95004BPHB95005B,