数据库必考·····求最小函数依赖集分三步:、判别一个分解的无损连接性、转换为3NF既具有无损连接性又保持函数依赖的分解算法
4星 · 超过85%的资源 需积分: 33 80 浏览量
2009-12-25
21:15:57
上传
评论 5
收藏 89KB DOC 举报 
求最小函数依赖集分三步:
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->i
F={abd->e,ab->g,b->f,c->j,c->i,g->h};
3.去掉F中所有冗余依赖关系.
做法为从F中去掉某关系,如去掉(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的保持函数依赖的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#,SN,P,C,S), R2(P,C,S,Z), R3(Z,P,C)}
R3是R2的子集，所以去掉R3
q={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,F>，U={A,B,C,D,E}，F={A→C,B→C,C→D,DE→C,CE→A}，R 的
一个分解为 R
1
(AD)，R
2
(AB)，R
3
(BE)，R
4
(CDE)，R
5
(AE)，判断这个分解是否具有无损连
接性。
解：用判断无损连接的算法来解。
① 构造一个初始的二维表，若“属性”属于
“模式”中的属性，则填 a
j
，否则填 b
ij
。
② 根据 A→C，对上表进行处理，由于属
性列 A 上第 1、2、5 行相同均为 a
1
，所
以将属性列 C 上的 b
13
、b
23
、b
53
改为同
一个符号 b
13
（取行号最小值）。
③ 根据 B→C，对上表进行处理，由于属
性列 B 上第 2、3 行相同均为 a
2
，所以将
属性列 C 上的 b
13
、b
33
改为同一个符号
b
13
（取行号最小值）。
④ 根据 C→D，对上表进行处理，由于属
性列 C 上第 1、2、3、5 行相同均为
b
13
，所以将属性列 D 上的值均改为同一
个符号 a
4
。
⑤ 根据 DE→C，对上表进行处理，由于
属性列 DE 上第 3、4、5 行相同均为
a
4
a
5
，所以将属性列 C 上的值均改为同
一个符号 a
3
。
评论5
最新资源