第4章_关系规范化理论

1、1 1971 E.F.Codd 提出 1NF 2NF 3NF BCNF 4NF 5NF 规范化 函数依赖 模式分解24.1 4.1 问题的提出问题的提出关系模式 R (UR (U，D D，domdom，I I，F) F) 数据依赖：关系中属性间互相依存、互相制约的关系。 函数依赖函数依赖、多值依赖、连接依赖、分层依赖和相互依赖3例：例： U=学号，系部，系主任，课程名称，成绩 F=学号系部，系部 系主任, (学号，课程名称) 成绩系部系部系主任系主任成绩成绩 学号学号课程名称课程名称4缺点1、冗余太大2、操作异常 1）插入异常 2）删除异常 3）修改异常 学号学号系部系部 系主系主任任 课程课

2、程 名称名称成成绩绩02101CSXAAA02101CSXBBB02101CSXCCA02102MAMAAB02102MAMDDA02103MAMEEC02104ISJEEB02105ISJBBA5适当地进行模式分解 可以避免各种问题1、冗余太大2、操作异常 1）插入异常 2）删除异常 3）修改异常学生（学号，系部）系部（系部，系主任）选课（学号，课程名称，成绩）6适当地进行模式分解 关系规范化理论关系规范化理论 数据依赖和关系规范化数据依赖和关系规范化 阿姆斯特朗公理系统阿姆斯特朗公理系统 模式分解模式分解7一、一、 函数依赖：函数依赖： 属性或属性组之间可能存在的依赖性。属性或属性组之间可

3、能存在的依赖性。1、定义 定义定义4.14.1：设R(U)是属性集U上的关系模式。X，Y是U的子集。若对于R(U)的任意一个可能的关系r，当且仅当r中任意一个给定的X的值，r中存在唯一的Y值与之对应。也就是说，如果X相等，Y也相等，则称Y函数依赖与X，或者X函数确定Y，记作XY。8定义定义4.3：R（U）的属性子集）的属性子集X，Y之间的函数依赖之间的函数依赖用用X Y表示，它在构成关系表示，它在构成关系R的任意元组的任意元组r上指定了上指定了一个约束。这个约束是：如果对于一个约束。这个约束是：如果对于r中的任何两个元中的任何两个元组组t1和和t2有有t1Xt2X，则必须也有，则必须也有t1Y

4、t2Y。 定义定义4.2：设设R(U)是属性集是属性集U上的关系模式，上的关系模式，X，Y是是U的子集。若对于的子集。若对于R (U)的任意一个可能的关系的任意一个可能的关系r，r中不可能存在两个元组在中不可能存在两个元组在X上的属性值相等，而在上的属性值相等，而在Y上的属性值不等，则称上的属性值不等，则称X函数确定函数确定Y或或Y函数依赖于函数依赖于X，记作，记作XY。9例：例：U=学号，系部，系主任，课程名称，成绩 F=学号系部，系部 系主任, (学号，课程名称) 成绩注意：函数依赖不是指关系模式R的某个或某些关系满足的条件，而是指R的一切关系均要满足的约束条件10由定义可以导出下列基本概

5、念： 1 .1 .决定因素：决定因素：若X Y，则X叫做决定因素 2 .2 .互相依赖：互相依赖：若X Y， Y X， 则记作X Y。 3 .3 .若若Y Y不函数依赖于不函数依赖于X X，则记作X Y。11 定义定义4.4 ：平凡（非平凡）函数依赖平凡（非平凡）函数依赖 在在R(U)中，一个函数依赖如果满足中，一个函数依赖如果满足Y X，则称此函数依赖是非平凡函数依赖，否则称则称此函数依赖是非平凡函数依赖，否则称为平凡函数依赖。为平凡函数依赖。 12 定义定义4.5 ：完全函数依赖完全函数依赖 在在R(U)中，如果中，如果X Y，并且对于，并且对于X的的任何一个真子集任何一个真子集X，都有，

