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

核心觀念

本題考查三件事：從敘述找出功能相依、將 ER 圖轉成關聯式綱要，以及用功能相依判斷並消除違反第三正規化的相依。關鍵是區分「一趟飛行」與「某機組員參與該趟飛行」：航班資料屬於飛行本身，Role 則屬於機組員參與飛行的關係。

以下將圖中的 Dest 視為題目敘述的到達目的地。並依「時間精確到秒」將 DepTime 視為可區分航班的完整起飛時間。

解題方法與推導

先逐一判斷哪些屬性由哪些鍵值決定：

• 機組員編號決定機組員姓名：$CID \to CName$。
• 飛機編號決定飛機型號：$ANO \to Model$。
• 同一架飛機在同一個起飛時間只對應一趟飛行，因此 $(ANO, DepTime)$ 決定該趟飛行的起點、到達時間、目的地與里程。
• Role 是個別機組員在該趟飛行中的角色，須由機組員與該趟飛行共同決定。

（一）功能相依

列出非平凡且最小的功能相依如下：

最後一項表示同一機組員在同一趟飛行中的角色。依這些相依，$(CID, ANO, DepTime)$ 可決定飛行紀錄中的所有屬性；但 Role 不由 $(ANO, DepTime)$ 單獨決定，因為同一趟飛行的不同機組員可以擔任不同角色。

（二）將原 ER 圖轉成關聯式綱要

原圖中的 Crew、Airplane 是實體；Fly 是兩者之間的多對多關係。多對多關係轉成一個關聯，納入雙方的主鍵以及關係屬性。

• Crew(CID, CName)，主鍵：$CID$
• Airplane(ANO, Model)，主鍵：$ANO$
• Fly(CID, ANO, Origin, Dest, DepTime, ArrTime, Miles, Role)，主鍵：$(CID, ANO, DepTime)$
• 外鍵：$CID \to Crew(CID)$
• 外鍵：$ANO \to Airplane(ANO)$

原圖將 CID、ANO、DepTime 劃底線，故依圖將三者列為 Fly 的主鍵。此主鍵表示：同一機組員可在同一架飛機上參與不同起飛時間的飛行。

（三）將上述綱要轉成第三正規化

在 Fly 關聯中，$(ANO, DepTime)$ 是主鍵 $(CID, ANO, DepTime)$ 的真子集合，卻已決定 Origin、ArrTime、Dest、Miles。這些非主鍵屬性只依賴複合主鍵的一部分，造成部分相依，因此不符合第三正規化。

依 $(ANO, DepTime) \to (Origin, ArrTime, Dest, Miles)$ 拆分：

• Crew(CID, CName)，主鍵：$CID$
• Airplane(ANO, Model)，主鍵：$ANO$
• Flight(ANO, DepTime, Origin, ArrTime, Dest, Miles)，主鍵：$(ANO, DepTime)$；ANO 為外鍵
• CrewFlight(CID, ANO, DepTime, Role)，主鍵：$(CID, ANO, DepTime)$；CID 為外鍵，$(ANO, DepTime)$ 為外鍵

核心觀念

本題考 ER 圖轉關聯綱要，重點是弱實體識別、關係基數映射、關係屬性處理，以及 is-a 特殊化的映射。

• 弱實體 G 依賴擁有者 F 識別。G 的主鍵由 F 的主鍵與 G 的 Partial Key 組成，因此是 $(FK,GK)$；識別關係 R1 可併入 G，不另建關係表。
• 一對多關係可將「多」端的外鍵放入另一端。R3 中 H 端為 $(1,1)$、G 端為 $(0,*)$，因此把 G 的複合主鍵放入 H。
• 多對多關係需建立中介關係表，主鍵通常由兩端的主鍵組成；若一端是弱實體，須帶入其完整主鍵。
• is-a 特殊化需保留子類與父類的參照關係。依圖中底線標示，S 的 SK 為主鍵；S 同時繼承 H 的 HK，作為唯一且非空的外鍵，確保每筆 S 對應一筆 H。J 為 S 的子類，沿用 SK 作為主鍵及外鍵。

解題方法

先逐一判讀每個菱形兩端的 $(\mathrm{min},\mathrm{max})$。若為一對多，把「一」端鍵值放進「多」端；若為多對多，建立關係表。再處理弱實體與特殊化，最後以主鍵、唯一性與外鍵檢查識別和參照完整性。

（一）所有關聯及主鍵

以下以底線標示主鍵，並在欄位旁註明外鍵：

