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(b2), unpin(b4), pin(b3), unpin(b1), unpin(b3), pin(b2), unpin(b3), pin(p5), pin(b6).

(a) Using FIFO buffer replacement policy.

(b) Using LRU buffer replacement policy.

(c) Using Clock buffer replacement policy.

2. (15pt) Given the SimpleDB grammar shown on Slide 15 and 16 of the lecture notes.

(a) Decide whether the following SQL statements are syntactically correct in SimpleDB:

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

select id, name from students, departments

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

(b) Modify the SimpleDB grammar to allow the use of arithmetic operations (i.e. +, -, *, and /) in WHERE conditions. For example, the following query should be syntactically correct under the modified grammar:

select id, name from students where id + 2 * 5 = 100 - 2

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 (Flush(log) operations can be added or removed if necessary) 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 (Flush(log) operations can be added or removed if necessary) so it can be recovered using Redo-only Recovery.

4. (20pt) 

(a) Show an example of a schedule that is serializable but not serial. Explain why it is serializable but not serial.

(b) Show an example of a schedule that is serializable but not 2PL. Explain why it is serializable but not 2PL.

(c) Show an example of a schedule that is serializable but not recoverable. Explain why it is serializable but not recoverable.

(d) Show an example of a schedule that is recoverable but not ACR. Explain why it is recoverable but not ACR.

5. (10pt) 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. (15pt) 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: 1,47,106,13,135,190,20,41.

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