110 調查局特考三等 資訊科學組 資料庫應用 考古題詳解

核心觀念

本題考查 ER Model 中的：

1. 強實體型態（Strong Entity Type）
2. 弱實體型態（Weak Entity Type）
3. 主鍵（Primary Key）與部分鍵（Partial Key）
4. 識別關係（Identifying Relationship）
5. 基數限制（Cardinality Constraint）
6. 參與限制（Participation Constraint），即全參與與部分參與
7. 一對多關係與多對多關係的判斷

判斷原則如下：

• 強實體具有自己的完整主鍵，可獨立由主鍵識別。
• 弱實體不能獨立存在，必須依附於某一強實體；其識別通常由「擁有者主鍵＋弱實體部分鍵」共同組成。
• 「必須隸屬」表示全參與，最小基數為 $1$。
• 「可以沒有」表示部分參與，最小基數為 $0$。
• 「許多」表示最大基數為 $N$。
• 「一」表示最大基數為 $1$。

---

解題方法

先將名詞分成實體，再從需求逐一判斷：

1. 找出各實體及其屬性。
2. 找出每個實體的識別屬性。
3. 判斷哪些實體不能單獨存在，以決定弱實體。
4. 依「一方」與「多方」標示基數。
5. 依「必須」與「可以沒有」標示參與限制。
6. 將多對多關係保留為 M:N 關係，日後轉換成關聯式資料庫時再建立關聯表。

---

一、實體型態與屬性

1. BANK：強實體型態

銀行具有自己的銀行代碼，可獨立識別不同銀行。

• Code：主鍵
• Name
• Addr

表示為：

$$BANK(\underline{Code}, Name, Addr)$$

其中 Code 為主鍵。

---

2. BANK-BRANCH：弱實體型態

需求明確指出：

一分行不能單獨存在，一定要隸屬於某一銀行。

因此，分行具有存在依賴性，必須依附 BANK，適合設計為弱實體型態。

• BranchNo：部分鍵
• BranchAddr

分行的完整識別鍵為：

$$(Code, BranchNo)$$

其中：

• Code 來自擁有者實體 BANK
• BranchNo 是分行在同一銀行中的部分鍵

---

3. ACCOUNT：強實體型態

需求指出帳戶編號用以區別不同帳戶，因此 AcctNo 可作為完整主鍵。

• AcctNo：主鍵
• Balance
• Type

表示為：

$$ACCOUNT(\underline{AcctNo}, Balance, Type)$$

帳戶雖然必須隸屬於分行，但其本身已有完整識別鍵 AcctNo，因此依題目所給的識別條件，設計為強實體型態；帳戶與分行之間以全參與關係表示其存在依賴。

---

4. CUSTOMER：強實體型態

客戶具有自己的客戶代碼，可獨立識別。

• SSN：主鍵
• CustName
• Phone
• CustAddr

表示為：

$$CUSTOMER(\underline{SSN}, CustName, Phone, CustAddr)$$

---

5. LOAN：強實體型態

貸款編號用以區別不同貸款，因此 LoanNo 可作為完整主鍵。

• LoanNo：主鍵
• LoanType
• Amount

表示為：

$$LOAN(\underline{LoanNo}, LoanType, Amount)$$

---

二、各關係與限制

1. BANK — HAS-BRANCH — BANK-BRANCH

需求：

• 一銀行可以沒有分行。
• 一分行一定要隸屬於某一銀行。
• 一銀行可以有許多分行。
• 分行不能脫離銀行單獨存在。

因此：

• BANK 端：$0..N$
• BANK-BRANCH 端：$1..1$
• BANK-BRANCH 對關係為全參與
• BANK 對關係為部分參與
• 這是弱實體的識別關係

基數表示：

$$BANK\ 0..N \longleftrightarrow 1..1\ BANK\text{-}BRANCH$$

其識別鍵為：

$$BANK\text{-}BRANCH\text{ 的鍵}=(Code, BranchNo)$$

---

2. BANK-BRANCH — HAS-ACCOUNT — ACCOUNT

需求：

