DBMS序列化的測試

序列化圖用於測試計劃的可序列化。

假設一個時間表S，對於S，我們構造一個稱為優先圖的圖。 該圖有一對G =(V，E)，其中V由一組頂點組成，E由一組邊組成。 頂點集用於包含參與計劃的所有事務。 該組邊用於包含三個條件之一所有的所有邊Ti - > Tj：

如果Ti在Tj執行讀取(Q)之前執行寫入(Q)，則建立節點Ti→Tj。
如果Ti在Tj執行寫入(Q)之前執行讀取(Q)，則建立節點Ti→Tj。
如果Ti在Tj執行寫入(Q)之前執行寫入(Q)，則建立節點Ti→Tj。

排程S的優先順序圖：

• 如果優先圖包含單個邊Ti→Tj，則在執行Tj的第一個指令之前執行Ti的所有指令。
• 如果排程S的優先順序圖包含迴圈，則S是不可序列化的。 如果優先順序圖沒有迴圈，那麼S稱為可序列化。

範例

說明：

Read(A)：在T1中，沒有後續寫入A，因此沒有新的邊界。
Read(B)：在T2中，沒有後續寫入B，因此沒有新的邊界。
Read(C)：在T3中，沒有後續寫入C，因此沒有新的邊界。
Write(B)：隨後通過T3讀取B，因此新增邊沿T2→T3。
Write(C)：隨後通過T1讀取C，因此新增邊沿T3→T1。
Write(A)：隨後由T2讀取A，因此新增邊沿T1→T2。
Write(A)：在T2中，沒有後續讀到A，所以沒有新的界。
Write(C)：在T1中，沒有後續讀到C，所以沒有新的界。
Write(B)：在T3中，沒有後續讀到B，所以沒有新的界。

排程S1的優先順序圖：

排程S1的優先順序圖包含一個迴圈，這就是排程S1不可序列化的原因。

說明：

Read(A)：在T4中，沒有後續寫入A，因此沒有新的邊界。
Read(C)：在T4中，沒有後續寫入C，因此沒有新的邊界。
Write(A)：隨後由T5讀取A，因此新增邊T4→T5
Read(B)：在T5中，沒有後續寫入B，因此沒有新的邊界。
Write(C)：隨後由T6讀取C，因此新增邊T4→T6
Write(B)：隨後由T6讀取A，因此新增邊T5→T6
Write(C)：在T6中，沒有後續讀到C，所以沒有新的邊界。
Write(A)：在T5中，沒有後續讀到A，所以沒有新的邊界。
Write(B)：在T6中，沒有後續讀到B，所以沒有新的邊界。

排程S2的優先順序圖：

排程S2的優先順序圖不包含迴圈，這就是排程S2可序列化的原因。