CSE 132A Lecture Notes - Lecture 16: Concurrency Control, Granularity
Document Summary
S1, s2 are conflict equivalent schedules if s1 can be transformed into s2 by a series of swaps of adjacent non-conflicting actions. Actions on different data read/read on the same data. T2 must precede t1 in any equivalent schedule, i. e. t2 t1 (t2 determines t1) We get a cycle, and this situation is not possible. Sd cannot be rearranged into a serial schedule. Pi(a), qj(a) are actions in s on same entity a. At least one of pi,qj is a write. What is p(s) for s = w3(a) w2(c) r1(a) w1(b) r1(c) w2(a) r4(a) w4(d) S1, s2 conflict equivalent p(s1) = p(s2) Transform s1 as follows: take t1 to be transaction w/ no incoming arcs, move all t1 actions to the front. S1 = qj(a) p1(a: we now have s1 = < rest , repeat above steps to serialize the rest!