《关系数据理论li》PPT课件.ppt

中国人民大学信息学院计算机系,数据库系统概论AnIntroductiontoDatabaseSystem第五章关系数据理论,第六章关系数据理论,6.1问题的提出6.2规范化6.3数据依赖的公理系统*6.4模式的分解6.5小结,6.1问题的提出,关系数据库逻辑设计针对具体问题，如何构造一个适合于它的数据模式数据库逻辑设计的工具关系数据库的规范化理论,问题的提出,一、概念回顾二、关系模式的形式化定义三、什么是数据依赖四、关系模式的简化定义五、数据依赖对关系模式影响,一、概念回顾,关系：描述实体、属性、实体间的联系。从形式上看，它是一张二维表，是所涉及属性的笛卡尔积的一个子集。关系模式：用来定义关系。关系数据库：基于关系模型的数据库，利用关系来描述现实世界。从形式上看，它由一组关系组成。关系数据库的模式：定义这组关系的关系模式的全体。,二、关系模式的形式化定义,关系模式由五部分组成，即它是一个五元组：R(U,D,DOM,F)R：关系名U：组成该关系的属性名集合D：属性组U中属性所来自的域DOM：属性向域的映象集合F：属性间数据的依赖关系集合,三、什么是数据依赖,1.完整性约束的表现形式限定属性取值范围：例如学生成绩必须在0-100之间定义属性值间的相互关联（主要体现于值的相等与否），这就是数据依赖，它是数据库模式设计的关键,什么是数据依赖（续）,2.数据依赖是通过一个关系中属性间值的相等与否体现出来的数据间的相互关系是现实世界属性间相互联系的抽象是数据内在的性质是语义的体现,什么是数据依赖（续）,3.数据依赖的类型函数依赖（FunctionalDependency，简记为FD）多值依赖（MultivaluedDependency，简记为MVD）其他,四、关系模式的简化表示,关系模式R（U,D,DOM,F）简化为一个三元组：R（U,F）当且仅当U上的一个关系r满足F时，r称为关系模式R（U,F）的一个关系,五、数据依赖对关系模式的影响,例：描述学校的数据库：学生的学号（Sno）、所在系（Sdept）系主任姓名（Mname）、课程名（Cname）成绩（Grade）单一的关系模式：StudentUSno,Sdept,Mname,Cname,Grade,数据依赖对关系模式的影响（续）,学校数据库的语义：一个系有若干学生，一个学生只属于一个系；一个系只有一名主任；一个学生可以选修多门课程，每门课程有若干学生选修；每个学生所学的每门课程都有一个成绩。,数据依赖对关系模式的影响（续）,属性组U上的一组函数依赖F：FSnoSdept,SdeptMname,(Sno,Cname)Grade,关系模式Student中存在的问题,数据冗余太大浪费大量的存储空间例：每一个系主任的姓名重复出现更新异常（UpdateAnomalies）数据冗余，更新数据时，维护数据完整性代价大。例：某系更换系主任后，系统必须修改与该系学生有关的每一个元组,关系模式Student中存在的问题,插入异常（InsertionAnomalies）该插的数据插不进去例，如果一个系刚成立，尚无学生，我们就无法把这个系及其系主任的信息存入数据库。删除异常（DeletionAnomalies）不该删除的数据不得不删例，如果某个系的学生全部毕业了，我们在删除该系学生信息的同时，把这个系及其系主任的信息也丢掉了。,数据依赖对关系模式的影响（续）,结论：Student关系模式不是一个好的模式。“好”的模式：不会发生插入异常、删除异常、更新异常，数据冗余应尽可能少。原因：由存在于模式中的某些数据依赖引起的解决方法：通过分解关系模式来消除其中不合适的数据依赖。,6.2规范化,规范化理论正是用来改造关系模式，通过分解关系模式来消除其中不合适的数据依赖，以解决插入异常、删除异常、更新异常和数据冗余问题。,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),说明：,1.函数依赖不是指关系模式R的某个或某些关系实例满足的约束条件，而是指R的所有关系实例均要满足的约束条件。2.函数依赖是语义范畴的概念。只能根据数据的语义来确定函数依赖。例如“姓名年龄”这个函数依赖只有在不允许有同名人的条件下成立3.数据库设计者可以对现实世界作强制的规定。例如规定不允许同名人出现，函数依赖“姓名年龄”成立。所插入的元组必须满足规定的函数依赖，若发现有同名人存在，则拒绝装入该元组。,函数依赖（续）,例:Student(Sno,Sname,Ssex,Sage,Sdept)假设不允许重名，则有:SnoSsex，SnoSage,SnoSdept，SnoSname,SnameSsex，SnameSageSnameSdept但SsexSage若XY，并且YX,则记为XY。若Y不函数依赖于X,则记为XY。,二、平凡函数依赖与非平凡函数依赖,在关系模式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，记作XY。若XY，但Y不完全函数依赖于X，则称Y部分函数依赖于X，记作XPY。,完全函数依赖与部分函数依赖（续）,例:在关系SC(Sno,Cno,Grade)中，由于：SnoGrade，CnoGrade，因此：(Sno,Cno)Grade,四、传递函数依赖,定义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中的属性或属性组合。若KU，则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.42NF,1NF的定义如果一个关系模式R的所有属性都是不可分的基本数据项，则R1NF。第一范式是对关系模式的最起码的要求。不满足第一范式的数据库模式不能称为关系数据库。但是满足第一范式的关系模式并不一定是一个好的关系模式。,2NF,例:关系模式SLC(Sno,Sdept,Sloc,Cno,Grade)Sloc为学生住处，假设每个系的学生住在同一个地方。函数依赖包括：(Sno,Cno)fGradeSnoSdept(Sno,Cno)PSdeptSnoSloc(Sno,Cno)PSlocSdeptSloc,2NF,SLC的码为(Sno,Cno)SLC满足第一范式。非主属性Sdept和Sloc部分函数依赖于码(Sno,Cno),SLC不是一个好的关系模式,(1)插入异常假设Sno95102，SdeptIS，SlocN的学生还未选课，因课程号是主属性，因此该学生的信息无法插入SLC。(2)删除异常假定某个学生本来只选修了3号课程这一门课。现在因身体不适，他连3号课程也不选修了。因课程号是主属性，此操作将导致该学生信息的整个元组都要删除。,SLC不是一个好的关系模式,(3)数据冗余度大如果一个学生选修了10门课程，那么他的Sdept和Sloc值就要重复存储了10次。(4)修改复杂例如学生转系，在修改此学生元组的Sdept值的同时，还可能需要修改住处（Sloc）。如果这个学生选修了K门课，则必须无遗漏地修改K个元组中全部Sdept、Sloc信息。,2NF,原因Sdept、Sloc部分函数依赖于码。解决方法SLC分解为两个关系模式，以消除这些部分函数依赖SC（Sno，Cno，Grade）SL（Sno，Sdept，Sloc）,2NF,SLC的码为(Sno,Cno)SLC满足第一范式。非主属性Sdept和Sloc部分函数依赖于码(Sno,Cno),2NF,函数依赖图：,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.53NF,例：2NF关系模式SL(Sno,Sdept,Sloc)中函数依赖：SnoSdeptSdeptSlocSnoSlocSloc传递函数依赖于Sno，即SL中存在非主属性对码的传递函数依赖。,3NF,函数依赖图：,3NF,解决方法采用投影分解法，把SL分解为两个关系模式，以消除传递函数依赖：SD（Sno，Sdept）DL（Sdept，Sloc）SD的码为Sno，DL的码为Sdept。,3NF,SD的码为Sno，DL的码为Sdept。,3NF,3NF的定义定义6.7关系模式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的每一个非主属性既不部分函数依赖于候选码也不传递函数依赖于候选码。如果R3NF，则R也是2NF。采用投影分解法将一个2NF的关系分解为多个3NF的关系，可以在一定程度上解决原2NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。将一个2NF关系分解为多个3NF的关系后，并不能完全消除关系模式中的各种异常情况和数据冗余。,6.2.6BC范式（BCNF）,定义6.8设关系模式R1NF，如果对于R的每个函数依赖XY，若Y不是X子集，则X必含有候选码，那么RBCNF。若RBCNF每一个决定属性集（因素）都包含（候选）码R中的所有属性（主，非主属性）都完全函数依赖于码R3NF（证明）若R3NF则R不一定BCNF,6.2.6BC范式（BCNF）,例5例6关系模式Student(sno,sname,ssex,sage,sdept)SC(sno,cno,grade)Course(cno,cname,ccredit,cpno)3个关系模式都是BC范式,6.2.6BC范式（BCNF）,例7关系模式SJP（S，J，P）中，S是学生，J是课程,P是名次，每个学生选修每门课程的成绩有一定的名次，每门课程中每一名次只有一个学生（即没有并列名次）。(S,J)P；(J，P)S,BCNF,例：在关系模式STJ（S，T，J）中，S表示学生，T表示教师，J表示课程。每一教师只教一门课。每门课由若干教师教，某一学生选定某门课，就确定了一个固定的教师。某个学生选修某个教师的课就确定了所选课的名称：(S，J)T，(S，T)J，TJ,6.2.6BCNF,BCNF,STJ3NF(S，J)和(S，T)都可以作为候选码S、T、J都是主属性STJBCNFTJ，T是决定属性集，T不是候选码,BCNF,STJ3NF（存在问题）插入异常。如果某个学生刚刚入校，尚未选修课程，则受主属性不能为空的限制，有关信息无法存入数据库中；同样原因，如果某个教师主授的某门课程，尚未有学生选修，则有关信息也无法存入数据库中。,BCNF,STJ3NF（存在问题）删除异常。如果选修过某门课程的学生全部毕业，在删除这些学生元组同时，相应教师主授的该门课程信息也同时删除。,BCNF,STJ3NF（存在问题）数据冗余度大。虽然一个教师只教一门课，但每个选修该教师该门课程的学生元组都要记录这一信息。,BCNF,STJ3NF（存在问题）修改异常。某个教师主授的某门课程改名后，所有选修了该教师该门课程的学生元组都要进行相应修改。原因：在于主属性J依赖于T，即部分依赖于码。,BCNF,解决方法：将STJ分解为二个关系模式：SJ(S，J)BCNF，TJ(T，J)BCNF没有任何属性对码的部分函数依赖和传递函数依赖,BCNF,1）ST关系中可以存储尚未选修课程的学生。TJ关系中可以存储课程尚未有学生选修的教师信息。2）选修某门课程的学生毕业了，只是删除ST关系中相应元组，不会影响TJ关系中相应教师主授该门课程的信息。3）关于每个教师主授课程的信息只在TJ关系中存储一次。某个教师主授某门课程改名后，只需修改TJ关系中的某一个元组即可。,3NF与BCNF的关系,任何由两个属性组成的关系模式必是3NF有唯一候选键，这时可能有如下3种可能：A是候选键，B不是。不存在部分和传递函数依赖。该关系是3NF。A是候选键，B不是。不存在部分和传递函数依赖。该关系是3NF。AB是候选键，该关系没有非主属性，该关系是3NF。,3NF与BCNF的关系,任何由两个属性组成的关系模式必是3NF有2个候选键即AB,BA,则有AB.因此该关系没有非主属性。所以是3NF，BCNF,3NF与BCNF的关系,如果关系模式RBCNF，必定有R3NF如果R3NF，且R只有一个候选码，则R必属于BCNF。,由BCNF的定义得到的结论(P177.),由BCNF的定义，非平凡的FD:XY,可以证明下述结论,一个满足BCNF的关系模式有:1.所有非主属性对每一个码都是完全函数依赖，即,若RBCNF,则R2NF。2.所有的主属性对每一个不包含它的码也是完全函数依赖。3.没有任何属性完全函数依赖于非码的任何一组属性。4.若RBCNF,则必有R3NF;反之不一定成立。,关于BCNF的结论,1.全码关系模式属于BCNF。没有以非码属性作为决定因素的函数依赖2.二目关系模式属于BCNF。如果有函数依赖,则其左部一定含码4.若R属于BCNF，那么R也属于3NF。5.若R属于3NF，但R不一定属于BCNF。例如，关系模式STC(S#,T#,C#),6.2.7多值依赖与第四范式（4NF）,例9:学校中某一门课程由多个教师讲授，他们使用相同的一套参考书。关系模式Teaching(C,T,B)课程C、教师T和参考书B,表5.1,用二维表表示Teaching,例如在关系模式TEACH(C,T,B)中，给定一对(C1,B1)值，有一组T值T1,T2与之对应；对(C1,B2)值也有一组T值T1,T2与之对应。事实上，T1,T2这组值仅取决于C的取值，而与B的取值无关。按MVD的定义有CT成立，同理有CB成立。,多值依赖与第四范式（续）,TeachingBCNF:Teach具有唯一候选码(C，T，B)，即全码Teaching模式中存在的问题(1)数据冗余度大：有多少名任课教师，参考书就要存储多少次,多值依赖与第四范式（续）,(2)插入操作复杂：当某一课程增加一名任课教师时，该课程有多少本参照书，就必须插入多少个元组例如物理课增加一名教师刘关，需要插入两个元组：（物理，刘关，普通物理学）（物理，刘关，光学原理）,多值依赖与第四范式（续）,(3)删除操作复杂：某一门课要去掉一本参考书，该课程有多少名教师，就必须删除多少个元组(4)修改操作复杂：某一门课要修改一本参考书，该课程有多少名教师，就必须修改多少个元组产生原因存在多值依赖,一、多值依赖,在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。txy1z1sxy2z2wxy1z2vxy2z1,一、多值依赖,定义6.9设R(U)是一个属性集U上的一个关系模式，X、Y和Z是U的子集，并且ZUXY，多值依赖XY成立当且仅当对R的任一关系r，r在（X，Z）上的每个值对应一组Y的值，这组值仅仅决定于X值而与Z值无关例Teaching（C,T,B）对于C的每一个值，T有一组值与之对应，而不论B取何值,多值依赖（续）,平凡多值依赖和非平凡的多值依赖若XY，而Z，则称XY为平凡的多值依赖否则称XY为非平凡的多值依赖,平凡多值依赖（续）,多值依赖（续）,例10关系模式WSC(W,S,C)中，W表示仓库中，S表示保管员，C表示商品。假设每个仓库若干个保管员，有若干种商品。每个保管员保管所在的仓库的所有商品，每种商品被所有保管员保管。,多值依赖（续）,多值依赖（续）,多值依赖的性质,（1）多值依赖具有对称性若XY，则XZ，其中ZUXY多值依赖的对称性可以用完全二分图直观地表示出来。（2）多值依赖具有传递性若XY，YZ，则XZ-Y,多值依赖的对称性,多值依赖的对称性,多值依赖（续）,（3）函数依赖是多值依赖的特殊情况。若XY，则XY。（4）若XY，XZ，则XYZ。（5）若XY，XZ，则XYZ。（6）若XY，XZ，则XY-Z，XZ-Y。,多值依赖与函数依赖区别,1.元组区别函数依赖规定某些元组不能出现在关系中。多值依赖要求某种形式的其它元组必须在关系中。2.有效性与属性集范围区别参见P181.XY的有效性与属性集范围有关。XY在U上成立XY在属性集W(XYWU)上成立；XY在属性集W(XYWU)上成立，但在U上不一定成立。,多值依赖与函数依赖区别,若在R(U)上，XY在属性集W(XYWU)上成立，则称XY为R(U)的嵌入型多值依赖参见P181.XY的有效性仅决定于X、Y属性集上的值，只要在X、Y属性集上成立,则它在任何属性集W(XYWU)上都成立。3.分解性上的区别参见P181.若XY在R(U)上成立，则对于任何YY，均有XY成立。若XY在R(U)上成立，则不能断言对于YY，是否有XY成立。,多值依赖与函数依赖区别,AB在ABC上成立，而在ABCD上不成立。元组不够。MVD的有效性与属性集范围有关，在小的范围内成立，而在大的范围内不一定成立-嵌入型的。,ABC成立，但AB不成立。MVD没有分解性。,AnIntroductiontoDatabaseSystem,多值依赖与函数依赖区别,多值依赖:实例,示例，百货商店将顾客的订货直接从供应商的仓库运到顾客所在地，定义一关系存储所有商品的可能的运输源和目的地，以便规划运输方案。运货路径(顾客名,顾客地址,商品名,供应商名,供应商地址)Key=(商品名,顾客名,供应商名)FD:顾客名顾客地址,供应商名供应商地址MVD:商品名(顾客名,顾客地址)商品名(供应商名,供应商地址),多值依赖:实例,可能的关系:商品名顾客名顾客地址供应商名供应商地址彩电张三10号王A100号.李四20号王A100号.张三10号刘B200号.李四20号刘B200号.VCD张三10号王A100号.林一30号王A100号.张三10号文C300号.林一30号文C300号,AnIntroductiontoDatabaseSystem,6.2.84NF(参见P181.),定义6.10关系模式R1NF，如果对于R的每个非平凡多值依赖XY(YX)，X都含有码，则称R4NF。说明：1.定义中的F是数据依赖集,包括FD和MVD;当F只包含FD时,4NF的定义就是BCNF的定义。2.4NF是BCNF的推广,适用于具有多值依赖的关系模式。3.4NF的定义就是限制关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖的存在。,AnIntroductiontoDatabaseSystem,4NF定义的说明,4.由定义可知,若XY是平凡的多值依赖,则不要求X包含码。5.由定义可知,若R4NF,则必有RBCNF;反之不成立(因为函数依赖是多值依赖的特例)。思考:1.任何一个二目关系模式R(A,B)属于4NF吗？2.全码关系模式属于4NF吗？,是,否，如WSC关系,二、第四范式（4NF）,定义6.10关系模式R1NF，如果对于R的每个非平凡多值依赖XY（YX），X都含有候选码，则R4NF。（XY）如果R4NF，则RBCNF不允许有非平凡且非函数依赖的多值依赖允许的是函数依赖（是平凡多值依赖）,第四范式（续）,例：Teach(C,T,B)4NF存在非平凡的多值依赖CT，且C不是候选码用投影分解法把Teach分解为如下两个关系模式：CT(C,T)4NFCB(C,B)4NFCT，CB是平凡多值依赖,6.2规范化,1第一范式（1NF）2第二范式（2NF）3第三范式（3NF）4BC范式（BCNF）5多值依赖与第四范式（4NF）6规范化,AnIntroductiontoDatabaseSystem,范式之间的关系(P183.图6.8),1NF,AnIntroductiontoDatabaseSystem,6.2.9规范化小结,1.规范化的目的参见P182.有些关系模式存在“插入异常,更新异常,删除异常,数据冗余大”的问题-不好的模式寻求解决这些问题的方法-规范化的目的2.规范化的基本思想参见P182.概念的单一化逐步消除数据依赖中不合适的部分,使关系模式达到某种程度的分离,即“一事一地”的模式设计原则3.各种范式及规范化的过程参见P183.图6.81NF2NF3NFBCNF4NF,AnIntroductiontoDatabaseSystem,规范化小结(续),4.关系模式的规范化过程是通过对关系模式的投影分解来实现的,把低一级的关系模式分解为若干高一级的关系模式,分解不是唯一的。6.4节介绍分解算法。5.规范化理论为数据库模式设计提供了理论指南和工具,但仅仅是指南和工具。并不是规范化程度越高越好。规范化程度高,可解决更新异常和冗余大的问题,但会失去检索查询方便快速的优点,增加(自然)连接运算的开销。必须结合应用环境和具体情况合理选择DB模式,经常用于检索查询的系统,宁肯规范化程度低些。,AnIntroductiontoDatabaseSystem,范式盘点,1.一个全是主属性的关系模式一定可以达到3NF。2.一个全码的关系模式一定可以达到BCNF。3.一个二目关系模式一定可以达到4NF。4.函数依赖和多值依赖是两种重要的数据依赖。在函数依赖的范畴内,BCNF是最高级别的范式。如果考虑多值依赖,则4NF是最高的范式级别。5.除FD和MVD外，还有其他数据依赖，如连接依赖，在连接依赖的概念上还可以定义5NF的范式级别。参见P182.,第六章关系数据理论,6.1数据依赖6.2规范化6.3数据依赖的公理系统6.4模式的分解,AnIntroductiontoDatabaseSystem,6.3函数依赖的公理系统,为了以下目的，需要建立函数依赖的推理系统:(1)求关系模式的候选码(2)判断关系模式的范式级别(3)给定一组函数依赖，需要导出另外一些函数依赖，或判断另外的函数依赖是否成立。例如FD=AB，BC，判断AC是否成立？本节内容:1.逻辑蕴涵；2.Armstrong函数依赖公理系统；3.函数依赖集的闭包；4.属性集闭包；5.函数依赖集的等价和覆盖；6.最小函数依赖集。,AnIntroductiontoDatabaseSystem,逻辑蕴涵(参见P183.),定义6.11关系模式R，F是其函数依赖集，X、Y是U的属性子集，r是R的任何一个关系，如果从F的函数依赖能够推出XY，则称F逻辑蕴涵XY，记作FXY。示例:R,U=X,Y,F=XY则F逻辑蕴涵以下函数依赖:XX，XY，YY,XYX，XYY，XYXY,Armstrong公理系统,一套推理规则，是模式分解算法的理论基础用途求给定关系模式的码从一组函数依赖求得蕴含的函数依赖,1.Armstrong公理系统,关系模式R来说有以下的推理规则：Al.自反律（Reflexivity）：若YXU，则XY为F所蕴含。A2.增广律（Augmentation）：若XY为F所蕴含，且ZU，则XZYZ为F所蕴含。A3.传递律（Transitivity）：若XY及YZ为F所蕴含，则XZ为F所蕴含。注意：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于F,AnIntroductiontoDatabaseSystem,A公理系统的正确性证明,按函数依赖定义，假设r是R上的任一关系实例，t、s是r的任意两个元组。证明自反律:若YXU，则XY参见P184.若tX=sX,由于YX,有tY=sY,所以有XY。,AnIntroductiontoDatabaseSystem,A公理系统：增广律证明,(2)证明增广律:若XY，则XZYZ。设tXZ=sXZ,则有tX=sX和tZ=sZ,由于XY,对tX=sX，就有tY=sY,从而有tYZ=sYZ,所以XZYZ成立。参见P184.,AnIntroductiontoDatabaseSystem,A公理系统：传递律证明,(3)证明传递律:若XY及YZ，则XZ。设tX=sX,由于XY,则有tY=sY,再由YZ，对tY=sY，有tZ=sZ,所以XZ成立。参见P184.,2.导出规则,1.根据A1，A2，A3这三条推理规则可以得到下面三条推理规则：合并规则：由XY，XZ，有XYZ。（A2，A3）伪传递规则：由XY，WYZ，有XWZ。（A2，A3）分解规则：由XY及ZY，有XZ。（A1，A3）,2.导出规则,合并规则：由XY，XZ，有XYZ。证明：XY|=XXY(增广律)XZ|=XYYZ(增广律)所以XYZ（传递律）,2.导出规则,伪传递规则：由XY，WYZ，有XWZ。（A2，A3）证明：XYWXWY（增广律）WYZ（给定条件）XWZ（传递律）,2.导出规则,分解规则：由XY及ZY，有XZ。（A1，A3）证明：ZY|=YZ(自反律)XY（给定条件）XZ（传递律）,补充示例：设有关系模式R(A,B,C,D,E)及其上的函数依赖集FABDE，AB，EC，求证F必蕴涵AC.证明:AB(给定条件)AAB(增广律)ABDE(给定条件)ADE(传递律)AD,AE（分解律）EC(给定条件)AC(传递律),Armstrong公理规则推导蕴涵的函数依赖,补充示例：设有关系模式R(A,B,C,D)及其上的函数依赖集FBA，BCD，那么关系模式R最高是什么范式。证明:BA(给定条件)BCAC(增广律)BCD(给定条件)BCACD(合并规则)BCABCD(自反律)非主属性A部分依赖于候选码BC关系模式R最高是1NF范式,Armstrong公理规则求关系模式的候选码,导出规则,2.根据合并规则和分解规则，可得引理6.1引理6.lXA1A2Ak成立的充分必要条件是XAi成立（i=l，2，k）。,3.函数依赖闭包,定义6.l2在关系模式R中为F所逻辑蕴含的函数依赖的全体叫作F的闭包，记为F+。定义6.13设F为属性集U上的一组函数依赖，XU，XF+=A|XA能由F根据Armstrong公理导出，XF+称为属性集X关于函数依赖集F的闭包,F的闭包,F=XY,YZ,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,关于闭包的引理,引理6.2设F为属性集U上的一组函数依赖，X，YU，XY能由F根据Armstrong公理导出的充分必要条件是YXF+用途将判定XY是否能由F根据Armstrong公理导出的问题，就转化为求出XF+，判定Y是否为XF+的子集的问题,AnIntroductiontoDatabaseSystem,设关系模式R（A，B，C）的函数依赖集为F=AB,BC分别求A,B,C闭包。可见计算属性集闭包比直接求函数依赖集闭包简单的多。,求闭包的算法,算法6.l求属性集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）,算法6.l,（4）判断X（i+1）=X（i）吗?（5）若相等或X（i）=U,则X（i）就是XF+,算法终止。（6）若否，则i=i+l，返回第（2）步。对于算法5.l，令ai=|X（i）|，ai形成一个步长大于1的严格递增的序列，序列的上界是|U|，因此该算法最多|U|-|X|次循环就会终止。,函数依赖闭包,(2)因为X（0）X（1），所以再找出左部为ABCD子集的那些函数依赖，又得到ABC，BD，CE，ACB，于是X（2）=X（1）BCDE=ABCDE。(3)因为X（2）=U，算法终止所以（AB）F+=ABCDE。,函数依赖闭包,例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。,4.Armstrong公理系统的有效性与完备性,有效性：由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F+中/*Armstrong正确完备性：F+中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来/*Armstrong公理够用，完全完备性：所有不能用Armstrong公理推导出来f,都不为真若f不能用Armstrong公理推导出来，fF+,Armstrong公理系统的有效性与完备性(续),Armstrong公理的完备性及有效性说明:“蕴含”=“导出”等价的概念F+=由F出发借助Armstrong公理导出的函数依赖的集合,5.函数依赖集等价,定义6.14如果G+=F+，就说函数依赖集F覆盖G（F是G的覆盖，或G是F的覆盖），或F与G等价。,函数依赖集等价的充要条件,引理6.3F+=G+的充分必要条件是FG+，和GF+证:必要性显然，只证充分性。（1）若FG+，则XF+XG+。（2）任取XYF+则有YXF+XG+。所以XY(G+）+=G+。即F+G+。（3）同理可证G+F+，所以F+=G+。,函数依赖集等价,要判定FG+，只须逐一对F中的函数依赖XY，考察Y是否属于XG+就行了。因此引理6.3给出了判断两个函数依赖集等价的可行算法。,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。引理5.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极小依赖集的过程,极小化过程,设有关系模式R(U,F),其中U=CDE,F=CDE,DE,CD,CDE求F的最小覆盖.1)将F的所有函数依赖的右部都分解成单一属性.F=CD,CE,DE,CD,CDE由于CD重复,删除后得到F=CD,CE,DE,CDE2)去掉冗余的函数依赖考察CD,令G=CE,DE,CDE,CG+=CE因为D不CG+,所以CD不冗余考察CE,令G=CD,DE,CDE,CG+=CDE因为ECG+,所以CE冗余,从F中删除,F=CD,DE,CDE考察DE,令G=CD,CDE,DG+=D因为E不DG+,所以DE不冗余考察CDE,令G=CD,DE,CDG+=CDE因为ECDG+,所以CDE冗余,从F中删除,F=CD,DE3)去除冗余属性因没有冗余属性,所以F的最小覆盖Fm=CD,DE,AnIntroductiontoDatabaseSystem,计算最小覆盖Fmin:例2,F=CA，AG，CGB，BA，求FminF已是单属性的；判断CGB中是否有重复属性:,=G,=C,A,G,B,BC不可去,B，G冗余，去掉，以C代替CG,得F=CA，AG，CB，BA再去掉CA得，Fmin=AG，CB，BA,极小化过程,设有关系模式R(U,F),其中U=ABC,F=ABC,AB,BA求F的最小函数依赖集.1)将F的所有函数依赖的右部都分解成单一属性.2)去掉冗余的函数依赖考察ABC,令G=AB,BA,ABG+=AB因为C不ABG+,所以ABC不冗余考察AB,令G=ABC,BA,AG+=A因为B不AG+,所以AB不冗余考察BA,令G=ABC,AB,BG+=B因为A不BG+,所以BA不冗余,极小化过程,设有关系模式R(U,F),其中U=ABC,F=ABC,AB,BA求F的最小函数依赖集.（续）3)去除冗余属性本题只考虑ABC情况方法1:,考察B是否是冗余属性。AF+=ABC,因为CAF+,所以从决定因素中去掉B，即以AC代替ABC。故Fm=AC,AB,BA方法2:考察A是否是冗余属性。BF+=ABC因为CBF+,所以从决定因素中去掉A,即以BC代替ABC。故Fm=BC,AB,BA,极小化过程,例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本身就是一个最小依赖集,极小化过程,在R中可以用与F等价的依赖集G来取代F原因：两个关系模式R1，R2，如果F与G等价，那么R1的关系一定是R2的关系。反过来，R2的关系也一定是R1的关系。,极小化算法在数据库上的应用在数据库的信息模型设计中，实体和属性冗余可以通过分析确定，而联系冗余可以通过函数依赖集的极小化算法查出和消除。步骤：1）把E-R图中实体、属性和联系符号化。符号化后，信息表达比较简洁，化简起来比较容易表达，运算起来也不容易出错。,极小化算法在数据库上的应用2）将实体之间联系用实体主码之间的联系表示，并转换为函数依赖表达式。对于1：1联系。转化为两个函数依赖表达式。例A.aB.b,B.bA.a实体集A、B的主码分别为a,b,极小化算法在数据库上的应用对于1：N联系。每个联系转化为一个函数依赖表达式。函数依赖表达式中的决定因素为联系的N方实体集，依赖因素为1方实体集。例A.aB.b实体集A、B的主码分别为a,b,极小化算法在数据库上的应用对于M：N联系。每个联系转化为一个函数依赖表达式。函数依赖表达式中的决定因素相关实体集组合，依赖因素为联系属性（当联系无属性时，依赖因素为联系名）。例(C.c,D.d)e(C.c,D.d,F.f)e,P,极小化算法在数据库上的应用3）利用求函数依赖集的最小化算法进行极小化处理。在处理时，应将重要联系放在后面，以免冗余时被消除。4）重新确定函数依赖集。设原集为F，最小函数依赖集为G，差集为D，则DF-G。逐一考查D中每一个函数依赖表达式，根据实际情况确定是否应该去掉。最后得到一组函数依赖表达式。用新得到的函数依赖表达式形成新的E-R图。,AnIntroductiontoDatabaseSystem,补充：候选码的求解算法,设关系模式R(1)将R的所有属性分为L、R、N和LR四类，并令X代表L、N两类，Y代表LR类。L类:仅出现在F的函数依赖左部的属性；R类:.右；N类:在F的函数依赖左右两边都不出现的属性；LR类:都出现的属性。(2)求属性集闭包X+，若X+包含了R的全部属性则X即为R的唯一候选码,转(5);,AnIntroductiontoDatabaseSystem,候选码的求解算法(续),(3)否则,在Y中取一属性A，求属性集闭包(XA)+，若(XA)+包含了R的全部属性，则转(4)；否则，调换一属性反复进行这一过程，直到试完所有Y中的属性。(4)如果已找出了所有的候选码，则转(5)；否则在Y中依次取2个、3个、属性，求X与它们的属性集闭包，直到其闭包包含R的全部属性。(5)停止，输出结果。,AnIntroductiontoDatabaseSystem,快速求解候选码的原理,AnIntroductiontoDatabaseSystem,候选码的求解：例1,设关系模式R(A,B,C,D),其函数依赖集：F=DB,BD,ADB,ACD求R的所有候选码。解:L类:A,CR类:N类:LR类:B,D因为(AC)F+=ACDB，所以AC是R的唯一候选码。,AnIntroductiontoDatabaseSystem,候选码的求解：例2,设关系模式R(A,B,C,D,E,G),其函数依赖集：F=AD,ED,DB,BCD,DCA求R的所有候选码。解:L类:C,ER类:N类:GLR类:A,B,D因为(CEG)F+=CEGDBA，所以CEG是R的唯一候选码。,AnIntroductiontoDatabaseSystem,候选码的求解：例3,设关系模式R(S,D,I,B,O,Q),其函数依赖集:F=SD,IB,BO,OQ,QI求R的所有候选码。解:L类(S);R类(D);N类(无);LR类(I,B,O,Q)因为S+=SD,所以S不是R的候选码；因为(SI)+=SIDBOQ，所以SI是一个候选码；因为(SB)+=SBDOQI，所以SB也是一个候选码；因为(SO)+=SODQIB，所以SO也是一个候选码；因为(SQ)+=SQDIBO，所以SQ也是一个候选码。,AnIntroductiontoDatabaseSystem,第6章小结(1),由数据库模式设计的问题提出关系数据库规范化理论，三部分内容：数据依赖(函数依赖)、范式、模式分解模式的好坏：数据冗余、插入异常、删除异常、更新异常函数依赖：定义、逻辑蕴涵、FD集的闭包F+、码及码的确定函数依赖的推理规则自反律、增广律、传递律,AnIntroductiontoDatabaseSystem,第6章小结(2),合并律、伪传递律、分解律属性集X的闭包X+及计算,与F+的联系函数依赖集的等价(覆盖)及判断函数依赖集F的最小依赖Fmin及计算范式:衡量关系模式达到的数据依赖程度的标准最低标准:1NF在函数依赖的范畴:2NF