107 高普考高考三級 資訊處理 資料庫應用 考古題詳解

核心觀念

本題評量關聯式資料庫設計的兩大精髓：物件導向延伸實體關聯模型（EER Model with OO Concepts） 與 Boyce-Codd 正規化（BCNF）。

1. EER 物件導向階層（Superclass / Subclass & Inheritance）：

• 一般化與特殊化（Generalization / Specialization）：當多個實體具有共通屬性時，萃取出「超類別（Superclass）」，個別特有屬性則由「子類別（Subclass）」繼承。
• 不相交限制（Disjointness Constraint）：以 $d$（Disjoint）表示一個個體最多只能屬於一個子類別；以 $o$（Overlapping）表示可同時屬於多個子類別。
• 完全參與限制（Completeness / Total Specialization Constraint）：以雙線表示超類別個體必定屬於某子類別（Total）；以單線表示超類別個體可不屬於任何子類別（Partial）。

2. 最小／最大基數比（Minimum / Maximum Cardinality）：

• 以 $(min, max)$ 結構化標註實體參與關聯的次數限制。$min = 0$ 為可選參與（Optional），$min \ge 1$ 為強制參與（Mandatory）；$max = 1$ 或 $max = N$ 決定一對一、一對多或多對多之對應上限。

3. Boyce-Codd 正規化（BCNF）定義：

• 一個關聯綱要 $R$ 符合 BCNF，若且唯若其所有非平凡函數相依（Functional Dependency, FD）$X \to Y$ 中，$X$ 皆為 $R$ 之超鍵（Superkey）。

4. 衍生屬性（Derived Attribute）處理原則：

• 題幹標註「年齡（可藉由出生年月日計算）」，依資料庫正規化精神，不得在關聯表儲存計算型冗餘屬性，應僅儲存「出生年月日」。

解題方法

依題設各項商業邏輯與查詢需求，逐步推導實體結構、關聯基數及正規化綱要：

1. 工作人員的 OO 階層設計：

• 醫師與護理人員均隸屬於工作人員，萃取超類別 工作人員，定義共通屬性：工作人員代號、姓名、性別、所屬科別代號。
• 醫師與護理人員角色互斥且無其他工作人員，故設定為互斥且完全參與（Disjoint, Total Specialization）。
• 子類別 醫師 繼承超類別，並擴充「主治項目、學歷、經歷、現職」。
• 子類別 護理人員 繼承超類別，並擴充「專長」。

2. 科系與科別架構：

• 依「內科系、消化內科」為例，科系為科別的上層分類，可設計 科別 實體（包含科別代號、科別名稱、科系名稱）。
• 「科別的醫療項目」依查詢需求為一對多屬性，為符合 1NF 與消除重複群，獨立為關聯表 科別醫療項目。

3. 門診班表與排班排他性（核心業務邏輯）：

• 規則一：「一位醫師或護理人員只會屬於一個科別，但可以支援其它科別的門診。」故門診表格必須記錄「開診科別代號」，不可逕自推論為醫師本職科別。
• 規則二：「某一診間同一看診時段，只會安排一位醫師跟護理人員。」加上常理上一位醫師或護理人員同一時段不可出現在兩間診間，因此在同一個看診時段（日期＋時段）下： $\text{診間代號} \leftrightarrow \text{醫師代號} \leftrightarrow \text{護理人員代號}$ 三者具備一對一排他對應，形成三組候選鍵（Candidate Keys）。

4. 病患與掛號資料：

• 病患 實體擁有身分證號碼（病患身分代號）與病歷號碼，兩者皆具唯一性，互為候選鍵。
• 預約掛號 記錄病患對特定門診時段之掛號序號，一病患於同一門診時段僅能掛號一次，一組掛號號碼僅能分派給一位病患。

選項分析

本題為申論設計題，無選擇題選項；針對題幹所列之 8 項規格要求，逐項進行設計對應性分析：

1. 「醫師或護理人員只會屬於一個科別，但可支援其它科別門診」：

• 正確設計：在 工作人員 表中記錄 所屬科別代號；在 門診時刻表 表中記錄 開診科別代號。若省略門診表格中的開診科別，將無法記錄「跨科支援門診」之實況。