6、都有X Y，则称，则称Y对对X完全函数依赖。记作：完全函数依赖。记作：FXY 定义定义4.6 ：部分函数依赖部分函数依赖 在在R(U)中，如果中，如果X Y，存在真子集，存在真子集X，有有X Y成立，则称成立，则称Y对对X部分函数依赖。部分函数依赖。记作记作： PXY13定义定义4.74.7：传递函数依赖传递函数依赖 在在R(U)中，如果中，如果X Y，(Y X )，Y X，Y Z，则称，则称Z对对X传递函数依赖。传递函数依赖。14系部系部系主任系主任成绩成绩 学号学号课程名称课程名称15定义4.8：设K为R(U，F)中的属性或属性组，若 ，则K为R的候选码。FKU主码：主码：若候选码多于一个

7、，则选定其中的一个为主码。主属性：主属性：包含在任何一个侯选码中的属性。非主属性：非主属性：不包含在任何码中的属性。 全码：全码：整个属性组是码。定义定义6.6:6.6: 关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R的外码外码。主码与外码提供了一个表示关系间联系的手段。主码与外码提供了一个表示关系间联系的手段。16三、第一范三、第一范式式(1NF)(1NF)定义4.9：满足关系的每一个分量是不可分的数据项这一条件的关系模式就属于第一范式(1NF)。缺点： 插入异常、删除异常、冗余太大、修改复杂 学号学号系部系部 系主系主任任 课程课程 名称名称成绩成绩99101C

8、SXAAA99101CSXBBB99101CSXCCA99102MAMAAB99102MAMDDA99103MAMEEC99104ISJEEB99105ISJBBA17第二范式第二范式(2NF)(2NF)定义4.10： 若R1NF，且每一个非主属性完全函数依赖于码，则R2NF。系部系部系主任系主任成绩成绩 学号学号课程名称课程名称18成绩成绩系部系部系主任系主任 学号，系部，系主任 学号学号 学号学号课程名称课程名称 学号，课程名称，成绩19第三范式第三范式(3NF)(3NF)定义定义4.11：关系模式：关系模式R(U，F)中若不存在这样的码中若不存在这样的码X，属性组属性组Y及非主属性组及非

