《資料庫系統》期末考複習 — Relational database design 篇

Functional Dependency ( 功能相依 )

#

所謂 Functional Dependency 就是像這樣 \(A \rightarrow B\) 用箭頭符號表示的式子。它的含意是 : 只要你知道了 A 的值，你就絕對能確定 B 的值。」

舉例 :

學號 (ID)	姓名 (Name)	系所 (Dept)	系辦位置 (Dept_Loc)
S001	芳乃	資工系	A館3樓
S002	茉子	資工系	A館3樓
S003	芳乃	企管系	B館1樓

• 成立的相依 :
  • 如果你知道學號是 S001，你能確定他的名字是 芳乃 嗎？ -> 可以。
  • 如果你知道學號是 S002，你能確定他的名字是 茉子 嗎？ -> 可以。
  • 因為學號是唯一的，一個學號只對應一個人。
  • 因此我們會寫成 \(ID \rightarrow Name\)
• 不成立的相依 :
  • 如果你知道名字是 芳乃，你能確定她的學號是哪一個嗎？ -> 不行！
  • 因為 芳乃 可能是 S001，也可能是 S003。
  • 因此，名字不能決定學號。
• 隱藏的相依
  • 如果你知道某人是「資工系」，你能確定系辦在哪裡嗎？ -> 可以，一定在「A館3樓」。
  • 所以可以寫成 \(Dept \rightarrow Dept\_Loc\)
  • 而這導致了資料冗餘，資工系出現幾次，A館3樓就要寫幾次。

Armstrong’s axioms ( 阿姆斯壯公理 )

#

這些關係算式記住就對了^^

• 反身性 ( reflexivity ) : \[A \subseteq B \;\Rightarrow\; B \rightarrow A\]
• 增廣性 ( augmentation ) : \[A \rightarrow B \;\Rightarrow\; CB \rightarrow CA \quad (\text{C 是任意屬性集})\]
• 遞移性 ( transitivity ) : \[X \to Y \text{ 且 } Y \to Z \;\Rightarrow\; X \to Z\]

Armstrong’s Axioms 的延伸公式

#

1. Union （ 合併律 ）

#

\[ X \to Y \text{ 且 } X \to Z \;\Rightarrow\; X \to YZ \]

🟩證明 :

由

\[ X \to Y \]

根據增廣性（Augmentation），可得

\[ X \to XY \]

又由

\[ X \to Z \]

根據增廣性，可得

\[ XY \to YZ \]

再根據遞移性（Transitivity），

\[ X \to YZ \]

2. decomposition（ 分解律 ）

#

\[ X \to YZ \;\Rightarrow\; X \to Y \text{ 且 } X \to Z \]

🟥證明 :

因為

\[ Y \subseteq YZ \quad \text{且} \quad Z \subseteq YZ \]

根據反身性（Reflexivity），

\[ YZ \to Y \quad \text{且} \quad YZ \to Z \]

又已知

\[ X \to YZ \]

根據遞移性，

\[ X \to Y \quad \text{且} \quad X \to Z \]

3. pseudotransitivity （ 擬傳遞律 ）

#

\[ X \to Y \text{ 且 } WY \to Z \;\Rightarrow\; WX \to Z \]

🟦證明 :

由

\[ X \to Y \]

根據增廣性，可得

\[ WX \to WY \]

又已知

\[ WY \to Z \]

根據遞移性，

\[ WX \to Z \]

Closure of Functional Dependencies

#

基礎

#

　　像這樣的 \(F^+\) 會念作 F closure ( 不是念 F plus) ，我們主要集中在 Attribute Closure 上。舉例 :

• 已知線索 (FDs)：
  • 看到 芳乃 \( (A) \) \(\rightarrow\) 就知道 茉子 \( (B) \) 在附近。
  • 看到 茉子 \( (B) \) \(\rightarrow\) 就知道 安晴 \( (C) \) 在附近。
