數據依賴

定義：設有一關係模式R（A1,A2,…,An),X和Y均為（A1,A2,…,An)的子集，對於R的值r來説，當其中任意兩個元組u,v中對應於X的那些屬性分量的值均相等時，則有u,v中對應於Y的那些屬性分量的值也相等，稱X函數決定Y，或Y依賴於X，記為X->Y ^[1]  。

例：有關係，學生（學號S#，姓名SN，系名SD），子集X（學號S#），子集Y（系名SD）。

每個學生有唯一的一個學號，學生中可以有重名的姓名，每個學生只能屬於一個系，每個繫有唯一的系代號。有此，可以找出學生關係模式中存在下列函數依賴：

S#->SN；S#->SD

例：有關係，學校簡況(學號S#，系名SD，系主任MN，課程CN，成績G)。可寫出函數依賴：

S#->SD；SD->MN；S#,CN->G

根據函數依賴的不同性質，函數依賴可分為完全函數依賴、部分函數依賴和傳遞函數依賴。

2.2 完全函數依賴

定義：在R(U)中，如果X->Y，對於X的任意一個真子集X’,都有X’不能決定Y，則稱Y對X完全函數依賴，記為XY 。

例：（S#,CN）->G

2.3 部分函數依賴

定義：在R(U)中，如果X-> Y，但Y不完全函數依賴於X，則稱Y對X部分函數依賴。

2.4 傳遞函數依賴

定義：在R(U)中，當且僅當X-> Y，Y->Z時，稱Z對X傳遞函數依賴。

例：描述學生（S#）、班級（SB）、輔導員（TN）的關係U(S#,SB,TN)。一個班有若干學生，一個學生只屬於一個班，一個班只有一個輔導員，但一個輔導員負責幾個班。根據現實世界可得到一組函數依賴：

F={S#->SB，SB->TN}

學生學號決定了所在班級，所在班級決定了輔導員，所以輔導員TN傳遞函數依賴於學生學號S#。

數據依賴還包括多值依賴和連接依賴兩種形式。

--------------------------------------------------------------------------------------------------

數據依賴是指一種狀態，當程序結構導致數據引用之前處理過的數據時的狀態。在編譯學中，數據依賴是數據分析的一部分。

解説：假設有如下表述S1和S2，

(I (S1) ∩ O(S2)) ∪ (O(S1) ∩ I(S2)) ∪ (O(S1) ∩ O(S2)) ≠ Φ

那麼S2依賴S1。I（Si）是內存位置的集合，可由Si和S2讀

O（Sj）是內存地址的集合，由Sj寫，

則這裏S1和S2就有一個必須遵守的執行順序。

數據依賴有三種，

1. 流依賴（flow dependency），一個變量在一次表達式中賦值或修改然後用在後來的另一個表達式中。例

a=b*c

...

d=a-e

2.反依賴（anti dependency），一個變量在一個表達式中被使用然後在後來一個表達式中被修改賦值。例

a=b*c

......

b=d+e

3.輸出依賴，一個變量在一表達式中被修改賦值然後又在後來另一個表達式中被修改值，例

a=b+c

......a=d-e

數據依賴是數據之間的相互制約關係，是一種語義體現，主要分為函數依賴（FD）、多值依賴（MVD）和連接依賴（JD） ^[2]  。

兩個實例化的屬性集X,Y，如果屬性集X中的兩個元組取值相同，必有對應的另外一個屬性集Y中元組取值相同，則稱Y函數依賴於X函數。

特別值得注意的是，如果屬性集X中不存在兩個取值相同的元組集合，則Y必定依賴於函數X，且函數X的屬性集為超鍵。

平凡函數依賴和非平凡函數依賴。平凡函數依賴：如果Y依賴於X，同時Y是X的子集，那麼稱X -> Y 為平凡函數依賴；非平凡函數依賴：Y不是X的子集。對於任意關係模式而言，平凡函數依賴是必然成立的，其並不反映新的語義特徵，因此我們一般不討論平凡函數依賴。

完全函數依賴和部分函數依賴。完全函數依賴表示的就是函數X的屬性集構成了候選鍵。其中形式化的表示就是如果對於X的任何一個子集Z，都有Y不依賴於Z，則稱Y完全函數依賴於X。如果Y不完全函數依賴於X，則稱Y部分函數依賴於X。完全函數依賴的左部構成主鍵，不包含冗餘的屬性。

傳遞函數依賴和直接函數依賴。如果Y函數依賴於X，Z函數依賴於Y，其Y不是X的子集，X不依賴於Y，則稱Z傳遞依賴於X，否則稱Z直接函數依賴於X。

函數依賴的邏輯藴涵。

，即對於關係模式上的函數依賴集合F，只要X→Y是一個函數依賴，那麼必然可以推導認為F邏輯藴涵X→Y。

函數依賴集合的閉包。由函數依賴集合F所邏輯藴涵的全部函數依賴所構成的集合稱之為F的閉包。

。閉包的性質：1. F 屬於 F+，這是因為根據閉包的定義F中的每個函數依賴必定也在中F+；2. (F+)+=F+，該性質説明閉包運算是冪等的，即F經過任意多次的閉包運算後其結果仍然等於F+；3.如果F=F+，則稱F是完備的。

函數依賴的推理規則（Armstrong公理）：

設U是關係模式R的屬性集，F是R上的函數依賴集，則有：

A1（自反律）：如果Y X U，則X→Y成立；

A2（增廣律）：如果X→Y成立，且Z U，則XZ→YZ成立；

A3（傳遞律）：如果X→Y，Y→Z成立，則X→Z成立。

定義：對於某個關係上的三個屬性A, B, C。如果屬性B，C的取值都不單一，同時B的取值與C無關，也就是B依賴於A，隨着A取值的變化可以取不同的值。

形式化描述：設R(U)是屬性集U上的一個關係模式。X，Y，Z是的U的子集,並且Z=U-X-Y，如果對R(U)的任一關係r，都有如下性質：如果r中存在2個元組s、t，使得：s[X]=t[X] ，則r中必存在元組u，使得： (1) s[X]=t[X]=u[X] (2) u[Y]=t[Y] 且 u[Z]=s[Z] (即交換s、t在Y上的值得到的2個元組必在r中) 則稱關係模式R滿足多值依賴X→→Y。

注意事項：多值依賴會導致數據冗餘和更新異常，因此在進行數據模式設計的時候，要消除多值依賴。一般使用的方法是建立兩個關係，讓每個關係只存儲一個多值屬性的數據。

推導規則：

A4：互補律(MVD) 如果X→→Y，則X→→(U-XY)

A5：擴展律(MVD) 如果X→→Y且VW，則WX→→VY

A6：傳遞律(MVD) 如果X→→Y且Y→→Z，則X→→(Z-Y)

下面兩條為(FD+MVD)公理：

A7：如果X→Y，則X→→Y，即FD是MVD的特例

A8：如果X→→Y、Z→→Y且對某個與Y不相交的W有：W→Z，則X→Z

設關係模式R、Ri的屬性集是U、Ui，UiU(1≤i≤n).若R每個容許的實例r均滿足r=∏U1(r)∞...∞∏Un(r)則稱R滿足連接依賴，記作∞(R1,...,Rn).若其中某個Ui=U，則稱連接依賴是平凡連接依賴。 多值依賴也是連接依賴。