9、主属性组Z(Z Y)使得使得XY，(Y X) Y Z成立，则称成立，则称R(U，F)3NF。即：若R 3NF，且每一个非主属性既不部分依赖于码也不传递依赖于码。系部系部系主任系主任 学号学号若若R 2NF，且每一个非主属性，且每一个非主属性不传递依赖于码，则不传递依赖于码，则R 3NF。20例：项目(编号，项目名称，负责人，职务，成员，任务情况) (假设:负责人无重名情况）编号编号成员成员负责人负责人项目名称项目名称任务情况任务情况职务职务21任务（编号，成员，任务情况）项目（编号，项目名称，负责人，职务）编号编号成员成员任务情况任务情况编号编号负责人负责人项目名称项目名称职务职务任务任务项目

10、项目22编号编号成成 员员任务情况任务情况任务任务编号编号负责人负责人项目名称项目名称项目项目负责人负责人职务职务负责人职务23例：分析下列关系属于第几范式例：分析下列关系属于第几范式 学生学习情况：（学号，姓名，班级，年龄，宿舍，系部，系主任，课程号，课程名，先修课程，成绩）24学号课程号学号课程号姓名成绩先修课程课程名系主任系部宿舍年龄班级分析函数依赖关系：判断：属于1NF25成绩学号+课程号姓名系部宿舍年龄班级学号系主任系部先修课程课程名课程号26设有关系模式设有关系模式R（A，B，C，D），其），其数据依赖集：数据依赖集：F（A，B）C，CD，则关系模式，则关系模式R的规范化程度最的规

11、范化程度最高达到（高达到（ ）。）。 27BCNF(扩充的扩充的3NF)定义：定义：关系模式R(U，F) 1NF。若 XY且Y X时X必含有码，则R(U，F) BCNF。即：关系模式R(U，F) 中，若每一个决定因素都包含码，则R(U，F) BCNF。28所有非主属性对每一个码都是完全所有非主属性对每一个码都是完全函数依赖。函数依赖。所有主属性对每一个不包含它的码所有主属性对每一个不包含它的码也是完全函数依赖。也是完全函数依赖。没有任何属性完全函数依赖于非码没有任何属性完全函数依赖于非码的任何一组属性。的任何一组属性。一个满足一个满足BCNF BCNF 的关系模式有的关系模式有: :29例：例

12、：关系模式SJP（S，J，P） S：学生 学生选修课程有一定的名次 J：课程 每门课程中每一名次只有一个学生 P：名次 （名次没有并列） 函数依赖： （S，J） P （J，P） S 分析得知：SJP 3NF SJP BCNF30例：例：关系模式STJ（S，T，J） S：学生 某一学生选定某门课，就对应一个固定教师 T：教师 每个教师只教一门课 J： 课程 每门课有若干教师 函数依赖： （S，J） T （S，T） J分析得知：STJ 3NF 但是：STJ BCNF 因为： T J STJ可以分解为：ST（S，T）TJ（T，J）31消除非主属性对码的部分函数依赖消除非主属性对码的部分函数依赖消除非

13、主属性对码的传递函数依赖消除非主属性对码的传递函数依赖消除主属性对码的部分和传递函数依赖消除主属性对码的部分和传递函数依赖1NF1NF2NF2NF3NF3NFBCNFBCNF消除消除决定决定因素因素非码非码的非的非平凡平凡函数函数依赖依赖32指出下列关系模式属于第几范式，并说明理由指出下列关系模式属于第几范式，并说明理由。(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 YZ33内容回顾内容回顾规范化的提出码（候选码、主码、外码、主属性、非主属性）范式（1NFBCNF）逻辑蕴涵函数集闭包和属性集闭包函数依赖集等

14、价和最小函数依赖集34假设某旅馆业务规定，每个账单对应一个顾客，账单的发票号假设某旅馆业务规定，每个账单对应一个顾客，账单的发票号是惟一的，账单中包含一个顾客姓名、到达日期和顾客每日的是惟一的，账单中包含一个顾客姓名、到达日期和顾客每日的消费明细，账单的格式如图所示消费明细，账单的格式如图所示:试回答下列问题：试回答下列问题：(1)找出找出R的候选键。的候选键。(2)判断判断R最高可达到第几范式，为什么最高可达到第几范式，为什么?35配件管理关系模式配件管理关系模式 WPE（WNO，PNO，ENO，QNT）分别表）分别表仓库号，配件号，职工号，数量。有以下条件仓库号，配件号，职工号，数量。有以

15、下条件 a.一个仓库有多个职工。一个仓库有多个职工。 b.一个职工仅在一个仓库工作。一个职工仅在一个仓库工作。 c.每个仓库里一种型号的配件由专人负责，但一个人可以管理每个仓库里一种型号的配件由专人负责，但一个人可以管理几种配件。几种配件。 d.同一种型号的配件可以分放在几个仓库中。同一种型号的配件可以分放在几个仓库中。 1 ENO WNO2 WNO,PNO ENO3 WNO, PNO QNT候选码1 (WNO， PNO)为候选码2 因为ENO，PNO WNO 所以（ ENO，PNO ）为候选码36定义定义4.15 逻辑蕴含逻辑蕴含定义：对于R(U,F)，如果XY不在F中，但是对于其任何一个关

16、系r，XY都成立，则称F逻辑蕴含XY。 或者说：或者说： XYXY可以由可以由F F导出导出 例：关系模式R(U，F)其中U(A，B，C，D，E，F，G) F(AB，CD，ABE，FG)问：F是否逻辑蕴含AE37ArmstrongArmstrong公理系统公理系统 对于关系模式R(U，F)，有公理公理1：自反律自反律(Reflexivity)(Reflexivity) 若Y X U，则XY为F所蕴含。公理公理2：增广律增广律(Augmenttation)(Augmenttation) 若XY为F所蕴含，且ZU，则XZYZ为F所蕴含。公理公理3：传递律传递律(Transitivity)(Tran

17、sitivity) 若XY，YZ为F所蕴含，则XZ为F所蕴含。自反律、增广律、传递律是最基本的自反律、增广律、传递律是最基本的Armstrong公理。公理。38公理公理4：合并规则合并规则 由XY，XZ，有XYZ。公理公理5：伪传递规则伪传递规则 由XY，WYZ，有XWZ公理公理6：分解规则分解规则 由XY及 Z Y，有XZ。由自反律、增广律、传递律可以导出下面三条推理规则。由自反律、增广律、传递律可以导出下面三条推理规则。39例：关系模式R(U，F)其中U(A，B，C，D，E，F，G) F(AB，CD，ABE，FG)问：F是否逻辑蕴含AE解：解： AB （已知） AAB （增广率） ABE

18、（已知） AE （传递率）404.3.2函数依赖集闭包和属性集闭包函数依赖集闭包和属性集闭包定义定义 4.16 F的闭包定义：在关系模式R(U，F)中为F及F所逻辑蕴含的函数依赖的全体叫做F的闭包。记为F+。F +=X Y|F及能由F根据Armstrong公理导出41X关于函数依赖集F的闭包定义：设F为属性集U上的一组函数依赖，X U， XF +=A|XA能由F根据Armstrong公理导出，XF+称为属性集X关于函数依赖集F的闭包。定义定义 4.174.17 42【例】设关系模式R（A、B、C）的函数依赖集为F=A B,B C，分别求A、B、C的闭包。若X=A，AB，BC （已知）AC （传

19、递律）AA （自反律） XF+=A，B，C若X=B，BB BC XF+=B，C若X=C，CC XF+=C43设F为属性集U上的一组函数依赖关系，X，Y U，X Y能由F根据Armstrong公理导出的充分必要条件是Y XF。定理定理 4.2：44求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：45例例1：已知关系模式R(

20、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的函数依赖46例例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

21、(3) = ACDEH不变，即X(3) = X(2) 所以 X+ = (AE)+= ACDEH47对于属性闭包算法的终止条件，下对于属性闭包算法的终止条件，下列四种方法是等价的：列四种方法是等价的： 1 X(i+1) = X(i) 2 当发现X(i) 包含了全部属性时； 3 在F中的函数依赖的右部属性中，再也找不到X(i) 中未出现过的属性。 4 在F中未用过的函数依赖的左部属性中已没有X(i) 的子集。48定理：定理：Armstrong公理系统是有效的(正确性）、完备的。正确性：正确性：指公理1、2、3是正确的。有效性：有效性：指由F出发根据Armstrong公理推导出来的每一个函数依赖一定

22、在F+。完备性：完备性：指F+中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来。494.3.3 4.3.3 函数依赖集的等价和函数依赖集的等价和最小函数依赖集最小函数依赖集定义定义4.184.18 如果如果G+=F+，则称，则称F与与G等价，记为等价，记为F=G。F+=G+的充分必要条件是F G+且G F+50例：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等价51定义定义 4.19

23、4.19： 最小依赖集定义：最小依赖集定义：如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集，也称最小依赖集或最小覆盖。1)F中任一函数依赖的右部仅含有一个属性。2)F中不存在这样的函数依赖XA，使得 F与F-X A等价。不存在冗余FD3) F中不存在这样的函数依赖XA，X有真子集Z使得F-X AZA与F等价。决定因素不存在冗余52例：例：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

24、与 F 等价 F是最小覆盖，F不是。53算法算法 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。判每个函数依赖左部是

25、否有冗余判每个函数依赖左部是否有冗余属性属性54例：例：将下列函数依赖集将下列函数依赖集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

26、X(1)=B=X+ 因为因为C不属于不属于X+ 所以所以BC不冗余。不冗余。55考察考察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，CA56 设有关系模式设有关系模式R（A，B，C，D），），其上的函数依赖集为：其上的函数依赖集为：FA

27、 C ,C A，B AC，D AC，求，求F的最小的最小覆盖。覆盖。57假定我们要构造一个数据库，属性集为假定我们要构造一个数据库，属性集为A,B,C,D,E,F,G，给定的函数依赖，给定的函数依赖集集F如下：如下：F=BCDA，BCE，AF，FG，CD，AG. .找出这个函数依赖集的最小覆盖找出这个函数依赖集的最小覆盖G584.4 4.4 关系模式的分解关系模式的分解 n 模式分解等价性的三个判定准则模式分解等价性的三个判定准则 n分解的无损连接性和函数依赖保持性分解的无损连接性和函数依赖保持性 n模式分解的算法模式分解的算法59T#TDDHT#TDDHT1T2T3T4D1D1D2D3AAA

28、ABBCC 设一关系模式R(T#，TD，DH)，其中T#表示教师编号，TD表示教师所属系部，DH表示系主任名。假定每位教师只能在一个系任教，每个系只有一位系主任。60分解1： 1=R1(T#)，R2(TD)，R3(DH)分解2： 2=R1(T#，TD)，R2(T#，DH)分解3： 3=R1(T#，TD)，R2(TD，DH)61分解分解 1：T#T1T2T3T4R1R2TDD1D2D3R3DHAABBCC问题：T1是哪一个系的教师？无法回答。R1，R2，R3也无法恢复到原来的R。62分解分解 2：T#T1T2T3T4R1TDD1D1D2D3T#T1T2T3T4R2DHAAAABBCC此时，R1，

29、R2的分解是可恢复的，但仍然存在操作异常。原因：TDDH 在R1，R2中没有体现。63分解分解 3：T#T1T2T3T4R1TDD1D1D2D3TDR2DHD1D2D3AABBCC此时，R1，R2的分解是可恢复的，并且消除了操作异常。64 关系模式R被分解为两个投影R1和R2是独立的，当且仅当： 1. R中的每个函数依赖都可由R1和R2的函数依赖导出。 2. R1和R2中的公共属性至少是R1和R2 中某个关系的侯选码。654.4.2 4.4.2 无损连接和函数依赖保持无损连接和函数依赖保持一、分解的无损连接性：一、分解的无损连接性： 如果一个关系模式分解后，可以通过自然如果一个关系模式分解后，

30、可以通过自然连接恢复原模式的信息，这一特性称为分解连接恢复原模式的信息，这一特性称为分解的无损连接性。的无损连接性。66分解的无损连接性：分解的无损连接性：设设R是关系模式，是关系模式，F是是R上的函数依赖集，则上的函数依赖集，则R的分解的分解=R1, , Rk是无损连接的，如果是无损连接的，如果R中每个满足中每个满足F的关系的关系r都有下式成立：都有下式成立：1( )Rrr 2( )Rr ( )Rkr67Tij=aj， 如果如果AjRibij，如果，如果AjRi1) 构造一个k行n列的二维表T： 每列对应一个属性Aj 每行对应一个模式Ri =R1(U1,F1),Rk(Uk,Fk)是R(U,F

31、)的一个分解，U=A1,An，F=FD1,FD2,FDp。算法算法 4.34.3 判定分解的无损连接性判定分解的无损连接性682) 根据F中函数依赖修改表T的内容。修改规则：修改规则：逐个考察F中的每个函数依赖FD：XY，找到表格中在X属性上取值相等的行，将在这些行上的Y属性取值改为相等，具体如下： （1）如果其中有一个符号为a aj j，则把其它符号也改为 a aj j，否则改为b bmjmj，其中m是这些行的最小行号。 （2）特别注意：修改过程中若某个bij被改动，则它所在列的所有bij都要做相应改动 693) 如果发现表中有一行已变成a1a2ak，则表示该分解具有无损连接性，否则分解不是

