关系模式的分解与函数依赖关系的判断

1、关系模式的分解与函数依赖关系的判断（在读此文章时须认真细心读懂每一行每一个细节）关于无损分解和保持依赖的判断，是系分和数工考试中每年基本上都会考的题，而且绝大部分是对一个关系模式分解成两个模式的考察，分解为三个以上模式时无损分解和保持依赖的判断比较复杂，考的可能性不大，因此我们只对“一个关系模式分解成两个模式”这种类型的题的相关判断做一个总结。以下的论述都基于这样一个前提：R是具有函数依赖集F的关系模式，（R1 ，R2）是R的一个分解。首先我们给出一个看似无关却非常重要的概念：属性集的闭包。令为一属性集。我们称在函数依赖集F下由函数确定的所有属性的集合为F下的闭包，记为+ 。下面给出一个计算+

2、的算法，该算法的输入是函数依赖集F和属性集，输出存储在变量result中。算法一：result=;while(result发生变化)do for each 函数依赖 in F do begin if result then result=(result); end(此算法是要算出属性所能决定的所有属性是那些，包括传递依赖的属性，如主键所能决定的是整个表的所有属性。例如、，此算法能算出属性为：、)属性集闭包的计算有以下两个常用用途：判断是否为超码 : 通过计算+（在F下的闭包），看+ 是否包含了R中的所有属性。若是，则为R的超码。通过检验是否+，来验证函数依赖是否成立。也就是说，用属性闭包计算+

3、，看它是否包含。（请原谅我用符号来表示两个集合之间的包含关系，那个表示包含的符号我找不到，大家知道是什么意思就行了。）看一个例子吧，2005年11月系分上午37题： 给定关系R(A1，A2，A3，A4)上的函数依赖集F=A1A2，A3A2，A2A3，A2A4，R的候选关键字为_。（37）A. A1 B. A1A3 C. A1A3A4 D. A1A2A3首先我们按照上面的算法计算A1+ 。result=A1，由于A1A2，A1result，所以result=resultA2=A1A2由于A2A3，A2result，所以result=resultA3=A1A2A3由于A2A4，A2result，所

4、以result=resultA4=A1A2A3A4由于A3A2，A3result，所以result=resultA2=A1A2A3A4通过计算我们看到，A1+ =result=A1A2A3A4，所以A1是R的超码，理所当然是R的候选关键字。此题选A 。好了，有了前面的铺垫，我们进入正题。无损分解的判断。如果R1R2是R1或R2的超码，则R上的分解（R1，R2）是无损分解。这是一个充分条件，当所有的约束都是函数依赖时它才是必要条件（例如多值依赖就是一种非函数依赖的约束），不过这已经足够了。保持依赖的判断。如果F上的无论那个函数依赖都能在其分解后的若干个关系中找到一个关系，并且该函数依赖在此关系上

5、成立，则这个分解是保持依赖的（这是一个充分条件），即F上全部函数依赖都能在分解后的关系上成立。如果上述判断失败，并不能断言分解不是保持依赖的，还要使用下面的通用方法来做进一步判断。该方法的表述如下：算法二：对F上的每一个使用下面的过程：result=; /此行result=中的与 中的是同一个while(result发生变化)do for each 分解后的Ri t=(resultRi)+) Ri /“(resultRi)+”表示”resultRi”的闭包(即在此处调算法一计算出”resultRi”的闭包值) result=resultt这里的属性闭包是在函数依赖集F下计算出来的。如果resu

6、lt中包含了的所有属性，则函数依赖。分解是保持依赖的当且仅当上述过程中F的所有依赖都被保持。下面给出一个例题，2006年5月系分上午43题：设关系模式R，其中U=A, B, C, D, E，FABC，CD，BCE，EA，则分解=R1（ABCE），R2（CD）满足 （43） 。（43） A具有无损连接性、保持函数依赖 B不具有无损连接性、保持函数依赖 C具有无损连接性、不保持函数依赖 D不具有无损连接性、不保持函数依赖先做无损链接的判断。R1R2=C，计算C+。Result=C由于CD，Cresult，所以result=resultD=CD可见C是R2的超码，该分解是一个无损分解。再做保持依赖的

7、判断。ABC，BCE， EA都在R1上成立（也就是说每一个函数依赖左右两边的属性都在R1中），CD在R2上成立，因此给分解是保持依赖的。选A。再看一个复杂点的例题。2007年5月数工40-41题。给定关系模式R，U=A, B, C, D, E，FBA，DA，AE，ACB，其候选关键字为 （40），则分解=R1（ABCE），R2（CD）满足 （41） 。（40） AABD BABE CACD DCD（41） A具有无损连接性、保持函数依赖 B不具有无损连接性、保持函数依赖 C具有无损连接性、不保持函数依赖 D不具有无损连接性、不保持函数依赖看见了吧，和前面一题多么的相像！对于第一问，分别计算AB

8、CD四个选项的闭包，（ABD）+ = ABDE （ABE）+ = ABE （ACD）+ = ABCDE （CD）+ = ABCDE 选D。再看第二问。先做无损链接的判断。R1R2=C，计算C+。result=C因此C既不是R1也不是R2的超码，该分解不具有无损分解性。再做保持依赖的判断。BA，AE，ACB在R1上成立，DA在R1和R2上都不成立，因此需做进一步判断。由于BA，AE都是被保持的（因为它们的元素都在R1中），因此我们要判断的是DA，ACB是不是也被保持。对于DA应用算法二：result=D对R1，resultR1=（空集，找不到空集的符号，就用这个表示吧），t=，result=D再

9、对R2，resultR2=D，D+ =ADE ，t=D+ R2=D (D+ =ADE表示resultR2的闭包值为ADE,用算法一计算得到)一个循环后result未发生变化，因此最后result=D，并未包含A，所以DA未被保持，该分解不是保持依赖的。选D。在以下给定的关系模式分解中，DA的依赖是保持下来的：给定关系模式R，U=A, B, C, D, E,h，FBA，DA，AE，ACB,dh,hb，则分解=R1（ABCE），R2（CDh）,(abh)原因是：DH，HB，BA，所以DA成立。总结：函数依赖：u X Y、YZ ， ” 符号左右两边的属性X、Y必须在同一个关系中X与Y的依赖关系才能成立，Y与Z必需在同一个关系中Y与Z的依赖关系才能成立，但X与Z却可以不必在同一个关系中，函数的传递依赖关