Consider schedules S3, S4, and S5 below. Determine whether each schedule is strict, cascadeless, recoverable, or nonrecoverable. (Determine the strictest recoverability condition that each schedule satisfies.)

Question

S3: r1(x); r2(z); r1(z); r3(x); r3(y); w1(x); c1; w3(y); c3; r2(y); w2(z); w2(y);c2
S4: r1(x); r2(z); r1(z); r3(x); r3(y); w1(x); w3(y); r2(y); w2(z); w2(y); c1; c2; c3;
S5: r1(x); r2(z); r3(x); r1(z); r2(y); r3(y); w1(x); w2(z); w3(y); w2(y); c3; c2;

Answer 1

Strict schedule: A schedule is strict if it satisfies the following conditions:
1. Tj reads a data item X after Ti has written to X and Ti is terminated (aborted or committed)
2. Tj writes a data item X after Ti has written to X and Ti is terminated (aborted or committed)
Schedule S3 is not strict because T3 reads X (r3(X)) before T1 has written to X (w1(X))
but T3 commits after T1. In a strict schedule T3 must read X after C1.
Schedule S4 is not strict because T3 reads X (r3(X)) before T1 has written to X (w1(X))
but T3 commits after T1. In a strict schedule T3 must read X after C1.
Schedule S5 is not strict because T3 reads X (r3(X)) before T1 has written to X (w1(X))
but T3 commits after T1. In a strict schedule T3 must read X after C1.
Cascadeless schedule: A schedule is cascadeless if the following condition is satisfied:
??Tj reads X only after Ti has written to X and terminated (aborted or committed).
Schedule S3 is not cascadeless because T3 reads X (r3(X)) before T1 commits.
Schedule S4 is not cascadeless because T3 reads X (r3(X)) before T1 commits.
Schedule S5 is not cascadeless because T3 reads X (r3(X)) before T1 commits or T2 reads
Y (r2(Y)) before T3 commits.

NOTE: According to the definition of cascadeless schedules S3, S4, and S4 are not
cascadeless. However, T3 is not affected if T1 is rolled back in any of the schedules, that is,
T3 does not have to roll back if T1 is rolled back. The problem occurs because these schedules are not serializable.

Recoverable schedule: A schedule is recoverable if the following condition is satisfied:
??Tj commits after Ti if Tj has read any data item written by Ti.
NOTE: Ci > Cj means Ci happens before Cj. Ai denotes abort Ti. To test if a schedule is recoverable one has to include abort operations. Thus in testing the recoverability abort operations will have to used in place of commit one at a time. Also the strictest condition is where a transaction neither reads nor writes to a data item, which was written to by a transaction that has not committed yet.

??If A1>C3>C2, then S3 is recoverable because rolling back of T1 does not affect T2 and
T3. If C1>A3>C2. S3 is not recoverable because T2 read the value of Y (r2(Y)) after
T3 wrote X (w3(Y)) and T2 committed but T3 rolled back. Thus, T2 used non- existent value of Y. If C1>C3>A3, then S3 is recoverable because roll back of T2 does not affect T1 and T3. Strictest condition of S3 is C3>C2.
??If A1>C2>C3, then S4 is recoverable because roll back of T1 does not affect T2 and
T3. If C1>A2>C3, then S4 is recoverable because the roll back of T2 will restore the value of Y that was read and written to by T3 (w3(Y)). It will not affect T1. If C1>C2>A3, then S4 is not recoverable because T3 will restore the value of Y which was not read by T2. Strictest condition of S4 is C3>C2, but it is not satisfied by S4.
??If A1>C3>C2, then S5 is recoverable because neither T2 nor T3 writes to X, which is written by T1. If C1>A3>C2, then S5 is not recoverable because T3 will restore the value of Y, which was not read by T2. Thus, T2 committed with a non-existent value of
Y. If C1>C3>A2, then S5 is recoverable because it will restore the value of Y to the value, which was read by T3. Thus, T3 committed with the right value of Y. Strictest condition of S3 is C3>C2, but it is not satisfied by S5.