求最小函數(shù)依賴集例題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 基于閉包的求最小函數(shù)依賴集算法 定義：如果函數(shù)依賴集F滿足下列條件，則稱F為最小函數(shù)依賴集或最小覆蓋。 F中的任何一個函數(shù)依賴的右部僅含有一個屬性； F中不存在這樣一個函數(shù)依賴XA，使得F與F-XA等價； F中不存在這樣一個函數(shù)依賴XA，X有真子集Z使得F-XAZA與F等價。算法：計(jì)算最小函數(shù)依賴集。輸入 一個函數(shù)依賴集輸出 F的一個等價的最小函數(shù)依賴集G步驟： 用分解的法則，使F中的任何一個函數(shù)依賴的右部僅含有一個屬性； 去掉多余的函數(shù)依賴：從第一個函數(shù)依賴XY開始將其從F中去掉，然后在剩下的函數(shù)依賴中求X的閉包X+，看X+是否包含Y，若是，則去掉XY；否則不能去

2、掉，依次做下去。直到找不到冗余的函數(shù)依賴； 去掉各依賴左部多余的屬性。一個一個地檢查經(jīng)過第步去掉了多余依賴后的函數(shù)依賴左部非單個屬性的依賴。例如XYA，若要判Y為多余的，則以XA代替XYA是否等價？若A屬于(X)+，則Y是多余屬性，可以去掉。注：以下題目中有些步驟（如判斷左部單屬性的依賴是否為多余依賴的步驟）作者嫌麻煩就省略掉了例題1：已知關(guān)系模式R，U=A,B,C,D,E,G，F(xiàn)=ABC,DEG,CA,BEC,BCD,CGBD,ACDB,CEAG，求F的最小函數(shù)依賴集。解1：利用算法求解，使得其滿足三個條件 利用分解規(guī)則，將所有的函數(shù)依賴變成右邊都是單個屬性的函數(shù)依賴，得F為：F=ABC,D

3、E,DG,CA,BEC,BCD,CGB,CGD,ACDB,CEA,CEG 去掉F中多余的函數(shù)依賴A設(shè)ABC為冗余的函數(shù)依賴，則去掉ABC，得：F1=DE,DG,CA,BEC,BCD,CGB,CGD,ACDB,CEA,CEG計(jì)算(AB)F1+：設(shè)X(0)=AB計(jì)算X(1)：掃描F1中各個函數(shù)依賴，找到左部為AB或AB子集的函數(shù)依賴，因?yàn)檎也坏竭@樣的函數(shù)依賴。故有X(1)=X(0)=AB，算法終止。(AB)F1+= AB不包含C，故ABC不是冗余的函數(shù)依賴，不能從F1中去掉。B設(shè)CGB為冗余的函數(shù)依賴，則去掉CGB，得：F2=ABC,DE,DG,CA,BEC,BCD,CGD,ACDB,CEA,CE

4、G計(jì)算(CG)F2+：設(shè)X(0)=CG計(jì)算X(1)：掃描F2中的各個函數(shù)依賴，找到左部為CG或CG子集的函數(shù)依賴，得到一個CA函數(shù)依賴。故有X(1)=X(0)A=CGA=ACG。計(jì)算X(2)：掃描F2中的各個函數(shù)依賴，找到左部為ACG或ACG子集的函數(shù)依賴，得到一個CGD函數(shù)依賴。故有X(2)=X(1)D=ACDG。計(jì)算X(3)：掃描F2中的各個函數(shù)依賴，找到左部為ACDG或ACDG子集的函數(shù)依賴，得到兩個ACDB和DE函數(shù)依賴。故有X(3)=X(2)BE=ABCDEG，因?yàn)閄(3)=U，算法終止。(CG)F2+=ABCDEG包含B，故CGB是冗余的函數(shù)依賴，從F2中去掉。C設(shè)CGD為冗余的函

