求最小函数依赖集例题

基于闭包的求最小函数依赖集算法 定义：如果函数依赖集F满足下列条件，则称F为最小函数依赖集或最小覆盖。 F中的任何一个函数依赖的右部仅含有一个属性； F中不存在这样一个函数依赖XA，使得F与F-XA等价； F中不存在这样一个函数依赖XA，X有真子集Z使得F-XAZA与F等价。算法：计算最小函数依赖集。输入 一个函数依赖集输出 F的一个等价的最小函数依赖集G步骤： 用分解的法则，使F中的任何一个函数依赖的右部仅含有一个属性； 去掉多余的函数依赖：从第一个函数依赖XY开始将其从F中去掉，然后在剩下的函数依赖中求X的闭包X+，看X+是否包含Y，若是，则去掉XY；否则不能去掉，依次做下去。直到找不到冗余的函数依赖； 去掉各依赖左部多余的属性。一个一个地检查经过第步去掉了多余依赖后的函数依赖左部非单个属性的依赖。例如XYA，若要判Y为多余的，则以XA代替XYA是否等价？若A属于(X)+，则Y是多余属性，可以去掉。注：以下题目中有些步骤（如判断左部单属性的依赖是否为多余依赖的步骤）作者嫌麻烦就省略掉了例题1：已知关系模式R，U=A,B,C,D,E,G，F=ABC,DEG,CA,BEC,BCD,CGBD,ACDB,CEAG，求F的最小函数依赖集。解1：利用算法求解，使得其满足三个条件 利用分解规则，将所有的函数依赖变成右边都是单个属性的函数依赖，得F为：F=ABC,DE,DG,CA,BEC,BCD,CGB,CGD,ACDB,CEA,CEG 去掉F中多余的函数依赖A设ABC为冗余的函数依赖，则去掉ABC，得：F1=DE,DG,CA,BEC,BCD,CGB,CGD,ACDB,CEA,CEG计算(AB)F1+：设X(0)=AB计算X(1)：扫描F1中各个函数依赖，找到左部为AB或AB子集的函数依赖，因为找不到这样的函数依赖。故有X(1)=X(0)=AB，算法终止。(AB)F1+= AB不包含C，故ABC不是冗余的函数依赖，不能从F1中去掉。B设CGB为冗余的函数依赖，则去掉CGB，得：F2=ABC,DE,DG,CA,BEC,BCD,CGD,ACDB,CEA,CEG计算(CG)F2+：设X(0)=CG计算X(1)：扫描F2中的各个函数依赖，找到左部为CG或CG子集的函数依赖，得到一个CA函数依赖。故有X(1)=X(0)A=CGA=ACG。计算X(2)：扫描F2中的各个函数依赖，找到左部为ACG或ACG子集的函数依赖，得到一个CGD函数依赖。故有X(2)=X(1)D=ACDG。计算X(3)：扫描F2中的各个函数依赖，找到左部为ACDG或ACDG子集的函数依赖，得到两个ACDB和DE函数依赖。故有X(3)=X(2)BE=ABCDEG，因为X(3)=U，算法终止。(CG)F2+=ABCDEG包含B，故CGB是冗余的函数依赖，从F2中去掉。C设CGD为冗余的函数依赖，则去掉CGD，得：F3=ABC,DE,DG,CA,BEC,BCD,ACDB,CEA,CEG计算(CG)F3+：设X(0)=CG计算X(1)：扫描F3中的各个函数依赖，找到左部为CG或CG子集的函数依赖，得到一个CA函数依赖。故有X(1)=X(0)A=CGA=ACG。计算X(2)：扫描F3中的各个函数依赖，找到左部为ACG或ACG子集的函数依赖，因为找不到这样的函数依赖。故有X(2)=X(1)，算法终止。(CG)F3+=ACG。(CG)F3+=ACG不包含D，故CGD不是冗余的函数依赖，不能从F3中去掉。D设CEA为冗余的函数依赖，则去掉CEA，得：F4=ABC,DE,DG,CA,BEC,BCD,CGD,ACDB,CEG计算(CG)F4+：设X(0)=CE计算X(1)：扫描F4中的各个函数依赖，找到左部为CE或CE子集的函数依赖，得到一个CA函数依赖。故有X(1)=X(0)A=CEA=ACE。计算X(2)：扫描F4中的各个函数依赖，找到左部为ACE或ACE子集的函数依赖，得到一个CEG函数依赖。故有X(2)=X(1)G=ACEG。计算X(3)：扫描F4中的各个函数依赖，找到左部为ACEG或ACEG子集的函数依赖，得到一个CGD函数依赖。故有X(3)=X(2)D=ACDEG。计算X(4)：扫描F4中的各个函数依赖，找到左部为ACDEG或ACDEG子集的函数依赖，得到一个ACDB函数依赖。故有X(4)=X(3)B=ABCDEG。因为X(4)=U，算法终止。(CE)F4+=ABCDEG包含A，故CEA是冗余的函数依赖，从F4中去掉。 去掉F4中各函数依赖左边多余的属性（只检查左部不是单个属性的函数依赖）由于CA，函数依赖ACDB中的属性A是多余的，去掉A得CDB。故最小函数依赖集为：F=ABC,DE,DG,CA,BEC,BCD,CGD,CDB,CEG例题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-C C-A BC-D ACD-B BE-C CE-F CE-A CF-B CF-D D-E D-F 2:去掉F中所有冗余依赖关系.做法为从F中去掉某关系,如去掉(X-Y),然后在F中求X+,如果Y在X+中,则表明X-Y是多余的.需要去掉. 去掉AB-C 得到AB+= 所以AB-C 不是冗余的函数依赖 再依次去掉 1中其余的函数依赖，计算去掉依赖左边属性的必包，发现 ACD-B，CE