• 問題 : 如果我們看到 芳乃 \( (A) \) 可以看到那些人 ?
• 推導 \( (A^+) \)
  1. 首先有 芳乃 \( (A) \)。
  2. 因為有 芳乃 \( (A) \) \( \rightarrow \) 找到 茉子 \( (B) \) 。
  3. 因為有 茉子 \( (B) \) \( \rightarrow \) 找到 安晴 \( (C) \)。
• 答案 : \(A^+ = \{ \text{芳乃, 茉子, 安晴} \}\)。

作業第 2 題

#

⛄題目 Consider the relation schema R = (A, B, C, D, E) and the set F of functional dependencies:

• \(A \rightarrow\ BC \)
• \(CD \rightarrow\ E \)
• \(B \rightarrow\ D \)
• \(E \rightarrow\ A \)

1. \( (A^+) \)
   1. 首先有 \(A\) 自己
   2. \(A\) 可以決定 \( \rightarrow \) \(BC\)
   3. \(B\) 可以決定 \( \rightarrow \) \(D\)
   4. \(CD\) 可以決定 \( \rightarrow \) \(E\)
   5. 答案 : \(A^+ = \{ ABCDE \}\)

⭐ 因為 \( (A^+) \) 包含了所有的欄位 \(\{A, B, C, D, E\}\) ，這代表：「只要給我 A ，我就能決定整張表的每一筆資料！」，我們會把 A 叫做 Superkey 。

2. \( B^+ \)
   1. 首先有 \(B\) 自己
   2. \(B\) 可以決定 \( \rightarrow \) \(D\)
   3. 答案 : \(B^+ = \{ BD \}\)
3. \( C^+ \)
   1. 首先有 \(C\) 自己
   2. 答案 : \(C^+ = \{ C \}\)
4. \( D^+ \)
   1. 首先有 \(D\) 自己
   2. 答案 : \(D^+ = \{ D \}\)
5. \( E^+ \)
   1. 首先有 \(E\) 自己
   2. \(E\) 可以決定 \( \rightarrow \) \(A\)
   3. \(A\) 可以決定 \( \rightarrow \) \(BC\)
   4. \(B\) 可以決定 \( \rightarrow \) \(D\)
   5. 答案 : \(A^+ = \{ EABCD \}\)

⭐ 接下來是組合的部分，因為是要找 Candidate Key 所以已經是 Superkey 的就不用去組 ! ( Candidate Key 的定義是其子集不能有 Superkey )

6. \( BC^+ \)
   1. 首先有 \(BC\) 自己
   2. \(B\) 可以決定 \( \rightarrow \) \(D\)
   3. \(CD\) 可以決定 \( \rightarrow \) \(E\)
   4. \(E\) 可以決定 \( \rightarrow \) \(A\)
   5. 答案 : \(BC^+ = \{ BCDEA \}\)
7. \( BD^+ \)
   1. 首先有 \(BD\) 自己
   2. 答案 : \(BD^+ = \{ BD \}\)
8. \( CD^+ \)
   1. 首先有 \(CD\) 自己
   2. \(CD\) 可以決定 \( \rightarrow \) \(E\)
   3. \(E\) 可以決定 \( \rightarrow \) \(A\)
   4. \(A\) 可以決定 \( \rightarrow \) \(B\)
   5. 答案 : \(CD^+ = \{ CDEAB \}\)

🌟 老師有強調 : 「記得寫上最後答案」。所以最後答案是 : \( A^+ \) 、 \( E^+ \) 、 \( BC^+ \) 、 \( CD^+ \)

作業第 3 題

#

⛄題目 Suppose schema R is decomposed into R1 = (A, B, C) and R2 = (A, D, E).

1. Is this decomposition a lossless-join decomposition? Why?
2. Is this decomposition a dependency preserving decomposition? Why?

