CS计算机代考程序代写 database Microsoft Word – Exercise 4_Database Storage Structures and Transaction Management.docx

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.