IIS'08, Exercise 4 - Transactions and Recovery (Solutions)

Part 1. Concurrency

1)  A schedule is conflict-serializable iff its serializability graph is acyclic.

The serializability graph of the given schedule is the following:


It contains no cycles hence the schedule is conflict-serializable.

In order to find a serial schedule to which the above schedule is conflict equivalent we swap in each step two executions which have no conflicts among themselves (hence each schedule has the same conflicts)

r1(A) ; w1(A) ; r2(A) ; w2(A) ; r1(B) ; w1(B) ; r2(B) ; w2(B);

r1(A) ; w1(A) ; r2(A) ; r1(B); w2(A) ; w1(B) ; r2(B) ; w2(B);

r1(A) ; w1(A) ; r1(B); r2(A) ; w2(A) ; w1(B) ; r2(B) ; w2(B);

r1(A) ; w1(A) ; r1(B); r2(A) ; w1(B) ; w2(A) ; r2(B) ; w2(B);

r1(A) ; w1(A) ; r1(B); w1(B) ; r2(A) ; w2(A) ; r2(B) ; w2(B);


2) If we want the schedule to become non conflict serializable we have to “create” a conflict between the two transactions. This can be achieved, for example, by making T2 access the B variable first:


r1(A) ; w1(A) ; r2(A) ; w2(A) ; r2(B) ; w2(B) ; r1(B) ; w1(B) ;


In this case the serializability graph is the following:


 3) The waiting graph is the following:  

The operation Xlock(A) launched by T3 generates a deadlock.

Part 2. Recovery

1) The missing values “****” are replaced by the identifiers of the transactions which are active at the beginning of the checkpoints. For the three checkpoints the values are:

 CKPT1 - T1

CKPT2 - T2, T3

CKPT3 - T4, T5

 2) Recovery operations:

 X4: 8

X5: 7

X4: 6

 All other transactions (except T4 and T5) have ended (COMMIT).

 3) The portion of the log from second checkpoint (<START CKPT T2T3> ) till the end is used.

 4) We don’t need to read the entire log and the transactions can still run during the logging operation