108 高普考高考二級 資訊處理 高等資料庫設計 考古題詳解

核心觀念

本題考核關聯式資料庫設計前期的概念綱要設計（Conceptual Schema Design），核心技術為陳氏實體關聯模型（Chen's Entity-Relationship Model）​及其延伸擴充。解題時涉及的定義與規範如下：

1. 實體型態（Entity Types）：

• 現實世界中可獨立辨識的物件集合，在 ER 圖中以矩形表示。
• 鍵屬性（Key Attribute）：能唯一識別實體的屬性，以實線底線標示。

2. 屬性分類（Attribute Types）：

• 單值屬性（Single-valued Attribute）：每個實體在此屬性上僅有單一值，以單線橢圓表示。
• 多值屬性（Multivalued Attribute）：單一實體在此屬性上可具備多個值（例如：多個電子郵件信箱），在陳氏模型中嚴格規定以雙線橢圓表示。

3. 關聯型態（Relationship Types）：

• 多個實體之間的互動或隸屬關係，在 ER 圖中以菱形表示。

4. 結構限制（Structural Constraints）：

• 基數比（Cardinality Ratio）：描述參與關聯的實體個數上限，包含一對一（$1:1$）、一對多（$1:N$）、多對多（$M:N$）。
• 參與限制（Participation Constraint）：實體的存在是否強制依賴該關聯。完全參與（Total Participation）​以雙線連接實體與關聯（表示每個實體都必須參與）；部分參與（Partial Participation）​以單線連接。

5. 描述性屬性（Descriptive / Relationship Attributes）：

• 附著於關聯型態本身的屬性。當屬性無法由單一實體決定、而必須由參與關聯的實體共同決定時（例如：學生的修課成績），該屬性必須置於關聯上。

解題方法

採用「由語意規格映射至資料塑模元件」由上而下的系統化切入法，依題目需求逐段拆解：

1. 需求 1 剖析（學院與院長）：

• 實體：SCHOOL。
• 屬性：sch-id（主鍵）、sch-name。
• 關聯：SCHOOL 與 PROFESSOR 存在「領導/院長（Dean）」關聯。每一學院必有一位院長，且由一名教授擔任，故此關聯為 $1:1$；SCHOOL 端為完全參與（雙線，每個學院都有院長），PROFESSOR 端為部分參與（單線，並非每位教授都是院長）。

2. 需求 2 剖析（學院、學系與課程）：

• 實體：DEPARTMENT、COURSE。
• 屬性：
• DEPARTMENT：dept-id（主鍵）、dept-name。
• COURSE：crs-id（主鍵）、crs-name、crs-descript、crs-credit。
• 關聯：
• SCHOOL 與 DEPARTMENT：組成（Has_Dept）關聯，基數比為 $1:N$（一學院有多學系，一學系屬於一學院）。
• DEPARTMENT 與 COURSE：開課所屬（Offers）關聯，基數比為 $1:N$（一學系開多門課，一課程僅由一學系開授）。

3. 需求 3 剖析（學生與多值屬性）：

• 實體：STUDENT。
• 屬性：stud-id（主鍵）、stud-name、stud-email。
• 特殊約束：題目明示「有學生可能會有多個電子信箱」，故 stud-email 判定為多值屬性（Multivalued Attribute）。
• 關聯：DEPARTMENT 與 STUDENT 存在學籍隸屬（Enroll）關聯，基數比為 $1:N$（一學系有多名學生，一學生隸屬一學系）。

4. 需求 4 剖析（教授與學系）：

• 實體：PROFESSOR。
• 屬性：prof-id（主鍵）、prof-name、prof-rank。
• 關聯：DEPARTMENT 與 PROFESSOR 存在聘任（Employs）關聯，基數比為 $1:N$（一學系有多名教授，一教授僅隸屬於一學系）。

5. 需求 5 剖析（授課與指導關係）：

• 關聯一（開課/授課，Teaches）：PROFESSOR 與 COURSE，一教授可開多門課，一門課只能由一教授開課，基數比為 $1:N$。
• 關聯二（指導，Advises）：PROFESSOR 與 STUDENT，一教授可指導多個學生，一學生僅被一個教授指導，基數比為 $1:N$。

6. 需求 6 剖析（學生修課與成績）：

• 關聯：STUDENT 與 COURSE 存在修課（Takes）關聯，學生可修多門課，課程可由多位學生修習，基數比為 $M:N$。
• 關聯屬性：成績（grade）取決於特定學生修習特定課程的表現，為多對多關聯上的描述性屬性。

解題技巧