🟦 第一小題問是不是 lossless-join ，而所謂 lossless-join 是指 : 「當我把原本的大表 \(R\) 拆成兩個小表 \(R_1\) 和 \(R_2\) 之後，如果我再把它們 JOIN (黏) 回去，資料會和原本的一模一樣」

判斷方法很簡單 : 「兩個小表的交集 (重疊的欄位)，必須是其中一個小表的 Key (能決定該小表的所有欄位)。」

\[(R_1 \cap R_2) \rightarrow R_1 \quad \text{OR} \quad (R_1 \cap R_2) \rightarrow R_2\]

很輕鬆的可以得到 : \((R_1 \cap R_2) = A\)
因為 \(A \rightarrow\ BC \) 所以 \(A\) 可以決定 \(BC\)，也就是 \(A\) 可以決定 \(R_1\) 的意思，因此是 lossless-join。

---

🟥 第二小題問 : 「這是一個保存函數相依的分解嗎？」也就是 「拆成兩個小表後，原本的那些規則 (FDs)，能不能分別在各自的小表裡被檢查？還是一定要 JOIN 起來才能檢查？」

• Dependency Preserving： 所有規則都可以在單一小表中檢查，不需要跨表。 (效率高 ✅)
• Not Preserving： 有些規則的欄位被拆散到不同表了，檢查起來很麻煩。 (效率低 ❌)

具體解法是把 \(R_1\) 和 \(R_2\) 的相依關係找出來，我把它們稱作 \(F_1\) 和 \(F_2\)，參考第 2 題求出來的 closure :