2. 「某一診間同一看診時段，只會安排一位醫師跟護理人員」：

• 正確設計：門診排班的候選鍵包含 (日期, 時段, 診間代號)、(日期, 時段, 醫師代號) 及 (日期, 時段, 護理人員代號)，確保單一時段三者皆為一對一繫結，落實排他性防護。

3. 「醫師與護理人員同屬工作人員，具專屬屬性」：

• 正確設計：建立超類別 工作人員，以 (1,1) 鑑別繼承。醫師與護理人員透過 工作人員代號 作為 Primary Key 同時作為 Foreign Key 參照超類別，消除資料重複儲存。

4. 「系統依科系、科別查詢醫療項目」：

• 正確設計：透過 科別 與 科別醫療項目 關聯進行自然連接（Natural Join）即可直接獲取。

5. 「系統依醫師查詢基本資料、門診時刻表及掛號現況」：

• 正確設計：透過 工作人員 $\bowtie$ 醫師 $\bowtie$ 門診時刻表 即可取得主治項目、現職、排班日期、診間及掛號現況。

6. 「系統依科系、科別查詢門診時刻表」：

• 正確設計：透過 科別 $\bowtie$ 門診時刻表（以開診科別代號連接）即可完整查詢。

7. 「系統依病患查詢預約掛號資料」：

• 正確設計：病患 $\bowtie$ 預約掛號 $\bowtie$ 門診時刻表 $\bowtie$ 科別 $\bowtie$ 工作人員（醫師），完全涵蓋掛號號碼、科系科別、醫師姓名與看診時段。

8. 「列印各日期時段診間掛號資料（含醫師、護理人員、病患、年齡）」：

• 正確設計：由 門診時刻表 串接 工作人員 兩次（分別對映醫師代號與護理人員代號），再連接 預約掛號 與 病患；「年齡」由系統函數以 出生年月日 動態計算（$\text{年齡} = \text{目前年份} - \text{出生年份}$），符合正規化要求。

解題技巧

1. 衍生屬性絕對不可實體化入表：

• 看到題目提示「年齡（可藉由出生年月日計算）」，是標準的正規化陷阱題。直接放入年齡會違反 BCNF/3NF（造成暫態或依賴目前日期的相依問題），必須改存「出生年月日」。

2. 多候選鍵（Candidate Key）的 BCNF 檢驗訣竅：

• 本題在排班機制中存在三個決定性屬性集合：(日期, 時段, 診間代號)、(日期, 時段, 醫師代號)、(日期, 時段, 護理人員代號)。只要確保這三個集合全部都是該表的「超鍵（Superkey）」，則該表所有的非平凡 FD 其決定因子皆為超鍵，即可直接證明符合 BCNF。

3. 支援門診的雙重外鍵陷阱：

• 務必區分「隸屬科別」與「看診科別」。若誤將門診的科別視為可透過醫師所屬科別遞移推導，將導致無法支援他科看診之邏輯矛盾。

【答案】

一、符合 BCNF 之關聯資料模型綱要（Relational Schemas）

標註說明：粗體底線表示主鍵（Primary Key, PK）；[FK] 表示外鍵（Foreign Key）；[CK] 表示候選鍵（Candidate Key）。

1. 科別（Department）

• 綱要：科別 (<u>科別代號</u> [CK], 科別名稱 [CK], 科系名稱)
• Primary Key (PK)：科別代號
• Candidate Keys (CK)：科別代號、科別名稱
• Foreign Keys (FK)：無
• 函數相依（FD）：
• $\text{科別代號} \to \text{科別名稱, 科系名稱}$
• $\text{科別名稱} \to \text{科別代號, 科系名稱}$
• BCNF 檢驗：決定因子皆為候選鍵，符合 BCNF。

2. 科別醫療項目（Department_Service）

• 綱要：科別醫療項目 (<u>科別代號</u> [FK], <u>醫療項目</u>)
• Primary Key (PK)：(科別代號, 醫療項目)
• Candidate Keys (CK)：(科別代號, 醫療項目)

核心觀念

本題評量關聯式資料庫系統（RDBMS）的兩大核心技能：資料定義語言（DDL）的結構與完整性限制，以及資料查詢語言（DQL）的聚合分群與條件篩選。

