资源描述:
《求最小函数依赖集例题.docx》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、基于闭包的求最小函数依赖集算法 定义:如果函数依赖集F满足下列条件,则称F为最小函数依赖集或最小覆盖。 ①F中的任何一个函数依赖的右部仅含有一个属性; ②F中不存在这样一个函数依赖X→A,使得F与F-{X→A}等价; ③F中不存在这样一个函数依赖X→A,X有真子集Z使得F-{X→A}∪{Z→A}与F等价。 算法:计算最小函数依赖集。 输入一个函数依赖集 输出F的一个等价的最小函数依赖集G 步骤:①用分解的法则,使F中的任何一个函数依赖的右部仅含有一个属性; ②去掉多余的函数依赖:从第一个函数依赖X→Y开始将其从F中去掉,然后在剩下的
2、函数依赖中求X的闭包X+,看X+是否包含Y,若是,则去掉X→Y;否则不能去掉,依次做下去。直到找不到冗余的函数依赖; ③去掉各依赖左部多余的属性。一个一个地检查经过第②步去掉了多余依赖后的函数依赖左部非单个属性的依赖。例如XY→A,若要判Y为多余的,则以X→A代替XY→A是否等价?若A属于(X)+,则Y是多余属性,可以去掉。注:以下题目中有些步骤(如判断左部单属性的依赖是否为多余依赖的步骤)作者嫌麻烦就省略掉了例题1:已知关系模式R,U={A,B,C,D,E,G},F={AB→C,D→EG,C→A,BE→C,BC→D,CG→BD,ACD→B,CE→
3、AG},求F的最小函数依赖集。 解1:利用算法求解,使得其满足三个条件 ①利用分解规则,将所有的函数依赖变成右边都是单个属性的函数依赖,得F为:F={AB→C,D→E,D→G,C→A,BE→C,BC→D,CG→B,CG→D,ACD→B,CE→A,CE→G} ②去掉F中多余的函数依赖 A.设AB→C为冗余的函数依赖,则去掉AB→C,得:F1={D→E,D→G,C→A,BE→C,BC→D,CG→B,CG→D,ACD→B,CE→A,CE→G} 计算(AB)F1+:设X(0)=AB 计算X(1):扫描F1中各个函数依赖,找到左部为AB或AB子集的函数依
4、赖,因为找不到这样的函数依赖。故有X(1)=X(0)=AB,算法终止。 (AB)F1+=AB不包含C,故AB→C不是冗余的函数依赖,不能从F1中去掉。 B.设CG→B为冗余的函数依赖,则去掉CG→B,得:F2={AB→C,D→E,D→G,C→A,BE→C,BC→D,CG→D,ACD→B,CE→A,CE→G} 计算(CG)F2+:设X(0)=CG 计算X(1):扫描F2中的各个函数依赖,找到左部为CG或CG子集的函数依赖,得到一个C→A函数依赖。故有X(1)=X(0)∪A=CGA=ACG。 计算X(2):扫描F2中的各个函数依赖,找到左部为ACG或
5、ACG子集的函数依赖,得到一个CG→D函数依赖。故有X(2)=X(1)∪D=ACDG。 计算X(3):扫描F2中的各个函数依赖,找到左部为ACDG或ACDG子集的函数依赖,得到两个ACD→B和D→E函数依赖。故有X(3)=X(2)∪BE=ABCDEG,因为X(3)=U,算法终止。 (CG)F2+=ABCDEG包含B,故CG→B是冗余的函数依赖,从F2中去掉。 C.设CG→D为冗余的函数依赖,则去掉CG→D,得:F3={AB→C,D→E,D→G,C→A,BE→C,BC→D,ACD→B,CE→A,CE→G} 计算(CG)F3+:设X(0)=CG 计算
6、X(1):扫描F3中的各个函数依赖,找到左部为CG或CG子集的函数依赖,得到一个C→A函数依赖。故有X(1)=X(0)∪A=CGA=ACG。 计算X(2):扫描F3中的各个函数依赖,找到左部为ACG或ACG子集的函数依赖,因为找不到这样的函数依赖。故有X(2)=X(1),算法终止。(CG)F3+=ACG。 (CG)F3+=ACG不包含D,故CG→D不是冗余的函数依赖,不能从F3中去掉。 D.设CE→A为冗余的函数依赖,则去掉CE→A,得:F4={AB→C,D→E,D→G,C→A,BE→C,BC→D,CG→D,ACD→B,CE→G} 计算(CG)F4
7、+:设X(0)=CE 计算X(1):扫描F4中的各个函数依赖,找到左部为CE或CE子集的函数依赖,得到一个C→A函数依赖。故有X(1)=X(0)∪A=CEA=ACE。 计算X(2):扫描F4中的各个函数依赖,找到左部为ACE或ACE子集的函数依赖,得到一个CE→G函数依赖。故有X(2)=X(1)∪G=ACEG。 计算X(3):扫描F4中的各个函数依赖,找到左部为ACEG或ACEG子集的函数依赖,得到一个CG→D函数依赖。故有X(3)=X(2)∪D=ACDEG。 计算X(4):扫描F4中的各个函数依赖,找到左部为ACDEG或ACDEG子集的函数依赖,
8、得到一个ACD→B函数依赖。故有X(4)=X(3)∪B=ABCDE