Transaction ProcessingProblem 1Consider the four transactions, T1, T2, T3, and T4, which are in schedule S1. Draw the serializability (precedence) graphs for S1, and state whether the schedule is serializable or not. If the schedule is serializable, write down the equivalent serial schedule(s). If it is not, write down all cycles. Note that S1 is shown both as an operation list and as a table.T1 = r1(X), w1(X)T2 = r2(X), w2(Y)T3 = r3(X), w3(Z)T4 = r4(Y), w4(Z)S1 = r1(X); w1(X); r2(X); w2(Y); r3(X); w3(Z); r4(Y); w4(Z)T1T2T3T4read(X)write(X)read(X)write(Y)read(X)write(Z)read(Y)write(Z)Problem 2Consider the three transactions T1, T2, and T3, and the schedules S1 and S2 given below. Draw the serializability (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). !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(Z); 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); !S1S2T1T2T3read(X)read(Z)read(Z)read(X)read(Y)write(X)write(Y)read(Y)write(Z)write(Y)T1T2T3read(X)read(Z)read(X)read(Z)read(Y)read(Y)write(X)write(Z)write(Y)write(Y)Problem 3Given the following eight precedence graphs, determine the serializability of each. If a graph is serializable, draw all equivalent serial graphs. If a graph is not serializable, draw all cycles.T1 T2T3 T4T1 T2T3 T4(a) (b)T1 T2T3 T4T1 T2T3 T4(c) (d)T1 T2T3 T4T1 T2T3 T4(e) (f)T1 T2T3 T4T1 T2T3 T4T5(g) (h)ANSWER KEYProblem 1Serializability GraphEquivalent Serial SchedulesT1→T2→T3→T4T1→T3→T2→T4T1 T2T3 T4XX YZProblem 2Justification – The red arrows in the tables below are informational purposes. Such notation will not be required on the Exam. Only the precedence graphs above will be required, along with equivalent serial schedule (if serializable) or cycles (if non-serializable).S1 S2T1T2T3T3 ⟶ T1 ⟶ T2 XYZT1T2T3Cycle: Z(T1 ⟶ T2); Y(T2 ⟶ T3); X(T3 ⟶ T1)Cycle: Y(T2 ⟶ T3); Y(T3 ⟶ T2) XYZYS1S2T1T2T3read(X)read(Z)read(Z)read(X)read(Y)write(X)write(Y)read(Y)write(Z)write(Y)T1T2T3read(X)read(Z)read(X)read(Z)read(Y)read(Y)write(X)write(Z)write(Y)write(Y)Problem 3T1 T2T3 T4T1 T2T3 T4T1 T2T3 T4T1 T2T3 T4T1 ⟶ T3 ⟶ T2 ⟶ T4T1 ⟶ T2 ⟶ T3 ⟶ T4T1 ⟶ T2 ⟶ T4 ⟶ T3T1 ⟶ T2 ⟶ T3 ⟶ T4T1 ⟶ T2 ⟶ T4 ⟶ T3T1 T2T3 T4T1 ⟶ T2 ⟶ T3 ⟶ T4T1 T2T3 T4T1 ⟶ T2 ⟶ T3 ⟶ T4(a) (b)(c) (d)(e) (f)Cycle: (T1→T2), (T2→T3), (T3→T1)Cycle: (T2→T3), (T3→T4), (T4→T2)T1 T2T3 T4T1 T2T3 T4T5T1 ⟶ T3 ⟶ T2 ⟶ T4 ⟶ T5T1 ⟶ T2 ⟶ T3 ⟶ T4 ⟶ T5T1 ⟶ T2 ⟶ T3 ⟶ T4T1 ⟶ T3 ⟶ T2 ⟶ T4(g)
View Full Document