




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
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:
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 檔案實施管理辦法試行
- 公文秘密管理暫行辦法
- 銀行裝修施工安全巡查流程他
- 壽光垃圾傾倒管理辦法
- 晚會主持團隊演職人員安排及職責
- 合作培訓管理暫行辦法
- 心血管介入手術護理
- 客戶誠信管理暫行辦法
- 監(jiān)獄信訪工作管理辦法
- 對講工作平臺管理辦法
- 教育數字化轉型背景下的小學英語教學研究
- CSCO 膽道惡性腫瘤指南更新2025
- WB/T 1139-2024國家物流樞紐統(tǒng)計分類
- 常見慢性病的健康管理試題及答案
- 高中英語單詞資料-英譯漢
- 2025年保安員職業(yè)技能考試筆試試題(100題)附答案
- 社區(qū)急救知識培訓課件
- 礦坑回填施工方案
- 中醫(yī)護理指南
- 2025-2030農藥塑料瓶市場發(fā)展現狀調查及供需格局分析預測報告
- 首件檢驗培訓
評論
0/150
提交評論