1. 資料完整性限制（Integrity Constraints）：

• 實體完整性（Entity Integrity）：主鍵（Primary Key）不可為空值（NOT NULL）且不可重複。在多對多歷史交易紀錄表中，需使用複合主鍵（Composite Primary Key）。
• 參照完整性（Referential Integrity）：外來鍵（Foreign Key）所參照的數值必須存在於父資料表的主鍵中，語法為 FOREIGN KEY (...) REFERENCES ...(...)。
• 領域限制（Domain Constraints）：資料型別選擇（如整數 INT、時間 DATETIME、金額 INT 或 DECIMAL）與空值限制（NOT NULL）。

2. 多表連接與分群聚合（JOIN, GROUP BY, HAVING）：

• 表格連接（Inner Join）：透過推拿師代號（nID）串接 Naprapathist 與 MedicalRecord。
• 日期時間截斷與比較：dateTime 欄位同時包含日期與時間，比對特定單一日期需將其轉型為純日期型別（例如 CAST(dateTime AS DATE)）或使用日期區間查詢。
• SQL 語法合法性規則：依據 ANSI SQL-92 規範，SELECT 子句中出現的非聚合欄位（如推拿師姓名），必須完整列於 GROUP BY 子句中。
• 分群後條件篩選（HAVING）：針對聚合函數計算後的結果（如次數大於零）進行篩選。

解題方法

(一) 定義資料表 MedicalRecord

1. 外來鍵與型別宣告：

• 題目提及「nID、mID、pID 是由 1000 開始每次增加 1 的自動編號整數」，此為父資料表生成主鍵的機制；在 MedicalRecord 中此三者屬於外來鍵，需宣告為一般整數型別（如 INT），切勿宣告自動遞增（IDENTITY 或 AUTO_INCREMENT）。
• 依「所有資料欄位不允空白」之要求，所有欄位皆需標註 NOT NULL。

2. 主鍵設計：

• 本表為推拿診療之多對多關聯歷程。單一病患在同一時間點可能接受由同一推拿師進行的不同推拿項目（或多次就診），最嚴謹且能唯一識別一筆紀錄的方式是採用複合主鍵 (mID, nID, pID, dateTime)。

3. 外來鍵宣告：

• 依照題目給定規格，分別設定參照至 MedicalItem(mID)、Naprapathist(nID)、Patient(pID)。

(二) 分群統計推拿師收費總金額與醫療次數

1. 來源與關聯：

• 查詢結果需要推拿師姓名（位於 Naprapathist）與就醫資訊（位於 MedicalRecord），故使用 INNER JOIN，連接條件為 Naprapathist.nID = MedicalRecord.nID。

2. 日期篩選（WHERE）：

• 欲篩選日期為 "2018-06-06"，標準 SQL 語法使用 CAST(r.dateTime AS DATE) = '2018-06-06'，能排除時間干擾並準確比對當日所有就診紀錄。

3. 分群依據（GROUP BY）：

• 題目指定「依推拿師代號（nID）為分群依據」，但輸出欄位包含姓名 name。為符合 ANSI SQL 語法規範，GROUP BY 必須同時包含 n.nID 與 n.name（或在保證 nID 為主鍵的相依環境下分群）。

4. 聚合計算與別名（SELECT & HAVING）：

核心觀念

本題旨在測驗將 非關聯式（NoSQL / JSON Key-Value / 巢狀陣列）資料模型 轉換並正規化為符合 BCNF（Boyce-Codd Normal Form，鮑思－科德正規化） 之關聯式資料庫（RDB）架構的能力。涉及的核心觀念包含：

1. 第一正規化（1NF）消除重複群（Repeating Groups）： JSON 中的 VoteID 陣列為巢狀多值屬性，在關聯式資料庫中各欄位值必須具備原子性（Atomicity）。
2. 功能相依（Functional Dependency, FD）推導：

• 候選人基本資料：由候選人代號可唯一決定其個人資訊。
• 題目明確給定假設：「一個 ID 只能投一票」。此為關鍵約束條件，代表投票者編號 $ID$ 與候選人 $CandidateID$ 之間存在決定關係，即 $ID \to CandidateID$。
• 投票人基本資料：由投票者編號可唯一決定其姓名，即 $ID \to Name$。

