Transaction Processing Problem 1 Consider 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 T1 T2 T3 T4 read X write X read X write Y read X write Z read Y write Z Problem 2 Consider 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 S1 T1 T2 T3 read X read Z read Z read X read Y write X write Y read Y write Z write Y S2 T1 T2 T3 read X read Z read X read Z read Y read Y write X write Z write Y write Y Problem 3 Given 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 a b T1 T2 T1 T2 T3 T4 T3 T4 c d T1 T2 T1 T2 T3 T4 T3 T4 e f T1 T2 T1 T2 T3 T4 T3 T4 g h T1 T2 T1 T2 T5 T3 T4 T3 T4 ANSWER KEY Problem 1 Serializability Graph T1 X X T3 T2 Y Z Equivalent Serial Schedules T1 T2 T3 T4 T1 T3 T2 T4 T4 Problem 2 S1 S2 T1 X X Z Y T3 T1 Z Y T2 T3 Y T2 Cycle Z T1 T2 Y T2 T3 X T3 T1 Cycle Y T2 T3 Y T3 T2 T3 T1 T2 Justification 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 nonserializable S1 S2 T1 T2 T3 read X T1 T2 T3 read X read Z read Z read Z read X read X read Y read Z read Y write X read Y write Y read Y write Z write Y write X write Z write Y write Y Problem 3 a b T1 T2 T1 T2 T3 T4 T3 T4 T1 T3 T2 T4 T1 T2 T3 T4 T1 T2 T4 T3 T1 T2 T3 T4 c d T1 T2 T1 T2 T3 T4 T3 T4 T1 T2 T3 T4 T1 T2 T4 T3 T1 T2 T3 T4 e f T1 T2 T1 T2 T3 T4 T3 T4 Cycle T2 T3 T3 T4 T4 T2 Cycle T1 T2 T2 T3 T3 T1 g h T1 T2 T1 T2 T5 T3 T4 T1 T2 T3 T4 T1 T3 T2 T4 T3 T4 T1 T3 T2 T4 T5 T1 T2 T3 T4 T5