1971 E.F.Codd 提出 1NF 2NF 3NF BCNF 4NF 5NF 规范化 函数依赖 模式分解14.1 4.1 问题的提出问题的提出关系模式 R (UR (U，D D，domdom，I I，F) F) 数据依赖：关系中属性间互相依存、互相制约的关系。 函数依赖函数依赖、多值依赖、连接依赖、分层依赖和相互依赖2例：例： U=学号，系部，系主任，课程名称，成绩 F=学号系部，系部 系主任, (学号，课程名称) 成绩系部系部系主任系主任成绩成绩 学号学号课程名称课程名称3缺点1、冗余太大2、操作异常 1）插入异常 2）删除异常 3）修改异常 学号学号系部系部 系主系主任任 课程课程 名称名称成成绩绩02101CSXAAA02101CSXBBB02101CSXCCA02102MAMAAB02102MAMDDA02103MAMEEC02104ISJEEB02105ISJBBA4通过适当地进行模式分解通过适当地进行模式分解可以避免上述问题：可以避免上述问题：1、冗余太大2、操作异常 1）插入异常 2）删除异常 3）修改异常学生（学号，系部）系部（系部，系主任）选课（学号，课程名称，成绩）原模式分解为三个子模式原模式分解为三个子模式5适当地进行模式分解适当地进行模式分解关系规范化理论关系规范化理论即适当地进行模式分解的理论，包括：即适当地进行模式分解的理论，包括： 4.2 函数依赖和范式理论函数依赖和范式理论 4.3 ArmStrong公理系统公理系统 4.4 模式分解的方法模式分解的方法6范式理论的目的和内容：范式理论的目的和内容：1） 定义范式级别：定义范式级别：衡量模式的规范化程度，即模式衡量模式的规范化程度，即模式的数据冗余和操作异常程度。的数据冗余和操作异常程度。2）范式的判定：）范式的判定：通过分析模式中的数据依赖关系，通过分析模式中的数据依赖关系，判断关系模式的范式级别。判断关系模式的范式级别。3）函数依赖：）函数依赖：是最基本的数据依赖关系，是属是最基本的数据依赖关系，是属性或者属性组间存在的依赖。性或者属性组间存在的依赖。7定义和判定范式级别定义和判定范式级别利用函数依赖利用函数依赖一、定义函数依赖的概念一、定义函数依赖的概念二、基于函数依赖来重新定义候选码二、基于函数依赖来重新定义候选码三、几种级别的范式及其判定三、几种级别的范式及其判定8一、定义函数依赖函数依赖：类比于数学函数f: XY定义定义4.1：设设R(U)是属性集是属性集U上的关系模式。上的关系模式。X，Y是是U的子集。若对于的子集。若对于R(U)的任意一个可能的关的任意一个可能的关系系r，当且仅当，当且仅当r中任意一个给定的中任意一个给定的X的值，的值，r中存中存在唯一的在唯一的Y值与之对应。则称值与之对应。则称Y函数依赖与函数依赖与X，或，或者者X函数确定函数确定Y，记作，记作XY。回忆：映射，单射、满射、双射、函数回忆：映射，单射、满射、双射、函数9定义定义4.3：R（U）的属性子集的属性子集X，Y之间的函数依赖用之间的函数依赖用X Y表示，它在构成关系表示，它在构成关系R的任意元组的任意元组r上指定了一上指定了一个约束。这个约束是：如果对于个约束。这个约束是：如果对于r中的任何两个元组中的任何两个元组t1和和t2有有t1Xt2X，则必须也有则必须也有t1Yt2Y。 定义定义4.2：设设R(U)是属性集是属性集U上的关系模式，上的关系模式，X，Y是是U的子集。若对于的子集。若对于R (U)的任意一个可能的关系的任意一个可能的关系r，r中不可能存在两个元组在中不可能存在两个元组在X上的属性值相等，而在上的属性值相等，而在Y上的属性值不等，则称上的属性值不等，则称X函数确定函数确定Y或或Y函数依赖于函数依赖于X，记作记作XY。一、定义函数依赖10例如：例如：U=学号，系部，系主任，课程名称，成绩 F=学号系部，系部 系主任, (学号，课程名称) 成绩注意：函数依赖，不是指关系模式R的某个或某些关系满足的条件，而是指R的一切关系均要满足的约束条件11由函数依赖导出的概念： 1 .1 .决定因素：决定因素：若XY，则X叫做决定因素 2 .2 .互相依赖：互相依赖：若XY， YX， 则记作XY。 3 .3 .若若Y Y不函数依赖于不函数依赖于X X，则记作X Y。一、定义函数依赖12 定义定义4.4 ：平凡（非平凡）函数依赖平凡（非平凡）函数依赖在在R(U)中，一个函数依赖中，一个函数依赖XY，如果满足，如果满足Y X，则称此函数依赖是非平凡函数依赖，则称此函数依赖是非平凡函数依赖，否则称为平凡函数依赖。否则称为平凡函数依赖。 一、定义函数依赖几种类型的函数依赖：几种类型的函数依赖：13 定义定义4.5 ：完全函数依赖完全函数依赖 在在R(U)中，如果中，如果X Y，并且对于并且对于X的的任何一个真子集任何一个真子集X，都有都有X Y，则称则称Y对对X完全函数依赖。记作：完全函数依赖。记作：FXY 定义定义4.6 ：部分函数依赖部分函数依赖 在在R(U)中，如果中，如果X Y，存在真子集存在真子集X，有有X Y成立，则称成立，则称Y对对X部分函数依赖。部分函数依赖。记作记作： PXY几种类型的函数依赖：几种类型的函数依赖：14定义定义4.74.7：传递函数依赖传递函数依赖 在在R(U)中，如果对于非平凡函数依赖中，如果对于非平凡函数依赖X Y，有，有Y X，且，且Y Z，则称：则称：Z对对X传递函数依赖。传递函数依赖。几种类型的函数依赖：几种类型的函数依赖：15系部系部系主任系主任成绩成绩 学号学号课程名称课程名称几种类型的函数依赖：几种类型的函数依赖：16二、利用函数依赖定义候选码定义4.8：设K为R(U，F)中的属性或属性组，若 ，则K为R的候选码。FKU主码主码主属性：主属性：包含在任何码中的属性。非主属性：非主属性：不包含在任何码中的属性。 全码全码外码外码主码与外码提供了一个表示关系间联系的手段主码与外码提供了一个表示关系间联系的手段17三、几种级别的范式第一范式第一范式(1NF)(1NF)定义4.9：满足关系的每一个分量都是不可分的数据项的关系模式就属于第一范式(1NF)。缺点： 插入异常、删除异常、冗余太大、修改复杂18 学号学号系部系部 系主系主任任 课程课程 名称名称成绩成绩99101CSXAAA99101CSXBBB99101CSXCCA99102MAMAAB99102MAMDDA99103MAMEEC99104ISJEEB99105ISJBBA第一范式第一范式(1NF)(1NF)关系的每一个分量都是不可分的数据项缺点：插入异常删除异常冗余太大修改复杂19第二范式第二范式(2NF)(2NF)定义4.10： 若R1NF，且每一个非主属性完全函数依赖于码，则R2NF。系部系部系主任系主任成绩成绩 学号学号课程名称课程名称存在部分函数依赖20成绩成绩系部系部系主任系主任 R1（学号，系部，系主任） 学号学号 学号学号课程名称课程名称 R2（学号，课程名称，成绩）模式分解，消除部分函数依赖模式分解后的子模式：21第三范式第三范式(3NF)(3NF)定义定义4.11：关系模式：关系模式R(U，F)中若不存在这样的码中若不存在这样的码X，属性属性组组Y及非主属性组及非主属性组Z(Z Y)使得使得XY，(Y X) Y Z成立，则称成立，则称R(U，F)3NF。3NF需要消除掉了部分和传递依赖。若若R 2NF，且每一个非主属性不传递且每一个非主属性不传递依赖于码，则依赖于码，则R 3NF。系部系部系主任系主任 学号学号22编号编号成员成员负责人负责人项目名称项目名称任务情况任务情况职务职务例如：例如：项目(编号，项目名称，负责人，职务，成员，任务情况) (假设:负责人无重名情况）23任务（编号，成员，任务情况）项目（编号，项目名称，负责人，职务）编号编号成员成员任务情况任务情况编号编号负责人负责人项目名称项目名称职务职务任务任务项目项目24编号编号成成 员员任务情况任务情况任务任务编号编号负责人负责人项目名称项目名称项目项目负责人负责人职务职务负责人职务25例如：例如：分析以下关系属第几范式分析以下关系属第几范式学生学习情况：R(学号，姓名，班级，年龄，宿舍，系部，系主任，课程号，课程名，先修课程，成绩)26学号课程号学号课程号姓名成绩先修课程课程名系主任系部宿舍年龄班级分析函数依赖关系：判断：属于1NF27成绩学号+课程号姓名系部宿舍年龄班级学号系主任系部先修课程课程名课程号28问题：问题：设有关系模式设有关系模式R（A，B，C，D），），其数据依赖集：其数据依赖集：F（A，B）C，CD，则关系模式则关系模式R的规的规范化程度最高达到（范化程度最高达到（ ）。）。 29BCNF(扩充的扩充的3NF)定义：定义：关系模式R(U，F) 1NF。若 XY且Y X时X必含有码，则R(U，F) BCNF。即：关系模式R(U，F) 中，若每一个决定因素都包含码，则R(U，F) BCNF。三、几种级别的范式30所有非主属性对每一个码都是完全所有非主属性对每一个码都是完全函数依赖。函数依赖。所有主属性对每一个不包含它的码所有主属性对每一个不包含它的码也是完全函数依赖。也是完全函数依赖。没有任何属性完全函数依赖于非码没有任何属性完全函数依赖于非码的任何一组属性。的任何一组属性。满足满足BCNFBCNF的关系模式的性质：的关系模式的性质：31例如：例如：关系模式SJP(S, J, P) S：学生 学生选修课程有一定的名次 J：课程 每门课程中每一名次只有一个学生 P：名次 （名次没有并列） 函数依赖：(S，J)P (J，P)S 分析得知：SJP 3NF SJP BCNF32例如：例如：关系模式STJ(S，T，J) S：学生 某一学生选定某门课，就对应一个固定教师 T：教师 每个教师只教一门课 J： 课程 每门课有若干教师 函数依赖： (S，J)T (S，T)J分析得知：STJ 3NF 但是STJ BCNF，因为 TJSTJ可以分解为：ST(S，T)和TJ(T，J)33消除非主属性对码的部分函数依赖消除非主属性对码的部分函数依赖消除非主属性对码的传递函数依赖消除非主属性对码的传递函数依赖消除主属性对码的部分和传递函数依赖消除主属性对码的部分和传递函数依赖1NF1NF2NF2NF3NF3NFBCNFBCNF消除消除决定决定因素因素非码非码的非的非平凡平凡函数函数依赖依赖34小测验小测验指出下列关系模式属第几范式，并说明理由。(1) R（X,Y,Z） FXY Z(2) R（X,Y,Z） FY Z, XZ Y(3) R（X,Y,Z） FY Z, Y X ,X YZ35假设某旅馆业务规定，每个账单对应一个顾客，账单的发票号假设某旅馆业务规定，每个账单对应一个顾客，账单的发票号是惟一的，账单中包含一个顾客姓名、到达日期和顾客每日的是惟一的，账单中包含一个顾客姓名、到达日期和顾客每日的消费明细，账单的格式如图所示消费明细，账单的格式如图所示:试回答下列问题：试回答下列问题：(1)找出找出R的候选键。的候选键。(2)判断判断R最高可达到第几范式，为什么最高可达到第几范式，为什么?36配件管理模式配件管理模式 WPE（WNO，PNO，ENO，QNT）分别）分别表示仓库号，配件号，职工号，数量。有以下条件表示仓库号，配件号，职工号，数量。有以下条件 a. 一个仓库有多个职工。一个仓库有多个职工。 b. 一个职工仅在一个仓库工作。一个职工仅在一个仓库工作。 c. 每个仓库里一种型号的配件由专人负责，但一个人可以每个仓库里一种型号的配件由专人负责，但一个人可以管理几种配件。管理几种配件。 d. 同一种型号的配件可以分放在几个仓库中。同一种型号的配件可以分放在几个仓库中。 1. ENO WNO2. WNO,PNO ENO3. WNO, PNO QNT候选码候选码1. (WNO， PNO)为候选码为候选码2. 因为因为ENO，PNO WNO 所以所以( ENO，PNO)为候选码为候选码37内容回顾内容回顾规范化的提出规范化的提出函数依赖函数依赖码（候选码、主码、外码、码（候选码、主码、外码、主属性、非主属性）主属性、非主属性）范式（范式（1NFBCNF）一个事实一个事实：函数依赖存在冗余，一个函数依赖或许可以从其他依赖导出。38一个事实一个事实：函数依赖存在冗余，一个函数依赖或许可以从其他依赖导出。例如：关系模式R(U，F)其中U(A，B，C，D，E，F，G) F(AB，CD，ABE，FG)则函数依赖AE可以从F中导出39定义定义4.15 逻辑蕴含逻辑蕴含对于R(U,F)，如果XY不在F中，但是对于其任何一个关系r，XY都成立，则称F逻辑蕴含XY。 或者说：或者说： XYXY可以由可以由F F导出导出 例：关系模式R(U，F)其中U(A，B，C，D，E，F，G) F(AB，CD，ABE，FG)问：F是否逻辑蕴含AE40函数依赖间的蕴含关系的推理规则的理论系统，包括：1）三个基本公理）三个基本公理2）三个扩展的推理规则）三个扩展的推理规则4.3.1 Armstrong公理系统公理系统41对于关系模式R(U，F)，有公理公理1：自反律自反律(Reflexivity)(Reflexivity) 若Y X U，则XY为F所蕴含。公理公理2：增广律增广律( (AugmenttationAugmenttation) ) 若XY为F所蕴含，且ZU，则XZYZ为F所蕴含。公理公理3：传递律传递律(Transitivity)(Transitivity) 若XY，YZ为F所蕴含，则XZ为F所蕴含。三条基本三条基本公理：公理：自反律、增广律、传递律自反律、增广律、传递律42公理公理4：合并规则合并规则 由XY，XZ，有XYZ。公理公理5：伪传递规则伪传递规则 由XY，WYZ，有XWZ公理公理6：分解规则分解规则 由XY及 Z Y，有XZ。由基本公理导出的三条推理规则：由基本公理导出的三条推理规则：43例：关系模式R(U，F)其中U(A，B，C，D，E，F，G) F(AB，CD，ABE，FG)问：F是否逻辑蕴含AE解：解： AB （已知） AAB （增广率） ABE （已知） AE （传递率）44定义定义 4.16 函数依赖集F的闭包在关系模式R(U，F)中，函数依赖集F及F所逻辑蕴含的函数依赖的全体叫做F的闭包，记为F+。4.3.2 函数依赖集和属性集的闭包函数依赖集和属性集的闭包F+=XY | F及能由及能由F根据根据Armstrong公理导出公理导出45设R(U, F)，F为属性集U上的一组函数依赖，属性集XU，则X关于F的闭包定义为XF+ ： XF +=A|XA能由F根据Armstrong公理导出 。定义定义 4.17：X关于F的闭包46【例如】设关系模式R（A、B、C）的函数依赖集为F=A B,B C，分别求A、B、C的闭包。若X=A，AB，BC （已知）AC （传递律）AA （自反律） XF+=A，B，C若X=B，BB BC XF+=B，C若X=C，CC XF+=C47定理定理 4.2：设F为属性集U上的一组函数依赖关系，X，Y U，XY能由F根据Armstrong公理导出的充分必要条件是Y XF。利用XF+可以判定：函数依赖XY是否为F所蕴含如何求得如何求得XF+呢？呢？48求求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)(4)判断X(i+1)= X(i)吗？(5)若相等或X(i)=U则X(i)就是XF+ ，算法终止。(6)若否，则i=i+1，返回第(2)步。算法算法 4.1：49例例1：已知关系模式R(U，F)，其中U=A，B，C，D，E；F=ABC，BD，CE，ECB，ACB求(AB)F+。解：1：X(0)=AB 2：计算X(1) = X(0) C D = ABCD 3：求X(2) = X(1) E B = ABCDE 4：由于X(2) 已经等于全部属性集合，所以(AB)F+ = ABCDE找出左部为A，B或AB的函数依赖50例例2：已知关系模式R(U，F)，其中U=A，B，C，D，E，F，G，H；F=AD，ABE，BHE，CDH，EC令X=AE，求X+。解：1：X(0)=AE 2：X(1) = X(0) D C = ACDE 3：X(2) = X(1) D H C = ACDEH 4：X(3) = ACDEH不变，即X(3) = X(2) 所以 X+ = (AE)+= ACDEH51对于属性闭包算法的终止条件，下对于属性闭包算法的终止条件，下列四种方法是等价的：列四种方法是等价的： 1 X(i+1) = X(i) 2 当发现X(i) 包含了全部属性时； 3 在F中的函数依赖的右部属性中，再也找不到X(i) 中未出现过的属性。 4 在F中未用过的函数依赖的左部属性中已没有X(i) 的子集。52定理：定理：Armstrong公理系统是有效的(正确性）、完备的。正确性：正确性：指公理1、2、3是正确的。有效性：有效性：指由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F+。完备性：完备性：指F+中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来。534.3.3 4.3.3 函数依赖集的等价和函数依赖集的等价和最小函数依赖集最小函数依赖集定义定义4.184.18 如果如果G+=F+，则称则称F与与G等价，记为等价，记为F=G。F+=G+的充分必要条件是F G+且G F+54例：R(U) U=ABC F=AB，BC，AC，ABC,A BC可以写成：G=AB，BC证明：1：AB，BC 传递规则 AC 2： AB，扩展ABBB 即 AB B 再由BC 所以 ABC3： AB，BC 扩展 BBC 所以 A BCF与G等价55定义定义 4.194.19： 最小依赖集定义：最小依赖集定义：如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集，也称最小依赖集或最小覆盖。1)F中任一函数依赖的右部仅含有一个属性。2)F中不存在这样的函数依赖XA，使得 F与F-X A等价。不存在冗余FD3) F中不存在这样的函数依赖XA，X有真子集Z使得F-X AZA与F等价。决定因素不存在冗余56例：例：U=SNO，SDEPT，MN，CNAME，G F=SNO SDEPT，SDEPT MN，SNO，CNAME G 设F =SNO SDEPT，SNO MN，SDEPT MN，(SNO，CNAME) G，(SNO，SDEPT) SDEPT结论：结论： F与 F 等价 F是最小覆盖，F不是。57算法算法 4.2求求Fm （F的最小依赖集）的算法的最小依赖集）的算法(1)将将XA1A2Ak(k2)转换为转换为XAi(i=1,2,k) 将右部属性分解为单个属性将右部属性分解为单个属性(2)逐个检查函数依赖逐个检查函数依赖XA，令，令G=F-XA，若若A(X)G+，则从则从F中去掉中去掉XA。逐个检查逐个检查F中的每一项，看是否中的每一项，看是否F-XA与与F等价等价(3)逐个检查函数依赖逐个检查函数依赖XA，若，若X=B1B2Bm，逐个考查逐个考查Bi(i=1,2,m)，若，若A(X-Bi)F+，则则以以X-Bi取代取代X。判每个函数依赖左部是否有冗判每个函数依赖左部是否有冗余属性余属性58例：例：将下列函数依赖将下列函数依赖集集F划为最小函数依赖集。划为最小函数依赖集。F=AB，BA，BC，AC，CA解：解：1：分解为单个属性：分解为单个属性F1=F 2：消去消去F中冗余的函数依赖中冗余的函数依赖考察考察AB：令令X=A 求求X+= ？ X(0)=A X(1)=AC=X+ 因为因为B不属于不属于X+ 所以所以AB不冗余。不冗余。考察考察BA：令令X=B 求求X+ = ？ X(0)=B X(1)=BC X(2)=ABC =X+ 因为因为A属于属于X+ 所以所以BA冗余。冗余。考察考察BC：令令X=B 求求X+ = ？ X(0)=B X(1)=B=X+ 因为因为C不属于不属于X+ 所以所以BC不冗余。不冗余。59考察考察AC：令令X=A 求求X+ = ？ X(0)=A X(1)=AB X(2)=ABC =X+ 因为因为C属于属于X+ 所以所以AC冗余。冗余。考察考察CA：令令X=C 求求X+ = ？ 因为因为A不属于不属于X+ 所以所以CA不冗余。不冗余。因此因此 3：判每个函数依赖左部是否有冗余属性判每个函数依赖左部是否有冗余属性F=AB，BA，BC，AC，CAF m=AB，BA，AC，CA思思考考F2=AB，BC，CA60 设有关系模式设有关系模式R（A，B，C，D），），其上的函数依赖集为：其上的函数依赖集为：FA C ,C A，B AC，D AC，求，求F的最小的最小覆盖。覆盖。61假定我们要构造一个数据库，属性集为假定我们要构造一个数据库，属性集为A,B,C,D,E,F,G，给定的函数依赖给定的函数依赖集集F如下：如下：F=BCDA，BCE，AF，FG，CD，AG. .找出这个函数依赖集的最小覆盖找出这个函数依赖集的最小覆盖G624.4 4.4 关系模式的分解关系模式的分解 n 模式分解等价性的三个判定准则模式分解等价性的三个判定准则 n分解的无损连接性和函数依赖保持性分解的无损连接性和函数依赖保持性 n模式分解的算法模式分解的算法63T#TDDHT#TDDHT1T2T3T4D1D1D2D3AAAABBCC 设一关系模式R(T#，TD，DH)，其中T#表示教师编号，TD表示教师所属系部，DH表示系主任名。假定每位教师只能在一个系任教，每个系只有一位系主任。64分解1： 1=R1(T#)，R2(TD)，R3(DH)分解2： 2=R1(T#，TD)，R2(T#，DH)分解3： 3=R1(T#，TD)，R2(TD，DH)65分解分解 1：T#T1T2T3T4R1R2TDD1D2D3R3DHAABBCC问题：T1是哪一个系的教师？无法回答。R1，R2，R3也无法恢复到原来的R。66分解分解 2：T#T1T2T3T4R1TDD1D1D2D3T#T1T2T3T4R2DHAAAABBCC此时，R1，R2的分解是可恢复的，但仍然存在操作异常。原因：TDDH 在R1，R2中没有体现。67分解分解 3：T#T1T2T3T4R1TDD1D1D2D3TDR2DHD1D2D3AABBCC此时，R1，R2的分解是可恢复的，并且消除了操作异常。68 关系模式R被分解为两个投影R1和R2是独立的，当且仅当： 1. R中的每个函数依赖都可由R1和R2的函数依赖导出。 2. R1和R2中的公共属性至少是R1和R2 中某个关系的侯选码。694.4.1 4.4.1 无损连接和函数依赖保持无损连接和函数依赖保持一、分解的无损连接性：一、分解的无损连接性： 如果一个关系模式分解后，可以通过自然如果一个关系模式分解后，可以通过自然连接恢复原模式的信息，这一特性称为分解连接恢复原模式的信息，这一特性称为分解的无损连接性。的无损连接性。70分解的无损连接性：分解的无损连接性：设设R是关系模式，是关系模式，F是是R上的函数依赖集，则上的函数依赖集，则R的分解的分解=R1, , Rk是无损连接的，如果是无损连接的，如果R中每个满足中每个满足F的关系的关系r都有下式成立：都有下式成立： 71Tij=aj， 如果如果AjRibij，如果，如果AjRi1) 构造一个k行n列的二维表T： 每列对应一个属性Aj 每行对应一个模式Ri =R1(U1,F1),Rk(Uk,Fk)是R(U,F)的一个分解，U=A1,An，F=FD1,FD2,FDp。算法算法 4.34.3 判定分解的无损连接性判定分解的无损连接性722) 根据F中函数依赖修改表T的内容。修改规则：修改规则：逐个考察F中的每个函数依赖FD：XY，找到表格中在X属性上取值相等的行，将在这些行上的Y属性取值改为相等，具体如下： （1）如果其中有一个符号为a aj j，则把其它符号也改为 a aj j，否则改为b bmjmj，其中m是这些行的最小行号。 （2）特别注意：修改过程中若某个bij被改动，则它所在列的所有bij都要做相应改动 733) 如果发现表中有一行已变成a1a2ak，则表示该分解具有无损连接性，否则分解不是无损连接的。例：例：已知 R(U，F) U=A，B，C，D，E，F，F=ABC, CD，AF，DE，DF R的一个分解为 ： =R1(A，B，C)，R2(C，D)，R3(D，E，F) 判断是否具有无损连接性。74ABCDEFa1b21b31a2b22b32a3a3b33b14a4a4b15b25a5b16b26a6第一步：建第一步：建T=R1(A，B，C) R2(C，D) R3(D，E，F)Tij=aj， 如果如果AjRibij， 如果如果AjRi75 第二步：逐个考察函数依赖，并修改表。第二步：逐个考察函数依赖，并修改表。(1)ABC, (2)CD, (3)AF, (4)DE, (5)DFa4a5a5ABCDEFa1b21b31a2b22b32a3a3b33a4a4a5a6b14b16b15b25b26a6a6由于没有相同的分量，所以表不改变76 1=R1(T#)，R2(TD)，R3(DH) 2 =R1(T#，TD)，R2(T#，DH) 3=R1(T#，TD)，R2(TD，DH) 1 T# TD DH a1 b12 b13 b21 a2 b23 b31 b32 a3具有无损连接性具有无损连接性 2T# TD DH a1 a2 b13 a1 b22 a3 3 T# TD DH a1 a2 b13 b21 a2 a3具有无损连接性具有无损连接性77练习设关系模式 R为 R(H,I,J,K,L)，R上的一个函数依赖集为 F=HJ,JK,IJ,JLH，判断如下哪个分解是无损连接的。 A. p=HK，HI，IJ，JKL，HL B. p=HIL，IKL，IJLC. p=HJ，IK，HLD. p=HI，JK，HL78HIJKLHKa1b12b13a4b15HIa1a2b23b24b25IJb31a2a3b34b35JKLb41b42a3a4a5HLa1b52b53b54a5A. p=HK，HI，IJ，JKL，HL 建表：79HIJKLHKa1b12b13a4b15HIa1a2b13b24b25IJb31a2a3b34b35JKLb41b42a3a4a5HLa1b52b13b54a5F=HJ,JK,IJ,JLH修改表：80HIJKLHKa1b12b13a4b15HIa1a2b13a4b25IJb31a2a3a4b35JKLb41b42a3a4a5HLa1b52b13a4a5F=HJ,JK,IJ,JLH修改表：81HIJKLHKa1b12a3a4b15HIa1a2a3a4b25IJb31a2a3a4b35JKLb41b42a3a4a5HLa1b52a3a4a5F=HJ,JK,IJ,JLH修改表：82HIJKLHKa1b12a3a4b15HIa1a2a3a4b25IJb31a2a3a4b35JKLa1b42a3a4a5HLa1b52a3a4a5F=HJ,JK,IJ,JLH修改表：83HIJKLHKa1b12a3a4b15HIa1a2a3a4b25IJb31a2a3a4b35JKLa1b42a3a4a5HLa1b52a3a4a5F=HJ,JK,IJ,JLH修改表：陷入循环，结束非无损84HIJKLHILa1b12b13a4b15IKLa1a2b23b24b25IJLb31a2a3b34b35B. p=HIL，IKL，IJLF=HJ,JK,IJ,JLH建表：85HIJKLHILa1a2a3b14a5IKLa1a2a3a4a5IJLa1a2a3b34a5B. p=HIL，IKL，IJLF=HJ,JK,IJ,JLH修改表：无损连接分解。86 设设=R1，R2是关系模式是关系模式R的一个分解，的一个分解，F是是R的一个函数依赖集，则对于的一个函数依赖集，则对于F，具有具有连接不失真性的充分必要条件是：连接不失真性的充分必要条件是： R1R2R1-R2F+ 或或 R1R2R2-R1F+。定理定理4.4:4.4: R1和R2中的公共属性至少是R1和R2 中某个关系的侯选码。87二、分解的函数依赖保持性：二、分解的函数依赖保持性： 若关系R(U,F)的一个分解=R1(U1,F1),Rk(Uk,Fk)的所有函数 依赖的并集 逻辑蕴涵了F中所有 函数依赖， 即 =F+， 则称分解具有函数依赖保持性。i=1k(Fi)i=1k(Fi)+88二、分解的函数依赖保持性二、分解的函数依赖保持性问题：给定关系R(U,F)，及其分解：=R1(U1,F1),Rk(Uk,Fk)如何计算Fi：称为F在Ui上的投影Fi=XY| XYF+XYUi；或与其等价的依赖集 89例：关系模式R(U，F) U=A，B，C，DF=AB，BC，CD，DA分解=R1(A，B)，R2(B，C)，R3(C，D)是否具有函数依赖保持性？其中： F1U1 ( F )=(AB,BA) F2 U2 ( F )=(BC,CB) F3 U3 ( F )=(CD,DC)90 F1F2 F3=AB,BA, BC,CB, CD,DC F=AB，BC，CD，DA因为 (F1F2 F3)+=F+ 所以 分解具有函数依赖保持性。91练习 设有R（U，F），其中， U=A，B，C，D，F，F= AC， BC，CD， DFC， CFA ，R的一个分解为：R1=AB，R2=AD，R3=AF，R4=BF，R5=CDF，判断该分解是否具有函数依赖保持性。 92算法算法4.54.5： 结果为结果为3 3NFNF的依赖保持分解算的依赖保持分解算法法 如果如果R R中有某些属性与中有某些属性与F F 的最小覆盖的最小覆盖F中的每个依赖的左中的每个依赖的左边和右边都无关，原则上可由这些属性构成一个关系模式，并边和右边都无关，原则上可由这些属性构成一个关系模式，并从从R R中将它们消除；否则，中将它们消除；否则， 如果如果FF中有一个依赖涉及到中有一个依赖涉及到R R 的所有属性，则输出的所有属性，则输出R R；否否则，则， 输出一个分解输出一个分解，它由模式它由模式XAXA组成，其中组成，其中XA XA F 。但但当当XA1XA1，XA2XA2，XAn XAn 均属于均属于FF时，则用模式时，则用模式XA1 XA1 A2A2AnAn代替代替XAiXAi（i=1i=1，2 2，n n）。）。93假定我们要够造一个数据库，属性集为假定我们要够造一个数据库，属性集为A,B,C,D,E,F,G，给定的函数依赖给定的函数依赖集集F如下：如下：F=BCDA，BCE，AF，FG，CD，AG. .求求R R的一个满足的一个满足3NF3NF的函数依赖保持分解的函数依赖保持分解举举 例例94举举 例例 1 求求F的最小覆盖的最小覆盖FmBC AE, AF , FG， CD2 条件（条件（1）不满足）不满足 3 条件（条件（2）不满足）不满足 4 根据条件（根据条件（3）输出）输出 =BCAE,AF,FG,CD95算法算法4.64.6： 结果为结果为3 3NFNF的依赖保持和连接不失真分解的依赖保持和连接不失真分解 设设是是由由“结结果果为为3NF3NF的的依依赖赖保保持持分分解解算算法法”得得到的到的3NF3NF分解，分解，X X为为R R的一个候选关键字，则：的一个候选关键字，则： = X = X 是是R R的的一一个个分分解解，且且其其中中的的所所有有关关系系模模式式均均满满足足3NF3NF，同时，既具有连接不失真性，又具有依赖保持性。同时，既具有连接不失真性，又具有依赖保持性。问题：如何找到候选码？问题：如何找到候选码？码值理论码值理论96 对对于于给给定定的的关关系系R R（A1A1，A2A2，AnAn）和和函函数依赖集数依赖集F F，可将其属性分为可将其属性分为4 4类：类：n L L类类 仅出现在仅出现在F F的函数依赖左部的属性的函数依赖左部的属性n R R类类 仅出现在仅出现在F F的函数依赖右部的属性的函数依赖右部的属性n N N类类 在在F F的的函函数数依依赖赖左左右右两两边边均均未未出出现现的的属属性性n LRLR类类 在在F F的函数依赖左右两边均出现的属性的函数依赖左右两边均出现的属性97定理定理1 对于给定的关系对于给定的关系模式模式R R及其函数依赖集及其函数依赖集F F，若，若X X（XRXR）是）是L L类类属性，则属性，则X X必是必是R R的候的候选码的成员选码的成员。定理定理3 对于给定的关系模式对于给定的关系模式R R及其函数依赖集及其函数依赖集F F，若，若X X（XRXR）是）是R R类属性，则类属性，则X X不在任何候选码中不在任何候选码中。定理定理2 对于给定的关系对于给定的关系模式模式R R及其函数依赖集及其函数依赖集F F，若，若X X（XRXR）是）是N N类属类属性，则性，则X X必是必是R R的候选码的候选码的成员。的成员。98候选码求解推论候选码求解推论 对于给定的关系模式对于给定的关系模式R R及其函数依赖集及其函数依赖集F F，若若X X（XRXR）是）是R R的的L L类或类或N N类属性组成的属性集，类属性组成的属性集，且且X X包含了包含了R R的全部属性，则的全部属性，则X X是是R R的唯一候选的唯一候选码码。99设有关系模式R（A，B，C，D，E，P），R的函数依赖集为：FAD,ED,DB,BC D,DC A求R的候选码。举例举例：因因为为 C C，E E是是L L类类属属性性，P P是是N N类类属属性性，所所以以CEPCEP包含在所有候选码中；包含在所有候选码中；因为因为 （CEPCEP）ABCDEPABCDEP；所以所以 CEPCEP是是R R的唯一候选码。的唯一候选码。100假定我们要够造一个数据库，属性假定我们要够造一个数据库，属性集为集为A,B,C,D,E,F,G，给定的函给定的函数依赖集数依赖集F如下：如下：F=BCDA，BCE，AF，FG，CD，AG. .求求R R的一个满足的一个满足3NF3NF的无损连接和函的无损连接和函数依赖保持的分解数依赖保持的分解举举 例例101 1 求求F的最小覆盖的最小覆盖FmBC AE, AF , FG， CD2 R的满足的满足3NF且函数依赖保持的分且函数依赖保持的分解为：解为： =BCAE,AF,FG,CD 3 R的候选码为：的候选码为：BC 4 R的满足的满足3NF且函数依赖保持和无损且函数依赖保持和无损连接的分解为：连接的分解为： =BCAE,AF,FG,CD102设有关系模式设有关系模式R(A，B，C，D，E，P)，R的函数依赖集为：的函数依赖集为： FCB, ED, DB, B D, BC D, DC A, 求求R的一个满足的一个满足3NF的无损连接和的无损连接和函数依赖保持的分解函数依赖保持的分解举举 例例103第一步：求最小函数依赖集第一步：求最小函数依赖集FmFm=C B,E D,D B,B D,DC A第二步：求基于第二步：求基于3NF的函数依赖保持的分解的函数依赖保持的分解=CB,ED,DB,DCA第三步：求候选码第三步：求候选码XX=CEP第四步第四步:求基于求基于3NF的函数依赖保持和连接不失真的分解的函数依赖保持和连接不失真的分解=CB,ED,DB,DCA,CEP1041）若要求连接不失真，分解可达到BCNF；2）若要求依赖保持，则分解可达到3NF，但 不一定能达到BCNF。3）若同时要求连接不失真和依赖保持，则 分解可达到3NF，但不一定能达到BCNF。模式分解的几个重要事实模式分解的几个重要事实：105为什么要规范化为什么要规范化非形式化判定准则非形式化判定准则 形式化判定（规范化理论）形式化判定（规范化理论） 1NF、2NF、3NF、BCNF 模式分解（等价性的判定：连接不失真性、依赖保持性）模式分解（等价性的判定：连接不失真性、依赖保持性） 函数依赖集等价函数依赖集等价F+=G+（ =F+） 连接不失真性连接不失真性的判定的判定 i=1k(Fi)+规格化理论小结106 分解算法分解算法 函数依赖保持的函数依赖保持的3NF分解分解 连接不失真和函数依赖保持的连接不失真和函数依赖保持的3NF分解分解 求最小覆盖求最小覆盖Fm 求候选码求候选码 属性集闭包属性集闭包XF+ 、码值理论、码值理论107