• 一分行可以有許多帳戶。
• 一分行可以沒有帳戶。
• 每一帳戶必須隸屬於某一分行。

因此：

• BANK-BRANCH 端：$0..N$
• ACCOUNT 端：$1..1$
• ACCOUNT 為全參與
• BANK-BRANCH 為部分參與

基數表示：

$$BANK\text{-}BRANCH\ 0..N \longleftrightarrow 1..1\ ACCOUNT$$

---

3. CUSTOMER — OWNS — ACCOUNT

需求：

• 一客戶可以擁有多個帳戶。
• 一帳戶可以由多個客戶共同擁有。
• 一帳戶必須至少有一位客戶擁有。
• 客戶可以沒有帳戶。

因此這是多對多關係：

• CUSTOMER 端：$0..N$
• ACCOUNT 端：$1..N$
• ACCOUNT 為全參與
• CUSTOMER 為部分參與

基數表示：

$$CUSTOMER\ 0..N \longleftrightarrow 1..N\ ACCOUNT$$

特別注意，帳戶端不是 $1..1$，因為題目明確允許一帳戶由多個客戶共同擁有。

---

4. BANK-BRANCH — HAS-LOAN — LOAN

需求：

• 一分行可以有許多貸款。
• 一分行可以沒有貸款。
• 每一筆貸款必須隸屬於某一分行。

因此：

• BANK-BRANCH 端：$0..N$
• LOAN 端：$1..1$
• LOAN 為全參與
• BANK-BRANCH 為部分參與

基數表示：

$$BANK\text{-}BRANCH\ 0..N \longleftrightarrow 1..1\ LOAN$$

---

5. CUSTOMER — BORROWS — LOAN

需求：

• 一客戶可以有多筆貸款。
• 一筆貸款可以由多個客戶共同借貸。
• 一筆貸款至少必須有一位客戶。
• 客戶可以沒有貸款。

因此這也是多對多關係：

• CUSTOMER 端：$0..N$
• LOAN 端：$1..N$
• LOAN 為全參與
• CUSTOMER 為部分參與

基數表示：

$$CUSTOMER\ 0..N \longleftrightarrow 1..N\ LOAN$$

「一貸款必須隸屬於一客戶」在本題同時明確說明一筆貸款可由多個客戶共同借貸，因此應解讀為「至少隸屬於一位客戶」，不是「恰好一位客戶」。

---

三、ER Diagram

以下以文字方式表示 Chen ER Diagram。實際作圖時：

• 強實體使用單一矩形。
• 弱實體使用雙矩形。
• 弱實體的部分鍵使用虛線底線。
• 識別關係使用雙菱形。
• 全參與使用雙線。
• 部分參與使用單線。
• 關係兩端標示最小、最大基數。

核心觀念

本題考查：

1. 功能依附性（Functional Dependency, FD）
2. 主鍵與候選鍵
3. 更新異常（Update Anomalies）
4. 第二正規化（Second Normal Form, 2NF）
5. 依功能依附性進行關聯綱要分割

原關聯綱要為：

$$\text{EMP-PROJ}(\text{SSN},\text{Pnumber},\text{Hours},\text{Ename},\text{Pname},\text{Plocation})$$

主鍵為：

$$\{\text{SSN},\text{Pnumber}\}$$

功能依附性為：

$$\{\text{SSN},\text{Pnumber}\}\rightarrow\{\text{Hours}\}$$ $$\text{SSN}\rightarrow\text{Ename}$$ $$\text{Pnumber}\rightarrow\text{Pname}$$ $$\text{Pnumber}\rightarrow\text{Plocation}$$

其中：

• $\text{SSN}$：員工識別碼
• $\text{Ename}$：員工姓名
• $\text{Pnumber}$：計畫編號
• $\text{Pname}$：計畫名稱
• $\text{Plocation}$：計畫所在位置
• $\text{Hours}$：員工參與該計畫的時數

---

解題方法：先判斷是否存在更新異常

由於一名員工可以參與多個計畫，因此同一個 $\text{SSN}$ 會在多筆資料中重複出現；同樣地，一個計畫也可能有多名員工參與，因此同一個 $\text{Pnumber}$ 也會在多筆資料中重複出現。

