關系資料理論

一、問題的提出

關系資料庫邏輯設計

• 針對具體問題，如何構造一個适合于它的資料模式
• 資料庫邏輯設計的工具──關系資料庫的規範化理論

關系模式由五部分組成，是一個五元組：

R(U, D, DOM, F)

• 關系名R是符号化的元組語義
• U為一組屬性
• D為屬性組U中的屬性所來自的域
• DOM為屬性到域的映射
• F為屬性組U上的一組資料依賴

資料依賴

• 是一個關系内部屬性與屬性之間的一種限制關系
  • 通過屬性間值的相等與否展現出來的資料間互相聯系
• 是現實世界屬性間互相聯系的抽象
• 是資料内在的性質
• 是語義的展現

資料依賴的主要類型

• 函數依賴（Functional Dependency，簡記為FD）
• 多值依賴（Multi-Valued Dependency，簡記為MVD）

函數依賴普遍存在于現實生活中

• 描述一個學生關系，可以有學号、姓名、系名等屬性。
  • 一個學号隻對應一個學生，一個學生隻在一個系中學習
  • “學号”值确定後，學生的姓名及所在系的值就被唯一确定。
• Sname=f(Sno)，Sdept=f(Sno)
  • 即Sno函數決定Sname
  • Sno函數決定Sdept
  • 記作Sno→Sname，Sno→Sdept

[例] 建立一個描述學校教務的資料庫。涉及的對象包括：

• 學生的學号（Sno）
• 所在系（Sdept）
• 系主任姓名（Mname）
• 課程号（Cno）
• 成績（Grade）

假設學校教務的資料庫模式用一個單一的關系模式Student來表示，則該關系模式的屬性集合為：

U ＝{Sno, Sdept, Mname, Cno, Grade}

現實世界的已知事實（語義）：

• 一個系有若幹學生， 但一個學生隻屬于一個系；
• 一個系隻有一名（正職）負責人；
• 一個學生可以選修多門課程，每門課程有若幹學生選修；
• 每個學生學習每一門課程有一個成績。

由此可得到屬性組U上的一組函數依賴F：

F={Sno→Sdept, Sdept→ Mname, (Sno, Cno)→ Grade}

關系模式Student<U, F>中存在的問題：

（1）資料備援

浪費大量的存儲空間

每一個系主任的姓名重複出現，重複次數與該系所有學生的所有課程成績出現次數相同。

（2）更新異常（Update Anomalies）

資料備援 ，更新資料時，維護資料完整性代價大。

某系更換系主任後，必須修改與該系學生有關的每一個元組。

（3）插入異常（Insertion Anomalies）

如果一個系剛成立，尚無學生，則無法把這個系及其系主任的資訊存入資料庫。

（4）删除異常（Deletion Anomalies）

如果某個系的學生全部畢業了， 則在删除該系學生資訊的同時，把這個系及其系主任的資訊也丢掉了。

結論

• Student關系模式不是一個好的模式。

• 一個“好”的模式應當不會發生插入異常、删除異常和更新異常，資料備援應盡可能少。

  原因

• 由存在于模式中的某些資料依賴引起的。

解決方法

• 用規範化理論改造關系模式來消除其中不合适的資料依賴

把這個單一的模式分成三個關系模式：

S(Sno,Sdept,Sno → Sdept);

SC(Sno,Cno,Grade,(Sno,Cno) → Grade);

DEPT(Sdept,Mname,Sdept → Mname);

這三個模式都不會發生插入異常、删除異常的問題，資料的備援也得到了控制。

二、規範化

1、函數依賴

1.1.函數依賴

定義 設R(U)是一個屬性集U上的關系模式，X和Y是U的子集。若對于R(U)的任意一個可能的關系r，r 中不可能存在兩個元組在X上的屬性值相等， 而在Y上的屬性值不等， 則稱“X函數确定Y”或“Y函數依賴于X”，記作X→Y。

函數依賴是語義範疇的概念，隻能根據資料的語義來确定一個函數依賴。

例如“姓名→年齡”這個函數依賴隻有在不允許有同名人的條件下成立

1.2.平凡函數依賴與非平凡函數依賴

X→Y，但Y⊈X則稱X→Y是非平凡的函數依賴。

X→Y，但Y⊆X 則稱X→Y是平凡的函數依賴。

對于任一關系模式，平凡函數依賴都是必然成立的，它不反映新的語義。

若不特别聲明， 我們總是讨論非平凡函數依賴。

若X→Y，則X稱為這個函數依賴的決定因素（Determinant）。

若X→Y，Y→X，則記作X←→Y。

若Y不函數依賴于X，則記作X↛Y。

1.3.完全函數依賴與部分函數依賴

定義在R(U)中，如果X→Y，并且對于X的任何一個真子集X’, 都有 X’ ↛ Y, 則稱Y對X完全函數依賴，記作X → Y。

若X→Y，但Y不完全函數依賴于X，則稱Y對X部分函數依賴，記作X → Y

1.4.傳遞函數依賴

