The following two questions relate to scheduling: a) For each of the following s

Question

The following two questions relate to scheduling:

a) For each of the following schedules, draw the precedence graph and argue if the schedule is conflict serializable. If the schedule is conflict serializable, give one possible equivalent serial schedule. (Ri means transaction i reads an item and Wi writes an item.)

Schedule a) R1(A);W1(A);R2(A);R2(B);W3(B);W2(C);R4(A);R4(B);R4(C);R2(D);R3(E);

Schedule b) R1(A);R4(A);W1(A);W3(B);R2(A);R2(B);W2(C);R4(B);R4(C);R2(D);R3(E);

________________________________________________________________________________

b) For the following two schedules, insert the appropriate locks (shared and exclusive) into the schedule following the Strict 2PL protocol. Also explain what happens as the scheduler executes each schedule. Note that, if a transaction blocks because of an operation, the transaction with the next operation in the schedule will continue. If you have a deadlock, you need to chose a transaction to abort, release its locks, and let the rest of the schedule continue. You need to restart the aborted transaction again at some point after it has been aborted. When a transaction unblocks, it resumes its operations. Write the actual executed schedule at the end.

Schedule a) R1(A);R2(B);R3(C);W1(B);W2(C);W3(D);

Schedule b) R1(A);R2(B);R3(C);R1(B);R2(C);R3(A);W1(A);W2(B);W3(C);

Explanation / Answer

conflict-equivalent to T1, T2 r1(A) w1(A) r1(B) w1(B) r2(B) w2(B) r2(A) w2(A) This is the serial schedule T1, T2. There are no other conflict-equivalent schedules, since there is no non-conflicting swap of adjacent actions in this schedule: we cannot swap actions within a transaction, and w1(B) r2(B) cannot be swapped, because they are both manipulating the same database element and one of them is a write. conflict-equivalent to T2, T1 r2(B) w2(B) r2(A) w2(A) r1(A) w1(A) r1(B) w1(B) This is the serial schedule T2, T1. There are no other conflict-equivalent schedules, since there is no non-conflicting swap of adjacent actions in this schedule: we cannot swap actions within a transaction, and w2(A) r1(A) cannot be swapped, because they are both manipulating the same database element and one of them is a write. b) T1: r1(A) w1(A) r1(B) w1(B) T2: r2(A) w2(A) r2(B) w2(B) Note that the action in bold font is the one that has been moved forward in the last swap. conflict-equivalent to 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) r1(B) r2(A) w2(A) w1(B) 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) No further swap is possible, since (1) we cannot swap actions of the same transaction and (2) w1(A) r2(A) and w1(B) r2(B) are both manipulating the same database element and one of them is a write. conflict-equivalent to T2, T1 r2(A) w2(A) r2(B) w2(B) r1(A) w1(A) r1(B) w1(B) r2(A) w2(A) r2(B) r1(A) w2(B) w1(A) r1(B) w1(B) r2(A) w2(A) r2(B) r1(A) w1(A) w2(B) r1(B) w1(B) r2(A) w2(A) r1(A) r2(B) w2(B) w1(A) r1(B) w1(B) r2(A) w2(A) r1(A) r2(B) w1(A) w2(B) r1(B) w1(B) r2(A) w2(A) r1(A) w1(A) r2(B) w2(B) r1(B) w1(B) No further swap is possible, since (1) we cannot swap actions of the same transaction and (2) w2(A) r1(A) and w2(B) r1(B) are both manipulating the same database element and one of them is a write.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.