1. 多值屬性的圖示規範： 公職國考閱卷時，陳氏模型符號極為嚴格。stud-email 切勿畫成一般單線橢圓，必須使用雙線橢圓。若轉換為關聯綱要（Relational Schema），多值屬性會獨立拆成新資料表，故此處是拿分與失分的鑑別點。
2. 區分「學系開課」與「教授授課」雙重路徑： 題目第 2 點指出「一課程僅由一學系開授」，第 5 點又指出「一門課只能由一教授開課」。這代表在資料結構中，COURSE 分別與 DEPARTMENT 及 PROFESSOR 各有一條獨立的 $1:N$ 關聯線，不可擅自合併或省略任何一方。
3. 關聯屬性歸屬判斷： 成績 grade 絕不可置於 STUDENT 實體（否則無法記錄不同課程成績）或 COURSE 實體（否則無法記錄不同學生成績），必須直接掛在 Takes 菱形關聯上。
4. 完全參與的線條標記：

核心觀念

本題評量關聯式資料庫（Relational Database）的基礎理論與查詢處理核心架構，主要涵蓋三大主軸：

1. 關聯式模型（Relational Model）之三要素：依據 E. F. Codd 的定義，關聯模型由「資料結構（Data Structure）」、「資料完整性限制（Data Integrity Constraints）」以及「運算子（Operators / Relational Algebra）」構成。
2. SQL 執行生命週期（Query Processing Pipeline）：SQL 為宣告式（Declarative）語言，使用者僅指定「要什麼（What）」而非「如何做（How）」。查詢處理器必須歷經剖析（Parsing）、轉譯（Translation）、最佳化（Optimization）、代碼生成（Code Generation）與執行引擎（Execution Engine）調度等程序。
3. 查詢最佳化（Query Optimization）原理：區分為「啟發式規則最佳化（Heuristic / Rule-Based Optimization, RBO）」與「成本式最佳化（Cost-Based Optimization, CBO）」。前者基於關聯代數等價變換定理（Equivalence Rules）減少中間產物；後者依據資料庫目錄統計值（Catalog Statistics）建立成本函數（包含 I/O 與 CPU 成本）進行評估。

解題方法

本題採「由整體到局部、結構化拆解」方式作答：

1. 要素拆解法：依據題目要求的「基本結構」、「限制」、「運算」三層次，分別列舉正式數學定義與資料庫實務對應概念（如 Relation 對應 Table、Tuple 對應 Row 等）。
2. 流程管線法：以管線架構（Pipeline Architecture）依序說明 SQL 語句從原始文字（Textual Query）被轉換為抽象語法樹（AST）、邏輯查詢計畫（Logical Query Plan / Relational Algebra Tree），再經最佳化轉為實體查詢計畫（Physical Execution Plan），最後由儲存引擎讀取資料塊的過程。
3. 最佳化雙軌比較法：將最佳化原理劃分為「代數重寫（邏輯層次）」與「成本估算（實體演算法層次）」，系統化闡明啟發式原則（如及早選擇、及早投影）與成本公式的評估機制。

選項分析

本題為高考二級之申論申論題型，無選擇題選項。考生應特別注意專有名詞的定義邊界，避免常見觀念混淆：

• 結構層面：不可將「綱要（Schema，型態與結構）」與「實例（Instance，特定時間點的資料集合）」混為一談。
• 限制層面：務必區分「實體完整性（主鍵不為 Null 且唯一）」與「參照完整性（外部鍵需存在或為 Null）」的不同保護目的。
• 運算層面：基本運算（Primitive Operations）僅有五或六種（$\sigma, \pi, \cup, -, \times, \rho$），合併（$\bowtie$）與交集（$\cap$）均為衍生運算。

解題技巧

1. 記憶口訣：

• 關聯要素：「結・限・算」（結構、限制、運算）。
• 查詢執行流程：「析・譯・佳・碼・執」（剖析 $\rightarrow$ 轉譯 $\rightarrow$ 最佳化 $\rightarrow$ 編碼/計畫 $\rightarrow$ 執行）。
• 啟發式最佳化金律：「及早過濾、縮減規模」（Pushdown Selection & Projection）。

2. 評分關鍵：申論「查詢最佳化」時，切忌只回答概念性文字。必須寫出關聯代數變換範例（如 $\sigma_{C}(R \bowtie S) \equiv (\sigma_{C}(R)) \bowtie S$）及成本模型所考量的統計參數（如元組數 $N_R$、區塊數 $B_R$、相異值數 $V(A, R)$），方能拿下高分。

【答案】

一、關聯式資料庫模型的組成要素（Components）

