Homework 5
CS422, Fall 2012

Due: Thursday, November 29

Please upload your files to CSNS. Note that file uploading will be disabled automatically after 11:59PM of the due date, so please turn in your work on time.

1. (30pt) For a transaction T, consider the following sequence of operations performed by a DBMS:

Start Transaction
<START, T>
Write(X, vx')
<UPDATE, T, X, vx, vx'>
Write(Y, vy’)
<UPDATE, T, Y, vy, vy'>
Flush(log);
Flush(X);
<COMMIT, T>
Flush(log)
Commit;
Flush(Y)

Suppose a system crash may happen between any two operations in the sequence. Please answer the following questions, and for each question, give a brief explanation of your answer.

(a) Can the DBMS recover from a system crash using Undo-only Recovery?

(b) Can the DBMS recover from a system crash using Redo-only Recovery?

(c) Can the DBMS recover from a system crash using Undo/Redo Recovery?

2. (40pt) Consider the following two schedules:

S1:  r2(b2),r2(b3),w1(b1),r2(b1),w2(b1),r1(b2),w2(b3),r2(b4),r1(b3),w1(b3),r1(b4),w2(b4)

S2:  r1(b1),w1(b1),r2(b2),r2(b3),r2(b1),r1(b2),w2(b1),r1(b3),w2(b3),r2(b4),r1(b4),w2(b4)

(a) Are these two schedules serializable? Explain why.

(b) Are these two schedules 2PL (i.e. can a scheduler produce these two schedules by following the 2PL protocol)? Explain why.

3. (20pt) Consider the following schedule:

w1(b1),w1(b2),c1,r3(b1),w2(b2),c2,r3(b2),c3

According to the Multiversion Locking protocol, the read-only transaction T3 should read blocks b1 and b2 written by T1. However, we notice that a new version of b2 written by T2 is available before T3 reads it, and furthermore, T2 is already committed before T3 reads b2, so it seems to make sense to modify the Multiversion Locking protocol to allow T3 to read the version of b2 written by T2 instead of the one by T1. Use an example to show that this "modified Multiversion Locking protocol" may produce non-serializable schedules.