因此，員工資料與計畫資料被混合存放於「員工—計畫參與」關聯中，會產生資料重複與更新異常。

1. 修改異常（Update Anomaly）

若員工姓名改變，必須修改該員工參與之每一個計畫的資料列。

例如，員工：

$$\text{SSN}=S001,\quad \text{Ename}=\text{王大明}$$

參與計畫 $P01$ 與 $P02$，則資料可能為：

SSN	Pnumber	Hours	Ename	Pname	Plocation
S001	P01	10	王大明	計畫甲	臺北
S001	P02	20	王大明	計畫乙	高雄

若姓名改為「王小明」，兩筆資料都必須修改。若只修改其中一筆，便會造成同一員工同時具有兩個姓名的矛盾資料。

2. 插入異常（Insertion Anomaly）

本題要求舉例說明插入異常。

例如，現在要新增一個尚未有任何員工參與的計畫：

$$\text{Pnumber}=P03,\quad \text{Pname}=\text{計畫丙},\quad \text{Plocation}=\text{臺中}$$

由於原關聯的主鍵是 $\{\text{SSN},\text{Pnumber}\}$，新增資料時必須同時提供 $\text{SSN}$。但此計畫尚無參與員工，沒有合理的 $\text{SSN}$ 可以填入，因此無法只登錄計畫本身。

同理，若要新增一名尚未參與任何計畫的員工，也無法只登錄：

$$\text{SSN},\quad \text{Ename}$$

而必須同時提供 $\text{Pnumber}$，因而產生插入異常。

3. 刪除異常（Deletion Anomaly）

若某計畫只有一名員工參與，刪除該員工的參與紀錄時，也會一併刪除該計畫的名稱與所在地資料。

例如，若 $P01$ 只有 $S001$ 參與，刪除：

$$(S001,P01)$$

後，計畫 $P01$ 的計畫名稱與位置也會消失，造成計畫基本資料遺失。

因此，EMP-PROJ 關聯綱要確實具有更新異常。

---

判斷是否符合 2NF

2NF 定義

一個關聯綱要符合 2NF，必須：

1. 先符合 1NF；
2. 每一個非主鍵屬性都必須完全功能依附於整個候選鍵，不得只依附於候選鍵的一部分。

本題主鍵為複合鍵：

$$K=\{\text{SSN},\text{Pnumber}\}$$

非主鍵屬性為：

$$\{\text{Hours},\text{Ename},\text{Pname},\text{Plocation}\}$$

逐一分析如下：

$\text{Hours}$ 的依附性

$$\{\text{SSN},\text{Pnumber}\}\rightarrow\text{Hours}$$

$\text{Hours}$ 必須由特定員工參與特定計畫共同決定，依附於完整主鍵，因此符合 2NF 對此屬性的要求。

$\text{Ename}$ 的依附性

$$\text{SSN}\rightarrow\text{Ename}$$

$\text{SSN}$ 是複合主鍵 $\{\text{SSN},\text{Pnumber}\}$ 的真子集，但 $\text{Ename}$ 只依附於 $\text{SSN}$，並不需要完整的 $\text{Pnumber}$。

因此：

$$\text{SSN}\rightarrow\text{Ename}$$

是非主鍵屬性對主鍵的部分功能依附性（Partial Functional Dependency），違反 2NF。

核心觀念

本題考查資料庫交易處理的基本架構，核心包括：

1. 交易對資料庫的存取指令。
2. 交易與行程（Schedule）的定義。
3. 多個交易並行執行所造成的資料異常。
4. DBMS 透過並行控制與回復機制，確保交易具備 ACID 特性。
5. 並行行程必須具備可串行化與可回復性。

---

一、交易處理的資料庫存取指令

交易（Transaction）是由一連串資料庫操作所組成的邏輯工作單位。最基本的資料庫存取指令包括：

1. read_item(X)

將資料項目 $X$ 從資料庫或磁碟讀入交易可使用的主記憶體緩衝區。

例如：

$$read\_item(A)$$

表示交易讀取資料項目 $A$。

2. write_item(X)