關聯式資料庫模型奠基於集合論與一階述詞邏輯，主要由三大部分組成：

1. 基本結構或概念（Basic Constructs or Concepts）

• 領域（Domain, $D$）：一組不可分割（Atomic）的純量值集合，定義屬性的取值範圍與資料型態。
• 屬性（Attribute, $A_i$）：關聯中的具名欄位（Column），代表領域在該關聯中所扮演的角色。關聯所含屬性的個數稱為維度（Degree）。
• 元組（Tuple, $t$）：關聯中的一筆記錄（Row），由一組 $\langle\text{屬性}, \text{值}\rangle$ 序對組成，形式為 $t = \langle v_1, v_2, \dots, v_n \rangle$，其中 $v_i \in \text{Domain}(A_i)$。
• 關聯綱要（Relation Schema, $R(A_1, A_2, \dots, A_n)$）：定義關聯的名稱及其屬性清單，屬於靜態的結構定義。
• 關聯實例（Relation Instance, $r(R)$）：特定時間點下，該關聯所包含之元組的有限集合，$r(R) \subseteq D_1 \times D_2 \times \dots \times D_n$。其元組總數稱為基數（Cardinality）。

2. 限制（Constraints）

• 領域限制（Domain Constraint）：每個元組在屬性 $A_i$ 上的值，必須落在該屬性所定義的領域範圍內，且必須為原子值（滿足第一正規化 1NF）。
• 超鍵與候選鍵限制（Key Constraints）：
• 超鍵（Superkey）：能唯一識別關聯中特定元組的一組屬性集合。
• 候選鍵（Candidate Key）：具極小性（Minimality）的超鍵，移除任一屬性即失去唯一識別能力。
• 實體完整性限制（Entity Integrity Constraint）：關聯的主鍵（Primary Key）屬性在任何情況下皆不得為空值（NOT NULL），且數值必須唯一，確保每一筆實體記錄皆可被明確辨認。
• 參照完整性限制（Referential Integrity Constraint）：用於維護關聯間的父子關係。若關聯 $R_1$ 中的外部鍵（Foreign Key, $FK$）參照至關聯 $R_2$ 的主鍵（$PK$），則 $R_1$ 中 $FK$ 的數值必須要麼等於 $R_2$ 某元組的 $PK$ 值，要麼全為空值（NULL）。
• 語意或企業限制（Semantic / Enterprise Constraints）：依業務邏輯自訂的條件約束，例如利用 CHECK 限制員工薪資必須大於基本工資。

3. 運算（Operations）

• 關聯代數運算（Relational Algebra Operations）：
• 基本運算（Fundamental Operations）：
• 選擇（Selection, $\sigma_\theta(R)$）：依條件 $\theta$ 水平篩選符合的元組。
• 投影（Projection, $\pi_L(R)$）：垂直選取屬性清單 $L$ 所指定的欄位，並去除重複元組。
• 聯集（Union, $R \cup S$）：合併兩相容關聯的元組。
• 差集（Set Difference, $R - S$）：求存在於 $R$ 但不存在於 $S$ 的元組集合。
• 卡氏積（Cartesian Product, $R \times S$）：將兩關聯所有元組進行兩兩配對組合。
• 重新命名（Rename, $\rho_S(R)$ 或 $\rho_{S(B_1, \dots, B_n)}(R)$）：重新命名關聯或屬性。
• 衍生運算（Derived Operations）：包含交集（Intersection, $\cap$）、自然合併（Natural Join, $\bowtie$）、條件合併（Theta Join, $\bowtie_\theta$）及除法（Division, $\div$）。

核心觀念

order 3 的 B-tree 每個節點最多有 3 個子節點、2 個鍵值；非根節點至少有 1 個鍵值。節點內的鍵值依序排列，子樹鍵值則落在相鄰分隔鍵值所界定的範圍內。

插入時，鍵值放入適當葉節點；節點超過 2 個鍵值時，將中間鍵值往上提升。刪除內部節點的鍵值時，以前驅或後繼替換，再從葉節點刪除；若節點因此低於最少鍵值數，便透過合併或借鍵修復。

解題方法

（A）插入 62

原圖右側葉節點為 $[65,68]$。插入 62 後成為 $[62,65,68]$，超過每個節點最多 2 個鍵值，因此提升中間鍵值 65：

• 原根節點 $[40,60]$ 接收 65，成為 $[40,60,65]$，仍超過上限。
• 提升中間鍵值 60 成為新根；左右分別形成內部節點 $[40]$、$[65]$。

 [60]
 / \
 [40] [65]
 / \ / \
 [30] [50] [62] [68]

