[計(jì)算機(jī)軟件及應(yīng)用]kc第16講-事務(wù)管理技術(shù)(已改無(wú)錯(cuò)字)
2023-02-19 17:26:37 本頁(yè)面
【正文】 ility ? The schedule S1 below produces same oute as the serial schedule S2 T1, T5 , yet is not conflict equivalent or view equivalent to it. ? Determining such equivalence requires analysis of operations other than read and write. 原因說(shuō)明 : S1中 T5讀 初始值 B , 但在 S2中 T5只能讀 到 B+50 , 而非值 B ! 34 還有什么可串行化術(shù)語(yǔ)？ 其它可串行化概念 ? Consider some schedule of a set of transactions T1, T2, ..., Tn ? 優(yōu)先圖 Precedence graph — a direct graph where the vertices are the transactions (names). ? We draw an arc from Ti to Tj if the two transaction conflict, and Ti accessed the data item on which the conflict arose earlier. ? We may label the arc by the item that was accessed. ? 例子： Example 35 什么是調(diào)度的優(yōu)先圖？ x y Precedence graph 可串行化的檢測(cè) 問(wèn)題 6答案 Example of Schedule Aamp。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 可串行化的檢測(cè) 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拓?fù)渑判? 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 沖突可串行化如何判定？ 又例： 可串行化的檢測(cè) 問(wèn)題 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 視圖可串行化可以判定？ 可串行化的檢測(cè) Recoverable Schedules 可恢復(fù)調(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. 四 其它事務(wù)相關(guān)知識(shí) 41 什么是可恢復(fù)調(diào)度 , 為何需要？ 可恢復(fù)與無(wú)級(jí)聯(lián)調(diào)度 問(wèn)題 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 什么叫事務(wù)的級(jí)聯(lián)回卷？ 可恢復(fù)與無(wú)級(jí)聯(lián)調(diào)度 Cascadeless Schedules 無(wú)級(jí)聯(lián)調(diào)度 ? Cascadeless schedules — cascading rollbacks cannot occur。 for each pair of transactions Ti and Tj , su
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1