资源描述：
《既具有无损连接性又保持函数依赖的分解算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、求最小函数依赖集分三步:1.将F中的所有依赖右边化为单一元素此题fd={abd->e,ab->g,b->f,c->j,cj->i,g->h};已经满足2.去掉F中的所有依赖左边的冗余属性.作法是属性中去掉其中的一个,看看是否依然可以推导此题:abd->e,去掉a,则(bd)+不含e,故不能去掉,同理b,d都不是冗余属性ab->g,也没有cj->i,因为c+={c,j,i}其中包含i所以j是冗余的.cj->i将成为c->iF={abd->e,ab->g,b->f,c->j,c->i,g->h};3.去掉F中所有冗余依赖关系.做法为从F中去掉某关系,如去
2、掉(X->Y),然后在F中求X+,如果Y在X+中,则表明x->是多余的.需要去掉.此题如果F去掉abd->e,F将等于{ab->g,b->f,c->j,c->i,g->h},而(abd)+={a,d,b,f,g,h},其中不包含e.所有不是多余的.同理(ab)+={a,b,f}也不包含g,故不是多余的.b+={b}不多余,c+={c,i}不多余c->i,g->h多不能去掉.所以所求最小函数依赖集为F={abd->e,ab->g,b->f,c->j,c->i,g->h};转换为3NF既具有无损连接性又保持函数依赖的分解算法：第一步：首先用算法1求出R的
3、保持函数依赖的3NF分解，设为q={R1,R2,…,Rk}（这步完成后分解已经是保持函数依赖，但不一定具有保持无损连接）第二步：设X是R的码，求出p=q{R(X)}第三步：若X是q中某个Ri的子集，则在p中去掉R(X)第四步：得到的p就是最终结果例题：R(S#,SN,P,C,S,Z)F={S#→SN,S#→P,S#→C,S#→S,S#→Z,{P,C,S}→Z,Z→P,Z→C}·第一步:求出最小FD集：F={S#→SN,S#→P,S#→C,S#→S,{P,C,S→Z,Z→P,Z→C}//S#→Z冗余，FD：最小函数依赖按具有相同左部分组：q={R1(S
4、#,SN,P,C,S),R2(P,C,S,Z),R3(Z,P,C)}R3是R2的子集，所以去掉R3q={R1(S#,SN,P,C,S),R2(P,C,S,Z)}·第二步:R的主码为S＃，于是p=q{R(X)}={R1(S#,SN,P,C,S),R2(P,C,S,Z),R(S#)}·第三步:因为{S＃}是R1的子集，所以从p中去掉R(S#)·第四步:p={R1(S#,SN,P,C,S),R2(P,C,S,Z)}即最终结果判别一个分解的无损连接性举例2：已知R，U={A,B,C,D,E}，F={A→C,B→C,C→D,DE→C,CE→A}，R的
5、一个分解为R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)，判断这个分解是否具有无损连接性。解：用判断无损连接的算法来解。①构造一个初始的二维表，若“属性”属于“模式”中的属性，则填aj，否则填bij。②根据A→C，对上表进行处理，由于属性列A上第1、2、5行相同均为a1，所以将属性列C上的b13、b23、b53改为同一个符号b13（取行号最小值）。③根据B→C，对上表进行处理，由于属性列B上第2、3行相同均为a2，所以将属性列C上的b13、b33改为同一个符号b13（取行号最小值）。④根据C→D，对上表进行处理，由于属性列C上
6、第1、2、3、5行相同均为b13，所以将属性列D上的值均改为同一个符号a4。⑤根据DE→C，对上表进行处理，由于属性列DE上第3、4、5行相同均为a4a5，所以将属性列C上的值均改为同一个符号a3。⑥根据CE→A，对上表进行处理，由于属性列CE上第3、4、5行相同均为a3a5，所以将属性列A上的值均改为同一个符号a1。⑦通过上述的修改，使第三行成为a1a2a3a4a5，则算法终止。且分解具有无损连接性。求属性集合X关于函数依赖集F的闭包X+【算法5.1】 计算属性集Ｘ关于Ｆ的闭包Ｘ＋。输入：属性集Ｘ为Ｕ的子集，函数依赖集Ｆ。输出：Ｘ＋。步骤：(1)置
7、初始值A=ф，A*=X；(2)如果A≠A*，置A=A*，否则转(4)；(3)A*，置A*=A*∪Z。全部搜索完,转(2)；Í依次检查F中的每一个函数依赖Y→Z，若Y(4)输出A*，即为X+。【例】 已知关系模式R(A,B,C,D,E)，F={AB→C,B→D,C→E,EC→B,AC→B}是函数依赖集，求(AB)+。依算法2.1解：(1)置初始值A=ф，A*=AB；(2)因A≠A*，置A=AB；(3)第一次扫描F，找到AB→C和B→D，其左部ÍAB，故置A*=ABCD。搜索完,转(2)；(2)因A≠A*，置A=ABCD；(3)第二次扫描F，找到C→E和
8、AC→B，其左部ÍABCD，故置A*=ABCDE。搜索完,转(2)；(2)因A≠A*，置A=ABCDE；(3