（B）刪除 30

核心觀念

本題評量關聯式資料庫理論中「關聯綱要設計」與「資料庫正規化（Database Normalization）」之核心能力，包含以下重點：

1. 屬性閉包（Attribute Closure, $X^+$）與候選鍵（Candidate Key）：

• 閉包 $X^+$ 為在功能相依集合 $F$ 下，可由屬性集合 $X$ 邏輯推導出的所有屬性集合。
• 若 $X^+ = R$，則 $X$ 為超鍵（Super Key）；若 $X$ 的任何真子集之閉包皆無法涵蓋 $R$（滿足極小性 Minimality），則 $X$ 為候選鍵（Candidate Key），在資料庫綱要中亦常簡稱為鍵（Key）。

2. 正規格式定義（Normal Forms）：

• 第一正規化（1NF）：所有屬性值皆為不可再分割的原子值（Atomic Values）。
• 第二正規化（2NF）：符合 1NF，且消除「部分功能相依（Partial Functional Dependency）」，即所有非主屬性（Non-prime Attributes）必須完全相依於任一候選鍵。
• 第三正規化（3NF）：符合 2NF，且消除「遞移功能相依（Transitive Functional Dependency）」，即非主屬性之間不可存在功能相依。正規定義為：對於 $F$ 中所有非平凡相依 $X \rightarrow Y$，$X$ 必須為超鍵，或者 $Y$ 的每個屬性皆為主屬性。
• BCNF（Boyce-Codd Normal Form）：比 3NF 更嚴格，消除所有非超鍵為決定子（Determinant）的相依關係。

3. 無失真連接（Lossless Join）與相依性保留（Dependency Preservation）：

• 良好的關聯分割必須在保證資料連接無失真的前提下，完整保留原有的功能相依關係。

解題方法

第一小題：求 $R$ 的鍵值（Key）

利用屬性分類法分析功能相依集合 $F$： $F = \{\{A,B\}\rightarrow\{C\}, \{A\}\rightarrow\{D,E\}, \{B\}\rightarrow\{F\}, \{F\}\rightarrow\{G,H\}, \{D\}\rightarrow\{I,J\}\}$

1. 屬性位置分類：

• 僅出現在左側（L）：$A, B$
• 僅出現在右側（R）：$C, E, G, H, I, J$
• 兩側皆出現（LR）：$D, F$

2. 推論候選鍵的核心集合：

• 屬性 $A$ 與 $B$ 從未出現在任何功能相依的右側，代表沒有任何其他屬性可以決定 $A$ 或 $B$。
• 因此，$A$ 與 $B$ 必然屬於 $R$ 的每一個候選鍵中。

3. 計算閉包 $\{A, B\}^+$：

• 初始集合：$\{A, B\}^{(0)} = \{A, B\}$
• 套用 $\{A, B\} \rightarrow \{C\}$：$\{A, B, C\}$
• 套用 $\{A\} \rightarrow \{D, E\}$：$\{A, B, C, D, E\}$
• 套用 $\{B\} \rightarrow \{F\}$：$\{A, B, C, D, E, F\}$
• 套用 $\{F\} \rightarrow \{G, H\}$：$\{A, B, C, D, E, F, G, H\}$
• 套用 $\{D\} \rightarrow \{I, J\}$：$\{A, B, C, D, E, F, G, H, I, J\} = R$

4. 結論： $\{A, B\}^+ = R$，且其任何真子集（$\{A\}^+ = \{A, D, E, I, J\} \neq R$、$\{B\}^+ = \{B, F, G, H\} \neq R$）均無法推得完整屬性集合。 因此，$R$ 唯一的候選鍵（Key）為 $\{A, B\}$。

第二小題：刪除遞移依附性的正規格式

根據關聯式資料庫正規化階層定義：

• 2NF 主要解決「部分相依（Partial Dependency）」。
• 第三正規化（3NF, Third Normal Form） 之核心目標即為消除「遞移相依（Transitive Dependency）」。

因此，將 $R$ 分割至第三正規格式（3NF）​可以刪除遞移依附性。

第三小題：將 $R$ 分割至第三正規格式（3NF）

本題可採用循序分解法（先達 2NF 再達 3NF）或 3NF 合成演算法（Bernstein's Synthesis Algorithm），兩者所得結果一致。

步驟一：識別違反各級正規化的功能相依

• 主屬性（Prime Attributes）：$A, B$
• 非主屬性（Non-prime Attributes）：$C, D, E, F, G, H, I, J$
• 違反 2NF 之部分相依：