关系模式分解.ppt

1、4.1 关系模式的设计问题,4.2 关系模式的规范化,4.3 数据依赖的公理系统,4.4 关系模式的分解,第四章 关系数据理论,本章小结,4.1函数依赖,一、问题如何构造一个关系模式 例：假设有学生关系模式,其中，S#学号、 SNAME学生姓名、 CLASS班级、 C#课程号、 TNAME教师姓名、 TAGE教师年龄、ADDRESS教师地址、 GRADE成绩。,S(S#,SNAME,CLASS,C#,TNAME,TAGE,ADDRESS,GRADE),关系S存在以下问题： 1数据冗余度高。 SNAME、CLASS、TNAME、TAGE、ADDRESS重复存储多次。,4.1函数依赖,2数据修改复

2、杂。 3插入异常。 插入异常是指应该插入到数据库中的数据不能执行插入操作的情形。,关系S的主码：,（S#，C#）,从在S#、C#、和(S#,c#)上出现NULL值去分析。 注意：当一个元组在主码的属性上部分或全部为空时，该元组不能插入到关系中。,4.1函数依赖,4删除异常。 删除异常是指不应该删去的数据被删去的情形。 例如：选修某门课的所有学生都退选时，删除相关元组，会丢失该课程老师的信息。 解决：关系模式分解（关系规范化） 分解为 ST(S#，SNAME，CLASS) CT(C#,TNAME) TA(TNAME,TAGE,ADDRESS) SC(S#,C#,GRADE),4.1函数依赖,二、

3、函数依赖functional dependency, abbr. FD,设：R（A1，A2，An)=R( U ) X，Y，Z 为U的不同子集,定义4.1： 函数依赖 是完整性约束的一种，它推广了关键词的概念。If t1.X=t2.X, then t1.Y=t2.Y 函数依赖：若R的任意关系有：对X中的每个属性值，在Y中都有惟一的值与之对应，则称Y函数依赖于X，记作 XY 。,属性全集,4.1函数依赖,例：指出下列关系R中的函数依赖。,FD: AB-C、 AC、CA、ABD？ Insert into R values(a1, b1, c2, d1) FD = key constraint ?,4