將交易在主記憶體中修改後的資料項目 $X$ 寫回資料庫或緩衝區。

例如：

$$write\_item(A)$$

表示交易將修改後的 $A$ 寫回資料庫。

3. 交易控制指令

實務上的交易還包括下列控制操作：

• BEGIN TRANSACTION：開始交易。
• COMMIT：交易成功完成，正式確認所有更新。
• ROLLBACK 或 ABORT：交易失敗或被取消，撤銷交易所造成的更新。

因此，典型交易可表示為：

$$T_i: begin,\ read(X),\ write(X),\ read(Y),\ write(Y),\ commit$$

其中 read 與 write 是資料庫存取操作，begin、commit、rollback 則是交易控制操作。

---

二、交易（Transaction）的意義

交易是資料庫中一組具有邏輯完整性的操作集合，通常代表一項不可分割的工作。

例如銀行轉帳可表示為：

$$T_1: \begin{cases} read(A)\\ A := A - 1000\\ write(A)\\ read(B)\\ B := B + 1000\\ write(B) \end{cases}$$

此交易必須同時完成「甲帳戶扣款」與「乙帳戶加款」。若只完成其中一項，資料庫就會出現錯誤。

交易具有下列特性：

• 交易開始前，資料庫處於一致狀態。
• 交易執行期間可能暫時處於中間狀態。
• 交易成功完成後，資料庫必須回到另一個一致狀態。
• 交易失敗時，必須撤銷其已完成的更新，使資料庫回復至交易開始前的狀態。

---

三、行程（Schedule）的意義

行程是多個交易中所有操作的排列順序，且必須維持每一交易內部原有的操作先後關係。

假設有兩個交易：

$$T_1: read_1(X),\ write_1(X)$$ $$T_2: read_2(X),\ write_2(X)$$

1. 串行行程（Serial Schedule）

先完整執行一個交易，再執行下一個交易，例如：

$$read_1(X),\ write_1(X),\ read_2(X),\ write_2(X)$$

此時交易彼此沒有交錯，容易維持正確性，但並行程度低。

2. 非串行行程（Non-serial Schedule）

多個交易的操作彼此交錯，例如：

$$read_1(X),\ read_2(X),\ write_1(X),\ write_2(X)$$

非串行行程可提高 CPU、磁碟及輸入輸出設備的使用率，但若缺乏適當的並行控制，便會造成資料不一致。

3. 可串行化行程（Serializable Schedule）

雖然操作彼此交錯，但其最後結果等同於某一個串行行程的結果。

可串行化是判斷並行執行是否正確的主要標準。常見判斷方式為衝突可串行化：

• 同一資料項目。
• 不同交易。
• 至少一個操作為 write。

若衝突操作的先後關係可透過交換不衝突操作，轉換成某個串行行程，則該行程具有衝突可串行性。

---

四、多個交易並行執行所產生的問題

1. 遺失更新（Lost Update）

兩個交易同時讀取同一資料項目，之後分別進行修改，後寫入的交易覆蓋先寫入的交易結果。

假設初始值為 $X=100$：

$$T_1: read(X=100),\quad X:=X+10$$ $$T_2: read(X=100),\quad X:=X-20$$

若執行順序為：

$$read_1(X),\ read_2(X),\ write_1(X=110),\ write_2(X=80)$$

$T_1$ 的更新被 $T_2$ 覆蓋，最後結果為 $80$，而非正確的 $90$。

---

2. 暫時更新或髒讀取（Temporary Update／Dirty Read）

一交易讀取另一尚未提交交易所寫入的資料。若寫入交易後來失敗並回復，讀取交易所依據的資料便是無效資料。

例如：

$$T_1: write(X=500)$$ $$T_2: read(X=500)$$

若 $T_1$ 隨後失敗並執行 ROLLBACK，則 $T_2$ 已經讀取了從未正式存在於資料庫中的值 $500$。

---

3. 不可重複讀取（Unrepeatable Read）

同一交易兩次讀取同一資料項目，但兩次讀取得到不同結果。

例如：

$$T_1: read(X=100)$$

此時 $T_2$ 修改並提交：