32、无损连接的。例：例：已知 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) 判断是否具有无损连接性。70ABCDEFa1b21b31a2b22b32a3a3b33b14a4a4b15b25a5b16b26a6第一步：建第一步：建T=R1(A，B，C) R2(C，D) R3(D，E，F)Tij=aj， 如果如果AjRibij， 如果如果AjRi71 第二步：逐个考察函数依赖，并修改表。第二步：逐个考察函数依赖，并修改表。(1)ABC, (2)CD, (3)AF, (4)DE, (5)DFa

33、4a5a5ABCDEFa1b21b31a2b22b32a3a3b33a4a4a5a6b14b16b15b25b26a6a6由于没有相同的分量，所以表不改变72 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具有无损连接性具有无损连接性73练习设关系模式 R为 R(H,I,J

34、,K,L)，R上的一个函数依赖集为 F=HJ,JK,IJ,JLH，判断如下哪个分解是无损连接的。 p=HK，HI，IJ，JKL，HL p=HIL，IKL，IJL p=HJ，IK，HL p=HI，JK，HL74HIJKLHKa1b12b13a4b15HIa1a2b23b24b25IJb31a2a3b34b35JKLb41b42a3a4a5HLa1b52b53b54a5A. p=HK，HI，IJ，JKL，HL 建表：75HIJKLHKa1b12b13a4b15HIa1a2b13b24b25IJb31a2a3b34b35JKLb41b42a3a4a5HLa1b52b13b54a5F=HJ,JK,IJ

