1. (15pt) Suppose a buffer pool has 4 buffer pages. Show the content of the buffer pages (including pin counts) after the following operations: pin(b1), pin(b2), pin(b3), pin(b4), unpin(b4), unpin(b2), unpin(b3), pin(b5), unpin(b5), pin(b6), pin(b3).

(a) Using FIFO buffer replacement policy.

(b) Using LRU buffer replacement policy.

(c) Using Clock buffer replacement policy.

2. (20pt) Analyze the original SimpleDB code and answer the following questions:

(a) When does SimpleDB flush the buffers modified by a transaction?

(b) When does SimpleDB flush the log records of a transaction?

(c) The original SimpleDB uses Undo-only recovery. Can we modify SimpleDB to use Redo-only recovery without changing the way SimpleDB flushes the buffers and the log? Explain why.

(d) The original SimpleDB uses Undo-only recovery. Can we modify SimpleDB to use Undo/Redo recovery without changing the way SimpleDB flushes the buffers and the log? Explain why.

3. (10pt) One of the ways to do nonquiescent checkpointing is as follows:

• Write a log record <START CKPT(T1,...,Tk)> and flush the log. T1,...,Tk are the currently running transactions.
• Wait until all T1,...,Tk commit or abort. New transactions may start during this time.
• When all T1,...,Tk have completed, write a log record <END CKPT> and flush the log

Suppose we use this type of nonquiescent checkpointing in Undo-only recovery. How far back in the log do we need to scan before we are certain that all incomplete transactions are undone?

4. (10pt) Consider the following two schedules:

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

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

(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.

5. (10pt) 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.

6. (20pt) Figure 1 shows a B-tree index of order 3.

Draw the B-tree index after the following keys are inserted: 180,139,176,115,1,147,155,2.

7. (15pt) Consider an Extendable Hash Index with the following parameters:

• Maximum depth M = 4
• Hash function is K%16, where K is the key value
• Each block can hold two index entries