\( F_1 = \{ A \to BC,\; BC \to A \} \)
\( F_2 = \{ E \to A \} \)
\( F' = F_1 \cup F_2 = \{ A \to BC,\; BC \to A,\; E \to A \} \)

接著我們看一下題目的關係算式有沒有在\( F' \)

• \(A \rightarrow BC\) ➡️ 有
• \(CD \rightarrow E\) ➡️ 沒有

所以它並不是 Dependency Preserving

作業第 4 題

#

⛄題目 Suppose schema R is decomposed into R1 = (A, B, C) and R2 = (C, D, E).

1. Is this decomposition a lossless-join decomposition? Why?
2. Is this decomposition a dependency preserving decomposition? Why?

和第 3 題問的一模一樣，只是 \(R_1\) 和 \(R_2\) 換掉而已

🟦 第一小題 :

\((R_1 \cap R_2) = C\)

然而
\(C^+ = \{ C \}\)
所以很明顯 \( C \) 不能決定 \(R_1\) 或 \(R_2\)，因此不是 lossless-join

---

🟥 第二小題 :

\( F_1 = \{ A \to BC,\; BC \to A \} \)
\( F_2 = \{ CD \to E\} \)
\( F' = F_1 \cup F_2 = \{ A \to BC,\; BC \to A,\; CD \to E \} \)

接著我們看一下題目的關係算式有沒有在 \( F' \)

• \(A \rightarrow BC\) ➡️ 有
• \(CD \rightarrow E\) ➡️ 有
• \(B \rightarrow D\) ➡️ 沒有

以它並不是 Dependency Preserving

作業第 5 題

#

⛄題目 List the three design goals for relational databases, and explain why each is desirable.

這題是在問：「請列出關聯式資料庫設計的三大目標，並解釋為什麼這三個目標是我們想要的

1. 避免資料冗餘 (Avoid Redundancy)

• 目標 : 確保每一筆資料只在一個地方出現，不要重複存儲，也就是不會出現重複或無意義的內容。
• 為什麼需要 ?
  1. 節省空間：不需要把「A館3樓」重複寫一千次
  2. 避免異常 (Avoid Anomalies)
     • 更新異常： 改一個地址不用改一萬筆資料。
     • 刪除異常： 刪除員工不會連帶讓部門資料消失
     • 新增異常： 可以先建部門而不需要先聘員工。

2. 無損分解 (Lossless-Join Decomposition)
   • 也就是作業第 3 和第 4 題再做的。
   • 目標 : 當我們把大表拆成小表時，必須保證「黏回去 (Join)」之後，資料跟原本一模一樣。
   • 為什麼需要 ?
     1. 資料正確性 (Correctness)：如果不符合這個目標，Join 回去會產生 「假資料 (Spurious Tuples)」。
3. 保存函數相依 (Dependency Preservation)
   • 一樣也是作業第 3 和第 4 題在做的。
   • 目標： 所有的規則 (Functional Dependencies)，最好都能在各自的小表內就能檢查完畢，不需要跨表。
   • 為什麼需要 ?
     1. 效能與效率 (Efficiency)：
        • 如果所有規則都在單一表格內，資料庫只要檢查那張表就能擋下錯誤資料。
        • 如果規則被拆散了 (Not Preserving)，資料庫每次新增或修改資料，都要先做昂貴的 Table Join 運算才能檢查規則，這會讓資料庫慢到無法使用。

作業第 6 題

#

⛄題目 Decompose schema R into BCNF.

把 R 拆成 BCNF :

而 BCNF 的規則只有一條 : 「在所有規則 (FD) 中，箭頭左邊 (決定者) 必須是 Superkey (老大)。」

如果有一條規則 \(X \rightarrow Y\)，但 \(X\) 不是整張表的 Key，那就是 「違反 BCNF」 (Bad Design)，必須拆掉！

回顧一下 :

R = (A, B, C, D, E)
有這幾條 FD :

• \(A \rightarrow\ BC \)
• \(CD \rightarrow\ E \)
• \(B \rightarrow\ D \)
• \(E \rightarrow\ A \)

然後我們知道這些是 Superkey : \( A^+ \) 、 \( E^+ \) 、 \( BC^+ \) 、 \( CD^+ \)

我們要做的是針對每條 FDs 做檢查，要找出那個不能決定表的「亂源」

1. \(A \rightarrow BC\) (A 是 key \(\rightarrow\) Pass ✅)
2. \(CD \rightarrow E\) (CD 是 key \(\rightarrow\) Pass ✅)
3. \(E \rightarrow A\) (E 是 key \(\rightarrow\) Pass ✅)
4. \(B \rightarrow D\) (B 不是 key \(\rightarrow\) Not Pass ❌ ， 理由是 B 不能決定整個 R ，B 只能決定 D)

找到「亂源」後，我們需要把它移出去

1. 把 BD 獨立出去，也就是
   • \(R_1 = (B, D)\)
   • key 是 B ，因為 \(B \rightarrow\ D \)，所以符合 BCNF
2. 剩下的部分：拿原本的 \(R\)，扣掉箭頭右邊 (\(D\))，但保留左邊 (\(B\)) 當作連結點。
   • \(R_2 = (A, B, C, E)\)
   • ( 註：D 被移走了 )

---

檢查 \(R_2\) 有沒有亂源

1. 首先，我們要看看切割出去的 \(R_2\) 有哪些 FDs ?
   • \(A \rightarrow BC \) ( B 和 C 都還在，保留)
   • \(CD \rightarrow E\) (\(D\) 不在了，這條規則失效)
   • \(E \rightarrow A\) (E 和 A 都還在，保留)
   • \(B \rightarrow D\) (\(D\) 不在了，這條規則失效)
   • 因此我們只要注意 \(A \rightarrow BC \) 和 \(E \rightarrow A\) 就好
2. 再來找 \(R_2 = (A, B, C, E)\) 的「亂源」🧐
   • 先看 \(E \rightarrow A\) ; \(E \rightarrow A \rightarrow BC\)。所以 \(E\) 可以決定全部。 \(E\) 是 Key！
   • 再來是 \(A \rightarrow BC \) ， 但 \(A\) 沒辦法決定 \(E\)。所以 \(A\) 不是 Key！
     • 你可能會疑惑，A 不是可以決定 ABCDE 嗎 ?
     • 這是因為在這張小表裡 \(A \rightarrow BC\) 這是 ok 的。但如果要決定 E 必須要有 CD ( \(CD \rightarrow E\) )，可是 D 已經被罷免了，不在這張小表中，所以在 \(R_2\) 的範圍類 A 並不能決定 E。

找到亂源後，下一步是一分割出去

• 把 ABC 獨立出去
  • \(R_2 = (A, B, C)\)
  • Key 是 \(A\)。 (符合 BCNF ✅)
• 剩下的，拿 \((A, B, C, E)\) 扣掉 \(B\), \(C\)
  • \(R_3 = (A, E)\)
  • 規則剩 \(E \rightarrow A\)。Key 是 \(E\)。 (符合 BCNF ✅)

最後答案 :

1. \(R_1 = (B, D)\)
2. \(R_2 = (A, B, C)\)
3. \(R_3 = (A, E)\)

作業第 7 題

#

⛄題目 Decompose schema R into 3NF.

和上一題相似，只是換成 3NF

3NF 的邏輯很簡單：「每一條規則，都應該要有自己的家。」 這樣才能保證規則不會弄丟 (Dependency Preserving)。
🍡步驟 1 : 我們依照 箭頭左邊 (LHS) 來分組建表：

1. 針對 \(A \rightarrow BC\)：
   • 建立表格 \(R_1 = (A, B, C)\)
2. 針對 \(CD \rightarrow E\)：
   • 建立表格 \(R_2 = (C, D, E)\)
3. 針對 \(B \rightarrow D\)：
   • 建立表格 \(R_3 = (B, D)\)
4. 針對 \(E \rightarrow A\)：
   • 建立表格 \(R_4 = (E, A)\)

🍡步驟 2 : 檢查主鍵 (Check for Candidate Keys)
這一步是為了確保資料表能串聯起來 (Lossless Join)。 我們必須確認：「所有產生的表格中，至少有一個包含了原本大表的主鍵 (Superkey)。」

• 原本大表 \(R\) 的 Key：我們算過是 \( A^+ \) 、 \( E^+ \) 、 \( BC^+ \) 、 \( CD^+ \)。
• 檢查目前表格 :
  • \(R_1 (A, B, C)\) 裡面有 \(A\)。 (Pass ✅)
  • \(R_4 (E, A)\) 裡面有 \(E\)。 (Pass ✅)

🍘結論： 因為 \(R_1\) 和 \(R_4\) 已經包含了 Key，我們不需要額外新增一個只放 Key 的表格。 (註：如果這一步沒過，我們就要手動新增一個表格 \(R_{key} = (A)\) )

🍡步驟 3 : 清理子集
檢查有沒有哪個表格是別人的「完全子集」？如果是，就刪掉它（省空間）。

• \(R_3(B, D)\) 是 \(R_1(A, B, C)\) 的子集嗎？ -> 不是。
• \(R_3(B, D)\) 是 \(R_2(C, D, E)\) 的子集嗎？ -> 不是。
• \(R_4(E, A)\) 是 \(R_1(A, B, C)\) 的子集嗎？ -> 不是。

🍘結論： 沒有人可以被合併或刪除 。

最後答案 :

1. \(R_1 = (A, B, C)\)
2. \(R_2 = (C, D, E)\)
3. \(R_3 = (B, D)\)
4. \(R_4 = (E, A)\)

作業第 8 題

#

終於….😹 到了最後一題!!

⛄題目 In designing a relational database, why might we choose a non-BCNF design?

有兩個原因 :

1. 為了保存規則 (Dependency Preservation) —— 最主要的原因
2. 為了效能 (Performance / Avoid Joins)\
   • BCNF 傾向於把表格拆得非常細（Decomposition）。
     • 優點：沒贅肉，更新時不用擔心資料不一致。
     • 缺點：查詢 (SELECT) 時很痛苦。