CS5481 Data Engineering Tutorial 11
1. Consider the following two transactions. Assume that the two transactions preserve database consistency in isolation.
T1: r1(A); w1(A); r1(B); w1(B);
T2: r2(A); w2(A); r2(B); w2(B);
Give all possible schedules (including serial schedule) of the two transactions that are conflict‐equivalent to the serial schedule (T1, T2).
r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B) r1(A)w1(A)r1(B)r2(A) w1(B)w2(A)r2(B)w2(B) r1(A)w1(A)r2(A)r1(B)w1(B)w2(A)r2(B)w2(B) r1(A)w1(A)r2(A)r1(B)w2(A)w1(B)r2(B)w2(B) r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B) r1(A)w1(A)r1(B)r2(A)w2(A)w1(B)r2(B)w2(B)
2. Consider the following two transactions and some possible schedules. T1: r1(x); w1(x); r1(y); w1(y); c1;
T2: r2(x); w2(x); c2;
S1: r1(x); w1(x); r1(y); w1(y); r2(x); c1; w2(x); c2; S2: r1(x); r2(x); w1(x); r1(y); w1(y); w2(x); c1; c2; S3: r2(x); w2(x); r1(x); w1(x); r1(y); c2; w1(y); c1;
For each of the above schedules, indicate whether the schedule is recoverable, cascadeless and conflict serializable. If the schedule is conflict serializable, show its serializability order.
S1: recoverable and conflict serializable (T1 T2) S2: cascadeless but not conflict serializable
S3: recoverable and conflict serializable (T2 T1)
CS5481 Data Engineering Tutorial 11
3. Consider using two‐phase locking on the following schedule of two transactions, T1 and T2.
r1(A); r2(B); r2(A); r1(B); w1(B); r2(C);
(a) Insert shared lock (sl), exclusive lock (xl) and unlock (ul) instructions at appropriate
locations.
(b) Describe the execution of the above schedule, assuming that a waiting transaction does not block the following non‐conflicting instructions of other transactions. Show the resultant schedule, if it is different from the one you constructed in (a).
(c) What will be the serializability order of the resultant schedule?
(d) Any changes if the schedule is modified to insert w2(A) at the end as follows?
r1(A); r2(B); r2(A); r1(B); w1(B); r2(C); w2(A);
sl1(A); r1(A); sl2(B); r2(B); sl2(A); r2(A); xl1(B); r1(B); w1(B); ul1(A); ul1(B); sl2(C); r2(C); ul2(B);
ul2(A); ul2(C);
(b)
(i) T1 is delayed. T1 cannot get the exclusive lock on B because T2 already has a shared
lock on B.
(ii) T2 completes and unlocks B.
(iii) T1 then can get the exclusive lock on B and completes.
Resultant schedule:
sl1(A); r1(A); sl2(B); r2(B); sl2(A); r2(A); xl1(B); sl2(C); r2(C); ul2(B); ul2(A); ul2(C); r1(B); w1(B); ul1(A); ul1(B);
(c) The serializability order is (T2 T1).
(d) The execution can result in deadlock, as shown in the following partial schedule. sl1(A); r1(A); sl2(B); r2(B); xl2(A); xl1(B);
(a)