RiKeR

本博客停止更新,最新内容请访问--> http://blog.csdn.net/shuailee

统计

留言簿(3)

积分与排名

阅读排行榜

评论排行榜

无损分解和保持依赖的判断

大部分是对一个关系模式分解成两个模式的考察,分解为三个以上模式时无损分解和保持依赖的判断比较复杂,考的可能性不大,因此我们只对“一个关系模式分解成两个模式”这种类型的题的相关判断做一个总结。

以下的论述都基于这样一个前提:
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,A1∈result,所以result=result∪A2=A1A2
由于A2→A3,A2∈result,所以result=result∪A3=A1A2A3
由于A2→A4,A2∈result,所以result=result∪A3=A1A2A3A4
由于A3→A2,A3∈result,所以result=result∪A2=A1A2A3A4

通过计算我们看到,A1+ =result={A1A2A3A4},所以A1是R的超码,理所当然是R的候选关键字。此题选A 。


好了,有了前面的铺垫,我们进入正题。

无损分解的判断
如果R1∩R2是R1或R2的超码,则R上的分解(R1,R2)是无损分解。这是一个充分条件,当所有的约束都是函数依赖时它才是必要条件(例如多值依赖就是一种非函数依赖的约束),不过这已经足够了。

保持依赖的判断
如果F上的每一个函数依赖都在其分解后的某一个关系上成立,则这个分解是保持依赖的(这是一个充分条件)。
如果上述判断失败,并不能断言分解不是保持依赖的,还要使用下面的通用方法来做进一步判断。
该方法的表述如下:
算法二:
对F上的每一个α→β使用下面的过程:
result:=α;
while(result发生变化)do
    for each 分解后的Ri
        t=(result∩Ri)+ ∩Ri
        result=result∪t

这里的属性闭包是在函数依赖集F下计算出来的。如果result中包含了β的所有属性,则函数依赖α→β。分解是保持依赖的当且仅当上述过程中F的所有依赖都被保持。


下面给出一个例题,2006年5月系分上午43题:

●设关系模式R<U, 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.不具有无损连接性、不保持函数依赖

先做无损链接的判断。R1∩R2={C},计算C+。
Result=C
由于C→D,C∈result,所以result=result∪D=CD
可见C是R2的超码,该分解是一个无损分解。

再做保持依赖的判断。
A→BC,BC→E, E→A都在R1上成立(也就是说每一个函数依赖左右两边的属性都在R1中),C→D在R2上成立,因此给分解是保持依赖的。

选A。


再看一个复杂点的例题。2007年5月数工40-41题。

●给定关系模式R<U, F>,U={A, B, C, D, E},F={B→A,D→A,A→E,AC→B},其候选关键字为
(40)  ,则分解ρ={R1(ABCE),R2(CD)}满足 (41) 。
(40) A.ABD
              B.ABE
              C.ACD
              D.CD
(41) A.具有无损连接性、保持函数依赖
              B.不具有无损连接性、保持函数依赖
              C.具有无损连接性、不保持函数依赖
              D.不具有无损连接性、不保持函数依赖

看见了吧,和前面一题多么的相像!
对于第一问,分别计算ABCD四个选项的闭包,
(ABD)+ = { ABDE }
(ABE)+ = { ABE }
(ACD)+ = { ABCDE }
(CD)+ = { ABCDE }
选D。

再看第二问。
先做无损链接的判断。R1∩R2={C},计算C+。
result=C
因此C既不是R1也不是R2的超码,该分解不具有无损分解性。

再做保持依赖的判断。
B→A,A→E,AC→B在R1上成立,D→A在R1和R2上都不成立,因此需做进一步判断。
由于B→A,A→E,AC→B都是被保持的(因为它们的元素都在R1中),因此我们要判断的是D→A是不是也被保持。

对于D→A应用算法二:
result=D
对R1,result∩R1=ф(空集,找不到空集的符号,就用这个表示吧),t=ф,result=D
再对R2,result∩R2=D,D+ =ADE ,t=D+ ∩R2=D,result=D
一个循环后result未发生变化,因此最后result=D,并未包含A,所以D→A未被保持,该分解不是保持依赖的。

选D。

posted on 2007-10-18 00:53 RiKeR 阅读(17813) 评论(17)  编辑  收藏

评论

# re: 无损分解和保持依赖的判断 2007-11-24 13:04 star

看书太抽象了,这个帖子不错,理解了,感谢  回复  更多评论   

# re: 无损分解和保持依赖的判断 2007-12-29 01:22

不错啊
  回复  更多评论   

# re: 无损分解和保持依赖的判断 2008-01-21 12:06 Danielsym

下午就考数据库了,这篇帖子真是雪中送炭哪!  回复  更多评论   

# re: 无损分解和保持依赖的判断 2008-01-24 23:42 good

good
  回复  更多评论   

# re: 无损分解和保持依赖的判断 2008-05-03 16:04 dbs

不错!这贴讲得很透彻  回复  更多评论   

# re: 无损分解和保持依赖的判断 2009-04-26 16:00 HHK

不错.谢谢作者.  回复  更多评论   

# re: 无损分解和保持依赖的判断[未登录] 2009-05-10 18:17 浪子

受益匪浅!  回复  更多评论   

# re: 无损分解和保持依赖的判断 2009-05-21 15:58 SimonKing

最后的D-A判断不是很明白,后天就考试了,这帖子不错。  回复  更多评论   

# re: 无损分解和保持依赖的判断 2009-06-22 15:22 和加快

谢谢  回复  更多评论   

# re: 无损分解和保持依赖的判断[未登录] 2011-01-08 23:01 OK

非常感谢!现在的课本真的太抽象了。。。  回复  更多评论   

# re: 无损分解和保持依赖的判断 2011-01-09 17:23 guy

@OK
你是华农吧  回复  更多评论   

# re: 无损分解和保持依赖的判断[未登录] 2011-05-15 20:04 ice

nice  回复  更多评论   

# re: 无损分解和保持依赖的判断[未登录] 2012-05-09 17:01 Roy

(ACD)+ = { ABCDE }
(CD)+ = { ABCDE }
选D。

2者都是超码,为什么选D呢  回复  更多评论   

# re: 无损分解和保持依赖的判断[未登录] 2014-06-12 23:57 JOJO

因为ACD虽然是超码,但是去掉属性A它仍然是超码,所以它不是候选码,看候选码的定义就知道了@Roy
  回复  更多评论   

# re: 无损分解和保持依赖的判断 2014-12-04 11:53 。。。

讲的太好了,看完立刻懂  回复  更多评论   

# re: 无损分解和保持依赖的判断 2015-06-30 00:12 111111111

谢谢了  回复  更多评论   

# re: 无损分解和保持依赖的判断 2015-08-29 17:48 ghost

相当感谢!!!!Orz....  回复  更多评论   


只有注册用户登录后才能发表评论。


网站导航: