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

关系模式的分解与函数依赖关系的判断 （在读此文章时须认真细心读懂每一行每一个细节） 关于无损分解和保持依赖的判断，是系分和数工考试中每年基本上都会考的题，而且绝大部分是对一个关系模式分解成两个模式的考察，分解为三个以上模式时无损分解和保持依赖的判断比较复杂，考的可能性不大，因此我们只对“一个关系模式分解成两个模式”这种类型的题的相关判断做一个总结。以下的论述都基于这样一个前提：R是具有函数依赖集F的关系模式，（R1 ，R2）是R的一个分解。首先我们给出一个看似无关却非常重要的概念：属性集的闭包。令α为一属性集。我们称在函数依赖集F下由α函数确定的所有属性的集合为F下α的闭包，记为α+ 。下面给出一个计算α+的算法，该算法的输入是函数依赖集F和属性集α，输出存储在变量result中。算法一：result=α;while(result发生变化)do? ? for each 函数依赖β→γ in F do? ? begin? ?? ???if βresult then result=(result∪γ);? ? end(此算法是要算出α属性α→β、β→γ、β→δ、δ→θ，此算法能算出属性为：{α、β、γ、β、δ、θ}) 属性集闭包的计算有以下两个常用用途：·判断α是否为超码 : 通过计算α+（α在F下的闭包），看α+ 是否包含了R中的所有属性。若是，则α为R的超码。·通过检验是否βα+，来验证函数依赖是否成立。也就是说，用属性闭包计算α+，看它是否包含β。（请原谅我用符号来表示两个集合之间的包含关系，那个表示包含的符号我找不到，大家知道是什么意思就行了。）看一个例子吧，2005年11月系分上午37题：● 给定关系R(A1，A2，A3，A4)上的函数依赖集F={A1→A2，A3→A2，A2→A3，A2→A4}，R的候选关键字为________。（37）A. A1 　B. A1A3 　C. A1A3A4 　D. A1A2A3首先我们按照上面的算法计算A1+ 。result=A1，由于A1→A2，A1result，所以result=resultA2=A1A2由于A2→A3，A2result，所以result=resultA3=A1A2A3由于A2→A4，A2result，所以result=resultA4=A1A2A3A4由于A3→A2，A3result，所以result=resultA2=A1A2A3A4通过计算我们看到，A1+ =result={A1A2A3A4}，所以A1是R的超码，理所当然是R的候选关键字。此题选A 。好了，有了前面的铺垫，我们进入正题。无损分解的判断。如果R1R2是R1或R2的超码，则R上的分解（R1，R2）是无损分解。这是一个充分条件，当所有的约束都是函数依赖时它才是必要条件（例如多值依赖就是一种非函数依赖的约束），不过这已经足够了。保持依赖的判断。如果F上的函数依赖都在其分解后的一个关系函数依赖上成立，则这个分解是保持依赖的（这是一个充分条件）函数依赖如果上述判断失败，并不能断言分解不是保持依赖的，还要使用下面的通用方法来做进一步判断。该方法的表述如下：算法二：对F上的每一个α→β使用下面的过程：result=α;result=α中的α与 α→β中的α是同一个αwhile(result发生变化)do? ? for each 分解后的Ri? ?? ???t=((resultRi)+) ∩Ri //“(result∩Ri)+”表示”result∩Ri”的闭包(即在此处调算法一计算出”result∩Ri”的闭包值)? ?? ???result=result∪t这里的属性闭包是在函数依赖集F下计算出来的。如果result中包含了β的所有属性，则函数依赖α→β。分解是保持依赖的当且仅当上述过程中F的所有依赖都被保持。下面给出一个例题，2006年5月系分上午43题：●设关系模式RU, F，其中U=｛A, B, C, D, E｝，F＝{A→BC，C→D，BC→E，E→A｝，则分解ρ={R1（ABCE），R2（CD）｝满足 （43） 。（43） A．具有无损连接性、保持函数依赖? ?? ?? ?? ? B．不具有无损连接性、保持函数依赖? ?? ?? ?? ? C．具有无损连接性、不保持函数依赖? ?? ?? ?? ? D．不具有无损连接性、不保持函数依赖先做无损链接的判断。R1R2={C}，计算C+。Result=C由于C→D，Cresult，所以result=resultD=CD可见C是R2的超码，该分解是一个无损分解。再做保持依赖的判断。A→BC，BC→E， E→A都在