• F（FK，A）
• E（EK）
• G（FK，GK，C），其中 FK 為參照 F 的外鍵；主鍵為 $(FK,GK)$
• R2（FK，EK，D），其中 FK 參照 F、EK 參照 E；主鍵為 $(FK,EK)$
• H（HK，A，FK，GK），其中 $(FK,GK)$ 參照 G；主鍵為 HK
• S（SK，HK，B），其中 HK 為繼承自 H 的鍵，參照 H，且在 S 中唯一；主鍵為 SK
• J（SK，A1），其中 SK 參照 S；主鍵為 SK
• R5（EK，FK，GK），其中 EK 參照 E、$(FK,GK)$ 參照 G；主鍵為 $(EK,FK,GK)$

R1 是 F 與弱實體 G 的識別關係，已由 G 的 FK 表示，不另建表。R3 是 G 對 H 的一對多關係，已由 H 的 $(FK,GK)$ 表示，不另建表。R5 兩端皆可多次參與，因此保留為中介表。R2 也為多對多，且有屬性 D，因此須另建 R2 表。

（二）G、H、S、R5 的 SQL 綱要

以下假設 F、E 已建立，且其主鍵分別為 FK、EK。每個資料欄位均使用固定長度字串。

CREATE TABLE G (
 FK CHAR(10) NOT NULL,
 GK CHAR(10) NOT NULL,
 C CHAR(30),

 CONSTRAINT PK_G PRIMARY KEY (FK, GK),
 CONSTRAINT FK_G_F
 FOREIGN KEY (FK) REFERENCES F (FK)
 ON DELETE RESTRICT ON UPDATE RESTRICT
);

G 的候選鍵為 $(FK,GK)$。FK 單獨不足以識別 G，GK 是相對於擁有者 F 的 Partial Key，因此不能單獨作為候選鍵。

【核心觀念】

本題考 Wait-die 與 Wound-wait 兩種以交易時間戳記預防 deadlock 的方法。交易年齡依圖中開始順序判定：T2 先開始，故 T2 較舊、T1 較年輕。兩種機制的規則如下：

交易回復時，尚未提交的資料修改會撤銷，並釋放持有的鎖。

【解題方法】

依時間順序追蹤每次鎖衝突，再按交易年齡套用相應規則。首先，T2 要求 $\beta$ 的寫鎖，與 T1 已持有的讀鎖衝突；之後 T1 要求 $\alpha$ 的寫鎖，與 T2 已持有的讀鎖衝突。兩種機制對第一個衝突的處理不同，因此 T1 回復的時點也不同。

（一）採 Wait-die

T2 較舊，T1 較年輕。T2 要求 $\beta$ 寫鎖時，鎖由較年輕的 T1 持有，因此 T2 等待。等待期間，T1 可以繼續執行，包含寫入 $\gamma$，再要求 $\alpha$ 寫鎖。

此時 $\alpha$ 的讀鎖由較舊的 T2 持有。較年輕的 T1 要求與其衝突的寫鎖，依 Wait-die 規則，T1 回復。T1 尚未提交，所以已寫入但未提交的 $\gamma$ 修改會撤銷；T1 也會釋放持有的鎖。T2 隨即取得 $\beta$ 寫鎖，完成更新並提交。之後 T1 重新執行並提交。

核心觀念

本題考查由下而上的合成法（synthesis method），分成兩個步驟：

1. 以功能相依（Functional Dependency, FD）的屬性封閉找出所有候選鍵。
2. 將函數相依化為最小涵蓋，再依 3NF 合成法建立關聯綱要。

屬性集合 $X$ 的封閉 $X^+$，是由 $X$ 出發，反覆套用功能相依後可決定的所有屬性。若 $X^+=R$，則 $X$ 是超鍵；若 $X$ 的任何真子集都不是超鍵，則 $X$ 是候選鍵。

（一）找出所有候選鍵

1. 找出候選鍵必含的屬性

右側未出現在任何功能相依中的屬性，不能由其他屬性推出，因此必須放入每一個候選鍵。

本題右側屬性為 $\{A,B,C,D,E,F,H\}$，未出現在右側的屬性為：

所以每個候選鍵都必須包含 $G,I,J$。

2. 計算 $\{G,I,J\}^+$

從 $\{G,I,J\}$ 開始，依序套用功能相依：

• $IJ\to H$，加入 $H$。
• $IG\to EF$，加入 $E,F$。
• $GJ\to CD$，加入 $C,D$。
• $GJ\to A$，加入 $A$。
• $J\to B$，加入 $B$。
• $C\to A$，可推出 $A$，但 $A$ 已在封閉中。

因此：

故 $\{G,I,J\}$ 是超鍵。

3. 確認最小性與全部候選鍵

由於 $G,I,J$ 都是右側未出現的屬性，每個候選鍵都必須包含三者。又 $\{G,I,J\}$ 已能決定全部屬性，因此不能再加入其他屬性形成更小的候選鍵。

候選鍵只有：

（二）合成 3NF 綱要

1. 化為最小涵蓋

先將右側拆成單一屬性：

接著檢查左側多餘屬性與冗餘相依：