[Solved] COMP9311 Assignment3

Consider the B+ tree shown in the following as an original tree.

Answer the following questions:

• (2 marks) There are currently 18 records in this tree. How many additional records could be added to this tree without changing its height (give the maximum possible number)?
• (3 marks) Show the B+ tree after inserting a data entry with key 3 into the original tree.
• (3 marks) Show the B+ tree after deleting the data entry with key 91 from the original tree.

Question 2

Consider a relation R(a,b,c,d,e,f,g,h) containing 10,000,000 records, where each data page of the relation holds 10 records. R is organised as a sorted file with the search key R.a. Assume that R.a is a candidate key of R, with values lying in the range 0 to 9,999,999. For the relational algebra ^!{a,b}((a>2,000,000 and a<8,000,000)(R)), state which of the following approaches (or combination thereof) is the most likely to be the cheapest:

1. Access the sorted file for R directly.
2. Use a clustered B+ tree index on attribute R.a.
3. Use a clustered B+ tree index on attribute R.b.
4. Use a linear hashed index on attribute R.a.
5. Use a clustered B+ tree index on attributes (R.a, R.b).
6. Use a linear hashed index on attribute s (R.a, R.b).

We assume that the database considers index-only plans. Index-only plans allow an index to contain all columns required to answer the query. It means that by using index-only plans, you will not have to access the data records in the file that contain the queried relations.

Question 3

Consider the schedule below. Here, R(*) and W(*) stand for Read and Write, respectively. T! ₁, !T₂, !T₃ and T! ₄ represent four transactions and !t_i represents a time slot.

Each transaction begins at the time slot of its first Read, and commits right after its last Write (same time slot).

Regarding the following questions, give and justify your answers.

• Assume a checkpoint is made between t! ₄ and t! ₅, what should be done to the four transactions when the crash happens between t! ₇ and t! ₈. (2 marks)
• Is the transaction schedule conflict serialisable? Give the precedence graph to justify your answer. (2 marks)
• Construct a schedule (which is different from above) of these four transactions which causes deadlock when using two-phase locking protocol. If no such schedule exists, explain why. (2 marks)
• Construct a schedule (which is different from above) of these four transactions which does not cause deadlock when using two-phase locking protocol. If no such schedule exists, explain why. (2 marks)