Consider the three transactions T1, T2, and T3, and the schedules S1 and S2 given below. Draw the serializibility (precedence) graphs for S1 and S2 and state whether each schedule is serializable or not. If a schedule is serializable, write down the equivalent serial schedule(s).

Question

T1: r1(x); r1(z); w1(x)
T2: r2(z); r2(y); w2(z); w2(y)
T3: r3(x); r3(y); w3(y)
S1: r1(x); r2(z); r1(x); r3(x); r3(y); w1(x); w3(y); r2(y); w2(z); w2(y)
S2: r1(x); r2(z); r3(x); r1(z); r2(y); r3(y); w1(x); w2(z); w3(y); w2(y)

Answer 1

Schedule S1: It is a serializable schedule because


• ?T1 only reads X (r1(X)), which is not modified either by T2 or T3,


• T3 reads X (r3(X)) before T1 modifies it (w1(X)),


• ?T2 reads Y (r2(Y)) and writes it (w2(Y)) only after T3 has written to it (w3(Y))


• Thus, the serializability graph is











Schedule is not a serializable schedule because


• ?T2 reads Y (r2(Y)), which is then read and modified by T3 (w3(Y))


• T3 reads Y (r3(Y)), which then modified before T2 modifies Y (w2(Y))


In the above order T3 interferes in the execution of T2, which makes the schedule nonserializable.