函数依赖的公理系统

1、1 函数依赖的公理系统函数依赖的公理系统n建立函数依赖推理系统建立函数依赖推理系统的目的的目的:(1) 求关系模式的候选码求关系模式的候选码(2) 判断关系模式的范式级别判断关系模式的范式级别(3) 给定一组函数依赖，需要导出另外一些函数依赖，给定一组函数依赖，需要导出另外一些函数依赖， 或判断另外的函数依赖是否成立。例如：或判断另外的函数依赖是否成立。例如： FD=A B，B C，判断，判断 A C是否成立？是否成立？n本节内容本节内容:1. 1. 逻辑蕴涵；逻辑蕴涵； 2.2. ArmstrongArmstrong函数依赖公理系统；函数依赖公理系统；3.3. 函数依赖集的闭包；函数依赖集的

2、闭包； 4.4. 属性集闭包；属性集闭包；5.5. 函数依赖集的等价和覆盖；函数依赖集的等价和覆盖； 6. 6. 最小函数依赖集。最小函数依赖集。2逻辑蕴涵逻辑蕴涵n定义定义4.11 关系模式关系模式R，F是其函数依是其函数依赖集赖集，X、Y是是U的属性子集，的属性子集，r是是R的任何一个的任何一个关系，如果从关系，如果从F的函数依赖能够推出的函数依赖能够推出XY，则则称称 F逻辑蕴涵逻辑蕴涵 XY，记作记作F XY 。n示例示例:R, U=X, Y, F = XY则则 F逻辑蕴涵以下函数依赖逻辑蕴涵以下函数依赖: XX， XY， YY, XYX，XYY，XYXY3函数依赖集的闭包函数依赖集的

3、闭包F+n定义定义4.12 在关系模式在关系模式R中，中，被被F所所逻辑蕴涵的函数依赖的全体所构成的集合称逻辑蕴涵的函数依赖的全体所构成的集合称作作F的的闭包闭包，记作，记作 F+ = XY | F XYn显然，显然，F F F F+ + 。nF+的计算很麻烦，的计算很麻烦，F不大，其不大，其F+也可能很大。也可能很大。 例如：例如：设设 R, U=X, Y, Z, F = XR, U=X, Y, Z, F = XY, YY, YZZ F F+ + = = X XX X， X XY Y，X X Z, Z, Y YY, Y, Y YZ, Z Z, Z Z, Z, XYXYX X，XYXYY Y，

4、XYXYXY, XZX, XY, XZX, Armstrong公理系统公理系统n函数依赖公理系统由函数依赖公理系统由ArmstrongArmstrong于于19741974年首先提出。年首先提出。n设关系模式设关系模式 RR，U U为属性全集，为属性全集，F F是是U U上的一上的一组函数依赖，组函数依赖，X X、Y Y、Z Z是是U U的属性子集，对的属性子集，对R R有以下推有以下推理规则：理规则： A1A1自反律自反律( (reflexivity)reflexivity)：若若 Y Y X, X, 则则 X X Y Y。 A2 A2增广律增广律( (augmentation)augmen

5、tation)：2 2若若 X X Y Y ，则则 XZ XZ YZ YZ。 A3 A3传递律传递律( (transitivity)transitivity)：若若 X X Y Y，Y Y Z Z，则则 X X Z Z 。n注意注意: : 由由自反律自反律所得到的函数依赖是所得到的函数依赖是平凡的平凡的, , 自反律的自反律的使用并不依赖于函数依赖集使用并不依赖于函数依赖集F F。传递律与传递依赖传递律与传递依赖？所得到的函数依赖是所得到的函数依赖是不平凡的。不平凡的。5A公理系统的正确性和完备性公理系统的正确性和完备性nArmstrongArmstrong公理的正确性公理的正确性( (即有效

6、性即有效性) )及完备性。及完备性。n正确性正确性：用：用ArmstrongArmstrong公理从公理从F F中导出的函数依赖中导出的函数依赖必为必为F F所蕴涵。所蕴涵。n完备性完备性：被：被F F所蕴涵的函数依赖都能用所蕴涵的函数依赖都能用ArmstrongArmstrong公理从公理从F F中导出。中导出。n公理的正确性公理的正确性保证由保证由F F出发根据公理推导出的每一个出发根据公理推导出的每一个函数依赖一定在函数依赖一定在F F+ +中。中。n公理的完备性公理的完备性保证用公理能推出所有的函数依赖保证用公理能推出所有的函数依赖, , 即即F F+ +中的所有函数依赖都能由中的所有