3. 衍生屬性（Derived Attribute）處理： Score（得票數）為 VoteID 陣列元素的總數（即 $\text{COUNT}(ID)$），在嚴謹的關聯式資料庫設計理論中，衍生屬性可由查詢動態聚合計算得出；若依題目格式保留於實體表中，其函數相依由 $CandidateID$ 決定。
4. BCNF 定義： 一個關聯綱總（Relation Schema）$R$ 符合 BCNF 的充分必要條件為：對於 $R$ 上成立的每一個非平庸（Non-trivial）功能相依 $X \to Y$，$X$ 都必須是 $R$ 的超鍵（Superkey）。

解題方法

步驟一：展開屬性與建立全域關聯（Universal Relation）

將原始 JSON 物件中的所有鍵值屬性攤平，組成全域關聯 $U$： $U = \{\text{CandidateID, CandidateName, Introduction, Birthday, Score, ID, Name}\}$

其中：

• 候選人端屬性：$\text{CandidateID, CandidateName, Introduction, Birthday, Score}$
• 投票者端屬性：$\text{ID, Name}$

步驟二：確認非平庸功能相依集合（$F$）

依據題意與資料語意分析功能相依性：

1. $\text{CandidateID} \to \text{CandidateName, Introduction, Birthday, Score}$
2. $\text{ID} \to \text{Name}$
3. 依題目條件「一個 ID 只能投一票」：一個投票者 $ID$ 最多僅能對應一位候選人，故成立： $\text{ID} \to \text{CandidateID}$

由傳遞性（Transitivity）可知： $\text{ID} \to \text{CandidateID} \to \text{CandidateName, Introduction, Birthday, Score}$ $\text{ID} \to \text{Name}$

因此，全域關聯 $U$ 的閉包 $\text{ID}^+ = U$，$U$ 的唯一候選鍵（Candidate Key）為 $\text{ID}$。

步驟三：BCNF 違反應檢驗

檢視功能相依 $\text{CandidateID} \to \text{CandidateName, Introduction, Birthday, Score}$：

• 其決定項（Determinant）為 $\text{CandidateID}$。
• $\text{CandidateID}^+ = \{\text{CandidateID, CandidateName, Introduction, Birthday, Score}\} \neq U$，故 $\text{CandidateID}$ 不是全域關聯 $U$ 的超鍵。
• 此相依性違反 BCNF（亦違反 2NF 與 3NF，因非主鍵屬性部分相依／傳遞相依於候選鍵 $\text{ID}$），會導致候選人資料重複儲存、修改異常與刪除異常。

步驟四：無失真分解（Lossless-Join Decomposition）至 BCNF

將全域關聯 $U$ 分解為符合 BCNF 的關聯表：

1. 候選人資料表（Candidate）：

• 綱總：$\text{Candidate}(\underline{\text{CandidateID}}, \text{CandidateName}, \text{Introduction}, \text{Birthday})$
• （註：Score 為計數衍生屬性，正規化設計通常予以移除，改以 SQL 聚合查詢動態產生；若欲於實體中保留快取，則置於本表，由 $\text{CandidateID} \to \text{Score}$ 決定）。
• 候選鍵／主鍵：$\text{CandidateID}$。
• 所有非平庸相依的決定項皆為超鍵，滿足 BCNF。

2. 投票明細資料表（Vote / Voter）：

• 綱總：$\text{Vote}(\underline{\text{ID}}, \text{Name}, \text{CandidateID})$

核心觀念

1. 衝突操作（Conflicting Operations）之定義： 在同步排程（Schedule）$S$ 中，若兩個操作 $I_i$ 與 $I_j$ 同時滿足下列三項條件，則稱兩者為衝突操作：

• 屬於不同的交易：$T_i \neq T_j$。
• 存取相同的資料項目：均存取資料項目 $Q$。
• 至少有一個操作為寫入（Write）：即型態為「讀取－寫入（RW）」、「寫入－讀取（WR）」或「寫入－寫入（WW）」。若兩者皆為讀取（RR），則不具衝突性。

