資料庫最小函數依賴集

1. 有沒有人懂最小函數依賴集到底是個啥，資料庫基礎的，不懂怎麼得到最小函數依賴集，概念也看起來也很抽象

最小函數依賴集就是把函數依賴集依據化簡規則消除不必要的/重復的函數依賴。
求最小函數依賴集分三步:

1.將F中的所有依賴右邊化為單一元素

此題fd={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->i

F={abd->e,ab->g,b->f,c->j,c->i,g->h};

3.去掉F中所有冗餘依賴關系.

做法為從F中去掉某關系,如去掉(X->Y),然後在F中求X+,如果Y在X+中,則表明x->是多餘的.需要去掉.

此題如果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};

最小函數依賴集

定義：如果函數依賴集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是多餘屬性，可以去掉。

舉例：已知關系模式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. 資料庫：求F={A→B,B→A,B→C,A→C,C→A},最小（極小）函數依賴集合

利用分解規則，將所有的函數依賴變成右邊都是單個屬性的函數依賴。從題目來看，F中的任何一個函數依賴的右部僅含有一個屬性：{A→B，B→A，B→C，A→C，C→A}

第二步去冗餘的的順序不同，產生結果也會不同，故最小函數依賴集合不止一個，還可發現另一個最小（極小）函數依賴集合為：{A→B，B→A，A→C，C→A}

給定一個數集A，假設其中的元素為x。現對A中的元素x施加對應法則f，記作f（x），得到另一數集B。假設B中的元素為y。則y與x之間的等量關系可以用y=f（x）表示。函數概念含有三個要素：定義域A、值域C和對應法則f。其中核心是對應法則f，它是函數關系的本質特徵。

(2)資料庫最小函數依賴集擴展閱讀：

函數的對應法則通常用解析式表示，但大量的函數關系是無法用解析式表示的，可以用圖像、表格及其他形式表示。

函數與不等式和方程存在聯系（初等函數）。令函數值等於零，從幾何角度看，對應的自變數的值就是圖像與X軸的交點的橫坐標；從代數角度看，對應的自變數是方程的解。

另外，把函數的表達式（無表達式的函數除外）中的「=」換成「<」或「>」，再把「Y」換成其它代數式，函數就變成了不等式，可以求自變數的范圍。