数据库课件第六章关系数据库设计理论.ppt

数据库原理及应用,第六章 关系数据库设计理论,问题的提出,基本概念,规范化,函数依赖的公理系统,模式分解,6.1 问题的提出,针对一个具体问题，设计一个好的关系数据库系统，关键是要构造一个适合于它的数据模式（数据库逻辑设计问题） 数据库逻辑设计主要解决的问题： 应该构造几个关系模式 每个关系模式包括哪些属性 数据库逻辑设计工具关系数据库的规范化理论,6.1 问题的提出,例：描述电力设备存放管理的数据库数据库： WAE(仓库号，所在区域，区域主管，设备号，数量),语义： 一个区域有多个仓库，一个仓库只能属于一个区域； 一个区域只有一个区域主管； 一个仓库可以存放多种设备，每种设备可以存放在多个仓库中； 每个仓库的每种设备都有一个库存数量。,6.1 问题的提出, 数据冗余太大 浪费大量的存储空间 更新异常 更新代价大，可能导致数据不一致 插入异常 该插的数据插不进去 删除异常 不该删除的数据不得不删，造成某些数据丢失,存在的问题：,6.1 问题的提出,结论： WAE关系模式不是一个好的模式。 “好”的模式：不会发生插入异常、删除异常、更新异常，数据冗余应尽可能少。 原因：由存在于模式中的某些数据依赖引起的 解决方法：通过分解关系模式来消除其中不合适的数据依赖。,6.1 问题的提出,分解成三个关系模式即可： W(仓库号，所在区域)； A(区域，区域主管)； WE(仓库号，设备号，数量),6.2 基本概念,规范化理论正是用来改造关系模式，通过分解关系模式来消除其中不合适的数据依赖，以解决插入异常、删除异常、更新异常和数据冗余等问题。,6.2.1 函数依赖,定义6.1 设R(U)是一个属性集U上的关系模式，X和Y是U的子集。若对于R(U)的任意一个可能的关系r，对t1,t2 r，若t1X=t2X，则t1Y=t2Y则称X函数决定Y或Y函数依赖X，记作XY。,如：仓库号 所在区域 所在区域 区域主管 （仓库号，设备号） 数量,若XY，则称X为这个函数依赖的决定因素。,6.2.1 函数依赖,1. 函数依赖是语义范畴的概念，只能根据数据的语义来确定函数依赖。 例：“区域主管所在区域” 只有在不允许有同名人的条件下成立 2. 函数依赖不是指关系模式R的某个或某些关系实例满足的约束条件，而是指R的所有关系实例均要满足的约束条件。 3.函数依赖存在的时间无关性。,说明:,6.2.1 函数依赖,函数依赖与属性间的联系类型有关 (1) 若属性X和Y之间有“一对一”的联系 则：X Y,Y X,X Y (2) 若属性X和Y之间有“多对一”的联系 则：X Y,但Y X (3)若属性X和Y之间有“多对多”的联系 则：X与Y之间不存在任何函数依赖 注：当确定函数依赖关系时,可从属性间的联系入手,6.2.1 函数依赖,平凡函数依赖与非平凡函数依赖,定义6.2 在关系模式R(U)中，对于U的子集X和Y： 若XY，但Y X，则称XY是非平凡函数依赖. 若XY，但Y X，则称XY是平凡函数依赖.,例：在关系WAE中， 非平凡函数依赖：（仓库号，设备号） 数量 平凡函数依赖： （仓库号，设备号）仓库号 （仓库号，设备号）设备号,注：对任一关系模式，平凡函数依赖必然存在，则一般讨论非平凡函数依赖。,6.2.1 函数依赖,完全函数依赖与部分函数依赖,6.2.1 函数依赖,传递函数依赖与直接函数依赖,如果YX， 即XY，则Z对X直接函数依赖。,例：在关系wae中有：,仓库号所在区域，所在区域区域主管 可得到传递函数依赖：仓库号 t 区域主管,6.2.2 码,定义6.5 设K为R中的属性或属性组合。若K F U，则K称为R的一个侯选码。 若关系模式R有多个候选码，则选定其中的一个做为主码。,主属性：包含在任何一个候选码中的属性 非主属性：不包含在任何一个码中的属性 全码：整个属性组全是码,6.2.2 码,定义6.5 关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R的外部码，也称外码。,注：主码和外码一起提供了表示关系间联系的手段。,例：在关系SC(Sno, Cno, Grade)中， 由于：Sno不是SC的码，但是另一个关系S的码 因此：Sno是SC的外码,6.3 规范化,范式是对关系数据库的规范化过程中为不同程度的规范化要求设立的不同标准。 范式是符合某一种级别的关系模式的集合。,6.3 规范化,各种范式之间存在联系： 5NF 4NF BCNF 3NF 2NF 1NF 某一关系模式R为第n范式，可简记为RnNF。 通过模式分解将一个低级范式的关系模式转换为若干个高级范式的关系模式的过程称作规范化。,6.3.1 第一范式（1NF）,定义6.7 满足最低要求的范式。 如果一个关系模式R的所有属性都是不可分的基本数据项，则R1NF。,第一范式是对关系模式的最起码要求。 不满足第一范式的数据库模式不能称为关系数据库。 但满足第一范式的关系模式并不一定是一个好的关系模式。,6.3.2 第二范式（2NF）,定义6.8 若关系模式R1NF，并且每一个非主属性都完全函数依赖于R的码，则R2NF。 即：消除非主属性对码的部分依赖,如果一个数据库模式中的每个关系模式都是第二范式的，则称此数据库模式属于第二范式的数据库模式。 从1NF中消除非主属性对候选码的部分函数依赖,则获得2NF。,6.3.2 第二范式（2NF）,例: 关系模式WAE中: WAE(仓库号，所在区域，区域主管，设备号，数量),码： (仓库号, 设备号) 主属性:仓库号, 设备号 非主属性: 所在区域、区域主管和数量,函数依赖：,6.3.2 第二范式（2NF）,码为(仓库号, 设备号) 非主属性所在区域和区域主管部分函数依赖于码 WAE满足第一范式，但不满足第二范式。,6.3.2 第二范式（2NF）,解决方法：将WAE分解为两个关系模式，消除这些部分函数依赖： 即： WE（仓库号，设备号，数量） WA（仓库号，所在区域，区域主管）,WE2NF, WA2NF,6.3.2 第二范式（2NF）,注： 采用投影分解法将一个1NF的关系分解为多个2NF的关系，可以在一定程度上减轻原1NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。 将一个1NF关系分解为多个2NF的关系，并不能完全消除关系模式中的各种异常情况和数据冗余。 如：(1) 若某个区域刚刚设立还没有仓库，则所在区域和区域主管的值无法插入，造成插入异常。 (2) 有一定的数据冗余，当多个仓库处于同一个区域时，区域主管的值被多次存储。 (3) 若某区域要更换区域主管，则要逐一地修改该区域的所有区域主管记录，稍有不慎，就有可能漏改某些记录，造成更新异常。,6.3.3 第三范式（3NF）,如果一个数据库模式中的每个关系模式都是第三范式的，则称此数据库模式属于第三范式的数据库模式。 从2NF中消除非主属性对候选码的传递依赖,则获得3NF。,定义6.9 如果关系模式R2NF，且每个非主属性都不传递函数依赖于R的候选码，则称R属于第三范式，简称3NF，记作R3NF。 即：消除非主属性对码的部分依赖和传递依赖,6.3.3 第三范式（3NF）,例: WE（仓库号，设备号，数量） WA（仓库号，所在区域，区域主管）,6.3.3 第三范式（3NF）,原因:区域主管传递依赖于码。 解决方法：将WA分解为两个关系模式，消除这些传递依赖： 即： W（仓库号，所在区域） A（所在区域，区域主管）,W3NF, A3NF,6.3.3 第三范式（3NF）,注： 采用投影分解法将一个2NF的关系分解为多个3NF的关系，可以在一定程度上减轻原2NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。 将一个2NF关系分解为多个3NF的关系，并不能完全消除关系模式中的各种异常情况和数据冗余。表现在可能存在主属性对码的部分和传递依赖。,6.3.4 BC范式（BCNF）,BCNF范式是第三范式的改进形式，建立在第一范式的基础上，消除了主属性对码的部分和传递依赖。,定义6.10 设关系模式R1NF，若对于R的每个函数依赖XY，若Y不属于X，则X必含有候选码，那么RBCNF。 即：每一个决定因素（决定属性集）都包含码,6.3.4 BC范式（BCNF）,证明：BCNF 3NF 反证：若RBCNF， 但R3NF，则按3NF定义，一定有非主属性对码的传递依赖。 于是存在：R的码X ，属性组Y，以及非主属性Z（Z Y），使得XY， Y Z，YX成立。 由YZ，按BCNF定义，Y含有码，则是YX成立，这与YX矛盾。 所以：R3NF。,6.3.4 BC范式（BCNF）,注意： 若RBCNF ，则R3NF 若R3NF ，则R不一定属于BCNF,若RBCNF 所有非主属性对每一个候选码都是完全函数依赖； 所有主属性对每一个不包含它的候选码都是完全函数依赖； 没有任何属性完全函数依赖于非码的任何一组属性。,6.3.4 BC范式（BCNF）,例1: Course（Cno, Creidt, Pcno）,函数依赖： Cno Credit, Cno Pcno 即：无部分依赖和传递依赖，且Cno是唯一决定因素,因此： Course 3NF，且Course BCNF,码： Cno 即为主属性，决定因素,6.3.4 BC范式（BCNF）,例2：在关系模式SCP（S, C, P）中，S表示学生，C表示课程， P表示名次。,说明： 每一个学生选修每一门课程都有一个固定的名次： 每一门课程中每一名次只对应一个学生（假设没有相同名次的学生） ：,(S，C)P,(C，P)S,6.3.4 BC范式（BCNF）,候选码： (S，C) 和(C，P) 即：S，C和P都是主属性,决定因素： (S，C)和(C，P),结论：,SCPBCNF 只有(S，C)和(C，P)决定因素且包含候选码，无其他决定因素,SCP3NF S、C、P都是主属性 无部分依赖和传递依赖,6.3.4 BC范式（BCNF）,例3：在关系模式WES(仓库号,设备号,职工号)中。,说明： 一个仓库可以有多个职工; 一个职工仅在一个仓库工作; 每个仓库一种设备仅由一名职工保管,但每名职工可以保管多种设备.,问:该关系的码?属于第几范式?,答:码: (仓库号,设备号) 属于3NF,但不属于BCNF,非BCNF的不良特性:某位职工刚分配到一个仓库工作，但尚未负责具体设备，这样的信息就无法插入。,职工号仓库号,(仓库号,设备号) 职工号,6.3.5 多值依赖与第四范式,例: 学校中某一门课程由多个教师讲授，他们使用相同的一套参考书。 即：关系模式Teaching(C, T, B) 课程C、教师T 和 参考书B,6.3.5 多值依赖与第四范式,用二维表表示Teaching,6.3.5 多值依赖与第四范式,Teach具有唯一候选码(C, T, B)， 即全码 TeachingBCNF,存在的问题 (1)数据冗余：有多少名任课教师，参考书就要存储多少次 ； (2)插入异常：当某一课程增加一名任课教师时，该课程有多少本参照书，就必须插入多少个元组；,(3) 删除异常：某一门课要去掉一本参考书，该课程有多少名教师，就必须删除多少个元组； (4) 修改异常：某一门课要修改一本参考书，该课程有多少名教师，就必须修改多少个元组。,产生原因：存在多值依赖,6.3.5 多值依赖与第四范式,定义6.11 设R(U)是属性集U上的一个关系模式。X、 Y、Z是U的子集，并且ZUXY，多值依赖 XY成立当且仅当对R的任一关系r，给定一对（x，z）值，则对应一组Y值，且这组值仅仅决定于X值而与Z值无关。,例： Teaching（C, T, B） 对于C的每一个值，T总有一组值与之对应，而与B的取值无关，则T多值依赖于C即：CT，且B也多值依赖于C即：CB。,6.3.5 多值依赖与第四范式,平凡多值依赖和非平凡的多值依赖 若XY，而Z，则称XY为平凡的多值依赖； 否则称XY为非平凡的多值依赖。,如非平凡的多值依赖：CT，CB,6.3.5 多值依赖与第四范式,多值依赖的性质：,（1）对称性： 即：若XY，则XZ，其中ZUXY 多值依赖的对称性可以用完全二分图直观地表示出来。,（2）传递性： 即：若XY，YZ， 则XZ Y,6.3.5 多值依赖与第四范式,完全二分图描述多值依赖对称性,6.3.5 多值依赖与第四范式,（5）函数依赖是多值依赖的特殊情况： 即：若XY，则XY。,（3）合并性: 若XY，XZ，则 XY Z。 （4）分解性: 若XY，XZ，则 XYZ, XYZ， XZY。,6.3.5 多值依赖与第四范式,定义6.12 关系模式R1NF，如果对于R的每个非平凡多值依赖XY（Y X），X都含有候选码，则R4NF。 即：消除各属性间非平凡且非函数依赖的多值依赖。,允许出现函数依赖（非平凡多值依赖） 允许出现平凡多值依赖 如果R 4NF， 则R BCNF,6.3.5 多值依赖与第四范式,证明：4NF BCNF 反证：若R4NF， 但RBCNF，则按BCNF定义，一定有一个决定因素不包含码。 于是存在：XY， Y X，且X中不含有码。 由于函数依赖是多值依赖的特殊情况，即：XY ，可得XY （Y X） ，按4NF定义，X一定含有码，则与X中不含有码矛盾。 所以：RBCNF。,6.3.5 多值依赖与第四范式,存在非平凡的多值依赖CT，且C不是候选码，该关系模式的码是(C,T,B) ，即全码。 存在问题：数据冗余大，插入、删除、更新异常 解决方法：用投影分解法把Teach分解为如下两个关系模式： CT(C, T) 4NF CB(C, B) 4NF 其中：CT， CB是平凡多值依赖,6.3.5 多值依赖与第四范式,函数依赖和多值依赖是两种非常重要的数据依赖 若只考虑函数依赖，则BCNF为最高范式（但不是数据库模式设计的最高范式）； 若考虑多值依赖，则4NF为最高范式； 若消除了4NF中的连接依赖，可以得到更为规范化的5NF。,6.3.6 关系模式规范化,一个关系只要其分量都是不可分的数据项，它就是规范化的关系，但这只是最基本的规范化1NF。 规范化程度过低的关系不一定能够很好地描述现实世界，可能会存在插入异常、删除异常、修改复杂、数据冗余等问题。 一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式集合，这种过程就叫关系模式的规范化。,6.3.6 关系模式规范化,消除不合适的数据依赖; 采用“一事一地”的模式设计原则，使各关系模式达到某种程度的“分离”； 让一个关系描述一个概念、一个实体或者实体间的一种联系; 若多于一个概念就把它“分离”出去； 所谓规范化实质上是概念的单一化。,规范化的基本思想,6.3.6 关系模式规范化,关系模式规范化的基本步骤 1NF 消除决定因素 2NF 非码的非平凡 函数依赖 3NF BCNF 4NF,消除非主属性对码的部分函数依赖,消除非主属性对码的传递函数依赖,消除主属性对码的部分和传递函数依赖,消除非平凡且非函数依赖的多值依赖,不能说规范化程度越高的关系模式就越好； 在设计数据库模式结构时，必须对现实世界的实际情况和用户应用需求作进一步分析，确定一个合适的、能够反映现实世界的模式； 上面的规范化步骤可以在其中任何一步终止。,注意：,练习,给定关系模式和函数依赖集合，要求判断达到的最高范式。步骤如下： 1.求出给定关系的候选码（可能不止一个） 2.根据码，写出主属性和非主属性。 3.判断是否满足第一范式(属性的值域是否可以分解） 4.判断是否满足第二范式(非主属性对码的部分函数依赖) 5.判断是否满足第三范式(非主属性对码的传递函数依赖) 6.判断是否满足BCNF范式(主属性对码的传递和部分函数依赖),解：1. 关系r的候选码为：AB和AC,练习1. 已知关系模式R U=A,B,C,D F=ABD, AC BD, BC 在函数依赖范围内该关系属于的最高范式是什么？,2. 主属性为：A、B、C 非主属性为：D,3. 判断是否满足各个范式的要求： 1) R的所有的属性值域都不可再分，则r 1NF。 2) 非主属性D不存在对任何码的部分函数依赖，则r 2NF。 3) 非主属性D不存在对任何码的传递函数依赖，则r 3NF。 4) 因为有函数依赖BC，而B不是关系R的码，则r不属于BCNF。,则： r 3NF,解：1. 关系r的候选码为：AC,练习2. 已知关系模式R U=A,B,C,D,E,F F=AB, C DF, ACE, DF 在函数依赖范围内该关系属于的最高范式是什么？,2. 主属性为：A、C 非主属性为：B、D、E、F,3. 判断是否满足各个范式的要求： 1) R的所有的属性值域都不可再分，则r 1NF。 2) 由于存在函数依赖AB, C DF，而A和C均不是关系的码，存在非主属性B、D、F对码的部分函数依赖，则r不属于2NF。,则： r 1NF,练习,练习3.假设：某商业集团数据库中有一关系模式R如下： R (商店编号，商品编号，数量，部门编号，负责人) 如果规定： (1) 每个商店的每种商品只在一个部门销售； (2) 每个商店的每个部门只有一个负责人； (3) 每个商店的每种商品只有一个库存数量。 试回答下列问题： (1) 根据上述规定，写出关系模式R的基本函数依赖； (2) 找出关系模式R的候选码； (3) 试问关系模式R最高已经达到第几范式？为什么？ (4) 如果R不属于3NF，请将R分解成3NF模式集,练习,(1)有三个函数依赖： (商店编号，商品编号) 部门编号 (商店编号，部门编号) 负责人 (商店编号，商品编号) 数量 (2) R的候选键: (商店编号，商品编号) (3)因为R中存在着非主属性“负责人”对候选码 (商店编号、商品编号)的传递函数依赖，但无部分函数依赖，所以R属于2NF，R不属于3NF。 (4) 将R分解成： R1 (商店编号，商品编号，数量，部门编号) R2 (商店编号，部门编号，负责人),6.4 函数依赖的公理系统,逻辑蕴含 定义6.13 对于满足一组函数依赖 F 的关系模式R ，其任何一个关系r，若函数依赖XY都成立， 则称F逻辑蕴含X Y ，或称X Y 为F所蕴含。,即：对于r中任意两个元组t和s， 有：若 tX=sX 则 tY=sY 必成立。,6.4.1 Armstong公理系统,Armstrong公理系统函数依赖的推理规则 关系模式R 有以下推理规则：,Al 自反律：若Y X U，则X Y为F所蕴含。 A2 增广律：若XY为F所蕴含，且Z U，则XZYZ为F所蕴含。 A3 传递律：若XY及YZ为F所蕴含，则XZ为F所蕴含。,注：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于F。,6.4.1 Armstong公理系统,伪传递规则：若X Y，WY Z，则XW Z 。 分解规则：若X Y及 ZY，则X Z 。,X Y 增广律,X Z 增广律,传递律,证明合并规则：,由Armstrong公理导出的推理规则:,合并规则：若X Y，X Z，则X YZ。,6.4.2 闭包,引理6.l 若A1A2An是关系模式R的属性集, 则：XA1 A2Ak XAi成立(i=l,2,k)。,证明：充分性：由合并律 必要性：由分解律 ,根据合并规则和分解规则，可得：,6.4.2 闭包,定义6.14 在关系模式R中为F所逻辑蕴含的函数依赖的全体叫作 F的闭包，记为F+。,定义6.15 设F为属性集U上的一组函数依赖，X U， XF+ = A|XA能由F 根据Armstrong公理导出，XF+称为属性集X关于函数依赖集F 的闭包。,引理6.2 设F为属性集U上的一组函数依赖，X，Y U，XY能由F 根据Armstrong公理导出的充分必要条件是Y XF+,用途：将判定XY是否能由F根据Armstrong公理导出的问题，转化为求出XF+ ，判定Y是否为XF+的子集的问题。,6.4.2 闭包,算法6.l 求属性集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）,（4）判断X（i+1）= X （i）吗? （5）若相等或X（i）=U , 则X（i）就是XF+ , 算法终止。 （6）若不相等, 则 i=i+l，返回第（2）步。,例： 已知关系模式R，其中U=A，B，C，D，E F=ABC，BD，CE，ECB，ACB 求（AB）F+ 。,解： (1) 设X（0）=AB； (2) 计算X（1）: 逐一扫描F集合中各个函数依赖，找左部为A，B或AB的函数依赖。 得到两个：ABC，BD。 (3) X（1）=ABCD=ABCD。,(4) X（0） X（1） 则需再找出左部为ABCD子集的那些函数依赖，又得到ABC，BD， CE，ACB 于是：X（2）=X（1）BCDE=ABCDE。 (5) X（2）=U，算法终止 所以（AB）F+ =ABCDE,6.4.2 闭包,练习： 已知关系模式R，其中 U=A，B，C，D，E，G F=AE, BEAG, CEA, GD 求（AB）F+ 。,解： 所用依赖 （AB）F+ AB AE（ A AB) ABE BEAG(BE ABE) ABEG GD(G ABEG) ABEGD,所以：（AB）F+ = ABDEG,6.4.3 函数依赖集的等价和最小化,函数依赖等价 定义6.16 如果G+=F+，就说函数依赖集F覆盖G（F是G的覆盖，或G是F的覆盖），或F与G等价。,引理6.3 F+ = G+ 的充分必要条件是： F G+ 和 G F+,6.4.3 函数依赖集的等价和最小化,最小依赖集 定义6.17 如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集，亦称为最小依赖集或最小覆盖: (1) F中任一函数依赖的右部仅含有一个属性。 (2) F中不存在这样的函数依赖XA，使得F与 F- XA等价。 (3) F中不存在这样的函数依赖XA， X有真子集Z使得（F - XA）ZA与F等价。,6.4.3 函数依赖集的等价和最小化,例: 对于关系模式S，其中： U=SNO，SDEPT，MN，CNAME，G ， F=SNOSDEPT, SDEPTMN, (SNO，CNAME)G 设:F=SNOSDEPT, SNOMN, SDEPTMN, (SNO,CNAME)G, (SNO,SDEPT)SDEPT F是最小覆盖，而F不是 因为：F-SNOMN与F 等价 F-(SNO，SDEPT)SDEPT也与F 等价,6.4.3 函数依赖集的等价和最小化,定理6.1 每一个函数依赖集F均等价于一个极小函数依赖集Fm，此Fm称为F的最小依赖集。 求解过程:依据定义分三步对F进行“极小化处理”，找出F的一个最小依赖集： (1) 逐一检查F中各函数依赖FDi：XY 若Y=A1A2 Ak，k 2， 则用 XAj |j=1，2， k 来取代XY。 理由：引理6.1保证了F变换前后的等价性。,6.4.3 函数依赖集的等价和最小化,(2)逐一检查F中各函数依赖FDi：XA 令G=F-XA， 若AXG+， 则从F中去掉此函数依赖。,理由：由于F与G =F-XA等价的充要条件是AXG+ ，因此F变换前后是等价的。,6.4.3 函数依赖集的等价和最小化,(3)逐一取出F中各函数依赖FDi：XA 设X=B1B2Bm， 逐一考查Bi （i=l，2，m）， 若A （X-Bi ）F+ ， 则以X-Bi 取代X。,理由：由于F与（F-XA）ZA等价的充要条件是AZF+ ，其中Z=X-Bi ，因此F变换前后是等价的。即：若AZF+ ，则说明ZA F+ ，又由Z X，则 XA F+ ，用Z取代X即可。,6.4.3 函数依赖集的等价和最小化,例：已知关系模式R，UA，B，C，D，E，G；FABC，CA，CGBD，ACDB，求F的最小函数依赖集。,(1) 分解右边: FABC，CA，CGB，CGD，ACDB (2)去掉F中多余的函数依赖: 检查ABC： G=F-ABC=CA，CGB，CGD，ACDB 则：ABG+ = AB， CAB 保留ABC： F = ABC，CA，CGB，CGD，ACDB,6.4.3 函数依赖集的等价和最小化,检查CA： G=F-CA=ABC, CGB, CGD, ACDB 则：CG+ = C， A C 保留CA：F = ABC，CA，CGB，CGD，ACDB,检查CGB： G=F-CGB=ABC, CA, CGD, ACDB 则：CGG+ = ABCDG， B ABCDG 删除CGB： F = ABC, CA, CGD, ACDB,6.4.3 函数依赖集的等价和最小化,检查CGD： G=F-CGD=ABC, CA, ACDB 则：CGG+ = ACG， D ACG 保留CGD： F = ABC, CA, CGD, ACDB,检查ACDB： G=F-ACDB=ABC, CA, CGD 则：ACDG+ = ACD， B ACD 保留ACDB： F = ABC, CA, CGD, ACDB,则： F = ABC, CA, CGD, ACDB,6.4.3 函数依赖集的等价和最小化,(3)去掉F中各依赖左部多余的属性:,检查ABC： G=F-ABC=CA, CGD, ACDB 由于：AG+ = A， BG+ = B 保留ABC： F = ABC, CA, CGD, ACDB,F = ABC, CA, CGD, ACDB,检查CGD： G=F-CGD=ABC, CA, ACDB 由于：CG+ = C，A， GG+ = G 保留CGD： F = ABC, CA, CGD, ACDB,6.4.3 函数依赖集的等价和最小化,检查ACDB： G=F-ACDB=ABC, CA, CGD 由于：CDG+ = C，D，A， 包含A 则A多余，可用CDB替代ACDB 得到： F = ABC, CA, CGD, CDB,最后： Fmin = ABC, CA, CGD, ACDB,F = ABC, CA, CGD, ACDB,注意:1)F的最小依赖集Fm不一定是唯一的，它与对各函数依赖FDi 及XA中X各属性的处置顺序有关。 2)若改造后的F与原来的F相同，说明F本身就是一个最小依赖集。,6.5 模式分解,把低一级的关系模式分解为若干个高一级的关系模式的方法并不是唯一的； 只有能够保证分解后的关系模式与原关系模式等价，分解方法才有意义； 实际上，关系模式的分解，不仅仅是属性集合的分解，它是对关系模式上的函数依赖集，以及关系模式的当前值的分解的具体表现。,6.5.1 模式分解的准则,定义6.18 关系模式R的一个分解： = R1，R2，Rn 其中：U=U1U2Un，且不存在 Ui Uj， Fi 为 F在 Ui 上的投影。,定义6.19 函数依赖集合XY|XYF+XY Ui 的一个覆盖 Fi 叫作 F 在属性 Ui 上的投影。,6.5.1 模式分解的准则,三种模式分解的“等价”定义： 分解具有无损连接性 分解要保持函数依赖 分解既要保持函数依赖，又要具有无损连接性,6.5.2 分解的函数依赖保持性和无损连接性,例: 已知关系模式：SDL U=Sno, Sdept, Sloc F=SnoSdept, SdeptSloc, SnoSloc,因为：SDL中存在传递函数依赖 SnoSloc 所以： SL2NF,存在插入异常、删除异常、冗余度大和更新异常等问题，则可进行分解，且分解方法可以有多种：,6.5.2 分解的函数依赖保持性和无损连接性,SDL Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004 IS B 95005 PH B ,6.5.2 分解的函数依赖保持性和无损连接性,第一种分解： SDL分解为下面三个关系模式： SN(Sno) SD(Sdept) SO(Sloc),SN SD SO Sno Sdept Sloc 95001 CS A 95002 IS B 95003 MA C 95004 PH 95005 ,注：分解后的数据库丢失了许多信息,6.5.2 分解的函数依赖保持性和无损连接性,第二种分解： SDL分解为下面两个关系模式： NL(Sno, Sloc) DL(Sdept, Sloc),NL DL Sno Sloc Sdept Sloc 95001 A CS A 95002 B IS B 95003 C MA C 95004 B PH B 95005 B ,