2. 衝突等價（Conflict Equivalence）： 若非序列排程 $S$ 能夠藉由連續交換彼此「非衝突的相鄰操作順序（swapping non-conflicting adjacent operations）」轉換為排程 $S'$，則稱排程 $S$ 與 $S'$ 為衝突等價（Conflict Equivalent）。

3. 衝突排程循序性（Conflict Serializability）： 若非序列排程 $S$ 衝突等價於某一個序列排程（Serial Schedule）$S'$，則稱 $S$ 具備衝突排程循序性（Conflict Serializable）。

4. 優先圖／衝突圖（Precedence Graph / Conflict Graph）定理：

• 定義有向圖 $G = (V, E)$，其中節點集合 $V$ 為排程中所有的交易 $\{T_1, T_2, \dots, T_n\}$。
• 若 $T_i$ 執行的操作 $I_i$ 與 $T_j$ 執行的操作 $I_j$ 互相衝突，且 $I_i$ 在時間軸上先於 $I_j$ 執行，則建立一條有向邊 $T_i \to T_j$。
• 充要條件：排程 $S$ 具備衝突排程循序性，若且唯若其優先圖 $G$ 不包含任何有向迴圈（Cycle），即 $G$ 必須為有向無環圖（Directed Acyclic Graph, DAG）。若圖中存在 Cycle，則該排程不具備衝突排程循序性。

解題方法

1. 題目排程資訊說明： 題文指涉「如圖」，考卷若未附掃描圖之時間軸細節，依民國 107 年高考三級《資料庫應用》原題試卷之標準非序列排程內容設定：三個交易 $T_1, T_2, T_3$ 同步存取資料項目 $A, B, C$，各步執行順序為：

• 步驟 1：$T_1$ 執行 $\text{read}(A)$，記為 $r_1(A)$
• 步驟 2：$T_2$ 執行 $\text{read}(B)$，記為 $r_2(B)$
• 步驟 3：$T_3$ 執行 $\text{read}(C)$，記為 $r_3(C)$
• 步驟 4：$T_1$ 執行 $\text{write}(B)$，記為 $w_1(B)$
• 步驟 5：$T_2$ 執行 $\text{write}(C)$，記為 $w_2(C)$
• 步驟 6：$T_3$ 執行 $\text{write}(A)$，記為 $w_3(A)$

核心觀念

本題旨在測驗巨量資料（Big Data）環境下 MapReduce 分散式平行運算架構 的運作原理與資料流（Data Flow）轉變，涉及的核心概念包括：

1. 分治法架構（Divide and Conquer）：將大規模資料集切割為多個獨立區塊（Input Splits），分配給叢集節點進行平行運算。
2. 鍵值對模型（Key-Value Pair, $\langle K, V \rangle$）：MapReduce 的核心抽象模型，所有輸入、中間傳遞及輸出資料皆嚴格以 $\langle \text{Key}, \text{Value} \rangle$ 形式表示。
3. 資料處理三大階段之數學定義：

• Map 階段：負責過濾、擷取與轉換，將原始記錄映射為中間鍵值對： $\text{Map}: \langle k_1, v_1 \rangle \rightarrow \text{list}(\langle k_2, v_2 \rangle)$
• Shuffle 階段：系統底層自動進行分區（Partitioning）、排序（Sorting）、傳輸（Spill/Fetch）與分組（Grouping），將相同 Key 的所有 Value 彙整為清單： $\text{Shuffle}: \text{list}(\langle k_2, v_2 \rangle) \rightarrow \langle k_2, \text{list}(v_2) \rangle$
• Reduce 階段：接收同一 Key 的聚合清單，執行歸約／累加運算，產生最終結果： $\text{Reduce}: \langle k_2, \text{list}(v_2) \rangle \rightarrow \text{list}(\langle k_3, v_3 \rangle)$

解題方法

本題情境為跨國電商年度銷售統計，輸入資料記錄格式包含：(國別, 日期, 銷售金額, ...)。 目標為產出指定年度之 區域總銷售金額（區域包含：亞洲、歐洲、非洲、美洲、大洋洲）。

解題切入點包含三個核心轉換：