7、函数依赖都能由F F出发用公理推导出来。出发用公理推导出来。这个问题很重要这个问题很重要, , 因为因为, , 如果如果F F+ +中有一个函数依赖不中有一个函数依赖不能用公理推导出来能用公理推导出来, , 那么那么, , 这些公理就不够用这些公理就不够用, , 就不完就不完备备, , 还必须补充新的公理还必须补充新的公理 。6A公理系统的正确性证明公理系统的正确性证明n定理定理4.1 Armstrong推理规则是正确的。推理规则是正确的。 按函数依赖定义，假设按函数依赖定义，假设 r r 是是RR上的任一关系上的任一关系实例，实例，t t、s s 是是 r r 的任意两个元组。的任意两个元组

8、。（1 1）证明自反律）证明自反律: : 若若Y Y X X U U，则则 X X Y Y 若若tX=sX, tX=sX, 由于由于Y Y X X, , 有有tY=sY, tY=sY, 所以有所以有X X Y Y。tX = sXYXtY = sYX Y自反律7A公理系统：增广律证明公理系统：增广律证明tXZ = sXZtX = sXXYtY = sYtXZ = sXZtZ = sZtYZ = sYZXZYZ增广律(2) (2) 证明增广律证明增广律: : 若若 X X Y Y， 则则 XZ XZ YZ YZ。 设设 tXZ=sXZ, tXZ=sXZ, 则有则有tX=sXtX=sX和和tZ=sZ

9、, tZ=sZ, 由于由于 X XY, Y, 对对tX=sXtX=sX，就有就有tY=sY, tY=sY, 从而有从而有tYZ=sYZ, tYZ=sYZ, 所以所以 XZ XZ YZ YZ成立。成立。8A公理系统：传递律证明公理系统：传递律证明X YtX = sXtY = sYY ZtZ = sZX Z传递律(3) (3) 证明传递律证明传递律: : 若若 X X Y Y 及及 Y YZ Z，则则 X X Z Z。 设设 tX = sX, tX = sX, 由于由于X XY, Y, 则有则有 tY = sY, tY = sY, 再由再由 Y YZ Z， 对对tY = sYtY = sY，有有

10、tZ=sZ,tZ=sZ, 所以所以 X X Z Z 成立。成立。.9A公理系统：推论公理系统：推论n由由ArmstrongArmstrong公理导出的公理导出的推理规则推理规则参见参见P184.P184.n合并律合并律( (union rule)union rule) 若若 X X Y Y，X X Z Z，则则 X X YZ YZ。n分解律分解律( (decomposition rule)decomposition rule) 若若 X X YZ YZ ，则则 X X Y Y，X X Z Z。n伪传递律伪传递律( (pseudotransitivitypseudotransitivity ru

11、le) rule) 若若 X X Y Y，WY Y Z Z，则则 WX X Z Z。n引理引理4.14.1 X X A A1 1 A A2 2 A Ak k 成立成立 X X A Ai i 成立。成立。 ( (i=1, 2, i=1, 2, , ,k)k)n证明：用数学归纳法证明。证明：用数学归纳法证明。 “ ”由由合并律合并律证明；证明； “”由由分解律分解律证明。证明。10A公理系统公理系统: 例例n示例：示例：R, U = A, B, C, G, H, I,R, U = A, B, C, G, H, I, F = A F = AB, AB, AC, CGC, CGH, CGH, CGI,

12、 BI, BH,H, nF F逻辑蕴涵以下函数依赖吗？逻辑蕴涵以下函数依赖吗？ A A H H？ CG CG HI HI？ AG AG I I？是是, , A AB B，B BH H 是是, , CGCGH H，CGCGI I 是是, , A AC, C, AGAGCGCG，CGCGI I传递律传递律合并率合并率增广律增广律传递律传递律11A公理系统的完备性公理系统的完备性nArmstrong公理系统是有效的公理系统是有效的、完备的。完备的。n有效性即正确性有效性即正确性：由：由F出发根据出发根据Armstrong公理推公理推导出来的每一个函数依赖一定在导出来的每一个函数依赖一定在F+中，中，

13、已经证明已经证明n完备性完备性： F+中的每一个函数依赖必定可以由中的每一个函数依赖必定可以由F出发出发根据根据Armstrong公理推导出来。公理推导出来。n要证明完备性要证明完备性，必须要计算集合，必须要计算集合F+，但这是一但这是一个个NP完全问题。比如从完全问题。比如从F=XA1,XAn出发，至少可以推导出出发，至少可以推导出2n个不同的函数依赖。个不同的函数依赖。n寻求其他办法证明寻求其他办法证明 - 先引入先引入属性集闭包。属性集闭包。12属性集的闭包属性集的闭包n示例：示例： 设属性集设属性集 U =A，B，C， 函数依赖集函数依赖集 F =AB，BC 则则 AF+ = A，B，