4、.1函数依赖,函数依赖与属性间的关系有： 若X，Y是1 1关系， 则存在 XY或Y X 。如学号与借书证号 若X，Y是m 1关系， 则存在 XY但 Y+ X。如学号与姓名 若X，Y是m n关系， 则X，Y间不存在函数依赖关系。如姓名与课程 CF: 实体间的联系 NOTE: 函数依赖的方向性,4.1函数依赖,例 试指出学生关系S(S#，SNAME，CLASS，C#，TNAME，TAGE，ADDRESS，GRADE)中存在的函数依赖关系。 S#SNAME（每个学号只能有一个学生姓名） S#CLASS（每个学号只能有一个班级） C#TNAME（设每门课程只有一个教师任教，而一个教师可教多门课程，见C

5、T表） TNAMETAGE（每个教师只能有一个年龄） TNAMEADDRESS（每个教师只能有一个地址） (S#，C#)GRADE（每个学生学习一门课只能有一个成绩） (S#，C#)SNAME、 (S#，C#)CLASS、 (S#，C#)C#、 (S#，C#)TNAME、 (S#，C#)TAGE、 (S#，C#)ADDRESS,4.1函数依赖,三、函数依赖的分类 XY，但Y 不包含于 X则称X是非平凡的函数依赖。 XY，但Y X 则称X是平凡的函数依赖。 若XY ，则X叫做决定因素。 若XY，Y X，则记作: XY。 定义4.2：在R( U)中，X, Y, Z为U的不同子集。 完全函数依赖:

6、是指 XY，且对任何X的真子集X， 都有X+Y，记作：X F Y。 部分函数依赖: 是指XY，且存在X的真子集X， 有X-Y， 记作：X P Y。,定义4.3：在R( U )中 传递函数依赖：是指若XY (Y 不包含于 X)， Y + X ， 而Y Z。记作： X T Z 。,4.1函数依赖,左部为单属性的函数依赖一定是完全函数依赖。 左部为多属性的函数依赖，如何判断其是否为完全函数依赖？ 方法：取真子集，看其能否决定右部属性。 例：试指出学生关系S中存在的完全函数依赖和部分函数依赖。 S#SNAME，S#CLASS，TNAMETAGE， TNAMEADDRESS，C#TNAME都是完全函数依

7、赖。 (S#，C#)GRADE 是一个完全函数依赖，因为S#+GRADE，C#+GRADE。,4.1函数依赖,例：试指出学生关系S中存在的传递函数依赖。 解：因为C#TNAME，TNAME+C#，TNAMETAGE，所以C#TAGE 是一个传递函数依赖。类似地，C#ADDRESS也是一个传递函数依赖。,(S#，C#)SNAME，(S#，C#)CLASS， (S#，C#)TNAME，(S#，C#)TAGE， (S#，C#)ADDRESS都是部分函数依赖，因为S#SNAME，S#CLASS，C#TNAME，C#TAGE，C#ADDRESS。,4.1函数依赖,四、候选码 用函数依赖的概念来定义码。

8、定义4.4 : 设X为R中的属性或属性组合，若 X F U 则X为R的候选码。 说明： X F U X - U X能决定整个元组 X+ U X中无多余的属性,术语： 主码 主属性: 侯选码中的属性 非主属性 全码：整个属性组为码 例：R(顾客，商品，日期),4.1函数依赖,例：试指出下列关系R中的侯选码、主属性和非主属性。,解：关系R的侯选码为：A，(D,E) 关系R的主属性为：A，D，E 关系R的非主属性：无,函数依赖判断：A-D? D-A? AD-E? 候选码判断: A-ADE? AD-ADE?,4.1函数依赖,例1. R(A, B, C, D)，F=A-B, A-C, AB-D 解：由

9、AB-A(自反律) 和 A-C(已知) 得：AB-C(传递律) 又因为 AB-A (自反律) ，AB-B (自反律) 和 AB-D (已知) 得：AB-ABCD。 AB是R的唯一候选码，同时也是R的主码。,4.1函数依赖,例2. R(A, B, C, D)，F=A-B, A-C, A-D, AB-D 解：由 A-A(自反律) 和 A-B, A-C, A-D(已知) 得：A- ABCD 可知 A是R的候选码 AB-ABCD，但由于存在A- ABCD，则AB对ABCD是部分函数依赖，因此AB不能成为候选码。 A是R的唯一候选码，A是主码。,4.2 关系模式的规范化,一、关系与范式 关系的规范化是将

10、一个低级范式的关系模式，通过关系模式的分解转换为若干个高级范式的过程。 关系模式分解的目的：去冗余、满足约束。 关系模式的冗余性问题。例R(A,B,C)，无任何约束可导致冗余，若规定FD:A-B，则冗余可利用FD预测到。 约束条件通过函数的多值依赖和连接依赖及范式完成。,4.2 关系模式的规范化,二、第一范式：1NF 定义4.5: 若R的每个分量都是不可分的数据项，则R1NF。 从型上看：不存在嵌套结构 从值上看，不存在重复组 1NF是关系模式的最低要求。 例：学生关系S(S#，SNAME，CLASS，C#，TNAME，TAGE，ADDRESS，GRADE)是1NF关系，但它存在数据冗余，插入

11、异常和删除异常等问题。,4.2 关系模式的规范化,三、第二范式： 2NF 定义4.6 若R1NF，且R中的每一个非主属性都完全函数依赖于R的任一候选码，则R2NF。 例：学生关系S(S#，SNAME，CLASS，C#，TNAME，TAGE，ADDRESS，GRADE),判断R是否为2NF? 侯选码为(S#，C#)，非主属性有：SNAME，CLASS，TNAME，TAGE，ADDRESS，GRADE (S#，C#)SNAME， S# SNAME (S#，C#) P SNAME S2NF(每一个非主属性!)。,4.2 关系模式的规范化,分解为2NF的方法：破坏部分依赖的条件。 将满足部分函数依赖和

12、满足完全函数依赖的属性分解到不同的关系中。 对上例，考察非主属性和侯选码之间的函数依赖关系： (S#，C#) P SNAME， (S#，C#) P CLASS， (S#，C#) P TNAME， (S#，C#) P TAGE， (S#，C#) P ADDRESS， (S#，C#) F GRADE 区分出完全依赖和部分依赖，若是部分依赖，标记出其中的主属性。,4.2 关系模式的规范化,关系S分解为三个关系： ST(S#，SNAME，CLASS)（只依赖S#的属性分解到一个子模式中） CTA(C#，TNAME，TAGE，ADDRESS) （只依赖C#的属性分解到另一个子模式中） SC(S#，C#，

13、GRADE) （完全函数依赖于候选码的属性分解到第三个子模式中） 分解后，关系ST、CTA和SC都为2NF。 结论1：若关系R的侯选码是单属性的，则R必定是2NF。,4.2 关系模式的规范化,达到2NF的关系仍然可能存在问题。 例如，在关系CTA中还存在以下问题： （1） 数据冗余。一个教师承担多门课程时，教师的姓名、年龄、地址要重复存储。 （2） 修改复杂。一个教师更换地址时，必须修改相关的多个元组。 （3） 插入异常。一个新教师报到，需将其有关数据插入到CTA关系中，但该教师暂时还未承担任何教学任务，则因缺码C#值而不能进行插入操作。 （4） 删除异常。删除某门课程时，会丢失该课程任课教师

14、的姓名、年龄和地址信息。,4.2 关系模式的规范化,四、第三范式： 3NF 定义4.7 如果关系R的任意一个非主属性都不传递函数依赖于它的任意一个候选码，则R3NF。 关系CTA(C#，TNAME，TAGE，ADDRESS)是2NF，但不是3NF。 候选码：C#，非主属性：TNAME、TAGE、ADDRESS。 由于C#TNAME，TNAME+C#，TNAMETAGE，所以 C# T TAGE ，同样有C# T ADDRESS，即存在非主属性对候选码的传递函数依赖。,关系模式R（A，B，C，D），码为AB，给出它的 一个函数依赖集，使得R属于2NF而不属于3NF,4.2 关系模式的规范化,分解

15、为3NF的方法：破坏传递依赖的条件。 将涉及传递函数依赖中的两个依赖中的属性分解到不同的关系中。 例：CTA中，两个传递依赖C# T TAGE ，C# T ADDRESS C#TNAME，TNAME+C#，TNAMETAGE。 C#TNAME，TNAME+C#，TNAMEADDRESS。 将CTA分解为： CT(C#，TNAME) TA(TNAME，TAGE，ADDRESS) 则关系CT和TA都是3NF，关系CTA中存在的问题得到了解决。,4.2 关系模式的规范化,定理4.1 一个3NF的关系必定是 2NF。 （3NF传递函数依赖，2NF完全函数依赖。） 证明：用反证法。设R3NF，但R2NF

16、，则R中必有非 主属性A、侯选码X和X的真子集X存在，使得XA。 X是侯选码X的真子集，有X-X；A是非主属性，A-X，A-X，这样A、X、X是U的不同子集。 X是侯选码X的真子集，则有XX 且 X+X，联合反证假设XA可知存在传递依赖（XX，X+X，XA） R不是3NF，与题设矛盾。,4.2 关系模式的规范化,通过转为2NF消除了部分依赖，通过转为3NF消除了传递依赖，问题：达到3NF的关系是否仍然存在问题？ 例：每一教师只教一门课。每门课由若干教师教，某一学生选定某门课，就确定了一个固定的教师。某个学生选修某个教师的课就确定了所选课的名称 ：,4.2 关系模式的规范化,解：关系SCT的侯选

17、码：(S#，CNAME)和(S#，TNAME) 非主属性：无 （SCT至少是一个3NF关系) 结论2：若关系R的所有属性都是主属性，则R必定是3NF。,候选码判断: S#-S# CNAME TNAME. 取左部的相同值，判断右部。,4.2 关系模式的规范化,在3NF关系SCT中存在： 插入异常。例如，一个新课程和任课教师的数据，在没有学生选课时不能插入数据库。 删除异常。例如，删除某门课的所有选课记录，会丢失课程与教师的数据。 达到3NF的关系仍然可能存在问题。,4.2 关系模式的规范化,五、BCNF 定义4.8 关系模式R1NF。若函数依赖集合F中的 所有函数依赖XY（Y不包含于X）的左部都

18、包含R的任一侯选码，则RBCNF。 换言之，BCNF中的所有依赖的左部都必须包含候选码。 例：关系SCT是否BCNF? 因为TNAMECNAME，其左部未包含该关系的任一侯选码 ，所以它不是BCNF。 解决：BCNF分解。,4.2 关系模式的规范化,分解为BCNF的方法： 消除不包含关系。 1. 假设R(U)不是BCNF, X是R的属性子集，A是R的单个属性，X-A是导致违反BCNF的函数依赖，则将R分解为R-A 以及 XA。 2. 若R-A以及 XA 仍然不是BCNF，则在R-A 以及 XA递归地执行上述分解。 例 SCT：(S#，CNAME，TNAME)，FD: TNAMECNAME。 可

19、分解为SC(S#，TNAME)和CT(CNAME，TNAME)，它们都是BCNF。,4.2 关系模式的规范化,定理4.2：一个BCNF的关系必定是3NF。 （3NF：任意的非主属性都不传递依赖于任意一个候选码。） 证明：用反证法。设R是一个BCNF，但不是3NF，则必存在一个非主属性A和候选码X以及属性集Y，使得A传递依赖于X，即XY(Y不包含于X)，Y+X，YA。 这就是说Y不包含R的候选码，但YA却成立。 根据BCNF定义可知，R不是BCNF，与题设矛盾。 结论3：任何的二元关系必定是BCNF。,4.2 关系模式的规范化,3NF下仍然存在插入异常和删除异常， 原因在于可能存在主属性对候选码

20、的部分函数依赖和传递函数依赖。 一个模式中的关系模式如果都属于BCNF，则在函数依赖的范畴内实现了彻底的分离，已消除了插入和删除的异常。 其它问题？,4.2 关系模式的规范化,六、第四范式：4NF 定义4.10 若R 1NF，D是R上的依赖集，如果对于任何一个多值依赖XY (Y-X,XY没有包含R的全部属性)，X都包含了R的一个候选关键词，则R4NF。 4NF必定是BCNF，但BCNF不一定是4NF。,5种范式的关系：,4.2 关系模式的规范化,1NF,非规范化的关系,2NF,3NF,4NF,BCNF,范式的 转换关系：,1NF,2NF,3NF,BCNF,4NF,4.2 关系模式的规范化,关系

21、的规范化是将一个低级范式的关系模式，通过关系模式的分解转换为若干个高级范式的过程。 范式的转换过程是通过分析和消除属性间的数据依赖关系来实现的。 属性可分为码和非主属性。 2NF, 3NF考察非主属性和码的关系，BCNF考察主属性和码的关系。 属性间的依赖关系包括函数依赖和多值依赖。 1NF, 2NF, 3NF, BCNF考察了函数依赖关系；4NF考察了多值依赖。,4.3 数据依赖的公理系统,1.阿氏公理 定义4.13 设F是关系模式R的函数依赖集，X、Y是R的属性子集，如果从F的函数依赖中能够推出XY，则称F逻辑蕴涵XY。 在R 中为F所逻辑蕴含的函数依赖全体叫F的闭包，记为：F+。 F+=

22、 F； F中推出的非平凡的函数依赖； 平凡的函数依赖：A-、A-A、AB- A. 例：有关系模式R(A，B，C)，它的函依赖集F=AB，BC，计算F的闭包。,4.3 数据依赖的公理系统,Armstrong公理(阿氏公理)： 对R 有： A1自反律：若YX ，则XY。 A2增广律：若XY，则XZYZ。 A3传递律：若XY、YZ，则XZ。 Note：XY与YX的次序无关。,4.3 数据依赖的公理系统,证：设s，t是r的任意两个元组，r是R的任意一个关系。 A1自反律：若YX ，则XY。 若sx=tx，则在s和t中的x的任何子集也必相等。 YX， sy=ty XY。 A2增广律：若XY，则XZYZ。

23、 若sxz=txz，即sxsz=txtz 则 sx=tx 且 sz=tz XY， sy=ty syz=sysz=tytz=tyz XZYZ,4.3 数据依赖的公理系统,A3传递律：若XY、YZ，则XZ。 若sx=tx XY sy=ty 又 YZ sz=tz XZ。,4.3 数据依赖的公理系统,公理的推论： 合并规则：若XY 、 XZ，则XYZ。 分解规则：若XYZ，则XY,XZ。 伪传递规则：若XY 、WYZ，则WXZ。 证明： 合并规则： XY XXY (A2) 又 XZ XYYZ (A2) XYZ (A3),4.3 数据依赖的公理系统,分解规则： YY Z YZY (A1) 又 XYZ(已

24、知） XY (A3) 同理可证XZ。 伪传递规则： XY WXWY (A2) 又 WYZ (已知) WXZ (A3) 定理4.5: XA1A2AK成立的充分必要条件是XAi成立。,由合并律 由分解律 ,4.3 数据依赖的公理系统,定义4.14: XF+=A|XA能由F用阿氏公理导出 XF+称为属性集X关于F的闭包。 定理4.6： XY能从F中用阿氏公理导出的充要条件是：YXF+,4.3 数据依赖的公理系统,定理4.6的证明 证明： 充分性（ YXF+ - XY） 假设YXF+ (其中Y=A1A2An ) 由属性闭包定义可知， XA1， XA2， XAn能由阿氏公理导出，再由合并规则得X A1A

25、2An，即XY。,4.3 数据依赖的公理系统,必要性：（ XY - YXF+ ） 假设XY能由阿氏公理导出(Y=A1A2An) 则有XA1A2An 由分解规则得： XA1， XA2， XAn 由XF+的定义可知，Ai XF+ (i=1,2,n) 即YXF+ 。,Armstrong公理系统,Armstrong公理完备性的证明 证明：（构造性证明）用反证法 假定存在函数依赖XY被F逻辑蕴涵，但XY不能用Armstrong公理从F中导出 由引理二， 构造R(U)上的关系r如下： 下面证明（1）r满足F，（2）r不满足XY,Y ，Y ， U ,4.3 数据依赖的公理系统,2. 属性闭包的计算 算法4.

26、1 : 求属性集X关于F的闭包XF+(X+)。 算法： 设 R，A为U中属性(集)。 (1) X(0)=X (2) X(i+1)=X(i)A 其中：对F中任一个Y-A ，且YX(i)； 求得X(i+1) 后，对Y-A 做删除标记。 (3)若X(i+1)=X(i) 或 X(i+1) =U则结束，否则转(2)。,最多|U-X|步,闭包的计算,示例1 R, U = (A, B, C, G, H, I), F = AB, AC, CGH, CGI, BH,计算 所用依赖 ABAGB ACAGBC CGHAGBCH CGIAGBCH I = AGBCH I,闭包的计算,示例2 R, U = (A, B,

27、 C, D, E), F = ABC, BD, CE, CEB, ACB,计算 所用依赖 ABCABC BDABCD CEABCDE = ABCDE,闭包的计算,示例3 R, U = (A, B, C, D, E, G), F = AE, BEAG, CEA, GD,计算 所用依赖 AEABE BEAGABEG GDABEGD = ABEGD,4.3 数据依赖的公理系统,3.函数依赖集的等价和覆盖 定义4.15 : 如果F+=G+ ，就说函数依赖集F覆盖G或F与G等价。 定理4.9: F+=G+ 的充分必要条件是FG+，和GF+。 （1）必要性 F和G等价，F+=G+，又FF+，FG+ 同理，

28、GG+，GF+。 （2）充分性 任取XYF+，则有YXF+ (定理4.6) 又FG+（已知），YXG+ XY(G+)+=G+，F+G+。 同理可证G+F+，F+=G+，即F和G等价。,4.3 数据依赖的公理系统,如何判断函数依赖集F和G是否等价？ 根据定理4.9: 只需FG+和GF+，即证集合的包含关系。 对每个T F,有T G+；对每个S G，有S F+，T和S是形如X-Y的属性依赖。 证 X-Y G+,根据定理4.6：只需Y XG+ 转为计算XG+,4.3 数据依赖的公理系统,例：F=AB，BC，G=ABC，BC，判断F和G是否等价。 解：（1）先检查F中的每一个函数依赖是否属于G+。 A

29、G+=ABC，BAG+，ABG+ (定理4.6) 又BG+=BC，CBG+，BCG+ FG+ （2）然后检查G中的每一个函数依赖是否属于F+。 AF+=ABC，BCAF+，ABCF+ 又BF+=BC，CBF+，BCF+ GF+ 由（1）和（2）可得F和G等价。,4.3 数据依赖的公理系统,4.最小函数依赖集 定义4.16:若F满足下列条件，则称其为一个最小函数依赖集Fm。 (1) F中每个函数依赖的右部都是单属性； (2) 对于F的任一函数依赖XA，F-XA与F都不等价； (3) 对于F中的任一函数依赖XA和X的真子集Z， (F-(XA)UZA与F都不等价。,最小：（1）F中每个函数依赖的右部

30、没有多余的属性； （2）F中不存在多余的函数依赖； （3）F中每个函数依赖的左部没有多余的属性。,4.3 数据依赖的公理系统,定理4.10: 每个F与Fm等价。 如何求最小函数依赖集Fm？ (1)分解：使F中任一函数依赖的右部仅含有单属性。 (2)删除冗余的函数依赖： 方法：对F中任一XA，在F-XA中求X+， 若AX+，则XA为多余的。 (3)最小化左边的多余属性： 方法：对F中任一XYA，在F中求X+， 若AX+ ，则Y为多余的。 (4)检查：用公理或(2) ,4.3 数据依赖的公理系统,例：设有F=BC，CAB，BCA，求与F等价的最小函数依赖集。 分解CAB，F=BC，CA，CB，BC

31、A 判断BC是否冗余，F=CA，CB，BCA B+ = B, BC非冗余。 F=BC，CA，CB，BCA 判断CA是否冗余，F=BC, CB，BCA C+ = ABC, CA冗余。 F=BC，CB，BCA 判断CB是否冗余，F=BC, BCA C+ = C, CB非冗余。 F=BC，CB，BCA 判断BCA是否冗余，F=BC，CB BC+ = BC, BCA非冗余。F=BC，CB，BCA 判断BCA。 B+ = ABC, AB+ ，则C在BCA中是多余的。 Fmin=BC，CB，BA,注意： 对当前F求闭包,4.3 数据依赖的公理系统,例：设有函数依赖集F=AB,ABCDE,EFG,EFH,A

32、CDFEG 求与F等价的最小函数依赖集。 注意：一个函数依赖集的最小集不是惟一的。 例如，F=AB，BA，BC，AC，CA Fm1=AB，BC，CA， Fm2=AB，BA，AC，CA。 方法1： 无多余属性；依次判断B-A, A-C是否冗余； 方法2： 无多余属性；依次判断B-C是否冗余。,Fmin = AB,ACDE, EFG,EFH,4.4 关系模式的分解,对于存在数据冗余、插入异常、删除异常的关系模式，可以通过对关系模式的分解来解决问题。关系模式分解后会带来两个问题： （1）查询时的连接操作是否会丢失某些信息或多出某些信息。这引出了无损连接的概念。 （2）分解后的关系模式是否保持了原来的

33、函数依赖。这是保持函数依赖性的问题。,4.4 关系模式的分解,1. 等价模式分解的定义 一个关系可以有多种分解方法，如何判断分解的好与坏呢？ 例：关系模式R(S#，SD，MN),F=S#SD，SDMN 分解一：1=R1(S#)， R2(SD)， R3(MN) 不好！无法恢复r. 分解二：2=R1(S#，SD)，R2(S#，MN) 不好！丢失SDMN 分解三：3=R1(S#，SD)，R2(SD，MN) 好！,R(A, B, C),AB(R),BC(R),AB(R),BC(R),R(A, B, C),AB(R),BC(R),AB(R),BC(R),有损分解,无损分解,4.4 关系模式的分解,2.无

34、损连接性与依赖保持性 对于R中任何一个关系r， R分解=R1, R2.RK 无损连接性： r=R1(r) R2(r) RK(r) 保持函数依赖： F R1(F)R2(F) RK(F) Ri(F)=X-Y| X-YF+XYRi ,Ri所蕴含的F+中的函数依赖,4.4 关系模式的分解,例：R(A，B，C) ， F=A-B，A-C ，分解=AB，AC 判断1： r=AB(r) |X| AC(r) 是无损连接分解。 判断2: FAB(F)AC(F) = A-B，A-C 具有函数依赖保持性。,r,?=AB，BC,4.4 关系模式的分解,算法4.3 无损连接性检验。 输入：关系模式R(A1，A2，An)，

35、它的函数依赖集F，以及分 解=R1，R2，Rk。 输出：确定是否具有无损连接性。 方法：(1)构造一个k行n列的表，第i行对应于关系模式Ri，第j列 对应于属性Aj。如果AjRi，则在第i行第j列上放符号aj，否则放 符号bij。（属于用a代表，且位置信息用j表示；不属于用b代表,且位置信息用ij表示。） (2)重复考察F中的每一个函数依赖，并修改表中的元素。其方 法如下：取F中一个函数依赖XY，在X的分量中寻找相同的行，然 后将这些行中Y的分量改为相同的符号，如果其中有aj，则将bij改 为aj；若其中无aj，则全部改为bij（i是这些行的行号最小值）。,4.4 关系模式的分解,(3)如果发

36、现表中某一行变成了al，a2，an，则分解 具有无损连接性；如果F中所有函数依赖都不能再修改 表中的内容，且没有发现这样的行，则分解不具有无 损连接性。,无损连接分解,示例一：U=A,B,C,D,E, F=ABC, CD,DE =(A, B, C), (C, D), (D, E),ABC,CD,DE,4.4 关系模式的分解,示例二：U=A,B,C,D,E, F=AC, BC, CD,DEC ,CEA =(A, D), (A, B), (B, E), (C, D, E), (A, E),AC,4.4 关系模式的分解,BC,CD,4.4 关系模式的分解,DEC,CEA,4.4 关系模式的分解,定理

37、4.12 设=(R1，R2)是R的一个分解，F是R上的函数 依赖集，分解具有无损连接性的充分必要条件是： R1R2(R1-R2)F+ 或 R1R2(R2-R1)F+ 证明： （1）充分性：设R1R2(R1-R2)，按算法5.2可构造出下表。表中省略了a和b的下标，这无关紧要。,只能用于判断分解为2个子模式的情况。,4.4 关系模式的分解,如果R1R2(R1-R2)在F中，则可将表中第2行位于(R1-R2)列 中的所有符号都改为a，这样该表中第2行就全是a了，则具有无 损连接性。同理可证R1R2(R2-R1)的情况。 如果R1R2(R1-R2)不在F中，但在F+中，即它可以用公理从 F中推出来，

38、从而也能推出R1R2Ax, 其中AxR1-R2，所以可 以将Ax列的第2行改为全a，同样可以将R1-R2中的其他属性的第2 行也改为a，这样第2行就变成全a行。所以分解=R1，R2具有 无损连接性。 同样可以证明R1R2(R2-R1)的情况。 （2）必要性：设构造的表中有一行全为a，例如第1行全为a，则 由函数依赖定义可知R1R2(R2-R1)；如果是第2行全为a，则 R1R2(R1-R2)。定理证毕。,4.4 关系模式的分解,例:下列分解是否具有无损连接性和函数依赖保持性。 已知：R(A,B,C) F=AB，CB (1）1=AB，BC （2）2=AC，BC,4.4 关系模式的分解,（1）对1

39、和F构造表：,（2）检查F=AB，CB 对AB，A列中无相同的行； 对CB, C列中无相同的行。 1不具有无损连接性。,1=AB，BC F=AB，CB,4.4 关系模式的分解,1=AB，BC F=AB，CB 利用定理4.12解。 R1R2 = B (R1-R2) = A R1R2 + (R1-R2) 1不是无损连接分解。,4.4 关系模式的分解,2=AC，BC F=AB，CB,对2和F构造表：,检查F=AB，CB 对CB, C列有相同的行，改写B列的相异符号为a，下标为列号2。第一行变为a1a2a3,2具有无损连接性。,4.4 关系模式的分解,2=AC，BC F=AB，CB 利用定理4.12解

40、。 R1R2 = C (R1-R2) = A；(R2-R1) = B； R1R2 + (R2-R1) 2是无损连接分解。,4.4 关系模式的分解,3. 模式分解的方法 3NF的保持无损连接及函数依赖的分解： 设： R 1)对Fm中任一X-A，若XA=U则不分解，结束。 2)若R中Z属性在Fm中未出现，则所有Z为一个子模式， 令U=U-Z。 3)对Fm中 X-A1，. X-An，用合成规则合成一个， 再对Fm中每个X-A，令Ri=XA。 4) R的分解为R1，R2，.RK，码,依赖保持不需要； 原包含有不需要。,4.4 关系模式的分解,BCNF的保持无损连接的分解： （1）令=R； （2）如果中

41、所有关系模式都是BCNF，则转（4）； （3）如果中有一个关系模式Ri不是BCNF，则Ri中必有XAFi+(AX)，且X不是Ri的码。设S1=XA，S2=Ui-A，用分解S1，S2代替Ri，转（2）； （4）分解结束，输出。 例：设R=A,B,C,D,F=AC，CA，BAC，DAC，BDA （1）将R 分解为3NF且具有无损连接性和依赖保持性。 （2）将R 分解为BCNF且具有无损连接性。,关系模式的分解算法,示例：U=S#，SD，MN，C#，G F=S#SD，S#MN，SDMN，(S#,C#)G U1=S#，SD , F1=S#SD U2=S#, MN, C#, G, F2=S#MN, (S

42、#,C#)G U1 = S#, SD, F1=S#SD U2 = S#, MN, F2=S#MN U3 = S#, C#, G, F3 = (S#,C#)G,4.4 关系模式的分解,关系模式CTHRSG，其中C表示课程，T表示教师，H表示时 间，R表示教室，S表示学生，G表示成绩。函数依赖集F及 其所反映的语义分别为： CT 每门课程仅有一位教师担任。 HTR 在任一时间，一个教师只能在一个教室上课。 HRC 在任一时间，每个教室只能上一门课。 HSR 在任一时间，每个学生只能在一个教室听课。 CSG 每个学生学习一门课程只有一个成绩。,4.4 关系模式的分解,解：HSCTHRSG，HS是关系

43、模式的关键字。, 面向3NF且保持函数依赖的分解。 最小函数依赖集为 F=CT,CSG,HRC,HSR,THR 分解为：CT，CSG，HRC，HSR，THR, 面向3NF既有无损连接性又保持函数依赖的分解。 HS是关键字， HS ，HS是HSR的一个子集 分解仍为：CT，CSG，HRC，HSR，THR,4.4 关系模式的分解, 面向BCNF且具有无损连接性的分解。,CTHRSG Key=HS,CSG Key=CS CSG,CTHRS Key=HS CT，THR HRC，HSR,CT Key=C CT,CHRS Key=HS CHR，HRC HSR,CHR Key=CH，HR CHR， HRC,

44、CHS Key=HS HSC,4.5. 多值依赖与第四范式4NF）,例: 学校中某一门课程由多个教师讲授，他们使用相同的一套参考书。 关系模式Teaching(C, T, B) 课程C、教师T 和 参考书B,例: 学校中某一门课程由多个教师讲授，他们使用相同的一套参考书。 关系模式Teaching(C, T, B) 课程C、教师T 和 参考书B,4.5. 多值依赖与第四范式4NF）,4.5. 多值依赖与第四范式4NF）,TeachingBCNF: Teach具有唯一候选码(C，T，B)， 即全码 Teaching模式中存在的问题 (1)数据冗余度大：有多少名任课教师，参考书就要存储多少次 (2

45、)插入操作复杂：当某一课程增加一名任课教师时，该课程有多少本参照书，就必须插入多少个元组 例如物理课增加一名教师刘关，需要插入两个元组： （物理，刘关，普通物理学） （物理，刘关，光学原理）,4.5. 多值依赖与第四范式4NF）,(3) 删除操作复杂：某一门课要去掉一本参考书，该课程有多少名教师，就必须删除多少个元组 (4) 修改操作复杂：某一门课要修改一本参考书，该课程有多少名教师，就必须修改多少个元组 产生原因 存在多值依赖,4.5. 多值依赖与第四范式4NF,第四范式：4NF 定义4.10 若R 1NF，D是R上的依赖集，如果对于任何一个多值依赖XY (Y-X,XY没有包含R的全部属性)

46、，X都包含了R的一个候选关键词，则R4NF。 4NF必定是BCNF，但BCNF不一定是4NF。,4.5. 多值依赖与第四范式4NF,在R（U）的任一关系r中，如果存在元组t，s 使得tX=sX，那么就必然存在元组 w，v r，（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。 t x y1 z2 s x y2 z1 w x y1 z1 v x y2 z2,4.5. 多值依赖与第四范式4NF,平凡多值依赖和非平凡的多值依赖 若XY，而Z，则称 XY为平凡的多值依赖 否则称XY为非平凡的多值依赖,4.5. 多值依赖与第四范式4NF多值依赖的性质,（1）多值依赖具有对称性 若XY，则XZ，其中