109 一般警察特考二等 刑事警察人員數位鑑識組 資料庫管理與運用 考古題詳解

核心觀念

本題旨在評量關聯式資料庫的正規化理論（Normalization Theory），涵蓋候選鍵（關聯鍵）的求解、各級正規化形式的定義與判定，以及無損連接分解（Lossless Join Decomposition）。核心定義如下：

1. 關聯鍵（Candidate Key）： 若屬性集合 $K$ 滿足：

• 超鍵性（Uniqueness）：其屬性閉包 $K^+$ 包含關聯綱目的所有屬性（$K^+ = R$）。
• 極小性（Minimality）：$K$ 的任何真子集合 $K' \subset K$ 之閉包皆無法涵蓋所有屬性（$K'^+ \neq R$）。

2. 多值相依（Multivalued Dependency, MVD）： $X \twoheadrightarrow Y$ 表示在給定 $X$ 的值時，一組 $Y$ 的值與其餘屬性相互獨立。多值相依不是函數相依（一個 $X$ 可對應多個相異的 $Y$），因此 $X$ 無法單獨以函數相依決定 $Y$。
3. 第 2 正規化（2NF）： 關聯綱目滿足 1NF，且每一個非主屬性（Non-prime attribute）均完全函數相依（Fully functionally dependent）於任一候選鍵（即消除非主屬性對候選鍵的部分函數相依 Partial Dependency）。
4. 第 3 正規化（3NF）： 關聯綱目滿足 2NF，且消除非主屬性對候選鍵的遞移函數相依（Transitive Dependency）。亦即對每一個非平凡函數相依 $X \rightarrow Y$，滿足 $X$ 為超鍵（Superkey），或 $Y$ 中的屬性皆為主屬性。
5. 第 4 正規化（4NF）： 關聯綱目滿足 3NF（或 BCNF），且對每一個非平凡多值相依 $X \twoheadrightarrow Y$，$X$ 必須為該關聯綱目的超鍵。

解題方法與詳細推導

（一）求關聯鍵（Candidate Key）

1. 列出所有屬性與相依性：

• 屬性集合：$U = \{callNumber, seqNum, author, title, publisherName, publisherAddress, publisherPhone, storeBranch\}$
• 函數相依（FD）與多值相依（MVD）：
• $f_1: callNumber \rightarrow \{title, publisherName\}$
• $f_2: publisherName \rightarrow \{publisherAddress, publisherPhone\}$
• $f_3: \{callNumber, seqNum\} \rightarrow storeBranch$
• $m_1: callNumber \twoheadrightarrow author$

2. 分析屬性位置：

• 檢查所有函數相依的右側（決定值）：
• 出現在右側的屬性：$\{title, publisherName, publisherAddress, publisherPhone, storeBranch\}$。
• 從未出現在任何函數相依右側的屬性：$callNumber$、$seqNum$、$author$。

備註：$author$ 僅出現在多值相依 $callNumber \twoheadrightarrow author$ 的右側。因多值相依代表一本書（$callNumber$）可有多位作者，在未經分解的扁平關聯中，$callNumber$ 並不能以函數相依唯一決定單一 $author$。因此，$author$ 無法被任何屬性函數決定。

• 任何候選鍵必須包含這些「未曾被函數決定」的屬性，故候選鍵必包含核心屬性集合：$K_{core} = \{callNumber, seqNum, author\}$

3. 計算閉包以驗證超鍵性：

• $\{callNumber, seqNum, author\}^+$ 的推導步驟：
• 起始集合：$\{callNumber, seqNum, author\}$
• 依 $f_1$ 加入 $title, publisherName$ $\rightarrow \{callNumber, seqNum, author, title, publisherName\}$
• 依 $f_2$ 加入 $publisherAddress, publisherPhone$ $\rightarrow \{callNumber, seqNum, author, title, publisherName, publisherAddress, publisherPhone\}$
• 依 $f_3$ 加入 $storeBranch$ $\rightarrow U$
• 因閉包涵蓋所有屬性，故 $\{callNumber, seqNum, author\}$ 為超鍵。

4. 驗證極小性（Minimality）：

• 移除 $author$：$\{callNumber, seqNum\}^+ = U \setminus \{author\} \neq U$（無法決定所有作者）。
• 移除 $seqNum$：$\{callNumber, author\}^+ = U \setminus \{seqNum, storeBranch\} \neq U$（無法決定館藏序列及所屬分館）。
• 移除 $callNumber$：$\{seqNum, author\}^+ = \{seqNum, author\} \neq U$。
• 任何真子集合皆無法擴展至全體屬性，故 $\{callNumber, seqNum, author\}$ 具備極小性。

5. 結論：關聯鍵為由 $\{callNumber, seqNum, author\}$ 三個屬性合成。

• 主屬性（Prime attributes）：$callNumber, seqNum, author$
• 非主屬性（Non-prime attributes）：$title, publisherName, publisherAddress, publisherPhone, storeBranch$

