B+ tree
Assignment 2
Question 1 (16 marks)
Consider a relation and its FD set.
1) Check if ∈ F+. Justify your answer. (2 mark)
2) List all the candidate keys for. (2 marks)
3) How many super keys can be found for R? Compute the total number of super keys and
list 5 of them. (2 marks)
lossless-join? Please justify your answer. (2 marks)
8) Decompose it into a collection of BCNF relations if it is not in BCNF. Make sure your
decomposition is lossless-join and briefly justify your answers. (2 marks)
Question 2 (8 marks)
Consider the schedule below. Here, R() and W() stand for‘Read’and‘Write’, respectively.
, , and represent four transactions and tirepresents a time slot.
Time t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12
R(B) R(A) W(B) W(A)
R(B) R(A) W(B) R(A) W(A)
R(B) W(B)
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.
1) Assume a checkpoint is made between t6 and t7, what should be done to the four
transactions when the crash happens between t9 and t10. (2 marks)
2) Is the transaction schedule conflict serializable? Give the precedence graph to justify your
answer. (2 marks)
3) Give a serial schedule of these four transactions (there can be more than 12 time slots).
(2 marks)
4) 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)
Question 3 (6 marks)
1) There are currently 20 records in this tree. How many additional records could be added
to this tree without changing its height (give the maximum possible number)? Justify
your answers. (2 marks)
2) Show the B+ tree after adding the data entry with key 5 into the original tree. (2 marks)
3) Show the B+ tree after deleting the data entry with key 80 from the original tree. (2
marks)