闫森
文章2
标签4
分类2
模式分解是否保持函数依赖的判断方法以及例子

模式分解是否保持函数依赖的判断方法以及例子

保持依赖的判断: 如果F上的每一个函数依赖都在其分解后的某一个关系上成立,则这个分解是保持依赖的(充分条件)。 如果上述判断失败,并不能断言分解不是保持依赖的,因为上面只是充分条件,还要使用下面的通用方法来做进一步判断。

对F上的每一个α→β使用下面的过程:

result:=α; 
while(result发生变化)do 
for each 分解后的Ri 
t=(result∩Ri)+ ∩Ri 
result=result∪t

例题1

考虑关系模式R(A,B,C,D)分解{R1(A,B),R2(BC),R3(C,D)},
函数依赖集F={A→B,B→C,C→D,D→A}显然,AB包含于R1,BC包含于R2,CD包含于R3。
因此,只需要验证是否有D→A呗分解p所保持。为此,我们使用算法。首先,result={D}进入 repeat循环,
当i=1时不改变,因为{D}U(({D}∩{A,B})+∩{A,B})仍是{D}。同样方法,当i=2时Z不变。
然而,i=3时,我们得到result={D}U(({D}∩{C,D})+∩{C,D}={D}U({D}+∩{C,D})={D}U({A,B,C,D}∩{C,D})={C,D}再次执行 repeat的循环体,
当i=2时产生result={B,C,D}而第三遍,当i=1时置result为{A,B,C,D}。
此后,T不再改变。这样,result={A,B,C,D}它包含A,因此,D→A被分解所保持。从而是保持函数依赖的分解。

例题2

已知R<U,F>,U={A,B,C,D,E},F={A→C,B→C,C→D,DE→C,CE→A},
R的一个分解为R1(AD),R2(AB),R3(BE),R4(CDE),R5(AE),判断这个分解是否具有函数依赖性。
先看F中每一个函数依赖,R4有C->D,DE->C。A->C,B->C,CE->A。这三个函数依赖分解模式里均未能覆盖。
开始使用算法进行检测:
首先对于A->C,result = A,(A)+ = ACD ,T=AD,result=AD,result改变,进入下一个循环:
result = AD,(ABD)+ = ABCD ,t=AB,result=ABD。
result改变:result = ABD, (ABD)+ = ABCDE, t=BE,result=ABDE。
result改变:result = ABDE,(ABCD)+=ABCDE,t=CDE,result=ABCDE。
result改变:(从这一步就能看出来,保持了函数依赖了,因为已经包含C了)result = ABCDE,(ABCDE)+=ABCDE,t=AE,result=ABCDE。
result未改变。退出循环。、由于result=ABCDE,包含了C,所以分解保持函数依赖。

More info: 见我CSDN博客