定義 在R(U)中，如果X→Y(Y⊈X)，Y↛X，Y→Z，Z⊈Y, 則稱Z對X傳遞函數依賴(transitive functional dependency)。記為：X →傳遞 Z。

注: 如果Y→X, 即X←→Y，則Z直接依賴于X，而不是傳遞函數依賴。

[例] 在關系Std(Sno, Sdept, Mname)中，有：

Sno → Sdept，Sdept → Mname，

Mname傳遞函數依賴于Sno

2、碼

定義 設K為R<U,F>中的屬性或屬性組合。若K → U，則K稱為R的一個候選碼(Candidate Key)。

如果U部分函數依賴于K，即K → U,則K稱為超碼 （Surpkey）。候選碼是最小的超碼，即K的任意一個真子集都不是候選碼。

若關系模式R有多個候選碼，則標明其中的一個做為主碼(Primary key)。

主屬性與非主屬性

• 包含在任何一個候選碼中的屬性 ，稱為主屬性 （Prime attribute）
• 不包含在任何碼中的屬性稱為非主屬性（Nonprime attribute）或非碼屬性（Non-key attribute）
• 全碼：整個屬性組是碼，稱為全碼（All-key）

[例]S(Sno, Sdept, Sage)，單個屬性Sno是碼

SC(Sno, Cno, Grade)中，(Sno, Cno)是碼

定義 關系模式 R中屬性或屬性組X 并非 R的碼，但 X 是另一個關系模式的碼，則稱 X 是R 的外部碼（Foreign key）也稱外碼。

SC(Sno,Cno,Grade)中，Sno不是碼

Sno是 S(Sno,Sdept,Sage)的碼，則Sno是SC的外碼

主碼與外部碼一起提供了表示關系間聯系的手段

3、範式

範式是符合某一種級别的關系模式的集合。

關系資料庫中的關系必須滿足一定的要求。滿足 不同程度要求的為不同範式。

範式的種類：

各種範式之間存在聯系：

某一關系模式R為第n範式，可簡記為R∈nNF。

一個低一級範式的關系模式，通過模式分解（schema decomposition）可以轉換為若幹個高一級範式的關系模式的集合，這種過程就叫規範化（normalization）。

4、2NF

定義 若關系模式R∈1NF，并且每一個非主屬性都完全函數依賴于任何一個候選碼，則R∈2NF

[例] S-L-C(Sno,Sdept,Sloc,Cno,Grade)， Sloc為學生的住處，并且每個系的學生住在同一個地方。S-L-C的碼為(Sno,Cno)。

函數依賴有：

非主屬性Sdept、Sloc并不完全依賴于碼

關系模式S-L-C不屬于2NF

一個關系模式不屬于2NF，會産生以下問題：

插入異常

如果插入一個新學生，但該生未選課，即該生無Cno，由于插入元組時，必須給定碼值，是以插入失敗。

删除異常

如果S4隻選了一門課C3，現在他不再選這門課，則删除C3後，整個元組的其他資訊也被删除了。

修改複雜

如果一個學生選了多門課，則Sdept，Sloc被存儲了多次。如果該生轉系，則需要修改所有相關的Sdept和Sloc，造成修改的複雜化。

出現這種問題的原因

例子中有兩類非主屬性：

• 一類如Grade，它對碼完全函數依賴
• 另一類如Sdept、Sloc，它們對碼不是完全函數依賴

解決方法：

用投影分解把關系模式S-L-C分解成兩個關系模式

SC(Sno,Cno,Grade)

S-L(Sno,Sdept,Sloc)

5、3NF

定義 設關系模式R<U,F>∈1NF,若R中不存在這樣的碼X、屬性組Y及非主屬性Z（Z ⊇ Y）, 使得X→Y，Y→Z成立，Y ↛ X不成立，則稱R<U,F> ∈ 3NF。

• SC沒有傳遞依賴，是以SC ∈ 3NF
• S-L中Sno →Sdept( Sdept ↛ Sno), Sdept→Sloc，可得Sno → Sloc。
• 解決的辦法是将S-L分解成
  • S-D(Sno,Sdept)∈ 3NF
  • D-L(Sdept,Sloc)∈ 3NF

6、BCNF

BCNF（Boyce Codd Normal Form）由Boyce和Codd提出，比3NF更進了一步。通常認為BCNF是修正的第三範式，有時也稱為擴充的第三範式。

定義 設關系模式R<U,F>∈1NF，若X →Y且Y ⊆ X時X必含有碼，則R<U,F>∈BCNF。

在關系模式R<U,F>中，如果每一個決定屬性集都包含候選碼，則R∈BCNF。

BCNF的關系模式所具有的性質

• 所有非主屬性都完全函數依賴于每個候選碼
• 所有主屬性都完全函數依賴于每個不包含它的候選碼
• 沒有任何屬性完全函數依賴于非碼的任何一組屬性

如果一個關系資料庫中的所有關系模式都屬于BCNF，那麼在函數依賴範疇内，它已實作了模式的徹底分解，達到了最高的規範化程度，消除了插入異常和删除異常。

