問題的提出

• 關係數據庫邏輯設計
  • 針對具體問題構造適合的數據模式
  • 關係數據庫的規範化理論
• 關係模式用五元組描述$R(U,D,DOM,F)$
  • R 關係名
  • U 全體屬性組
  • D 屬性組U中的屬性所來自的域
  • DOM 屬性到域的映射
  • F 屬性組U上的一組數據依賴

視爲三元組$R<U,F>$

第一範式（1NF, Normal Form）

• 對一個二維表$R$，如果它所有關係的分量都是不可分的，即稱關係模式R屬於第一範式，簡寫爲$R\in\rm{1NF}$

數據依賴

• 一個關係內部屬性與屬性之間的一種約束關係：通過屬性間值的相等與否體現數據間的相互聯繫
• 現實世界屬性間相互聯繫的抽象
• 數據內在的性質
• 語義的體現

數據依賴的類型

• 函數依賴（FD）
• 多值依賴（MVD）

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

• 姓名=f(學號)，系名=f(學號)

記爲$Sno\rightarrow Sname, Sno\rightarrow Sdept$

對 $R<U,F>$ 而言，部分實例使得U上屬性具有某種“依賴”關係，無法推斷$R$的所有關係均滿足該“依賴”關係。

例 學校教務數據庫

包含：

• Sno（學生學號）
• Sdept（所在系）
• Mname（系主任）
• Cno（課程號）
• Grade（成績）

即：
$U={Sno, Sdept, Mname, Cno, Grade}$
$F={Sno\rightarrow Sdept, Sdept \rightarrow Mname,(Sno,Cno)\rightarrow Grade}$

$Student<U,F>$ 存在的問題：系主任Mname

1. 數據冗餘
2. 更新異常
3. 插入異常
4. 刪除異常

規範化

函數依賴

設$R(U)$是屬性集$U$上的關係模式，$X$,$Y$是$U$的子集，若對於$R(U)$的任意一個可能的關係$r$,$r$中不可能存在兩個元組在$X$上的屬性值相等，而在$Y$上的屬性值不等，則稱$X$函數確定$Y$或$Y$函數依賴於$X$，記作$X\rightarrow Y$。

屬於語義範疇，只能根據語義來確定一個函數依賴。

非平凡的函數依賴

$$X\rightarrow Y,但Y\not\subseteq X$$

平凡的函數依賴

$$X\rightarrow Y,但Y\subseteq X$$

完全函數依賴

$X\rightarrow Y$，並且對於$X$的任何一個真子集$X’$,都有$X’\not\rightarrow Y$，則稱$Y$對$X$完全函數依賴，記作$X\stackrel{F}{\rightarrow}Y$
（胡扯：一一映射）

部分函數依賴

若$X\rightarrow Y$, 但$Y$不完全函數依賴於$X$，記作$X\stackrel{P}{\rightarrow}Y$

傳遞函數依賴

$X\rightarrow Y(Y\not\subseteq X)$, $Y\not\rightarrow X$, $Y\rightarrow Z$, $Z\not\subseteq Y$

• 無損連接

碼

設$K$爲$R<U,F>$中的屬性或屬性組合。若$K\stackrel{F}{\rightarrow}U$,則$K$稱爲$R$的一個候選碼。

• 若$U$部分函數依賴，則$K$稱爲超碼(Superkey)
• 候選碼是最小的超碼，則$K$的任意一個真子集

主屬性與非主屬性

全碼(all-key)

整個屬性組是碼

外碼

X非R的碼，但是另一個關係的碼

範式

滿足最低要求的叫第一範式，簡稱$\rm{1NF}$。
$$\rm{1NF\supset 2NF\supset 3NF\supset BCNF\supset 4NF\supset 5NF}$$

• 規範化

2NF

$R\in\rm{1NF}$且每個非主屬性都完全函數依賴於任何一個候選碼，則$R\in\rm{2NF}$

一個關係不屬於$\rm{2NF}$，則：

• 插入異常
• 刪除異常
• 修改複雜

3NF

$R<U,F>\in\rm{1NF}$，若R中不存在這樣的碼X，屬性組Y及非主屬性Z（$Z\not\subseteq Y$）使得$X\rightarrow Y， Y\rightarrow Z$成立，$Y\not\rightarrow X$，則$R<U,F>\in\rm{3NF}$

BCNF

$R<U,F>\in\rm{1NF}$，若$X\rightarrow Y$且 $Y\not\subseteq X$時X必含有碼，則$R<U,F>\in\rm{BCNF}$

換言之，在關係模式$R<U,F>$中，如果每一個決定屬性集都包含候選碼，則$R<U,F>\in\rm{BCNF}$
性質：

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

$R<U,F>\in\rm{BCNF}\Rightarrow R<U,F>\in\rm{3NF}$

多值依賴

4NF

關係模式$R<U,F>\in\rm{1NF}$，如果對於R的每個非平凡多值依賴$X\rightarrow \rightarrow Y(Y \not\subseteq X)$，X都含有碼。

限制屬性，不允許有非平凡且非函數依賴的多值依賴。

將BCNF的R分解成4NF的方法

• 假設$R(A,B,C)∈\rm{BCNF}$滿足$A→→B$，$A→→C$，則分解$R$可分解爲$R_1(A,B)$和$R_2(A,C)$

數據依賴的公理系統

Armstrong公理系統：

• A1 自反律 若$Y\subseteq X\subseteq U$，則$X\rightarrow Y$爲$F$所蘊涵
• A2 增廣律 若$X\rightarrow Y$爲$F$所蘊涵，且$Z\subset U$，則$XZ\rightarrow YZ$爲$F$所蘊涵
• A3 傳遞律 若$X\rightarrow Y$及$Y\rightarrow Z$爲$F$所蘊涵，則$X\rightarrow Z$爲$F$所蘊涵

定理 6.1 Armstrong定理是正確的。

引理 6.1 $X→A_1A_2…A_{k}$成立的充分必要條件是$X→A_i$成立（$i=1, 2, …, k$）。

定義6.12 在關係模式$R<U,F>$中爲$F$所邏輯蘊涵的函數依賴的全體叫作$F$的閉包，記爲$F^{+}$

定義6.14 如果$G^{+}=F^{+}$，就說函數依賴集$F$覆蓋$G$（$F$是$G$的覆蓋，或$G$是$F$的覆蓋），或$F$與$G$等價。

定義6.15 如果函數依賴集$F$滿足下列條件，則稱$F$爲一個極小函數依賴集，亦稱爲最小依賴集或最小覆蓋。