Question

2) Consider schedules S3, S4, and S5 below. Determine whether each schedule is strict, cascadeless, recoverable, or non-recoverable. You need to explain your reason.
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), c1, w2(z), w3(y), w2(y), c3, c2

Answer 1

Answer:

Explanation:

Consider schedules S3, S4, and S5 below. Determine whether each schedule is strict, cascadeless, recoverable, or non-recoverable. You need to explain your reason.

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), c1, w2(z), w3(y), w2(y), c3, c2

Strict schedule:

A schedule is strict if it satisfies the following conditions:

Tj reads a data item X after Ti has written to X and Ti is terminated means aborted or committed.

Tj writes a data item X after Ti has written to X and Ti is terminated means aborted or committed.

S3 is not strict because In a strict schedule T3 must read X after C1 but here T3 reads X (r3(X)) before Then T1 has written to X (w1(X)) and T3 commits after T1.

S4 is not strict because In a strict schedule T3 must read X after C1, but here T3 reads X (r3(X)) before T1 has written to X (w1(X)) and T3 commits after T1.

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:

Cascadeless schedule follows the below condition:

Tj reads X only? after Ti has written to X and terminated means aborted or committed.

S3 is not cascadeless schedule because T3 reads X (r3(X)) before T1 commits.

S4 is not cascadeless schedule because T3 reads X (r3(X)) before T1 commits.

S5 is not cascadeless schedule because T3 reads X (r3(X)) before T1 commits or T2 reads Y (r2(Y)) before T3 commits.

But while come to the definition of cascadeless schedules S3, S4, and S4 are not cascadeless, and 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:

Schedule that follows the below condition:

-----Tj commits after Ti if Tj has?read any data item written by Ti.

Ci > Cj means that 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 schedule S3 is recoverable because rolling back of T1 does not affect T2 and

T3. If C1>A3>C2. schedule 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 schedule S3 is C3>C2.

If A1?>C2>C3, then schedule S4 is recoverable because roll back of T1 does not affect T2 and T3. If C1>A2>C3, then schedule 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 schedule S4 is not recoverable because T3 will restore the value of Y which was not read by T2.