Description
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:
- Access the sorted file for R directly.
- Use a clustered B+ tree index on attribute R.a.
- Use a clustered B+ tree index on attribute R.b.
- Use a linear hashed index on attribute R.a.
- Use a clustered B+ tree index on attributes (R.a, R.b).
- 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! 1, !T2, !T3 and T! 4 represent four transactions and !ti represents a time slot.
| Time | t! 1 | t! 2 | t! 3 | t! 4 | t! 5 | t! 6 | t! 7 | t! 8 | t! 9 | t! 10 | t! 11 | t! 12 |
| T 1 | R(B) | R(A) | W(B) | W(A) | ||||||||
| T 2 | R(A) | W(A) | ||||||||||
| T 3 | R(B) | W(B) | ||||||||||
| T 4 | R(A) | W(A) | R(B) | W(B) |
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! 4 and t! 5, what should be done to the four transactions when the crash happens between t! 7 and t! 8. (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)
