1 Timestamps2 Multi-version timestamps3 ValidationOptimistic concurrency controlCSE 444, fall 2010 — section 6 worksheetNovember 4, 2010Our notation for actions in a schedule:• stk: transaction Tkbegins• rk(X): Tkreads database element X• wk(X): Tkwrites database element X• comk: TkcommitsOther notation will be introduced as needed.1 TimestampsEach of the following schedules is presented to a timestamp-based scheduler. Assume that the read andwrite timestamps of each element start at 0 (RT(X) = WT(X) = 0), and the commit bits for each elementare set (C(X) = 1). Please tell what happens as each schedule executes.1. st1, st2, st3, r1(A), r2(B), w1(C), r3(B), r3(C), w2(B), w3(A)12. st1, st3, st2, r1(A), r2(B), w1(C), r3(B), r3(C), w2(B), w3(A)3. st1, st2, st3, r1(A), r2(B), r2(C), r3(B), com2, w3(B), w3(C)24. st1, st2, r1(A), r2(B), w2(A), com2, w1(B)5. st1, st3, st2, r1(A), r2(B), r3(B), w3(A ), w2(B), com3, w1(A)36. st1, r1(A), w1(A ), st2, r2(C), w2(B), r2(A), w1(B)42 Multi-version timestampsTell what happens during the following schedules if we use a multi-version timestamp scheduler. Whathappens if the scheduler does not maintain multiple versions?1. st1, st2, st3, st4, w1(A), com1, w2(A), w3(A), com3, r2(A), com2, r4(A), com42. st1, st2, st3, st4, w1(A), com1, w3(A), com3, r4(A), com4, r2(A), com253. st1, st2, st3, st4, w1(A), com1, w4(A), com4, r3(A ), com3, w2(A), com263 ValidationFor the following schedules:• Rk(X) means “transaction Tkstarts, and its read set is the list of database elements X,”• Vkmeans “Tktries to validate,” and• Wk(x) means “Tkfinished, and its write set was X.”Note: Remember that each transaction must inform the scheduler of both its read and write sets whenit begins, or when it validates (at the latest). While the notation we use implies otherwise, and hence isslightly confusing, we use it to be consistent with your textbook’s notation.Tell what happens when each schedule is processed by a validation-based scheduler.1. R1(A, B), R2(B, C), R3(C), V1, V2, V3, W1(A), W2(B), W3(C)72. R1(A, B), R2(B, C), R3(C), V1, V2, V3, W1(C), W2(B), W3(A)3. R1(A, B), R2(B, C), R3(C), V1, V2, V3, W1(A), W2(C), W3(B)84. R1(A, B), R2(B, C), V1, R3(C, D ), V3, W1(C), V2, W2(A),
View Full Document
Unlocking...