$$T_2: write(X=200),\ commit$$

$T_1$ 再次讀取 $X$ 時得到 $200$。因此，$T_1$ 在同一交易內無法重複取得相同資料。

---

4. 不一致分析或錯誤摘要（Incorrect Summary）

一交易計算多筆資料的總和、平均值等彙總結果時，另一交易同時更新其中部分資料，導致彙總值混合新舊資料。

例如，$T_1$ 計算 $A+B$，$T_2$ 將金額 $100$ 從 $A$ 移至 $B$：

$$A:=A-100,\qquad B:=B+100$$

若 $T_1$ 在讀取 $A$ 後、$T_2$ 更新 $A$ 與 $B$ 的期間讀取 $B$，便可能計算出錯誤總和。

---

核心觀念

本題考查「衝突可序列化」（Conflict Serializability）與「優先序圖形」（Precedence Graph）。

若兩個交易的操作符合下列條件，且操作順序具有先後關係，即形成衝突：

1. 作用於同一資料項目；
2. 分屬不同交易；
3. 至少一個操作是 write_item。

因此，下列操作彼此衝突：

• $r_i(X)$ 與 $w_j(X)$
• $w_i(X)$ 與 $r_j(X)$
• $w_i(X)$ 與 $w_j(X)$

其中 $i \ne j$。

若交易 $T_i$ 的衝突操作先於交易 $T_j$，則在優先序圖形中加入有向邊：

$$T_i \rightarrow T_j$$

判斷原則如下：

• 優先序圖形無循環：行程具衝突可序列性。
• 優先序圖形有循環：行程不具衝突可序列性。

本題只有 $T_1$、$T_2$ 兩個交易，因此只要同時出現：

$$T_1 \rightarrow T_2 \quad\text{以及}\quad T_2 \rightarrow T_1$$

即形成循環，判定為不具序列性。

---

解題方法

逐一觀察每個行程中，$T_1$ 與 $T_2$ 對相同資料項目的讀寫順序：

1. 找出跨交易且具有衝突的操作；
2. 依實際執行順序建立有向邊；
3. 檢查優先序圖形是否有循環；
4. 若無循環，寫出其等價的序列執行順序。

其中，交易內的計算操作，例如：

$$Y := Y-N,\qquad X := X+N$$

只是交易的區域變數運算，不直接產生優先序圖形的邊；判斷重點在 read_item 與 write_item。

---

Schedule A 分析

相關操作順序

$T_1$ 先對 $Y$ 執行：

$$r_1(Y),\quad w_1(Y)$$

之後 $T_2$ 才執行：

$$r_2(Y),\quad w_2(Y)$$

由於 $T_1$ 的 write_item(Y) 先於 $T_2$ 的 read_item(Y) 與 write_item(Y)，形成衝突邊：

$$T_1 \rightarrow T_2$$

沒有任何 $T_2$ 先於 $T_1$ 的衝突操作，因此沒有反向邊。

優先序圖形

$$T_1 \rightarrow T_2$$

圖形沒有循環，因此其等價序列順序為：

$$T_1 \;\text{接著}\; T_2$$

判定

Schedule A 具衝突可序列性。

---

Schedule B 分析

相關操作順序

$T_2$ 先對 $Y$ 執行：

$$r_2(Y),\quad w_2(Y)$$

之後 $T_1$ 才執行：

$$r_1(Y),\quad w_1(Y)$$

由於 $T_2$ 的寫入先於 $T_1$ 的讀取與寫入，形成衝突邊：

$$T_2 \rightarrow T_1$$

沒有 $T_1$ 先於 $T_2$ 的衝突操作，因此沒有反向邊。

優先序圖形

$$T_2 \rightarrow T_1$$

圖形沒有循環，因此其等價序列順序為：

$$T_2 \;\text{接著}\; T_1$$

判定

Schedule B 具衝突可序列性。

---

Schedule C 分析

相關操作順序

$T_1$ 先對 $Y$ 執行：

$$r_1(Y),\quad w_1(Y)$$

之後 $T_2$ 才執行：

$$r_2(Y),\quad w_2(Y)$$

因此形成：