SQL 系列
資料庫學習（一）：資料庫導論: https://blog.yexca.net/archives/86
資料庫學習（二）：關聯模型: https://blog.yexca.net/archives/87
資料庫學習（三）：SQL 語言: https://blog.yexca.net/archives/88
資料庫學習（四）：關聯式資料庫理論: 本文
資料庫學習（五）：正規化: https://blog.yexca.net/archives/90
資料庫學習（六）：資料庫設計: https://blog.yexca.net/archives/91
資料庫學習（七）：資料庫的控制功能: https://blog.yexca.net/archives/92
關聯模式
一個關聯模式應為一個五元組（含關聯名稱）
R<U, D, dom, F>
- R 為關聯名稱，它是符號化的值組語義
- U 為一組屬性
- 屬性組 U 中的屬性來自值域 D
- dom 為屬性列表到值域的映射
- F 為屬性組 U 上的一組資料相依（函數相依）
由於第三點與第四點對模式設計影響不大，因此通常把關聯模式看作是一個三元組：R<U, F>，當且僅當 U 上的一個關聯 r 滿足 f 時，r 稱為關聯模式 R<U, F> 的一個關聯
例如：R 為成績表，U 為 (學號，姓名，課程號，成績)，F 為 {學號 → 姓名，課程號 → 課程名，(學號，課程號) → 成績}
函數相依
函數相依是一種最重要、最基本的資料相依
設 R(U) 是屬性集 U 上的關聯模式，X、Y 是 U 的子集。若對於 R(U) 的任何一個可能的關聯 r，r 中不可能存在兩個值組在 X 上的屬性值相等，而在 Y 上的屬性值不等，則稱 X 函數決定 Y 或 Y 函數相依於 X。記作 X → Y
- 非平凡的函數相依
如果 X → Y，但 Y ⊈ X，則稱 X → Y 是非平凡的函數相依。一般情況下，總是討論非平凡的函數相依
- 平凡的函數相依
如果 X → Y，但 Y ⊆ X，則稱 X → Y 是平凡的函數相依
- 完全函數相依
在 R(U) 中，如果 X → Y，並且對於 X 的任何一個真子集 X’ 都有 X’ 不能決定 Y，則稱 Y 對 X 完全函數相依，記作 X -F-> Y
- 部分函數相依
如果 X → Y，但 Y 不完全函數相依於 X，則稱 Y 對 X 部分函數相依，記作 X -P-> Y。部分函數相依也稱為局部函數相依
- 傳遞相依
在 R(U, F) 中，如果 X → Y，Y ⊈ X，Y → Z，則稱 Z 對 X 傳遞相依
參考： Untitled Document (pop0726.github.io)
鍵 (Key)
設 K 為 R(U, F) 中屬性的組合，若 K → U，且對於 K 的任何一個真子集 K’ 都有 K’ 不能決定 U，則 K 為 R 的候選鍵 (Candidate Key)。若有多個候選鍵，則選一個作為主鍵 (Primary Key)。候選鍵通常也稱為候選關鍵字
- 主屬性與非主屬性
包含在任意一個候選鍵中的屬性稱為主屬性，否則稱為非主屬性
- 外鍵 (Foreign Key)
若 R(U) 中的屬性或屬性組 X 非 R 的鍵，但 X 是另一個關聯的鍵，則稱 X 為外鍵
- 超鍵 (Super Key)
能表示出所有屬性的集合，候選鍵是最小的超鍵
- 全鍵 (All-Key)
所有的屬性都是主鍵
函數相依的公理系統 (Armstrong 公理系統)
設關聯模式 R(U, F)，其中 U 為屬性集，F 是 U 上的一組函數相依，那麼有以下推理規則：
- 自反律 (Reflexivity)：若 Y ⊆ X ⊆ U，則 X → Y 為 F 所蘊涵
- 增廣律 (Augmentation)：若 X → Y 為 F 所蘊涵，且 Z ⊆ U，則 XZ → YZ 為 F 所蘊涵
- 傳遞律 (Transitivity)：若 X → Y，Y → Z 為 F 所蘊涵，則 X → Z 為 F 所蘊涵
根據上述三條推理規則又可推出下述三條推理規則：
- 合併規則 (Union)：若 X → Y，X → Z，則 X → YZ 為 F 所蘊涵
- 偽傳遞律 (Pseudo-transitivity)：若 X → Y，WY → Z 為 F 所蘊涵，則 XW → Z 為 F 所蘊涵
- 分解規則 (Decomposition)：若 X → Y，Z ⊆ Y，則 X → Z 為 F 所蘊涵
屬性閉包計算
閉包計算即找出候選鍵，如何選出候選鍵？
- 只出現在左邊的一定是候選鍵的一部分
- 只出現在右邊的一定不是候選鍵
- 左右都出現的不一定
- 左右都不出現的一定是候選鍵的一部分
- 再求確定的候選鍵部分的閉包，如果可以推出全部屬性，那麼當前確定的就是候選鍵；否則，需要將每一個可能的值加入當前確定的集合中繼續求閉包
例如：
R<U, F>，U(A, B, C, D, E, G) F = {AB → C, CD → E, E → A, A → G}, 求候選鍵
- 只出現在左邊：B, D 一定是候選鍵的一部分
- 只出現在右邊：G 一定不是候選鍵
- 左右都出現的：A，C，E 不一定是候選鍵
- 求閉包
BD → 什麼也推不出來，所以要把每一個可能的屬性加入求閉包
(BDA)+ ：可推出 C，E，A，G，所以可以推出 ABCDEG
(BDC)+ ：可推出 E，A，G，所以可以推出 ABCDEG
(BDE)+ ：可推出 A，G，C，所以可以推出 ABCDEG
所以，它的候選鍵最終是 {(BDA), (BDC), (BDE)}
求最小函數相依集合
如何求最小相依集？
1）將右側拆分為多個元素（例如 A->BC 拆分為 A->B 和 A->C）
2）去除當前元素，求其餘元素的閉包，檢查是否能推出該元素，遍歷集合中所有元素
3）左側最小化（透過遮住左側屬性來看能否由剩下的屬性推出右側屬性）
例如 BCD->A，遮住 B 看 CD 能推出 A 嗎，遮住 C 看 BD 能推出 A 嗎，遮住 D 看 BC 能推出 A 嗎
例：
已知關聯 R<U, F> U{A, B, C, D, E, F, G}
F = {BCD->A, BC->E, A->F, F->G, C->D, A->G} 求 F 的最小相依集
解：
// (1)
(BCD)+ = BCDED
(BC)+ = BCD
(A)+ = AG
(F)+ = F
(C)+ = C
(A)+ = AFG（刪除，因為已有 G）
// (2)
BCD->A —> BC->A
BC->E
A->F
F->G
C->D