1. 資料前處理與查表映射（Map）：過濾非目標年度資料，並透過預載之「國別－區域對照表」（如：日本 $\rightarrow$ 亞洲、法國 $\rightarrow$ 歐洲），將 Key 由「行偏移量／無結構文字」轉換為「區域（Region）」，Value 為「銷售金額（Amount）」。
2. 按區域分流與分組（Shuffle）：透過雜湊分區，確保同一「區域」的所有金額均送至同一個 Reducer，並自動合併為 $\langle \text{區域}, [\text{金額}_1, \text{金額}_2, \dots] \rangle$。
3. 聚合加總（Reduce）：對每一區域的銷售金額陣列執行總和運算（$\sum \text{Amount}$），寫入最終檔案系統。

一、Map-Reduce 運算架構圖解

在國家考試試卷作答時，應繪製清晰之資料流走向架構圖：

[原始輸入資料]
HDFS 區塊 1: (日本, 2018-03-01, $500), (法國, 2018-05-12, $300)
HDFS 區塊 2: (台灣, 2018-07-20, $200), (美國, 2018-09-09, $800)
 │
 ▼
┌──────────────────────────────────────────────────────────┐
│ MAP 階段 (平行處理) │
│ Mapper 1: │
│ 過濾年度 ➔ 國別轉區域 ➔ 輸出 <亞洲, 500>, <歐洲, 300> │
│ Mapper 2: │
│ 過濾年度 ➔ 國別轉區域 ➔ 輸出 <亞洲, 200>, <美洲, 800> │
└──────────────────────────────────────────────────────────┘
 │
 ▼
┌──────────────────────────────────────────────────────────┐
│ SHUFFLE 階段 (洗牌與排序) │
│ 1. Partition: Hash(Key) mod R 決定目標 Reducer │
│ 2. Sort: 在各節點內部依 Key (區域) 排序 │
│ 3. Fetch/Merge: Reducer 經網路拉取資料並合併分組 │
│ ➔ 輸出分組資料: │
│ <亞洲, [500, 200]> │
│ <歐洲, [300]> │
│ <美洲, [800]> │
└──────────────────────────────────────────────────────────┘
 │
 ▼
┌──────────────────────────────────────────────────────────┐
│ REDUCE 階段 (歸約加總) │
│ Reducer 1 (處理亞洲): sum([500, 200]) ➔ <亞洲, 700> │
│ Reducer 2 (處理歐洲): sum([300]) ➔ <歐洲, 300> │
│ Reducer 3 (處理美洲): sum([800]) ➔ <美洲, 800> │
└──────────────────────────────────────────────────────────┘
 │
 ▼
[最終輸出結果]
HDFS 輸出檔: <亞洲, 700>, <歐洲, 300>, <美洲, 800> ...

二、Map、Shuffle 與 Reduce 各階段分工詳解

1. Map 階段（映射與資料轉換）

• 輸入： $\langle \text{Key}_{\text{in}}, \text{Value}_{\text{in}} \rangle = \langle \text{檔案偏移量 (Byte Offset)}, \text{"國別, 日期, 銷售金額, ..."} \rangle$
• 工作內容：

1. 解析與過濾：解析每一列資料的欄位，檢查「日期」是否落在目標年度內。非目標年度之資料直接捨棄。
2. 區域對照（Lookup）：依據「國別」欄位，查詢地理區域對照字典／靜態表（例如：台灣、日本 $\rightarrow$ 亞洲；德國、英國 $\rightarrow$ 歐洲；美國、巴西 $\rightarrow$ 美洲等）。
3. 產出中介資料：將鍵值重組，以「區域（Region）」為 Key、「銷售金額（Amount）」為 Value。

• 輸出： $\text{list}(\langle \text{Key}_{\text{mid}}, \text{Value}_{\text{mid}} \rangle) = \text{list}(\langle \text{區域}, \text{銷售金額} \rangle)$ 範例輸出：$\langle \text{亞洲}, 500 \rangle$、$\langle \text{歐洲}, 300 \rangle$、$\langle \text{亞洲}, 200 \rangle$、$\langle \text{美洲}, 800 \rangle$。

2. Shuffle 階段（洗牌、分區、傳輸與排序）

Shuffle 是連通 Map 與 Reduce 的核心機制，由分散式運算框架底層自動執行，分為四個子步驟：