35、,JLH修改表：76HIJKLHKa1b12b13a4b15HIa1a2b13a4b25IJb31a2a3a4b35JKLb41b42a3a4a5HLa1b52b13a4a5F=HJ,JK,IJ,JLH修改表：77HIJKLHKa1b12a3a4b15HIa1a2a3a4b25IJb31a2a3a4b35JKLb41b42a3a4a5HLa1b52a3a4a5F=HJ,JK,IJ,JLH修改表：78HIJKLHKa1b12a3a4b15HIa1a2a3a4b25IJb31a2a3a4b35JKLa1b42a3a4a5HLa1b52a3a4a5F=HJ,JK,IJ,JLH修改表：79HIJKLH

36、Ka1b12a3a4b15HIa1a2a3a4b25IJb31a2a3a4b35JKLa1b42a3a4a5HLa1b52a3a4a5F=HJ,JK,IJ,JLH修改表：陷入循环，结束非无损80HIJKLHILa1b12b13a4b15IKLa1a2b23b24b25IJLb31a2a3b34b35 B. p=HIL，IKL，IJL F=HJ,JK,IJ,JLH建表：81HIJKLHILa1a2a3b14a5IKLa1a2a3a4a5IJLa1a2a3b34a5 B. p=HIL，IKL，IJL F=HJ,JK,IJ,JLH修改表：无损连接分解。82 设设=R1，R2是关系模式是关系模式R的一

