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

(a) Using FIFO buffer replacement policy.

(b) Using LRU buffer replacement policy.

(c) Using Clock buffer replacement policy.

2. (10pt) Figure 1 shows a SimpleDB log page with one log record ["a", "b"]. Suppose two more log records, ["SetString", 10, "Joe"] and ["COMMIT", 10], are appended to the page. Show the content of the log page after each record is appended.

Figure 1. SimpleDB Log Page

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

Suppose a system crash may happen between any two operations in the sequence. Please answer the following questions:

(a) Can the DBMS recover from a system crash using Undo-only Recovery? If not, rearrange the operations so it can be recovered using Undo-only Recovery.

(b) Can the DBMS recover from a system crash using Redo-only Recovery? If not, rearrange the operations so it can be recovered using Redo-only Recovery.

4. (10pt) 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. Note that a schedule is not considered 2PL if there is a deadlock, and if that's the case you need to identify where the deadlock happens.

5. (15pt) According to the Multiversion Locking protocol, when a read-only transaction requests a value from a block, it can read from the version of the block that was most recently committed at the time the transaction began. Suppose we extend this to the read operations in read-write transactions. Specifically, for a read-write transaction T,

• If a block is updated by T, subsequent read operations in T will read from the version of the block produced by T.
• If a block is not updated by T, read operations in T will read from the version of the block that was most recently committed at the time when T began.

6. (10pt) Given the SimpleDB grammar shown on Slide 10 and 11 of the lecture notes, decide whether the following SQL statements are syntactically correct in SimpleDB:

create table students ( id integer, name varchar(10) );

select name from students where id > 10;

select * from students where id = 10 or name = 'Joe';

If a statement is not syntactically correct, you must identify which grammar rule(s) it violates.

7. (20pt) Figure 2 shows a B-tree index of order 3.

Figure 2. B-tree

Draw the B-tree index after the following keys are inserted: 155,4,8,31,113,10,162,141.

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