（二）分解成滿足 2NF 但不是 3NF 的關聯綱目

1. 辨識違反 2NF 的部分函數相依： 候選鍵為 $\{callNumber, seqNum, author\}$，檢視非主屬性是否相依於候選鍵的真子集合：

• $callNumber \subset \{callNumber, seqNum, author\}$，但： $callNumber \rightarrow \{title, publisherName, publisherAddress, publisherPhone\}$ 此為非主屬性對鍵的部分函數相依。
• $\{callNumber, seqNum\} \subset \{callNumber, seqNum, author\}$，但： $\{callNumber, seqNum\} \rightarrow storeBranch$ 此亦為非主屬性對鍵的部分函數相依。

2. 進行 2NF 分解（消除部分相依，但刻意保留遞移相依）：

• 將相依於 $\{callNumber, seqNum\}$ 的屬性獨立為一綱目： $B_1(\underline{callNumber, seqNum}, storeBranch)$ 主鍵為 $\{callNumber, seqNum\}$。

核心觀念

本題測驗關聯式資料庫系統架構的基礎理論——ANSI/SPARC 三層架構（Three-Level Architecture / Three-Schema Architecture）與資料抽象化（Data Abstraction）。

核心定義與理論依據包含：

1. 資料綱要（Schema）：指資料庫整體的邏輯與實體結構描述，不隨資料增刪而輕易變動。
2. 資料抽象化三層次：

• 外部層／外部模式（External Level / External Schema）：個別使用者的視圖（View）。
• 概念層／概念模式（Conceptual Level / Conceptual Schema）：資料庫全域的邏輯結構。
• 內部層／內部模式（Internal Level / Internal Schema）：資料在實體儲存媒體上的結構。

3. 資料獨立性（Data Independence）：上層模式不隨下層模式的修改而受到影響的能力，依賴兩層之間的「對應（Mapping）」機制達成。

解題方法

本題為標準的申論理論題，應採取「架構清晰、條列分明、圖示化表述、定義精準」的答題策略：

1. 第一子題（三種層次的模式）：採取由上至下（Top-Down）的邏輯順序，明確界定「外部模式」、「概念模式」與「內部模式」的定義、面向對象（使用者、DBA、作業系統/硬體）及其在系統中的數量關係。
2. 第二子題（建立三層模式的目的）：直擊資料庫設計的核心價值——「資料獨立性（Data Independence）」，並拆解為「邏輯資料獨立性」與「實體資料獨立性」進行論述；再輔以安全控管、降低維護負擔、支援多使用者檢視等實務目的，展現警政與數位鑑識領域所需的系統化思維。

選項分析

本題為申論題，無選擇題選項。以下針對考生作答時最容易混淆的關鍵對應概念進行深入對比分析：

1. 外部模式 vs. 概念模式 vs. 內部模式的數量與範疇差異：

• 外部模式（External Schema）：可有多個。每個外部模式是概念模式的一個子集（Subschema），針對不同使用者族群量身打造，具備存取權限控管與視圖隔離功能。
• 概念模式（Conceptual Schema）：整個資料庫系統僅有一個。它涵蓋所有實體、屬性、關聯與完整性限制條件，完全獨立於硬體儲存細節與應用程式。
• 內部模式（Internal Schema）：整個資料庫系統僅有一個。它描述資料在硬碟上的配置、索引結構（如 B+ Tree、Hash）、壓縮演算法、指標與記錄長度等底層實作。

2. 邏輯資料獨立性 vs. 實體資料獨立性之對應：

• 邏輯資料獨立性（Logical Data Independence）：對應「外部模式／概念模式對應（External/Conceptual Mapping）」。當概念層變更（如擴充新欄位、拆分表格），只需修改此對應，外部應用程式與使用者視圖無需改寫。
• 實體資料獨立性（Physical Data Independence）：對應「概念模式／內部模式對應（Conceptual/Internal Mapping）」。當內部層變更（如重組索引、更換儲存磁區），概念層與上層應用程式完全不受影響。

解題技巧

1. 口訣記憶法：記住「外、觀、內」（External, Conceptual, Internal）三層結構，由高層至底層分別對應「使用者、設計師、硬碟機」。
2. 常見扣分陷阱：

• 混淆兩種獨立性：常有考生將「更改硬碟索引不影響概念層」誤寫為邏輯資料獨立性。務必牢記：更動底層實體結構而概念層不變，稱為「實體資料獨立性」；更動概念結構而外部程式不變，稱為「邏輯資料獨立性」。

核心觀念

本題評量資料庫實體層中**雜湊式檔案組織（Hashed File Organization）**的核心定址演算與溢位處理機制，涉及觀念如下：

