求最小函數依賴集例題

1、精選優(yōu)質文檔-傾情為你奉上 基于閉包的求最小函數依賴集算法 定義：如果函數依賴集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；否則不能去

2、掉，依次做下去。直到找不到冗余的函數依賴； 去掉各依賴左部多余的屬性。一個一個地檢查經過第步去掉了多余依賴后的函數依賴左部非單個屬性的依賴。例如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：利用算法求解，使得其滿足三個條件 利用分解規(guī)則，將所有的函數依賴變成右邊都是單個屬性的函數依賴，得F為：F=ABC,D

3、E,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,CE

4、G計算(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為冗余的函

5、數依賴，則去掉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

6、,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

7、函數依賴。故有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.

8、將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中

9、去掉某關系,如去掉(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

10、,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中其余的函數依賴，計算去掉依賴左邊屬性的必包，發(fā)現 ACD->B，CE->A,CF->D是冗余的函數依賴， AB->C C->A BC->D BE->C CE->F CF->B D->E D->F 3: