《《关系规范化》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《关系规范化》PPT课件.ppt（149页珍藏版）》请在三一办公上搜索。
1、第六章 关系数据理论,学习要点：理解不规范关系可能带来的问题理解函数依赖、多值依赖的概念掌握1NFBCNF的定义及判定方法掌握候选码、函数依赖的闭包集和极小集的求解方法理解两种模式分解方式的概念掌握分解到满足3NF要求的模式分解算法,6.1节,6.2节,6.4节（重点）,6.3节（重点）,第六章 关系数据理论,6.1 问题的提出6.2 规范化6.3 数据依赖的公理系统6.4 模式的分解6.5 小结,6.1 问题的提出,关系数据理论的用途关系数据库的规范化理论数据库逻辑设计的工具；数据库逻辑设计针对具体问题，如何构造适合于它的关系模式。,6.1 问题的提出,一、关系模式的形式化定义二、关系模式的
2、简化定义三、什么是数据依赖四、数据依赖对关系模式影响,一、关系模式的形式化定义,关系模式由五部分组成，即它是一个五元组 R(U,D,DOM,F),R：关系名U：组成该关系的属性名集合D：属性组U中属性所来自的域DOM：属性向域的映象集合F：属性间数据的依赖关系集合,学生-课程数据库,学生表 Student(Sno,Sname,Ssex,Sage,Sdept)课程表 Course(Cno,Cname,Cpno,Ccredit)学生选课表 SC(Sno,Cno,Grade),二、关系模式的简化表示,关系模式R（U,D,DOM,F）简化为一个三元组：R（U,F）当且仅当U上的一个关系r 满足F时，r
3、称为关系模式 R（U,F）的一个关系,三、什么是数据依赖,1.数据依赖是现实世界属性间相互联系的抽象是数据内在的性质是语义的体现它是数据库模式设计的关键。,三、什么是数据依赖,2.数据依赖的类型,（1）函数依赖（Functional Dependency，简记为FD）,（2）多值依赖（Multivalued Dependency，简记为MVD）,（3）连接依赖（Jion Dependency，简记为JD）,四、数据依赖对关系模式的影响,【例1】建立一个描述学校教务的数据库包括：学生的学号(Sno)、所在系(Sdept)、系主任姓名(Mname)、课程名(Cname)、成绩(Grade)属性。,
4、四、数据依赖对关系模式的影响,该数据库的语义：一个系有若干学生，一个学生只属于一个系；一个系只有一名主任；一个学生可以选修多门课程，每门课程有若干学生选修；每个学生所学的每门课程都有一个成绩。,四、数据依赖对关系模式的影响,属性组U上的一组函数依赖F：F SnoSdept,SdeptMname,(Sno,Cname)Grade,单一的关系模式：Student U Sno,Sdept,Mname,Cname,Grade,四、数据依赖对关系模式的影响,关系模式Student中存在的问题,数据冗余太大,插入异常（Insertion Anomalies）,修改异常（Update Anomalies）,
5、删除异常（Deletion Anomalies）,四、数据依赖对关系模式的影响,结论：Student关系模式不是一个好的模式。,原因：由存在于模式中的某些数据依赖引起的,解决方法：通过分解关系模式来消除其中不合适 的数据依赖,“好”的模式：不会发生插入异常、删除异常、更新异常，数据冗余应尽可能少。,第六章 关系数据理论,6.1 问题的提出6.2 规范化6.3 数据依赖的公理系统6.4 模式的分解6.5 小结,6.2 规范化,规范化理论正是用来改造关系模式，通过分解关系模式来消除其中不合适的数据依赖，以解决插入异常、删除异常、更新异常和数据冗余问题。,6.2 规范化,6.2.1 函数依赖6.2.
6、2 码6.2.3 范式6.2.4 2NF（含1NF）6.2.5 3NF6.2.6 BCNF6.2.7 多值依赖6.2.8 4NF6.2.9 规范化小结,6.2.1 函数依赖,一、函数依赖二、平凡函数依赖与非平凡函数依赖三、完全函数依赖与部分函数依赖四、传递函数依赖,一、函数依赖,【定义6.1】设R(U)是一个属性集U上的关系模式，X和Y是U的子集。若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称“X函数确定Y”或“Y函数依赖于X”，记作XY。,X称为这个函数依赖的决定属性集(Determinant),函数依赖概念说明,1.函数依赖不是指
7、关系模式R的某个或某些关系实例满足的约束条件，而是指R的所有关系实例均要满足的约束条件。,2.函数依赖是语义范畴的概念。只能根据数据的语义来确定函数依赖。,3.数据库设计者可以对现实世界作强制的规定。,一、函数依赖,【例2】Student(Sno,Sname,Ssex,Sage,Sdept)假设不允许重名，有如下函数依赖:,Sno Ssex，Sno Sage,Sno Sdept，Sno Sname,Sname Ssex，Sname SageSname Sdept,若XY，并且YX,则记为XY。若Y不函数依赖于X,则记为XY。,二、平凡函数依赖与非平凡函数依赖,在关系模式R(U)中，对于U的子集
8、X和Y，如果XY，但Y X，则称XY是非平凡的函数依赖若XY，但Y X,则称XY是平凡的函数依赖,【例3】在关系SC(Sno,Cno,Grade)中，,(Sno,Cno)Grade(Sno,Cno)Sno(Sno,Cno)Cno,二、平凡函数依赖与非平凡函数依赖,任一关系模式，平凡函数依赖都是必然成立的，它不反映新的语义；,若不特别声明，我们总是讨论非平凡函数依赖。,三、完全函数依赖与部分函数依赖,【定义6.2】在关系模式R(U)中，如果XY，并且对于X的任何一个真子集X，都有 X Y,则称Y完全函数依赖于X，记作X Y。,若XY，但Y不完全函数依赖于X，则称Y部分函数依赖于X，记作X P Y
9、。,三、完全函数依赖与部分函数依赖,【例4】在关系SC(Sno,Cno,Grade)中，(Sno,Cno)Grade 由于：SnoGrade，CnoGrade,f,四、传递函数依赖,【定义6.3】在关系模式R(U)中，如果XY，YZ，且Y X，YX，则称Z传递函数依赖于X。,Sno Mname,【例5】在关系Std(Sno,Sdept,Mname)中，,【注】:如果YX，即XY，则Z直接依赖于X。,T,6.2 规范化,6.2.1 函数依赖6.2.2 码6.2.3 范式6.2.4 2NF（含1NF）6.2.5 3NF6.2.6 BCNF6.2.7 多值依赖6.2.8 4NF6.2.9 规范化小结
10、,6.2.2 码,【定义6.4】设K为关系模式R中的属性或属性组合。若K U，则K称为R的一个侯选码（Candidate Key）。若关系模式R有多个候选码，则选定其中的一个做为主码(Primary key)。主属性与非主属性ALL KEY,外部码,【定义6.5】关系模式 R 中属性或属性组X 并非R 的码，但 X 是另一个关系模式的码，则称 X 是R 的外部码（Foreign key）也称外码,主码和外部码一起提供了表示关系间联系的手段,6.2 规范化,6.2.1 函数依赖6.2.2 码6.2.3 范式6.2.4 2NF（含1NF）6.2.5 3NF6.2.6 BCNF6.2.7 多值依赖6
11、.2.8 4NF6.2.9 规范化小结,6.2.3 范式,范式是符合某一种级别的关系模式的集合。,6.2.3 范式,各种范式之间存在联系：,某一关系模式R为第n范式，可简记为RnNF。,6.2 规范化,6.2.1 函数依赖6.2.2 码6.2.3 范式6.2.4 2NF（含1NF）6.2.5 3NF6.2.6 BCNF6.2.7 多值依赖6.2.8 4NF6.2.9 规范化小结,6.2.4 2NF,一、1NF的定义如果一个关系模式R的所有属性都是不可分的基本数据项，则R1NF。,第一范式是对关系模式的最起码的要求。不满足第一范式的数据库模式不能称为关系数据库。,但是满足第一范式的关系模式并不一
12、定是一个好的关系模式。,6.2.4 2NF,二、2NF的定义【定义6.6】若关系模式R1NF，并且每一个非主属性都完全函数依赖于R的码，则R2NF。,6.2.4 2NF,采用投影分解法将一个1NF的关系分解为多个2NF的关系，可以在一定程度上减轻原1NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。,将一个1NF关系分解为多个2NF的关系，并不能完全消除关系模式中的各种异常情况和数据冗余。,6.2 规范化,6.2.1 函数依赖6.2.2 码6.2.3 范式6.2.4 2NF（含1NF）6.2.5 3NF6.2.6 BCNF6.2.7 多值依赖6.2.8 4NF6.2.9 规范化
13、小结,6.2.5 3NF,【定义6.7】关系模式R 中若不存在这样的码X、属性组Y及非主属性Z（Z Y）,使得XY，Y X，YZ，成立，则称R 3NF。,6.2.5 3NF,（1）若R3NF，则R的每一个非主属性既不部分函数依赖于候选码也不传递函数依赖于候选码。,（2）如果R3NF，则R2NF。,采用投影分解法将一个2NF的关系分解为多个3NF的关系，可以在一定程度上解决原2NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。,如果将一个2NF关系分解为多个3NF的关系后，并不能完全消除关系模式中的各种异常情况和数据冗余。,6.2.5 3NF,【例6】在关系模式STJ（S，T，J
14、）中，S表示学生，T表示教师，J表示课程。,每一教师只教一门课。每门课由若干教师教，某一学生选定某门课，就确定了一个固定的教师。某个学生选修某个教师的课就确定了所选课的名称。,(S，J)T，(S，T)J，TJ,6.2 规范化,6.2.1 函数依赖6.2.2 码6.2.3 范式6.2.4 2NF（含1NF）6.2.5 3NF6.2.6 BCNF6.2.7 多值依赖6.2.8 4NF6.2.9 规范化小结,6.2.6 BC范式（BCNF）,【定义6.8】设关系模式R1NF，如果对于R的每个函数依赖XY，若Y X，则X必含有候选码，那么RBCNF。,若RBCNF,（1）每一个决定属性集（因素）都包含
15、（候选）码,（2）R中的所有属性（主，非主属性）都完全函数依赖于码,（3）R3NF,6.2.6 BC范式（BCNF）,例6解决方法：将STJ分解为二个关系模式：SJ(S，J)BCNF，TJ(T，J)BCNF,没有任何属性对码的部分函数依赖和传递函数依赖,6.2.6 BC范式（BCNF）,如果关系模式RBCNF，必定有R3NF,如果R3NF，且R只有一个候选码，则R必属于BCNF。,3NF与BCNF的关系,函数依赖总结,3NF和BCNF是在函数依赖的条件下对模式分解所能达到的分离程度的测度。,一个模式中的关系模式如果都属于BCNF，那么在函数依赖范畴内，它已经实现了彻底分离，已经解决了插入异常、
16、删除异常等问题。,学生-课程数据库,学生表 Student(Sno,Sname,Ssex,Sage,Sdept)课程表 Course(Cno,Cname,Cpno,Ccredit)学生选课表 SC(Sno,Cno,Grade),6.2.9 规范化小结,关系模式规范化的基本步骤 1NF 消除非主属性对码的部分函数依赖消除决定属性 2NF集非码的非平 消除非主属性对码的传递函数依赖凡多值依赖 3NF 消除主属性对码的部分和传递函数依赖 BCNF,6.2 规范化,6.2.1 函数依赖6.2.2 码6.2.3 范式6.2.4 2NF（含1NF）6.2.5 3NF6.2.6 BCNF6.2.7 多值依赖
17、6.2.8 4NF6.2.9 规范化小结,6.2.7 多值依赖,【例7】关系模式Teaching(C,T,B)课程C、教师T 和 参考书B学校中某一门课程由多个教师讲授，他们使用相同的一套参考书；每个教员可以讲授多门课程，每种参考书可以供多门课程使用。,用二维表表示Teaching,6.2.7 多值依赖,结论：TeachingBCNF。,Teaching模式中存在的问题(1)数据冗余度大：有多少名任课教师，参考书就要存储多少次,6.2.7 多值依赖,(2)插入操作复杂：当某一课程增加一名任课教师时，该课程有多少本参照书，就必须插入多少个元组。,6.2.7 多值依赖,(3)删除操作复杂：某一门课
18、要去掉一本参考书，该课程有多少名教师，就必须删除多少个元组。,产生原因：存在多值依赖（MVD）,(4)修改操作复杂：某一门课要修改一本参考书，该课程有多少名教师，就必须修改多少个元组。,6.2.7 多值依赖,一、多值依赖定义二、平凡多值依赖和非平凡多值依赖三、多值依赖性质四、多值依赖和函数依赖的区别,一、多值依赖定义,【定义6.9】设R(U)是一个属性集U上的一个关系模式，X、Y和Z是U的子集，并且ZUXY，多值依赖 XY成立当且仅当对R的任一关系r，r在（X，Z）上的每个值对应一组Y的值，这组值仅仅决定于X值而与Z值无关。,二、平凡和非平凡的多值依赖,若XY，而Z，则称 XY为平凡的多值依赖
19、,否则称XY为非平凡的多值依赖,三、多值依赖的性质,（1）多值依赖具有对称性 若XY，则XZ。其中ZUXY,（2）多值依赖具有传递性 若XY，YZ，则XZ-Y,三、多值依赖的性质,（3）函数依赖是多值依赖的特殊情况。若XY，则XY。,（4）若XY，XZ，则XY Z。,（5）若XY，XZ，则XYZ。,（6）若XY，XZ，则XY-Z，XZ-Y。,四、多值依赖与函数依赖的区别,(1)有效性多值依赖的有效性与属性集的范围有关,只要在R（U）的任何一个关系r中，元组在X和Y上的值满足【定义6.1】，则函数依赖XY在任何属性集W（X Y W U）上成立。,若XY在U上成立，则在W（X Y W U）上一定成
20、立；反之则不然，即XY在W(W U)上成立，在U上并不一定成立。,四、多值依赖与函数依赖的区别,(2)平凡性若函数依赖XY在R（U）上成立，则对于任何Y Y均有XY 成立。,多值依赖XY若在R(U)上成立，不能断言对于任何Y Y，有XY 成立。,6.2 规范化,6.2.1 函数依赖6.2.2 码6.2.3 范式6.2.4 2NF（含1NF）6.2.5 3NF6.2.6 BCNF6.2.7 多值依赖6.2.8 4NF6.2.9 规范化小结,6.2.8 4NF,【定义6.10】关系模式R1NF，如果对于R的每个非平凡多值依赖XY（Y X），X都含有候选码，则R4NF。,如果R 4NF，则R BCN
21、F。,不允许有非平凡且非函数依赖的多值依赖 允许的是函数依赖和平凡多值依赖,6.2.8 4NF,例：Teaching(C,T,B)4NF 存在非平凡的多值依赖CT，且C不是候选码用投影分解法把Teaching分解为如下两个关系模式：CT(C,T)4NF CB(C,B)4NF CT，CB是平凡多值依赖,6.2 规范化,6.2.1 函数依赖6.2.2 码6.2.3 范式6.2.4 2NF（含1NF）6.2.5 3NF6.2.6 BCNF6.2.7 多值依赖6.2.8 4NF6.2.9 规范化小结,6.2.9 规范化小结,1.关系数据库的规范化理论是数据库逻辑设计的工具。,3.规范化程度可以有多个不
22、同的级别。,2.一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式集合，这种过程就叫关系模式的规范化。,6.2.9 规范化小结,5.规范化程度过低的关系不一定能够很好地描述现实世界，可能会存在插入异常、删除异常、修改复杂、数据冗余等问题。,4.一个关系只要其分量都是不可分的数据项，它就是规范化的关系，但这只是最基本的规范化。,6.2.9 规范化小结,关系模式规范化的基本步骤 1NF 消除非主属性对码的部分函数依赖消除决定属性 2NF集非码的非平 消除非主属性对码的传递函数依赖凡多值依赖 3NF 消除主属性对码的部分和传递函数依赖 BCNF 消除非平凡且非函数依赖的多值依
23、赖 4NF,6.2.9 规范化小结,消除不合适的数据依赖,采用“一事一地”的模式设计原则,所谓规范化实质上是概念的单一化,6.2.9 规范化小结,不能说规范化程度越高的关系模式就越好,在设计数据库模式结构时，必须对现实世界的实际情况和用户应用需求作进一步分析，确定一个合适的、能够反映现实世界的模式。,上面的规范化步骤可以在其中任何一步终止。,练 习,关系规范化中的删除异常是指（），插入操作异常是指（）。关系规范化是为解决关系数据库中（）问题而引入的。在关系DB中，任何一个二元关系模式的最高范式必定是（）。当属性B函数依赖于属性A时，属性A和B的联系是（）。关系模式中各范式之间的关系是（）。,6
24、.如下所示的关系R是（）范式。,练 习,7.关系模式STJ(S#,T,J#)中，存在函数依赖(S#,J#)T，(S#,T)J#，T J#，则关系STJ满足（）范式。,练 习,8.设有如下关系R，R的候选码是（），R中的函数依赖有（），R属于（）范式。,9.在关系模式R中，每个属性均不可分，而且是全码，那么R满足的最高范式必定是（）。,练 习,10.建立一个供应商、零件数据库。其中“供应商”表S（Sno，Sname，Zip，City）分别表示：供应商代码、供应商名、供应商邮编、供应商所在城市，其函数依赖为：Sno（Sname，Zip，City），ZipCity。“供应商”表S属于（）范式。,作
25、业,1.指出下列关系模式是第几范式？并说明理由。（1）R(X,Y,Z)F=YZ,YX,XYZ（2）R(W,X,Y,Z)F=XZ,WXY（3）R(X,Y,Z)F=XYZ（4）R(X,Y,Z)F=YZ,XZY（5）R（W,X,Y,Z F=WXZ,ZY,第六章 关系数据理论,6.1 问题的提出6.2 规范化6.3 数据依赖的公理系统6.4 模式的分解6.5 小结,6.3 数据依赖的公理系统,一.Armstrong(阿姆斯特朗)公理系统二.导出规则三.函数依赖的闭包四.Armstrong公理系统的有效性与完备性五.函数依赖集等价六.最小依赖集七.极小化算法八.候选码的求解理论和算法,6.3 数据依赖的
26、公理系统,逻辑蕴含【定义6.11】对于满足一组函数依赖 F 的关系模式R，其任何一个关系r，若函数依赖XY都成立,则称F逻辑蕴含XY,一.Armstrong公理系统,一套推理规则，是模式分解算法的理论基础,用途（1）从一组函数依赖求得逻辑蕴含的函数依赖（2）求给定关系模式的候选码,一.Armstrong公理系统,对关系模式R 来说有以下的推理规则：,【注意】由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于F,A1.自反律（Reflexivity）：若Y X U，则X Y为F所蕴含。,A2.增广律（Augmentation）：若XY为F所蕴含，且Z U，则XZYZ为F所蕴含。,
27、A3.传递律（Transitivity）：若XY及YZ为F所蕴含，则XZ为F所蕴含。,二.导出规则,(1)根据A1，A2，A3这三条推理规则可以得到下面三条推理规则：,合并规则：由XY，XZ，有XYZ。（A2，A3）,伪传递规则:由XY,WYZ,有XWZ。（A2，A3）,分解规则：由XY及 ZY，有XZ。（A1，A3）,二.导出规则,(2)根据合并规则和分解规则，可得引理6.1。,【引理6.1】XA1 A2Ak成立的充分必要条件是XAi成立（i=l，2，k）。,二.导出规则,【例1】假设关系模式为R(A,B,C,D),F=AB,BC,B D，求蕴含于F的所有非平凡的函数依赖。,1)单个属性的新
28、非平凡依赖为A C,A D2)两个属性的排列组合，8种新的：AB C,AB D,AC B,AC D,AD B,AD C,BC D,BD C3）三个属性的排列组合,3种新的：ABCD,ABD C ACDB,三.函数依赖的闭包,1.函数依赖的闭包定义【定义6.12】2.属性关于函数依赖的闭包定义【定义6.13】3.求闭包的算法【算法6.1】4.关于闭包的引理【引理6.2】,1.函数依赖的闭包定义,【定义6.12】在关系模式R中为F所逻辑蕴含的函数依赖的全体叫作 F的闭包，记为F+。,例如，已知R(X,Y,Z)，F=XY,YZ,求F+,F的闭包,F+=X,Y,Z,XY,XZ,YZ,XYZ,XX,YY
29、,ZZ,XYX,XZX,YZY,XYZX,XY,YZ,XYY,XZY,YZZ,XYZY,XZ,YYZ,XYZ,XZZ,YZYZ,XYZZ,XXY,XYXY,XZXY,XYZXY,XXZ,XYYZ,XZXZ,XYZYZ XYZ,XYXZ,XZXY,XYZXZ,XZYZ,XYXYZ,XZXYZ,XYZXYZ,2.属性关于函数依赖的闭包定义,【定义6.13】设F为属性集U上的一组函数依赖，X U，XF+=A|XA能由F 根据Armstrong公理导出，XF+称为属性集X关于函数依赖集F 的闭包。,例如，已知R(X,Y,Z)，F=XY,YZ,求XF+,求(XY)F+，(YZ)F+，(XZ)F+，.,3
30、.求闭包的算法,【算法6.1】求属性集X（X U）关于U上的函数依赖集F 的闭包XF+,输入：X，F输出：XF+,步骤：（1）令X（0）=X，i=0（2）求B，这里B=A|(V)(W)(VWF V X（i）A W)；（3）X（i+1）=BX（i）,3.求闭包的算法,（4）判断X（i+1）=X（i）吗?（5）若相等或X（i）=U,则X（i）就是XF+,算法终止。（6）若否，则 i=i+1，返回第（2）步。,对于算法6.l，令ai=|X（i）|，ai 形成一个步长大于1的严格递增的序列，序列的上界是|U|，因此该算法最多|U|-|X|次循环就会终止。,U=A,B,C,D;F=A B,BC D;A+
31、=？C+=？(AC)+=？,Example,3.求闭包的算法,【例2】已知关系模式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。,3.求闭包的算法,(2)因为X（0）X（1），所以再找出左部为ABCD子集的那些函数依赖，又得到ABC，BD，CE，ACB，于是X（2）=X（1）BCDE=ABCDE。,(3)因为X（2）=U，算法终止所以（AB）F+=ABCDE。,4.关于闭包的引理,【引理6
32、.2】设F为属性集U上的一组函数依赖，X，Y U，XY能由F 根据Armstrong公理导出的充分必要条件是Y XF+,用途 将判定XY是否能由F根据Armstrong公理导出的问题，即求F+遇到的难问题就转化为求XF+，判定Y是否为XF+的子集的问题。,4.关于闭包的引理,【例1】假设关系模式为R(A,B,C,D),F=AB,BC,B D，求蕴含于F的所有非平凡的函数依赖。,A+=ABCD,B+=BCD,C+=C,D+=D，则有新的非平凡依赖为A C,A D2)两个属性的排列组合，8种新的：AB C,AB D,AC B,AC D,AD B,AD C,BC D,BD C3）三个属性的排列组合，
33、3种新的：ABC D,ABD C，ACDB4）ABCD+=ABCD，无,四.Armstrong公理系统的有效性与完备性,有效性：由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F+中,完备性：F+中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来,/*Armstrong正确*/,/*Armstrong公理够用，完全*/,五.函数依赖集等价,【定义6.14】如果G+=F+，就说函数依赖集F覆盖G（F是G的覆盖，或G是F的覆盖），或F与G等价。,五.函数依赖集等价,【引理6.3】F+=G+的充分必要条件是 F G+，和G F+,六.最小依赖集,【定义6.15】如
34、果函数依赖集F满足下列条件，则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。,(1)F中任一函数依赖的右部仅含有一个属性。,(2)F中不存在这样的函数依赖XA，使得F与F-XA等价。,(3)F中不存在这样的函数依赖XA，X有真 子集Z使得F-XAZA与F等价。,六.最小依赖集,【例3】对于6.1节中的关系模式S，其中：U=SNO，SDEPT，MN，CNO，GRADE，F=SNOSDEPT，SDEPTMN，（SNO，CNAME）G,设F=SNOSDEPT，SNOMN，SDEPTMN，(SNO，CNAME)G，(SNO，SDEPT)SDEPT,F是最小覆盖，而F 不是。,六.最小依赖集,因
35、为：（1）F-SNOMN与F 等价（2）F-(SNO，SDEPT)SDEPT也与F 等价（3）F-(SNO，SDEPT)SDEPTSNOSDEPT也与F 等价,七.极小化算法,【定理6.3】每一个函数依赖集F均等价于一个极小 函数依赖集Fm。此Fm称为F的最小依赖集,引理6.1保证了F变换前后的等价性。,依据定义分三步对F进行“极小化处理”，找出F的一个最小依赖集。(1)逐一检查F中各函数依赖FDi：XY，若Y=A1A2 Ak，k 2，则用 XAj|j=1，2，k 来取代XY。,七.极小化算法,(2)逐一检查F中各函数依赖FDi：XA，令G=F-XA，若AXG+，则从F中去掉此函数依赖。,由于
36、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极小依赖集的过程。,七.极小化算法,【方法一】利用定理6.3求解：,用分解规则，使F中的任何一个函数依赖的右
37、部仅含有一个属性,去掉多余的函数依赖：从第一个函数依赖XY开始将其从F中去掉，得到F,然后在剩下的函数依赖中求X的闭包XF，看XF是否包含Y，若是，则去掉XY；否则不能去掉。直到找不到冗余的函数依赖。,去掉各依赖左部多余的属性：一个一个检查函数依赖左部非单个属性的依赖。例如XYA，若要判断Y为多余的，则可以用XA来代替XYA是否等价？若A（XF），则Y是多余属性，可以去掉。,七.极小化算法,【方法二】利用Armstrong公理系统的推理规则求解：假定某一函数依赖XY是冗余的，那么从F中去掉它后能根据Armstrong公理系统的推理规则导出。若能导出，则在函数依赖集中去掉XY；否则，不能去掉XY
38、。,七.极小化算法,【例4】F=AB，BA，BC，AC，CA 求其最小函数依赖集。,Fm1、Fm2都是F的最小依赖集：Fm1=AB，BC，CA Fm2=AB，BA，AC，CA,七.极小化算法,极小化过程(定理6.3的证明)也是检验F是否为极小依赖集的一个算法。若改造后的F与原来的F相同，说明F本身就是一个最小依赖集。,F的最小依赖集Fm不一定是唯一的，它与对各函数依赖FDi 及XA中X各属性的处置顺序有关。,八.候选码的求解理论和算法,给定关系模式和函数依赖集F，可将属性分成4类：（1）L类：仅出现在F的函数依赖左部的属性（2）R类：仅出现在F的函数依赖右部的属性（3）N类：在F的函数依赖左右
39、两边均未出现的属性（4）LR类：在F的函数依赖左右两边均出现的属性。,1.候选码求解理论,（1）L类属性一定是候选码中的成员；（2）R类属性一定不在任何候选码中；（3）N类属性一定是候选码中的成员；（4）LR类属性需要进一步判断。,2.候选码求解算法,输入：关系模式R及其函数依赖集F,输出：R的所有候选码,方法：（1）将R所有属性分为L、R、N、LR四类，并令X代表L、N两类，Y代表LR类；（2）求X+，若X+包含了R的全部属性，则X即为R的唯一候选码，转（5）；否则转（3）（3）在Y中取一属性A，求（XA）+。若它包含了R的全部属性，则转（4）；否则调换一属性反复进行这一过程，直到试完Y中的
40、属性；（4）如果已经找出所有候选码，则转（5）；否则在Y中依次取两个、三个、.，求它们的闭包，直到闭包含有R的所有属性。（5）停止，输出结果。,2.候选码求解算法,【例5】已知R(A,B,C),F=AB，AC，CA 求R的候选码。,练 习,1.设关系模式R（A,B,C），传递依赖指的是（11）；下列结论错误的是（12）。（11）A.若 AB，BC，则 AC B.若 AB，AC，则 ABC C.若 AC，则 ABC D.若 ABC，则 AB，AC（12）A.若 ABC，则 AB，AC B.若 AB，AC，则 ABC C.若 AC，则 ABC D.若 ABC，则 AC，BC,练 习,2.给定关系模
41、式R(U，F)，U=A，B，C，D，E，F=BA，DA，AE，ACB，其属性AD的闭包为_(21)_，其候选关键字为_(22)_。(21)A.ADE B.ABD C.ABCD D.ACD(22)A.ABD BADE CACD DCD,练 习,3.设有关系模式W(C,P,S,G,T,R),F=CG,(S,C)G,(T,R)C,(T,P)R,(T,S)R关系模式W的码是()，W的规范化程度最高达到()。若将关系模式W分解为3个关系模式W1(C,P),W2(S,C,G),W3(S,T,R,C),则W1的规范化程度最高达到(),W2达到(),W3达到()。,练 习,4设关系模式R，其中U=A,B,C,
42、D，函数依赖集F=AC,CA,BAC,DAC,BDA.（1）求出BF（2）求出F的最小函数依赖集。5.R(A,B,C,D,E,P),F=AB,CP,EA,CED,求R的所有候选码6.R(A,B,C,D,E),F=ABC,CDE,BD,EA,求(1)属性B关于F的闭包(2)R的所有候选码,练 习,7.已知F=ABCE,AC,GPB,EPA,CDEP,HBP,DHG,ABCPG,求（1）属性D关于F的闭包（2）F的最小函数依赖集,作 业,8.已知关系模式R(U,F),U=A,B,C,D,E,G;F=ABC,DEG,CA,BEC,BCD,CG BD,ACDB,CEAG请将F转换为最小函数依赖集。9.
43、设有关系模式R（ABCDE），R的函数依赖集FA D,E D,D B,BC D,CD A,求：（1）最小函数依赖集（2）R的候选码（3）将R分解为3NF,第六章 关系数据理论,6.1 数据依赖6.2 规范化6.3 数据依赖的公理系统6.4 模式的分解6.5 小结,6.4 模式的分解,把低一级的关系模式分解为若干个高一级的关系模式的方法并不是唯一的,只有能够保证分解后的关系模式与原关系模式等价，分解方法才有意义,模式的分解的定义,【定义6.16】关系模式R的一个分解：=R1,R2,Rn U=U1U2Un，且不存在 Ui Uj，Fi 为 F在 Ui 上的投影。,【定义6.17】函数依赖集合XY|X
44、Y F+XY Ui 的一个覆盖 Fi 叫作 F 在属性 Ui 上的投影,6.4.1关系模式分解的标准,分解保持函数依赖,分解具有无损连接性,分解既要保持函数依赖，又要具有无损连接性,6.4.1关系模式分解的标准,例:SL(Sno，Sdept，Mname)F=SnoSdept,SdeptMname,SnoMname,SL2NF 存在插入异常、删除异常、冗余度大和修改复杂等问题,1.具有无损连接性的模式分解,关系模式R的一个分解=R1，R2，Rn 若R与R1、R2、Rn自然连接的结果相等，则称关系模式R的这个分解具有无损连接性（Lossless join）,具有无损连接性的分解保证不丢失信息 无损
45、连接性不一定能解决插入异常、删除异常、修改复杂、数据冗余等问题,无损连接的测试算法【算法6.2】,输入：关系模式R(A1,A2,An),它的函数依赖集及分解p=R1,R2,Rk输出：确定p是否具有无损连接性,步骤：（1）构造k行n列的表，第i行对应于关系模式Ri，第j列对应于属性Aj。如果AjRi，则在第i行第j列上放符号aj，否则放符合bij。（2）逐个检查F中的每一个函数依赖，并修改表中的元素。其方法如下：取F中一个函数依赖xY，在X的分量中寻找相同的行，然后将这些行中Y的分量改为相同的符号，如果其中有aj，则bij改为aj；若其中无aj，则改为bij。,无损连接的测试算法【算法6.2】,
46、（3）这样反复进行，若发现某一行变成了a1,a2,ak，则分解p具有无损连接性；如果F中所有函数依赖都不能再修改表中的内容，且没有发现这样的行，则分解具有无损连接性。,【例】已知R(A,B,C,D,E),F=ABC,CD,DE,R的一个分解为R1(A,B,C),R2(C,D),R3(D,E)，判断是否具有无损连接性。,1.具有无损连接的分解,将SL分解为ND(Sno,Sdept)NL(Sno,Mname),问题:这种分解方法没有保持原关系中的函数依赖 SL中的函数依赖SdeptMname没有投影到关系模式ND、NL上,分解具有无损连接性,1.保持函数依赖的模式分解,【例】给定关系模式R(A,B
47、,C,D),F=AB,BC,CD,DA判断关系模式的分解p=AB,BC,CD是否具有保持依赖性。,1.保持函数依赖的模式分解,【快捷判定定理】设p=R1，R2是R的一个分解，F是R上的FD集，那么分解p相对于F是无损分解的充要条件是R1R2R1-R2或R1R2R2-R1。,2.保持函数依赖的模式分解,设关系模式R被分解为若干个关系模式 R1，R2，Rn（其中U=U1U2Un，且不存在Ui Uj，Fi为F在Ui上的投影），若F所逻辑蕴含的函数依赖一定也由分解得到的某个关系模式中的函数依赖Fi所逻辑蕴含，则称关系模式R的这个分解是保持函数依赖（Preserve dependency）。,2.保持函
48、数依赖的模式分解,将SL分解为下面二个关系模式：ND(Sno,Sdept)DL(Sdept,Mname)这种分解方法就保持了函数依赖,6.4.1关系模式分解的标准,1.如果一个分解具有无损连接性，则它能够保证不丢失信息,2.如果一个分解保持了函数依赖，则它可以减轻或解决各种异常情况,3.分解具有无损连接性和分解保持函数依赖是两个互相独立的标准。具有无损连接性的分解不一定能够保持函数依赖；同样，保持函数依赖的分解也不一定具有无损连接性。,6.4.1关系模式分解的标准,1.S-L分解为三个关系模式：SN(Sno)SD(Sdept)SO(Mname)2.SL分解为下面二个关系模式：NL(Sno,Mn
49、ame)DL(Sdept,Mname)3.将SL分解为下面二个关系模式：ND(Sno,Sdept)NL(Sno,Sname),6.4.1关系模式分解的标准,4.将SL分解为二个关系模式：ND(Sno,Sdept)DL(Sdept,Mname),6.4.1关系模式分解的标准,第1种分解方法既不具有无损连接性，也未保持函数依赖，它不是原关系模式的一个等价分解 第2种分解方法既不具有无损连接性，也未保持函数依赖第3种分解方法具有无损连接性，但未保持函数依赖 第4种分解方法既具有无损连接性，又保持了函数依赖,6.4.2 模式分解的算法,【算法6.3】（合成法）转换为3NF的保持函数依赖的分解。,【算法
50、6.4】转换为3NF既有无损连接性又保持函数依赖的分解,【算法6.5】（分解法）转换为BCNF的无损连接分解,【算法6.6】达到4NF的具有无损连接性的分解,6.4.2 模式分解的算法,1.若要求分解具有无损连接性，那么模式分解一定能够达到4NF。,2.若要求分解保持函数依赖，那么模式分解一定能够达到3NF，但不一定能够达到BCNF。,3.若要求分解既具有无损连接性，又保持函数依赖，则模式分解一定能够达到3NF，但不一定能够达到BCNF。,【算法6.3】保持函数依赖的3NF分解,步骤:(1)如果Fm中有一依赖XA,且XA=R，则输出p=R，转(4)(2)如果R中某些属性与F中所有依赖的左部和右
