事務并發調度問題
?
??? 昨天看模擬題，有一道關于數據庫并發的題目，不是很明白，所以今天特地到網上查了一下，在這里做一個記錄：
?
??? 題目是數據庫系統工程師考試06年5月下午卷的第5題，具體的題目是這樣的：
******************************************************************************
【說明】
現有一個事務集｛T1,T2,T3,T4｝，其中這四個事務在運行過程中需要讀寫X、Y和Z。設Ti對X的讀操作記作TiR(X)，Ti對X的寫操作記作TiW(X)。
事務對XYZ的訪問情況如下：
T1：T1R(x)
T2：T2R(Y)，T2W(X)
T3：T3W(Y)，T3W(X)，T3W(Z)
T4：T4R(Z)，T4W(X)
?
【問題1】試述事務并發高(調)度的正確性準則及其內容(4分)
【問題2】請判斷如下高(調)度是否正確。(4分)
T3W(Y)，T1R(X)，T2R(Y)，T3W(X)，T2W(X)，T3W(Z)，T4R(Z)，T4W(X)
按這種調度產生的事務依賴關系圖如下：
??? 
【問題3】給出與【問題2】中調度等價的一串行調度序列。(3分)
?
(注：嚴重質疑題目里的“高度”應該是錯別字，改成“調度”才可以理解)
******************************************************************************
?
??? 首先關于【問題1】，我的理解是這樣的：事務的并發調度的正確性，取決于這個并發調度是不是可以等價得轉換為串行調度。只有當一個并行調度可以與某一次的串行調度轉化時，這個并發調度才是正確的。
?
??? 然后對于【問題2】，可能對題目本身比較難以理解。其實對于并行調度的正確性判斷不需要考慮讀寫一致性和鎖定/解鎖的問題，雖然事務T1/T2/T3/T4中的每一個子項都是原子性的，在啟動前鎖定，完成后解鎖，但是如果不是按照整個事務的串行化執行，其最后的結果是會發生錯誤的。所以我們只能從事務對于X/Y/Z的依賴性的角度來進行分析，例如：
?
??? 數據項X:T1R(X),T3W(X),T2W(X),T4W(X)
??? 相對于X的事物依賴圖為:T1--->T3,T1--->T2,T1--->T4,T3--->T2,T3--->T4,T2--->T4
?
??? 數據項Y:T3W(Y),T2R(Y)
??? 相對于Y的事物依賴圖為:T3--->T2
?
??? 數據項Z:T3W(Z),T4R(Z)
??? 相對于Z的事物依賴圖為T3--->T4
?
??? 綜合X,Y,Z的事物依賴圖得到題目已知的事物調度依賴圖。
??? 在事物調度依賴圖中,沿箭頭方向不產生回路(要包含所有事務)的一條路徑就是與該并發調度等價的串行調度,假設在事務依賴圖中有回路產生,則該并發調度是不可串行化的。而本題按照T1--->T3--->T2--->T4的順序是滿足條件的，所以題中的并行調度順序是正確的。
?
?
??? 如果是不可串行化的調度，則可能是發生了死鎖。例如...,T2R(Y),T3W(X),...T2W(X),T3W(Y),...
??? 如果出現這種情況，則改換成串行模式時，對于Y，T3在等待T2結束后對Y解鎖，而對于X，T2在等待T3結束后對X解鎖，這樣就造成了互相等待的死鎖情況而無法進行下去。
?
??? 需要特別注意的是：在事物依賴有向圖中，選取的路徑是不可以包括回路(多方死鎖)，或者雙向路徑的。
?
??? 對于【問題三】，只要搞明白上面的原理，就很簡單了，答案就是 T1--->T3--->T2--->T4
?
?