調查局三等申論題
110年
[資訊科學組] 資料庫應用
第 四 題
四、給予下列四個行程 A、B、C、D，依優先序圖形（Precedence Graph），請論述那一行程不具序列性（Serializability）。（25 分）
Schedule A
T1 (read_item(Y); Y:=Y-N; write_item(Y); read_item(X); X:=X+N; write_item(X);)
T2 (read_item(Y); Y:=Y+M; write_item(Y);)
Schedule B
T1 (read_item(Y); Y:=Y-N; write_item(Y); read_item(X); X:=X+N; write_item(X);)
T2 (read_item(Y); Y:=Y+M; write_item(Y);)
Schedule C
T1 (read_item(Y); Y:=Y-N; write_item(Y); ... read_item(X); X:=X+N; write_item(X);)
T2 (... read_item(Y); Y:=Y+M; write_item(Y); ...)
Schedule D
T1 (read_item(Y); Y:=Y-N; write_item(Y); read_item(X); X:=X+N; write_item(X);)
T2 (read_item(Y); Y:=Y+M; write_item(Y);)
(註：各行程之實際執行時間順序如原圖Time箭頭所示)
Schedule A
T1 (read_item(Y); Y:=Y-N; write_item(Y); read_item(X); X:=X+N; write_item(X);)
T2 (read_item(Y); Y:=Y+M; write_item(Y);)
Schedule B
T1 (read_item(Y); Y:=Y-N; write_item(Y); read_item(X); X:=X+N; write_item(X);)
T2 (read_item(Y); Y:=Y+M; write_item(Y);)
Schedule C
T1 (read_item(Y); Y:=Y-N; write_item(Y); ... read_item(X); X:=X+N; write_item(X);)
T2 (... read_item(Y); Y:=Y+M; write_item(Y); ...)
Schedule D
T1 (read_item(Y); Y:=Y-N; write_item(Y); read_item(X); X:=X+N; write_item(X);)
T2 (read_item(Y); Y:=Y+M; write_item(Y);)
(註：各行程之實際執行時間順序如原圖Time箭頭所示)
📝 此題為申論題
思路引導 VIP
解題關鍵在於利用「優先序圖形（Precedence Graph）」檢驗「衝突可循序性（Conflict Serializability）」。需找出不同交易對同一資料項（本題為 Y）的衝突操作（Read-Write, Write-Read, Write-Write），若畫出的圖形產生迴圈（Cycle），則該行程即不具序列性。
🤖
AI 詳解
AI 專屬家教
【破題】 判斷一個行程（Schedule）是否具備衝突可循序性（Conflict Serializable），核心方法為建構「優先序圖形（Precedence Graph）」。若圖中出現迴圈（Cycle），則代表交易間存在循環依賴，該行程即不具序列性。 【論述】
▼ 還有更多解析內容
交易衝突可序列性判定
💡 利用優先序圖形（Precedence Graph）偵測迴圈以判定衝突可序列性。
🔗 序列性判定邏輯鏈
- 1 識別衝突 — 找出不同交易對同資料項之 Read-Write 或 Write-Write 關係
- 2 建立有向邊 — 依時間先後順序連接 Ti → Tj
- 3 偵測迴圈 — 檢查圖形是否出現循環路徑（如 T1→T2 且 T2→T1）
- 4 得出結論 — 有迴圈即為不具序列性，可能導致資料不一致
↓
↓
↓
🔄 延伸學習：延伸學習：若要確保可序列性，通常會實作兩階段鎖定協定 (2PL)。