1. 儲存架構階層：主儲存空間被劃分為多個可直接定址的儲存桶（Bucket），每個儲存桶內部可容納固定數量 $s$ 的儲存槽（Slot），每個儲存槽存放一筆資料錄（Record）。
2. 雜湊函數與除餘法（Division Method）：雜湊函數 $h(K)$ 將搜尋鍵值（Search Key）$K$ 映射到儲存桶位址。除餘法公式為： $h(K) = K \pmod M$ 其中 $M$ 為儲存桶總數。
3. 碰撞（Collision）與溢位（Overflow）：

• 碰撞：兩個相異鍵值經雜湊運算後映射至相同儲存桶，即 $h(K_1) = h(K_2)$（$K_1 \neq K_2$），此時 $K_1$ 與 $K_2$ 互為同義字（Synonyms）。
• 溢位：當某儲存桶內的所有儲存槽均已被佔滿，又有新的同義字記錄映射至該桶時，即產生溢位。

4. 鏈結式溢位處理（Chaining Techniques）：

• 分別鏈結（Separate Chaining）：各儲存桶之溢位記錄存放於獨立的外部溢位空間，以專屬指標串列鏈結。
• 合併鏈結（Coalesced Chaining）：將溢位記錄配置於主雜湊表本身的空槽內，致使不同雜湊位址的串列可能共用節點而產生「鏈結合併（Coalescing）」現象。

解題方法

第一子題：除餘法（Division/Remainder method）的主要步驟

除餘法為實務上最普遍且計算成本最低的雜湊演算法，其完整執行步驟如下：

1. 鍵值轉換與數值化（Key Conversion）

• 若搜尋鍵值 $K$ 為非整數型態（如字串、複合欄位），先將其各字元（如 ASCII 或 Unicode）編碼轉換，透過多項式摺疊或加權位移，轉換為一個非負大整數。

2. 選定模數 $M$（Modulus Selection）

• 決定儲存桶位址空間的大小 $M$。
• 選定準則：$M$ 應選取小於或等於可用儲存空間的最大質數（Prime Number），且嚴格避開接近 2 的冪次方（$2^p$）或 10 的冪次方（$10^p$）。
• 原因：若 $M = 2^p$，則 $K \pmod M$ 的結果僅取決於 $K$ 二進位表示法的最後 $p$ 個位元，會忽略高位元的所有特徵，導致資料分布嚴重不均；若選用質數，可打破輸入鍵值的公因數規律，使雜湊值呈均勻分布（Uniform Distribution）。

3. 執行除餘運算（Modulo Computation）

• 將數值化鍵值 $K$ 除以 $M$ 取其餘數： $h(K) = K \pmod M$
• 運算所得的 $h(K)$ 即為目標儲存桶的索引編號，其取值範圍為整數區間 $[0, M-1]$（若系統位址採 1-based 索引，則計算公式調整為 $(K \pmod M) + 1$）。

4. 定址與指派儲存槽（Bucket & Slot Assignment）

• 系統依據 $h(K)$ 直接計算實體磁區位址，讀取該儲存桶。
• 檢查該桶內是否有空閒儲存槽（Slot）：若有，則將資料錄寫入該槽；若所有儲存槽皆滿，則觸發溢位處理機制。

第二子題：合併鏈結（Coalesced Chaining）與分別鏈結（Separate Chaining）之技巧

1. 分別鏈結（Separate Chaining，又稱分立鏈結/外鏈法）

• 架構設計：
• 主雜湊表只維護儲存桶的基本結構，每個儲存桶包含一個指標欄位（Pointer），指向一個獨立的單向鏈結串列（Linked List）。
• 串列的節點存放於主檔案區之外的獨立動態記憶體空間或專用溢位檔案區（Overflow Area）。
• 運作技巧：
• 插入：當計算得 $h(K) = i$ 且第 $i$ 號桶發生溢位時，系統在外部溢位區動態配置一個新節點，寫入該資料錄，並將該節點掛載至第 $i$ 號桶的串列首部（Header）或尾部。
• 搜尋：計算 $h(K) = i$，先檢索第 $i$ 號桶內部儲存槽；若未命中，循著該桶的指標走訪專屬溢位串列，直至找到目標或指標為空（Null）。

核心觀念

本題考「概念模式的使用者觀點」：同一個公司的整體概念模式，依不同部門的業務需求，取出相關實體及其關係，形成各部門使用的局部概念模式。方框是實體，箭線表示資料間的邏輯結合方向；箭線本身不代表一對一或一對多的基數。

解題方法

先依部門的工作內容篩選實體，再保留這些實體在原圖中的直接關係：

• 銷售處理客戶訂單及產品。
• 會計處理客戶發票及產品。
• 採購處理供應商、原料及產品。
• 工作單屬生產作業，題目未指定生產使用者觀點，因此不納入這三個部門的局部模式。

依此可畫出：

一、銷售使用者觀點

flowchart LR
 客戶 --> 訂單 --> 產品