Serialisability

The purpose of this tutorial is to assess and reinforce your knowledge of the characterisation of schedules with respect to serialisability.

Exercise 1

For each of the following schedules state whether they are conflict serialisable and or recoverable. Assess conflict serialisability by producing the corresponding precedence graph. For those schedule that are serialisable, indicate the equivalent serial schedule.

Sa: r1(balx); r2(balx); w1(balx); w2(balx); commt(T1); commit(T2);

Sb: r1(balx); r2(baly); w3(balx); r2(balx); r1(baly); commit(T1);
      commit(T2);

Sc: r1(balx); w2(balx); w1(balx); abort(T2); commit(T1);

Sd: w1(balx); r2(balx); w1(balx); commit(T2); abort(T1);

Se: r1(balx); w2(balx); w1(balx); r3(balx); commt(T1); commit(T2); commit(T3);

Optional exercise

Consider the three transactions T1, T2, and T3. and the schedule S1 below. Determine whether S1 is strict, cascadeless, recoverable or non recoverable. Identify whether it is non serialisable.

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); r3(X); r1(Z); r2(Y);  r3(Y); w1(X); c1; w2(Z); w3(Y); w2(Y); c3; c2;