5、數(shù)依賴，則去掉CGD，得：F3=ABC,DE,DG,CA,BEC,BCD,ACDB,CEA,CEG計(jì)算(CG)F3+：設(shè)X(0)=CG計(jì)算X(1)：掃描F3中的各個函數(shù)依賴，找到左部為CG或CG子集的函數(shù)依賴，得到一個CA函數(shù)依賴。故有X(1)=X(0)A=CGA=ACG。計(jì)算X(2)：掃描F3中的各個函數(shù)依賴，找到左部為ACG或ACG子集的函數(shù)依賴，因?yàn)檎也坏竭@樣的函數(shù)依賴。故有X(2)=X(1)，算法終止。(CG)F3+=ACG。(CG)F3+=ACG不包含D，故CGD不是冗余的函數(shù)依賴，不能從F3中去掉。D設(shè)CEA為冗余的函數(shù)依賴，則去掉CEA，得：F4=ABC,DE,DG,CA,BEC

6、,BCD,CGD,ACDB,CEG計(jì)算(CG)F4+：設(shè)X(0)=CE計(jì)算X(1)：掃描F4中的各個函數(shù)依賴，找到左部為CE或CE子集的函數(shù)依賴，得到一個CA函數(shù)依賴。故有X(1)=X(0)A=CEA=ACE。計(jì)算X(2)：掃描F4中的各個函數(shù)依賴，找到左部為ACE或ACE子集的函數(shù)依賴，得到一個CEG函數(shù)依賴。故有X(2)=X(1)G=ACEG。計(jì)算X(3)：掃描F4中的各個函數(shù)依賴，找到左部為ACEG或ACEG子集的函數(shù)依賴，得到一個CGD函數(shù)依賴。故有X(3)=X(2)D=ACDEG。計(jì)算X(4)：掃描F4中的各個函數(shù)依賴，找到左部為ACDEG或ACDEG子集的函數(shù)依賴，得到一個ACDB

7、函數(shù)依賴。故有X(4)=X(3)B=ABCDEG。因?yàn)閄(4)=U，算法終止。(CE)F4+=ABCDEG包含A，故CEA是冗余的函數(shù)依賴，從F4中去掉。 去掉F4中各函數(shù)依賴左邊多余的屬性（只檢查左部不是單個屬性的函數(shù)依賴）由于CA，函數(shù)依賴ACDB中的屬性A是多余的，去掉A得CDB。故最小函數(shù)依賴集為：F=ABC,DE,DG,CA,BEC,BCD,CGD,CDB,CEG例題2：已知R（U，F(xiàn)）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(xiàn)）的最小函數(shù)依賴集解：分三步:1.

8、將F中的所有依賴右邊化為單一元素此題F=abd->e,ab->g,b->f,c->j,cj->i,g->h;已經(jīng)滿足2.去掉F中的所有依賴左邊的冗余屬性.作法是屬性中去掉其中的一個,看看是否依然可以推導(dǎo)此題:abd->e,去掉a,則(bd)+不含e,故不能去掉,同理b,d都不是冗余屬性ab->g,也沒有cj->i,因?yàn)閏+=c,j,i其中包含i所以j是冗余的.cj->i將成為c->iF=abd->e,ab->g,b->f,c->j,c->i,g->h;3.去掉F中所有冗余依賴關(guān)系.做法為從F中

9、去掉某關(guān)系,如去掉(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多不能去掉.所以所求最小函數(shù)依賴集為 F=abd->e,ab->g,b->f,c->j,c->i,g->h;例題3：關(guān)系R（A,B,C,D,E

10、,F，f）滿足下列函數(shù)依賴：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中所有冗余依賴關(guān)系.做法為從F中去掉某關(guān)系,如去掉(X->Y),然后在F中求X+,如果Y在X+中,則表明X->Y是多余的.需要去掉. 去掉AB->C 得到AB+= 所以AB->C 不是冗余的函數(shù)依賴 再依次去掉 1中其余的函數(shù)依賴，計(jì)算去掉依賴左邊屬性的必包，發(fā)現(xiàn) ACD->B，CE->A,CF->D是冗余的函數(shù)依賴， AB->C C->A BC->D BE->C CE->F CF->B D->E D->F 3: