FINAL
CS422, Fall 2012


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

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

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

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,

Use an example to show that this "modified Multiversion Locking protocol" may produce non-serializable schedules.

6. (15pt) Figure 2 shows a B-tree index of order 3.

[Btree Index]

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:

Draw the index after the following keys are inserted: 1,47,106,13,135,190,20,41.