Microsoft Word – Exercise 4_Database Storage Structures and Transaction Management.docx
Exercise 4
Question 1
Give and justify the answers regarding the following problems:
a) Construct a scenario that First in First Out (FIFO) buffer replacement policy is better than
Most Recently Used (MRU) buffer replacement policy.
b) Construct a scenario that First in First Out (FIFO) buffer replacement policy is better
than Least Recently Used (LRU) buffer replacement policy.
Question 2
Construct a scenario leading to the worst-case of the MRU buffer replacement policy.
Question 3
Consider the B+-tree shown in the following as an original tree.
Answer the following questions.
1) Show the B+-tree after inserting a data entry with key 37 into the original tree.
2) Draw a valid B+-tree with the maximum number of tree nodes that contains the same data entries
in the original tree. (The new B+-tree should have the same order as the original tree)
Question 4
What are the main differences between ISAM and B+ tree indexes?
Question 5
How many nodes must be examined for equality search in a B+ tree? How many for a range
selection? Compare this with ISAM.
Question 6
Prove that the basic two-phase locking protocol guarantees conflict serializability of
schedules.
Question 7
Consider a database with objects X and Y and assume that there are two transactions T1 and
T2. Transaction T1 reads objects X and Y and then writes object X. Transaction T2 reads
objects X and Y and then writes objects X and Y.
1. Give an example schedule with actions of transactions T1 and T2 on objects X and Y that
results in a write-read conflict.
2. Give an example schedule with actions of transactions T1 and T2 on objects X and Y that
results in a read-write conflict.
3. Give an example schedule with actions of transactions T1 and T2 on objects X and Y that
results in a write-write conflict.
4. For each of the three schedules, show that Strict 2PL disallows the schedule.
Question 8
An IT company developed a new database system to record the static data of the coming
Opera
House Open Day including the number of reservations X, remaining gifts Y and meals
ordered Z.
Here is a schedule of three transactions:
S1, R1(X), S2, R2(Y), W1(X), E1, S3, R3(X), A, W2(Y), E2, R3(Y), B, W3(Y), W3(X), E3
Where Si indicates the start point of transaction i, Ei indicates the end point of transaction i,
Ri(X)
indicates a read operation in transaction i on a variable X, and Wi(X) indicates a write
operation in
transaction i on a variable Y.
Answer the following questions and justify your answers.
1) Assume that the system crashes at B, what should be done to recover the system?
2) Assume a checkpoint is made at point A, what should be done to the three transactions
when the crash happens at B?
Question 9
Given the three transactions in Question 8:
1) Is the transaction schedule conflict serializable?
2) Construct a schedule (may not be the same as above) of these three transactions which
causes deadlock when using two-phase locking protocol. If no such schedule exists, explain
why.
Question 10
Consider the Extendible Hashing index shown below. Answer the following questions about
this index:
1) Show the index after inserting an entry with hash value 68.
2) Show the index after inserting entries with hash values 17 and 69.