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函数依赖,二、函数依赖fu
3、nctional 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.1函数依赖,函数
4、依赖与属性间的关系有：若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（设每门课程只有一个教师任教，而一个教师可教多门课程，见CT表）TNAMETAGE（每个教
5、师只能有一个年龄）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的不同子集。完全函数依赖: 是指 XY，且对任何X的真子集X， 都有X+Y，记
6、作：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都是完全函数依赖。(S#，C#)GRADE 是一个完全函数依赖，因为S#+
7、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函数依赖,四、候选码 用函数依赖的概念来定义码。定义4.4 : 设X为R中的属性或属性组合，若 X F U 则X为
8、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解：由 AB-A(自反律) 和 A-C(已知) 得：AB-C(传递律) 又因为 AB-A
9、 (自反律) ，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关系，但它存在数据冗余，插入异常和删除异常等问题。,4.2 关系模式的规范化,三、第二范式： 2NF 定义4.6 若R1N
11、F，且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的方法：破坏部分依赖的条件。 将满足部分函数依赖和满足完全函数依赖的属性分解到不同的关系中。对上例，考察非主属性和侯选码之间的函数依赖关系：(S#，
12、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#，GRADE) （完全函数依赖于候选码的属性分解到第三个子模式中）分解后，关系ST、CTA和SC都为2NF。结论1
13、：若关系R的侯选码是单属性的，则R必定是2NF。,4.2 关系模式的规范化,达到2NF的关系仍然可能存在问题。例如，在关系CTA中还存在以下问题：（1） 数据冗余。一个教师承担多门课程时，教师的姓名、年龄、地址要重复存储。（2） 修改复杂。一个教师更换地址时，必须修改相关的多个元组。（3） 插入异常。一个新教师报到，需将其有关数据插入到CTA关系中，但该教师暂时还未承担任何教学任务，则因缺码C#值而不能进行插入操作。（4） 删除异常。删除某门课程时，会丢失该课程任课教师的姓名、年龄和地址信息。,4.2 关系模式的规范化,四、第三范式： 3NF定义4.7 如果关系R的任意一个非主属性都不传递函数
14、依赖于它的任意一个候选码，则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 关系模式的规范化,分解为3NF的方法：破坏传递依赖的条件。 将涉及传递函数依赖中的两个依赖中的属性分解到不同的关系中。例：CTA中，两个传递依赖C# T T
15、AGE ，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，则R中必有非主属性A、侯选码X和X的真子集X存在，使得XA。X是侯选码X的真子集，有X-X；A是非主属性，A-X，A-X，这样A、X、X
16、是U的不同子集。 X是侯选码X的真子集，则有XX 且 X+X，联合反证假设XA可知存在传递依赖（XX，X+X，XA）R不是3NF，与题设矛盾。,4.2 关系模式的规范化,通过转为2NF消除了部分依赖，通过转为3NF消除了传递依赖，问题：达到3NF的关系是否仍然存在问题？例：每一教师只教一门课。每门课由若干教师教，某一学生选定某门课，就确定了一个固定的教师。某个学生选修某个教师的课就确定了所选课的名称 ：,4.2 关系模式的规范化,解：关系SCT的侯选码：(S#，CNAME)和(S#，TNAME) 非主属性：无 （SCT至少是一个3NF关系) 结论2：若关系R的所有属性都是主属性，则R必定是3N
17、F。,候选码判断: S#-S# CNAME TNAME.取左部的相同值，判断右部。,4.2 关系模式的规范化,在3NF关系SCT中存在：插入异常。例如，一个新课程和任课教师的数据，在没有学生选课时不能插入数据库。删除异常。例如，删除某门课的所有选课记录，会丢失课程与教师的数据。达到3NF的关系仍然可能存在问题。,4.2 关系模式的规范化,五、BCNF 定义4.8 关系模式R1NF。若函数依赖集合F中的所有函数依赖XY（Y不包含于X）的左部都包含R的任一侯选码，则RBCNF。 换言之，BCNF中的所有依赖的左部都必须包含候选码。 例：关系SCT是否BCNF? 因为TNAMECNAME，其左部未包
18、含该关系的任一侯选码，所以它不是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。 可分解为SC(S#，TNAME)和CT(CNAME，TNAME)，它们都是BCNF。,4.2 关系模式的规范化,定理4.2：一个BCNF的关系必定是3NF。（3N
19、F：任意的非主属性都不传递依赖于任意一个候选码。）证明：用反证法。设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下仍然存在插入异常和删除异常， 原因在于可能存在主属性对候选码的部分函数依赖和传递函数依赖。一个模式中的关系模式如果都属于BCNF，则在函数依赖的范畴内实现了彻底的分离，已消除了插入和删除的异常。其它问题？,4.2 关系模式的规
20、范化,六、第四范式：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 关系模式的规范化,关系的规范化是将一个低级范式的关系模式，通过关系模式的分解转换为若干个高级范式的过程。范式的转换过程是通过分析和消除属性间的数据依赖关系来实现的。属性可分为码和非主属性。 2NF,
21、 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+= F； F中推出的非平凡的函数依赖； 平凡的函数依赖：A-、A-A、AB- A. 例：有关系模式R(A，B，C)，它的函依赖集F=AB，BC，计算F的闭包。,4.3 数据依赖的公理系统,
22、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。 若sxz=txz，即sxsz=txtz 则 sx=tx 且 sz=tz XY， sy=ty syz=sysz=tytz=tyz XZYZ,4.3 数据依赖的公理系统,A3传递律：若XY、YZ，则X
23、Z。 若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(已知） XY (A3) 同理可证XZ。伪传递规则： XY WXWY (A2) 又 WYZ (已知) WXZ (A3)定理4.5: XA1A2AK成立的充分必要条件是XAi成立。,由合并律 由分解律 ,4
24、.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 A1A2An，即XY。,4.3 数据依赖的公理系统,必要性：（ XY - YXF+ ） 假设XY能由阿氏公理导出(Y=A1A2An) 则有XA1A2An 由分解规则得： XA1， XA2， XAn 由XF+的定义可
25、知，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.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 做删
26、除标记。 (3)若X(i+1)=X(i) 或 X(i+1) =U则结束，否则转(2)。,最多|U-X|步,闭包的计算,示例1R, U = (A, B, C, G, H, I), F = AB, AC, CGH, CGI, BH,计算 所用依赖 ABAGB ACAGBC CGHAGBCH CGIAGBCH I= AGBCH I,闭包的计算,示例2R, U = (A, B, C, D, E), F = ABC, BD, CE, CEB, ACB,计算所用依赖 ABCABC BDABCD CEABCDE= ABCDE,闭包的计算,示例3R, U = (A, B, C, D, E, G), F = A
27、E, 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+同理，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.
28、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+。 AG+=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.
29、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中每个函数依赖的右部没有多余的属性； （2）F中不存在多余的函数依赖； （3）F中每个函数依赖的左部没有多余的属性。,4.3 数据依赖的公理系统,定理4.10: 每个F与Fm等价。如何求最小函数依赖集Fm？ (1)分解：使F中任一函数依赖的右部仅含有单属性。 (2)删除冗余的函数依赖：
30、方法：对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，BCA判断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非冗余。
31、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,ACDFEG 求与F等价的最小函数依赖集。注意：一个函数依赖集的最小集不是惟一的。例如，F=AB，BA，BC，AC，CA Fm1=AB，BC，CA， Fm2=AB，BA，AC，CA。方法1： 无多余属性；依次判断B-A, A-C是否冗余；方法2： 无多余属性；依次判断B-C是否冗
32、余。,Fmin = AB,ACDE, EFG,EFH,4.4 关系模式的分解,对于存在数据冗余、插入异常、删除异常的关系模式，可以通过对关系模式的分解来解决问题。关系模式分解后会带来两个问题：（1）查询时的连接操作是否会丢失某些信息或多出某些信息。这引出了无损连接的概念。（2）分解后的关系模式是否保持了原来的函数依赖。这是保持函数依赖性的问题。,4.4 关系模式的分解,1. 等价模式分解的定义 一个关系可以有多种分解方法，如何判断分解的好与坏呢？例：关系模式R(S#，SD，MN),F=S#SD，SDMN分解一：1=R1(S#)， R2(SD)， R3(MN) 不好！无法恢复r.分解二：2=R1
33、(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.无损连接性与依赖保持性 对于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)
34、， 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)，它的函数依赖集F，以及分解=R1，R2，Rk。 输出：确定是否具有无损连接性。方法：(1)构造一个k行n列的表，第i行对应于关系模式Ri，第j列对应于属性Aj。如果AjRi，则在第i行第j列上放符号aj，否则放符号bij。（属于用a代表，且位置信息用j表示；不属于用b代表,且位置信息用ij表示。） (2
35、)重复考察F中的每一个函数依赖，并修改表中的元素。其方法如下：取F中一个函数依赖XY，在X的分量中寻找相同的行，然后将这些行中Y的分量改为相同的符号，如果其中有aj，则将bij改为aj；若其中无aj，则全部改为bij（i是这些行的行号最小值）。,4.4 关系模式的分解,(3)如果发现表中某一行变成了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 关系模式
36、的分解,示例二：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 关系模式的分解,定理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.
37、4 关系模式的分解,如果R1R2(R1-R2)在F中，则可将表中第2行位于(R1-R2)列 中的所有符号都改为a，这样该表中第2行就全是a了，则具有无 损连接性。同理可证R1R2(R2-R1)的情况。 如果R1R2(R1-R2)不在F中，但在F+中，即它可以用公理从 F中推出来，从而也能推出R1R2Ax, 其中AxR1-R2，所以可 以将Ax列的第2行改为全a，同样可以将R1-R2中的其他属性的第2 行也改为a，这样第2行就变成全a行。所以分解=R1，R2具有 无损连接性。 同样可以证明R1R2(R2-R1)的情况。 （2）必要性：设构造的表中有一行全为a，例如第1行全为a，则 由函数依赖定义
38、可知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和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不是无损连接分解。
39、,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解。 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为一个子模式，
40、令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）如果中所有关系模式都是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且具有无损连接性和依赖
41、保持性。 （2）将R 分解为BCNF且具有无损连接性。,关系模式的分解算法,示例：U=S#，SD，MN，C#，GF=S#SD，S#MN，SDMN，(S#,C#)GU1=S#，SD , F1=S#SD U2=S#, MN, C#, G, F2=S#MN, (S#,C#)GU1 = 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是关系模式的关键字。,
