【正文】 Its Precedence Graph T1 T2 T3 T4 T5 read(X) read(Y) read(Z) read(V) read(W) read(W) read(Y) write(Y) write(Z) read(U) read(Y) write(Y) read(Z) write(Z) read(U) write(U) T3 T4 T1 T2 T5 可串行化的檢測 Test for Conflict Serializability ? A schedule is conflict serializable if and only if its precedence graph is ? Cycledetection algorithms exist which take order n2 time, where n is the number of vertices in the graph. ? (Better algorithms take order n + e where e is the number of edges.) ? If precedence graph is acyclic, the serializability order can be obtained by a topological sorting拓撲排序 of the graph. ? This is a linear order consistent with the partial order of the graph. ? For example, a serializability order for Schedule A would be T5 ? T1 ? T3 ? T2 ? T4 ? Are there others? T5?T1?T2?T3?T4 … 36 沖突可串行化如何判定？ 又例： 可串行化的檢測 問題 7答案 Test for View Serializability ? The precedence graph test for conflict serializability cannot be used directly to test for view serializability. ? Extension to test for view serializability has cost exponential in the size of the precedence graph. ? The problem of checking if a schedule is view serializable falls in the class of NPplete problems. ? Thus existence of an efficient algorithm is extremely unlikely. ? However practical algorithms that just check some sufficient conditions for view serializability can still be used. 37 視圖可串行化可以判定？ 可串行化的檢測 Recoverable Schedules 可恢復調(diào)度 ? Recoverable schedule — if a transaction Tj reads a data item previously written by a transaction Ti , then the mit operation of Ti appears before the mit operation of Tj. ? The following schedule (Schedule 11) is not recoverable if T9 mits immediately after the read ? 原因分析： If T8 should abort, T9 would have read (and possibly shown to the user) an inconsistent database state. Hence, database must ensure that schedules are recoverable. Need to address the effect of transaction failures on concurrently running transactions. 四 其它事務相關(guān)知識 41 什么是可恢復調(diào)度 , 為何需要？ 可恢復與無級聯(lián)調(diào)度 問題 8答案 Cascading Rollbacks ? 定義 :Cascading rollback – a single transaction failure leads to a series of transaction rollbacks. ? 例子 :Consider the following schedule where none of the transactions has yet mitted (so the schedule is recoverable) If T10 fails, T11 and T12 must also be rolled back. 效果 : It can lead to the undoing of a significant amount of work 42 什么叫事務的級聯(lián)回卷？ 可恢復與無級聯(lián)調(diào)度 Cascadeless Schedules 無級聯(lián)調(diào)度 ? Cascadeless schedules — cascading rollbacks cannot occur。 also read the value of Q that was produced by transaction Tj . 3. For each data item Q, the transaction (if any) that performs the final write(Q) operation in schedule S must perform the final write(Q) operation in schedule S180。 are view equivalent if the following three conditions are met: 1. For each data item Q, if transaction Ti reads the initial value of Q in schedule S, then transaction Ti must in schedule S180。 are conflict equivalent. ? 沖突可串行化： We say that a schedule S is conflict serializable if it is conflict equivalent to a serial schedule （ 直觀例示 ） 基本概念 Conflict Serializability–沖突 可 串行化例示 ? Schedule 3 can be transformed into Schedule 6, a serial schedule where T2 follows T1, by series of swaps of nonconflicting instructions. ? Therefore Schedule 3 is conflict serializable. Schedule 3 Schedule 6 沖突可串行化 Conflict Serializability–沖