求最小函数依赖集例题

______________________________________________________________________________________________________________精品资料基于闭包的求最小函数依赖集算法定义：如果函数依赖集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中______________________________________________________________________________________________________________精品资料去掉，然后在剩下的函数依赖中求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→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子集的函数依赖，因为找不到这样的函数依赖。故有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或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计算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+：设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子集的函数依赖，得到一个ACD→B函数依赖。故有X(4)=X(3)∪B=ABCDEG。因为X(4)=U，算法终止。______________________________________________________________________________________________________________精品资料(CE)F4+=ABCDEG包含A，故CE→A是冗余的函数依赖，从F4中去掉。③去掉F4中各函数依赖左边多余的属性（只检查左部不是单个属性的函数依赖）由于C→A，函数依赖ACD→B中的属性A是多余的，去掉A得CD→B。故最小函数依赖集为：F={AB→C,D→E,D→G,C→A,BE→C,BC→D,CG→D,CD→B,CE→G}例题2：已知R（U，F）U={a,b,c,d,e,f,g,h,i,j},F={abd-e,ab-g,b-f,c-j,cj-i,g-h}求R（U，F）的最小函数依赖集解：分三步:1.将F中的所有依赖右边化为单一元素此题F={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中去掉某关系,如去掉(X-Y),然后在F中求X+,如果Y在X+中,则表明X-Y是多余的.需要去掉.此题如果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};例题3：关系R（{A,B,C,D,E,F}，f）满足下列函数依赖：AB-CC-ABC-DACD-BBE-CCE-FACF-BDD-EF找出该依赖集的最小依赖集1:.将F中的所有依赖右边化为单一元素AB-CC-ABC-DACD-BBE-CCE-FCE-ACF-BCF-D______________________________________________________________________________________________________________精品资料D-ED-F2:去掉F中所有冗余依赖关系.做法为从F中去掉某关系,如去掉(X-Y),然后在F中求X+,如果Y在X+中,则表明X-Y是多余的.需要去掉.去掉AB-C得到AB+={}所以AB-C不是冗余的函数依赖再依次去掉1中其余的函数依赖，计算去掉依赖左边属性的必包，发现ACD-B，CE-A,CF-D是冗余的函数依赖，AB-CC-ABC-DBE-CCE-FCF-BD-ED-F3:去掉F中的所有依赖左边的冗余属性.作法是属性中去掉其中的一个,看看是否依然可以推导没有所以{AB-CC-ABC-DBE-CCE-FCF-BD-ED-F}为f的最小依赖集______________________________________________________________________________________________________________精品资料WelcomeToDownload!!!欢迎您的下载，资料仅供参考！