37、个分解，的一个分解，F是是R的一个函数依赖集，则对于的一个函数依赖集，则对于F，具有具有连接不失真性的充分必要条件是：连接不失真性的充分必要条件是： R1R2R1-R2F+ 或或 R1R2R2-R1F+。定理定理4.4:4.4: R1和R2中的公共属性至少是R1和R2 中某个关系的侯选码。83二、分解的函数依赖保持性：二、分解的函数依赖保持性： 若关系R(U,F)的一个分解=R1(U1,F1),Rk(Uk,Fk)的所有函数 依赖的并集 逻辑蕴涵了F中所有 函数依赖， 即 =F+， 则称分解具有函数依赖保持性。i=1k(Fi)i=1k(Fi)+84二、分解的函数依赖保持性二、分解的函数依赖保持性

38、问题：给定关系R(U,F)，及其分解：=R1(U1,F1),Rk(Uk,Fk)如何计算Fi：称为F在Ui上的投影Fi=XY| XYF+XY Ui；或与其等价的依赖集 85例：关系模式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)86 F1F2 F3=AB,BA, BC,CB, CD,DC F=AB，BC，CD，DA因为 (F1F2 F3)+=F+ 所以 分解具有函数依赖保持性。87练习

39、 设有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，判断该分解是否具有函数依赖保持性。 88算法算法4.54.5： 结果为结果为3 3NFNF的依赖保持分解算法的依赖保持分解算法 如果如果R R中有某些属性与中有某些属性与F F 的最小覆盖的最小覆盖F中的每个依赖的左边中的每个依赖的左边和右边都无关，原则上可由这些属性构成一个关系模式，并从和右边都无关，原则上可由这些属性构成一个关系模式，并从R R中将它们消除；否则，中将它们消除；否则， 如果如果FF中有一个依赖涉及到