14、C； BF+ = B，C CF+ = CFXFXn设设F为属性集为属性集U上的一组函数依赖，上的一组函数依赖，X U， = A | XA能由能由F根据根据Armstrong公理导出公理导出 称称 为为属性集属性集X关于函数依赖集关于函数依赖集F的的闭包闭包。n 是由是由X所能函数决定的所能函数决定的全体属性全体属性的的集合集合。n定义定义4.13 属性集的闭包属性集的闭包.FXFXFX13属性集闭包引理属性集闭包引理n引理引理4.2 XY能从能从F出发由出发由A公理导出公理导出 Y FXFXn注意：注意：引理引理4.2给出了判断一个函数依赖给出了判断一个函数依赖XY能否能否从从F出发由出发由A

15、公理导出公理导出的方法的方法，即判，即判断是否有断是否有Y n例：例：设设U =A，B，C，F =AB，BC要判断函数依赖要判断函数依赖AC是否成立，只要判断是是否成立，只要判断是否有否有C AF+，而而AF+ =A，B，C，故故AC 成立。成立。14A公理系统公理系统: 完备性的证明完备性的证明n定理定理4.24.2 Armstrong Armstrong公理是有效的、完备的。公理是有效的、完备的。n证明：证明：n有效性的证明，见定理有效性的证明，见定理4.14.1的证明。的证明。n完备性的证明。完备性的证明。n完备性的证明是构造性的证明。完备性的证明是构造性的证明。n证明完备性的逆否命题：

16、若证明完备性的逆否命题：若函数依赖函数依赖XYXY不能由不能由F F出发从出发从公理推导出来，那么它必然公理推导出来，那么它必然不为不为F F所蕴涵所蕴涵( ( 即即XYXY不属于不属于F F+ + ) )，证明略证明略。15闭包闭包F F+ +的计算的计算-计算属性集闭包计算属性集闭包n公理的有效性和完备性说明了公理的有效性和完备性说明了“导出导出”与与“蕴蕴涵涵”是两个是两个完全等价完全等价的概念的概念: : X XY Y为为F F所蕴涵所蕴涵( (即即XYFXYF+ +) ) X XY Y可由可由F F出发根据出发根据ArmstrongArmstrong公理导出公理导出n即：欲判即：欲判

17、 X XYYF F+ + ? ? 再判再判 Y Y ? ?FXn由 引 理由 引 理 4 . 2 , 4 . 2 , 判 定判 定 X X Y Y 是 否 能 由是 否 能 由 F F 根 据根 据ArmstrongArmstrong公理导出，可转化为求公理导出，可转化为求 ，判定，判定Y Y 是否成立。是否成立。FXFXFX 先求出先求出16属性集闭包的计算属性集闭包的计算: 算法算法n算法算法4.1 求属性集求属性集X的闭包的闭包.Input：属性集属性集X，函数依赖集函数依赖集FOutput： := X;while ( 发生变化发生变化) dofor each 函数依赖函数依赖 AB i