7、多值依賴

定義 設R(U)是屬性集U上的一個關系模式。X,Y,Z是U的子集，并且Z=U-X-Y。關系模式R(U)中多值依賴X→→Y成立，當且僅當對R(U)的任一關系r，給定的一對(x,z)值，有一組Y的值，這組值僅僅決定于x值而與z值無關。

多值依賴的另一個等價的定義

在R(U)的任一關系r中，如果存在元組t，s使得t[X]=s[X]

，那麼就必然存在元組w，v∈r，（w，v可以與s，t相

同）, 使得w[X]=v[X]=t[X]，而w[Y]=t[Y]，w[Z]=s[Z]，

v[Y]=s[Y]，v[Z]=t[Z]（即交換s，t元組的Y值所得的兩

個新元組必在r中則Y多值依賴于X，記為X→→Y。這裡

X，Y是U的子集，Z=U-X-Y。

平凡多值依賴和非平凡的多值依賴

• 若X→→Y，而Z＝Ф，即Z為空，則稱X→→Y為平凡的多值依賴。
• 否則稱X→→Y為非平凡的多值依賴。

多值依賴的性質

（1）多值依賴具有對稱性。

即若X→→Y，則X→→Z，其中Z＝U－X－Y

多值依賴的對稱性可以用完全二分圖直覺地表示出來。

（2）多值依賴具有傳遞性。即若X→→Y，Y→→Z， 則 X→→Z -Y。

（3）函數依賴是多值依賴的特殊情況。即若X→Y，則 X→→Y。

（4）若X→→Y，X→→Z，則X→→YZ。

（5）若X→→Y，X→→Z，則X→→Y∩Z。

（6）若X→→Y，X→→Z，則X→→Y-Z，X→→Z -Y。

8、4NF

定義 關系模式R<U,F>∈1NF，如果對于R的每個非平凡多值依賴X→→Y（Y ⊈ X），X都含有碼，則R<U,F>∈4NF。

4NF就是限制關系模式的屬性之間不允許有非平凡且非函數依賴的多值依賴。4NF所允許的非平凡多值依賴實際上是函數依賴。

9、規範化小結

規範化的基本思想

• 是逐漸消除資料依賴中不合适的部分，使模式中的各關系模式達到某種程度的“分離”。
• 即采用“一事一地”的模式設計原則
  • 讓一個關系描述一個概念、一個實體或者實體間的一種聯系。
  • 若多于一個概念就把它“分離”出去。
• 是以 規範化實質上是概念的單一化

三、資料依賴的公理系統

定義 對于滿足一組函數依賴F的關系模式 R <U,F>，其任何一個關系r，若函數依賴X→Y都成立（即r中任意兩元組t、s，若t[X]=s[X]，則 t[Y]=s[Y]），則稱F邏輯蘊涵X →Y

Armstrong公理系統

• 一套推理規則，是模式分解算法的理論基礎
• 用途
  • 求給定關系模式的碼
  • 從一組函數依賴求得蘊涵的函數依賴

Armstrong公理系統 設U為屬性集總體，F是U上的一組函數依賴， 于是有關系模式R <U,F >。對R <U,F> 來說有以下的推理規則：

• A1 自反律（reflexivity rule）：若Y 包含于X 包含于 U，則X →Y 為F所蘊涵。
• A2 增廣律（augmentation rule）：若X→Y為F所蘊涵，且Z 包含于 U，則XZ→YZ 為F所蘊涵。

• A3 傳遞律（transitivity rule）：若X→Y及Y→Z為F所蘊涵，則X→Z 為F所蘊涵。

  注意：由自反律所得到的函數依賴均是平凡的函數依賴, 自反律的使用并不依賴于F。

定義 在關系模式R<U,F>中為F所邏輯蘊涵的函數依賴的全體叫作F的閉包，記為F +。

定義 設F為屬性集U上的一組函數依賴，X、Y U， XF+={ A|X→A能由F根據Armstrong公理導出}，XF+稱為屬性集X關于函數依賴集F的閉包。

求閉包的算法

求屬性集X（X 包含于 U）關于U上的函數依賴集F的閉包XF+

輸入：X，F

輸出：XF+

步驟：

[例] 已知關系模式R<U, F>，其中

U={A, B, C, D, E}；

F={AB→C, B→D, C→E, EC→B, AC→B}。

求(AB)F+ 。

小結

關系模式的規範化，其基本思想：

• 若要求分解具有無損連接配接性，那麼模式分解一定能夠達到4NF。
• 若要求分解保持函數依賴，那麼模式分解一定能夠達到3NF，但不一定能夠達到BCNF。
• 若分解既具有無損連接配接性，又保持函數依賴，則模式分解一定能夠達到3NF，但不一定能夠達到BCNF。

規範化理論為資料庫設計提供理論的指南和工具

僅僅是指南和工具

并不是規範化程度越高，模式就越好

必須結合應用環境和現實世界的具體情況合理地選擇資料庫模式