40、中有一个依赖涉及到R R 的所有属性，则输出的所有属性，则输出R R；否否则，则， 输出一个分解输出一个分解 ，它由模式，它由模式XAXA组成，其中组成，其中XA XA F 。但当。但当XA1XA1，XA2XA2，XAn XAn 均属于均属于FF时，则用模式时，则用模式XA1 XA1 A2AnA2An代替代替XAiXAi（i=1i=1，2 2，n n）。）。89假定我们要够造一个数据库，属性集为假定我们要够造一个数据库，属性集为A,B,C,D,E,F,G，给定的函数依赖，给定的函数依赖集集F如下：如下：F=BCDA，BCE，AF，FG，CD，AG. .求求R R的一个满足的一个满足3NF3NF

41、的函数依赖保持分解的函数依赖保持分解举举 例例90举举 例例 1 求求F的最小覆盖的最小覆盖FmBC AE, AF , FG， CD2 条件（条件（1）不满足）不满足 3 条件（条件（2）不满足）不满足 4 根据条件（根据条件（3）输出）输出 =BCAE,AF,FG,CD91算法算法4.64.6： 结果为结果为3 3NFNF的依赖保持和连接不失真分解的依赖保持和连接不失真分解 设设是由是由“结果为结果为3NF3NF的依赖保持分解算法的依赖保持分解算法”得到得到的的3NF3NF分解，分解，X X为为R R的一个候选关键字，则：的一个候选关键字，则： = X = X 是是R R的一个分解，且其中的

42、所有关系模式均满足的一个分解，且其中的所有关系模式均满足3NF3NF，同时，既具有连接不失真性，又具有依赖保持性。同时，既具有连接不失真性，又具有依赖保持性。如何找到候选码？如何找到候选码？码值理论码值理论92 对于给定的关系对于给定的关系R R（A1A1，A2A2，AnAn）和函数）和函数依赖集依赖集F F，可将其属性分为，可将其属性分为4 4类：类：n L L类类 仅出现在仅出现在F F的函数依赖左部的属性的函数依赖左部的属性n R R类类 仅出现在仅出现在F F的函数依赖右部的属性的函数依赖右部的属性n N N类类 在在F F的函数依赖左右两边均未出现的属性的函数依赖左右两边均未出现的属

43、性n LRLR类类 在在F F的函数依赖左右两边均出现的属性的函数依赖左右两边均出现的属性93定理定理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）是）是

44、NN类属性，类属性，则则X X必是必是R R的候选码的成的候选码的成员。员。94候选码求解推论候选码求解推论 对于给定的关系模式对于给定的关系模式R R及其函数依赖集及其函数依赖集F F，若若X X（XRXR）是）是R R的的L L类或类或N N类属性组成的属性集，类属性组成的属性集，且且X X包含了包含了R R的全部属性，则的全部属性，则X X是是R R的唯一候选的唯一候选码。码。95设有关系模式R（A，B，C，D，E，P），R的函数依赖集为：FAD,ED,DB,BC D,DC A求R的候选码。举例举例：因为因为 CC，E E是是L L类属性，类属性，P P是是N N类属性，所以类属性，所以CEPCEP包含在所有候选码中；包含在所有候选码中；因为因为 （CEPCEP）ABCDEPABCDEP；所以所以 CEPCEP是是R R的唯一候选码