18、n F dobegin if A then := BendFXFXFXFXFXFX开始开始：FX17属性集闭包的计算属性集闭包的计算: 示例示例n设设 R ，U = (A, B, C, G, H, I)， F = AB, AC, CGH, CGI, BH ， 计算计算 FAG)( 最后最后 = A,G,B,C,H,I FAG)(所用依赖所用依赖 变化变化 FAG)(初始初始 =A,GFAG)( AB A,G,B AC A,G,B,C CGH A,G,B,C,H CGI A,G,B,C,H,I 另例另例 ： = A,B,C,H FA18属性集闭包的计算属性集闭包的计算: 练习练习n设有设有 R，

19、U = (C, T, H, R, S) F = CT, HRC, HTR, HSRn计算计算 (HR)F+=n计算计算 (HS)F+ =n计算计算 HF+ =n计算计算 RF+ =n计算计算 SF+ =nHR是码吗？是码吗？nHS是码吗？是码吗？H，R，C，T H，S，R，C，T H R S 不是不是是。是。HSHSRCT是完全函数依赖是完全函数依赖19函数依赖集的等价和覆盖函数依赖集的等价和覆盖n定义定义4.14 函数依赖集函数依赖集F、G，若若F+= G+，则称则称F与与G等价等价，或者说，或者说F是是G的覆盖，的覆盖，G是是F的覆盖，的覆盖，F和和G互相覆盖。互相覆盖。n引理引理4.3

20、F+ = G+ F G+ 和和 G F+n证明证明: 略略n下面用下面用函数依赖集的等价和覆盖概念定义函函数依赖集的等价和覆盖概念定义函数依赖集的最小覆盖。数依赖集的最小覆盖。20最小函数依赖集最小函数依赖集(最小覆盖最小覆盖)n定义定义4.154.15 最小覆盖最小覆盖. . 满足下列条件的函数依赖集满足下列条件的函数依赖集F F称为最小覆盖称为最小覆盖( (最最小依赖集小依赖集, , 极小依赖集极小依赖集) )，记作，记作F Fminmin：n(1) 单属性单属性：F中任一函数依赖中任一函数依赖 XA，A必是单属必是单属性。性。n(2) 无冗余性无冗余性：F中不存在这样的函数依赖中不存在这

21、样的函数依赖X A，使得使得 F与与 F X A等价。等价。n(3) 既约性既约性：F中不存在这样的函数依赖中不存在这样的函数依赖 X A， X是多属性，在是多属性，在X中有真子集中有真子集 Z，使得使得 F 与与 F X A Z A等价。等价。n定理定理4.3 每一个函数依赖集每一个函数依赖集F都等价于一个极小函数都等价于一个极小函数依赖集依赖集Fmin n证明就是证明就是算法算法: 检查检查Fmin 应满足的三个条件应满足的三个条件。 1. 单属性单属性：逐个检查：逐个检查 F 中的各函数依赖中的各函数依赖：XY，若若Y=A1 A2 Ak ，k2，则用诸则用诸 XAi 代替代替 XY。 2

22、. 无冗余性无冗余性：逐个检查：逐个检查 F中各函数依赖中各函数依赖 XA, 判判XA是否冗余是否冗余，令，令G = F XA ，若若 A XG+ ，则则XA是冗余是冗余, 从从 F 中去掉该函数依赖。中去掉该函数依赖。 3. 既约性既约性：逐个检查：逐个检查 F 中各函数依赖中各函数依赖 XA，X是多属是多属性，设性，设 X=B1Bm, 逐个考查逐个考查 Bi , 判判 Bi 是否多余是否多余, 若若A (XBi)F+ ，则则 Bi 是冗余是冗余, 以以 (X Bi) 取代取代 X。计算最小覆盖计算最小覆盖Fmin: 算法算法22计算最小覆盖计算最小覆盖Fmin: 例例1nF = AB，BA

23、，AC，BC，求求Fmin 。nF是单属性的，既约性的，只检查冗余性。是单属性的，既约性的，只检查冗余性。n检查检查AB, G=F AB=BA, AC, BC =A, C，B A, C, AB 不冗余。不冗余。GA)(n检查检查AC,G=F AC=AB, BA, BC =A, B, C，CA, B, C, AC冗余冗余, 从从F中删中删除除AC。GA)(实际上，因为有实际上，因为有A AB B，B BC C， 从而从而 A AC C冗余冗余于是：于是： Fmin = AB，BA，BC23计算最小覆盖计算最小覆盖Fmin: 例例1(续续)nF = AB，BA，AC，BC，求求Fmin已经求出：已

24、经求出： Fmin = AB，BA，BC也可以是以下结果：也可以是以下结果：Fmin = AB，BA，ACn注意注意: 函数依赖集的最小依赖集可能不唯一。函数依赖集的最小依赖集可能不唯一。与考察的函数依赖的顺序有关。与考察的函数依赖的顺序有关。24计算最小覆盖计算最小覆盖Fmin: 例例2nF = CA，AG，CGB，BA，求求FminnF已是单属性的；已是单属性的；n判断判断CGB的既约性的既约性: = = GFCCG)(FG)( = = C, A, G, BFGCG)(FC)(B C不可去不可去FCCG)(B ， G冗余，去掉，以冗余，去掉，以C代替代替CGFGCG)(得得F = CA，A

25、G，CB，BA再去掉再去掉 CA 得，得，Fmin = AG，CB，BA25计算最小覆盖计算最小覆盖Fmin: 例例3 F = AB, BA，BC，AC，CA，求求Fmin 。n已经是单属性的已经是单属性的, 既约性的既约性的, 只检查冗余性。只检查冗余性。nBC，CA, 由传递律有由传递律有BA, BA多余多余, 从从F中删除中删除, F变为变为AB, BC, AC, CA；n有有AB，BC, 由传递律有由传递律有AC, AC多余多余, 从从F中删除中删除, F变为变为AB, BC，CA； 于是于是, Fmin = AB，BC，CA。n注意注意: 如果先检查如果先检查 BC, BA，AB,

26、由传递律有由传递律有BC, BC多余多余, 从从F中删除中删除, F变为变为AB, BA，AC，CA, 则：则： Fmin = AB，BA，AC，CA26计算最小覆盖计算最小覆盖Fmin: 练习练习n设设 F = AC, CA, BAC, DAC, BDA，n求求Fmin n检查单属性化检查单属性化 Fmin= AC, CA, BA, DC 或或 Fmin= AC, CA, BC, DA F= AC, CA, BA, BC , DA , DC ， BDA F= AC, CA, BA, BC , DA , DC n检查既约性检查既约性n检查冗余性检查冗余性27补充：候选码的求解算法补充：候选码的

27、求解算法 设关系模式设关系模式RRn(1) (1) 将将R R的所有属性分为的所有属性分为 L L、 R R、NN和和 LRLR四类，四类，并令并令X X代表代表L L、NN两类，两类，Y Y代表代表LRLR类。类。 L类类: 仅出现在仅出现在F的函数依赖左部的属性；的函数依赖左部的属性； R类类: .右右； N类类: 在在F的函数依赖左右两边都不出现的属性；的函数依赖左右两边都不出现的属性； LR类类: 都出现的属性都出现的属性 。 n(2) (2) 求属性集闭包求属性集闭包X X+ +，若若 X X+ +包含了包含了R R的全部属的全部属性则性则X X即为即为R R的唯一候选码的唯一候选码

28、, , 转转(5);(5);28候选码的求解算法候选码的求解算法(续续) (3) (3) 否则否则, , 在在Y Y中取一属性中取一属性A A，求求属性集闭包属性集闭包( (XA)XA)+ +，若，若( (XA)XA)+ +包含了包含了R R的全部属性，则转的全部属性，则转(4)(4)；否则，调换一属性反复进行这一过程，直到否则，调换一属性反复进行这一过程，直到试完所有试完所有Y Y中的属性。中的属性。 (4) (4) 如果已找出了所有的候选码，则转如果已找出了所有的候选码，则转(5)(5)；否；否则在则在Y Y中依次取中依次取2 2个、个、3 3个、个、属性，求属性，求X X与它与它们的属性

29、集闭包，直到其闭包包含们的属性集闭包，直到其闭包包含R R的全部属的全部属性。性。 (5) (5) 停止，输出结果。停止，输出结果。29候选码的求解：例候选码的求解：例1n设关系模式设关系模式R(A, B, C, D), R(A, B, C, D), 其函数依赖集：其函数依赖集： F=DB, BD, ADB, ACD F=DB, BD, ADB, ACD 求求R R的所有候选码。的所有候选码。n解解: : L L类类: : A, CA, C R R类类: : NN类类: : LR LR类类: : B, DB, Dn因为因为( (AC)AC)F F+ +=ACDB=ACDB，所以所以ACAC是是

30、R R的唯一候选的唯一候选码。码。30候选码的求解：例候选码的求解：例2n设关系模式设关系模式R(A, B, C, D, E, P), R(A, B, C, D, E, P), 其函数依赖集：其函数依赖集： F=AD, ED, DB, BCD, DCAF=AD, ED, DB, BCD, DCA 求求R R的所有候选码。的所有候选码。n解解: : L L类类: : C, E RC, E R类类: : NN类类: : P P LR LR类类: : A, B, DA, B, Dn因为因为( (CEP)CEP)F F+ +=CEPDBA=CEPDBA，所以所以CEPCEP是是R R的唯一的唯一候选码

31、。候选码。31候选码的求解：例候选码的求解：例3n设关系模式设关系模式R(S, D, I, B, O, Q), 其函数依赖集其函数依赖集: F = SD, IB, BO, OQ, QI 求求R的所有候选码。的所有候选码。n解解: L类类(S); R类类(D) ; N类类(无无) ; LR类类(I, B, O, Q) 因为因为S+=SD, 所以所以S不是不是R的候选码；的候选码； 因为因为(SI)+=SIDBOQ，所以所以SI是一个候选码；是一个候选码； 因为因为(SB)+=SBDOQI，所以所以SB也是一个候选码；也是一个候选码； 因为因为(SO)+=SODQIB，所以所以SO也是一个候选码；

32、也是一个候选码； 因为因为(SQ)+=SQDIBO，所以所以SQ也是一个候选码。也是一个候选码。*5.4 模式的分解模式的分解n5.4.1 模式分解的三个定义模式分解的三个定义n分解的目标：无损连接分解、保持函数依赖、达分解的目标：无损连接分解、保持函数依赖、达到更高级范式到更高级范式n5.4.2 分解的无损连接性和保持函数依赖性分解的无损连接性和保持函数依赖性n判别无损连接的充要条件判别无损连接的充要条件n判别分解是否保持函数依赖的方法判别分解是否保持函数依赖的方法n5.4.3 模式分解的算法模式分解的算法n转换为转换为3NF的保持函数依赖的分解的保持函数依赖的分解n转换为转换为3NF的既无

33、损连接又保持函数依赖的分解的既无损连接又保持函数依赖的分解n转换为转换为BCNF的无损连接分解的无损连接分解n达到达到4NF的具有无损连接性的分解的具有无损连接性的分解33模式的分解：两个记号模式的分解：两个记号 n定义定义5.165.16 关系模式关系模式RR的一个分解是指：的一个分解是指： = = R R1 1U, R, R2 2U, , ,R Rn nU其中其中U = U = U Ui i ，并且没有并且没有U Ui i U Uj j ， 1i 1i，j nj n， F Fi i是是F F在在U Ui i上的投影。上的投影。n定义定义5.175.17 函数依赖集合函数依赖集合F Fi i

34、 = X = XY | XY | XY Y F F+ + XY XY U Ui i ，称为称为F F在在U Ui i上的投影。上的投影。1in= =345.4.1 模式分解的三个定义模式分解的三个定义n对一个模式的对一个模式的分解是不唯一分解是不唯一的，但是的，但是分解前分解前后的两个模式应等价。后的两个模式应等价。n对对“等价等价”的概念有三种不同的定义的概念有三种不同的定义( (也称分也称分解的标准、分解的特性或分解的目标解的标准、分解的特性或分解的目标): ):1. 1. 分解具有分解具有无损连接性无损连接性( (Lossless join)Lossless join)；2. 2. 分解

35、要分解要保持函数依赖保持函数依赖( (Preserve dependency)Preserve dependency)3. 3. 分解既要保持函数依赖，又要具有无损连分解既要保持函数依赖，又要具有无损连接性。接性。35模式分解的三个定义模式分解的三个定义n按照不同的分解准则，模式所能达到的分离程按照不同的分解准则，模式所能达到的分离程度各不相同，度各不相同，各种范式就是对分离程度的测度各种范式就是对分离程度的测度。n进一步讨论进一步讨论: :n(1) “(1) “无损连接性无损连接性”和和“保持函数依赖保持函数依赖”的含的含义义? ? 如何判断如何判断? ?n(2) (2) 对不同的分解等价定

36、义，分离后的关系对不同的分解等价定义，分离后的关系模式的范式级别。模式的范式级别。n(3) (3) 如何实现分离，分解的算法。如何实现分离，分解的算法。模式分解中的问题模式分解中的问题: 有损分解有损分解R(A, B, C)ABC112221AB1122BC1221ABC112221AB(R)BC(R)AB(R)BC(R)R(A, B, C)ABC111212AB1121BC1112ABC111112211212AB(R)BC(R)AB(R)BC(R)有损分解有损分解无损分解无损分解模式分解中的问题模式分解中的问题: 不保持函数依赖不保持函数依赖ABCa1b1c1a2b1c1a3b2c2a4b

37、3c1A B, B CAa1a2a3a4Bb1b2b3Cc1c2各列值ABa1b1a2b1a3b2a4b3ACa1c1a2c1a3c2a4c1=ABCa1b1c1a2b1c1a3b2c2a4b3c1分解若插入若插入将违反将违反B B C C该分解保该分解保持持A A B B，而不保持而不保持B B C C，但是是无但是是无损分解损分解 A B a5b3a5c3a5b3c338模式分解中存在的问题模式分解中存在的问题: 例例ABa1b1a2b1a3b2a4b3BCb1c1b2c2b3c1ACa1c1a2c1a3c2a4c1BCb1c1b2c2b3c1=ABCa1b1c1a1b3c1a2b1c1a

38、2b3c1a3b2c2a4b1c1a4b3c1ABCa1b1c1a2b1c1a3b2c2a4b3c1该分解保持该分解保持B B C C，而而不保持不保持A A B, B, 且是有损分且是有损分解解该分解保该分解保持函数依持函数依赖赖, , 且是无且是无损分解损分解 B C A B B C 395.4.2 分解的无损连接性分解的无损连接性和保持函数依赖性和保持函数依赖性n如果一个分解具有无损连接性，则它能够保证如果一个分解具有无损连接性，则它能够保证不丢失信息。不丢失信息。n如果一个分解保持了函数依赖，则它可以减轻如果一个分解保持了函数依赖，则它可以减轻或解决各种异常情况。或解决各种异常情况。n

39、分解具有无损连接性和分解保持函数依赖是两分解具有无损连接性和分解保持函数依赖是两个互相独立的标准个互相独立的标准。具有无损连接性的分解不。具有无损连接性的分解不一定能够保持函数依赖。同样，保持函数依赖一定能够保持函数依赖。同样，保持函数依赖的分解也不一定具有无损连接性。的分解也不一定具有无损连接性。40分解的无损连接性定义分解的无损连接性定义n定义记号定义记号 mm ( r)( r)关系模式关系模式 R ，U = Ui ， =R1,R2, ,Rn是是R的一个分解，的一个分解，r 是是R的一个关系的一个关系, 定义：定义： m (r) = Ri(r) 是是r在在中各关系模式上投影的连接。这里，中

40、各关系模式上投影的连接。这里， Ri(r) =tUi|trn定义定义4.184.18 R(U, F) R(U, F)的一个分解的一个分解 是是无损连接分解：无损连接分解：r = mr = m (r) (r) 。ni1=1in= =41判无损连接性的方法判无损连接性的方法(chasechase过程过程) nP189.P189. 算法算法6.2 6.2 判别一个分解的无损连接性。判别一个分解的无损连接性。nP124P124. . 定理定理4.74.7 无损连接分解的充分必要条件无损连接分解的充分必要条件( (chasechase过程过程) ) 。n方法：构造一个表格，根据函数依赖变化表方法：构造一

41、个表格，根据函数依赖变化表格，能够变出一行全为格，能够变出一行全为a a，则是无损连接。则是无损连接。n用例子说明。用例子说明。n例例5:5: 设设 U=A, B, C, D, E, U=A, B, C, D, E, F=AB F=ABC, CC, CD, DD, DEE =(A, B, C), (C, D), (D, E) =(A, B, C), (C, D), (D, E) 是无损分解。是无损分解。ABCDEABCa1a2a3a4b15CDb21b22a3a4b25DEb31b32b33a4a5考察考察C CD DABCDEABCa1a2a3a4a5CDb21b22a3a4a5DEb31b

42、32b33a4a5考察考察D DE EABCDEABCa1a2a3b14b15CDb21b22a3a4b25DEb31b32b33a4a5ABCDEABCa1a2a3b14b15CDb21b22a3a4b25DEb31b32b33a4a5考察考察ABABC C制作制作5 5列列3 3行的表行的表 例例5：U=A, B, C, D, E, F=ABC, CD, DE =(A, B, C), (C, D), (D, E) 是无损分解。是无损分解。判无损连接分解判无损连接分解chasechase过程过程: 示例示例n设设 U=A, B, C, D, E, F=AC, BC, CD,DEC ,CEA

43、=(A, D), (A, B), (B, E), (C, D, E), (A, E) 是无损连接分解。是无损连接分解。ABCDEADa1b12b13a4b15ABa1a2b23b24b25BEb31a2b33b34a5CDEb41b42a3a4a5AEa1b52b53b54a5考察考察A AC CABCDEADa1b12b13a4b15ABa1a2b13b24b25BEb31a2b33b34a5CDE b41b42a3a4a5AEa1b52b13b54a5制作制作5 5列列5 5行的表行的表下页下页44判无损连接分解判无损连接分解chasechase过程过程: 示例示例2续续考察考察B BC

44、CABCDEADa1b12b13a4b15ABa1a2b13b24b25BEb31a2b13b34a5CDEb41b42a3a4a5AEa1b52b13b54a5考察考察C CD DABCDEADa1b12b13a4b15ABa1a2b13a4b25BEb31a2b13a4a5CDEb41b42a3a4a5AEa1b52b13a4a5F=AC, BC, CD,DEC ,CEA是无损连接分解是无损连接分解上页上页下页下页45判无损连接分解判无损连接分解chasechase过程过程: 示例示例2续续考察考察DEDEC CABCDEADa1b12b13a4b15ABa1a2b13a4b25BEb31

45、a2a3a4a5CDEb41b42a3a4a5AEa1b52a3a4a5考察考察CECEA AABCDEADa1b12b13a4b15ABa1a2b13a4b25BEa1a2a3a4a5CDEa1b42a3a4a5AEa1b52a3a4a5F=AC, BC, CD,DEC ,CEA是无损连接分解是无损连接分解上页上页46判无损连接分解判无损连接分解chasechase过程过程: 练习练习n设关系模式设关系模式R(A, B, C, D), FR(A, B, C, D), F是是R R上成立的上成立的FDFD集集, , F=AB, CD , DBF=AB, CD , DB 分解分解=AD=AD，B

46、CBC，BDBD。 问：问：相对于相对于F F是否无损连接分解是否无损连接分解?(?(需画出需画出chasechase过程的示意图过程的示意图) )n答案：不是答案：不是无损连接分解。无损连接分解。n大家现场练习一下大家现场练习一下, ,判断其结果。判断其结果。分解为两个关系模式的无损连接性判别分解为两个关系模式的无损连接性判别n定理定理4.54.5. . 关 系 模 式关 系 模 式 RR 的 分 解的 分 解 = = R R1 1 U , , R R2 2U，则则 是是一个无损连接分解的充要条件是一个无损连接分解的充要条件是 U U1 1UU2 2U U1 1 U U2 2 或或 U U1

47、 1UU2 2U U2 2 U U1 1 成立。成立。n注注: : 对于定理对于定理4.54.5，有的课本上是这样叙述：，有的课本上是这样叙述：P124P124 如果如果R R有一个分解有一个分解=R=R1 1, R, R2 2, , 则分解则分解具有无损连接具有无损连接的充分必要条件为：的充分必要条件为： R R1 1RR2 2(R(R1 1-R-R2 2) ) 或或 R R1 1RR2 2(R(R2 2-R-R1 1) ) 成立。成立。48分解为两个关系模式的无损连接分解为两个关系模式的无损连接: 例例n例：设例：设R, U=A, B, C, F=AR, U=A, B, C, F=AB,

48、B, 1. 1. 1 1 = R= R1 1(A, B), R(A, B), R2 2(A, C)(A, C) 则则 R R1 1RR2 2 = A, R = A, R1 1R R2 2 = B = B 由由 A A B B ，得到得到 1 1是无损连接分解。是无损连接分解。 2. 2. 2 2 = = R R1 1(A, B), R(A, B), R2 2(B, C)(B, C) 则则 R R1 1RR2 2 = B, R = B, R1 1R R2 2 = A, R = A, R2 2R R1 1 = C = C 由于由于B BA, BA, BC C均不成立，所以均不成立，所以 2 2不是

49、无损连不是无损连接分解。接分解。49分解为两个关系模式的无损连接分解为两个关系模式的无损连接: 练习练习n设关系模式设关系模式R(AR(A，B B，C C，D D，E E，P)P)，F F是是R R上成上成立的立的FDFD集，集，F=ABF=AB，CPCP，EAEA，CEDCED。设有分解：设有分解： =R1(A =R1(A，B B，E)E)，R2(CR2(C，D D，E E，P)P) 判断分解判断分解是否无损连接分解。是否无损连接分解。n解：因为解：因为 R R1 1RR2 2 = E = E， R R1 1R R2 2 = AB = AB，而而 E EA A和和E EB B均成立均成立(

50、即即 R1R2 R1R2成立成立) ，所，所以以 是无损连接分解。是无损连接分解。50n定义定义4.19 保持函数依赖的模式分解。保持函数依赖的模式分解。 设设Z是是U的子集，函数依赖集合的子集，函数依赖集合F在在Z上的投影上的投影定义为：定义为：Z(F) = XY | XY F+ XY Z 设设 = R1,R2,Rn 是关系模式是关系模式R的一个分解，的一个分解，如果如果 F+= ( Ri (F)+ ，则称则称 是保持函数依赖的分解。是保持函数依赖的分解。保持函数依赖的分解定义保持函数依赖的分解定义 n i =151保持函数依赖的分解保持函数依赖的分解: 例例n例：设关系模式例：设关系模式R

51、，U = C, S, Z, F = CS Z, Z C， = R1(S, Z), R2(C, Z) nR1R2 = Z, R2R1 = C R1R2 R2R1 ( 即即 Z C) 分解是无损的。分解是无损的。nR1(F) = ， R2(F) = Z C R1 (F) R2 (F) = Z C 丢失了函数依赖丢失了函数依赖 CS Z, 分解不保持函数依赖分解不保持函数依赖52保持函数依赖的分解保持函数依赖的分解: 判别法判别法n如何判断分解保持函数依赖？如何判断分解保持函数依赖？n引理引理4.3 给出了判别一个分解给出了判别一个分解是否保持函数依赖的方是否保持函数依赖的方法法 - FD集的覆盖集

52、的覆盖n例如，对于例如，对于(A, B, C)，AB , BC的分解的分解 ，显然显然, 丢失了函数依赖丢失了函数依赖: BCF+= ( Ri (F)+ n i =1534.4.3 关系模式分解的算法关系模式分解的算法n关于模式分解的几个关于模式分解的几个重要事实重要事实:.n(1) 若要求分解保持函数依赖，则分解可以若要求分解保持函数依赖，则分解可以达到达到3NF，但不一定能达到但不一定能达到BCNF。n(2) 若要求分解既保持函数依赖若要求分解既保持函数依赖, 又具有无损又具有无损连接连接, 则可以达到则可以达到3NF, 但不一定能达到但不一定能达到BCNF。n(3) 若只要求分解无损连接

53、性若只要求分解无损连接性, 那一定可以达那一定可以达到到4NF。54关系模式分解的算法关系模式分解的算法nP191P191. . 算法算法6.36.3 ( (合成法合成法) ) 转换为转换为3 3NFNF的保持函的保持函数依赖的分解。数依赖的分解。nP191P191. . 算法算法6.46.4 转换为转换为3 3NFNF既有无损连接性又既有无损连接性又保持函数依赖的分解。保持函数依赖的分解。nP192P192. . 算法算法6.56.5 转换为转换为BCNFBCNF的无损连接分解的无损连接分解( (分解法分解法) )。nP192P192. . 算法算法6.66.6 达到达到4 4NFNF的具有无损连接性的的具有无损连接性的分解分解n后面用例说明。后面用例说明。55达到达到3NF保持依赖的分解保持依赖的分解: 例例1n设设 U=S#，SD，MN，C#，G F=S