Practice questions from the second half of the semester

We prepared a series of practice questions to help you familiarize with the fundamental concepts introduced in the lecture, from Chapter 12 through Chapter 16.

(Answer Key)

Due Date

• Assignment 2 is due on 11:59 PM, Monday, December 15th.
• Note: In preparation for the final exam, we will release the answer key on Tuesday, December 16.

Question Set

A. B+ tree (40 pts)

1. (8 pts) Consider the following partially filled B+ tree with n = 5 (maximum of 5 pointers per node, therefore maximum of 4 keys per node)

   

   1. Part 1 (4 pts): Fill in the value(s) present in the root of the tree.
   2. Part 2 (4 pts): There are many sequences of exactly 3 insertions that will cause the root node in the given B+ tree (above) to split. List one such sequence of “three insertions”, and briefly justify your choice. (The justification should be In the format of: inserting [A, B, C] will lead to the root node to split because…).

2. (8 pts) Use the following B+ tree with n = 4 (maximum 4 pointers, maximum 3 keys per node), apply each of the following operations in order, and show the tree after each operation

   

   1. (4 pts) Insert 65
   2. (4 pts) Insert 68

3. (12 pts) Construct a B+ tree for the following set of key values:

   (5, 15, 25, 35, 45, 55, 20, 40, 60, 70, 80, 30, 50, 10, 65, 75)

   Assume that the tree is initially empty and values are added in the order as described. Construct the B+ tree for the case where the number of pointers (n) that will fit in one node is four (n = 4).

   You may draw and fill the tree by hand, take a screenshot/picture, and embed it in your report. Draw/write legibly; we have to deduct points if we are unsure what you drew/wrote.

4. (12 pts) Use the B+ tree constructed from the last question (question 3), apply each of the following operations in order, and show the tree after each operation:

   1. (3 pts) Insert 18.
   2. (3 pts) Insert 22
   3. (3 pts) Delete 30
   4. (3 pts) Delete 45

B. Query Processing - Join Cost Estimation (30 pts)

1. Join Cost Estimation: Let relations employee(emp_id, name, dept_id) and project(proj_id, dept_id, budget) have the following properties:

   • employee has 15,000 tuples
   • project has 30,000 tuples
   • 20 tuples of employee fit on one block
   • 25 tuples of project fit on one block
   • (Updated 12/14: Please use the same $b_b = 1$ for this question, as was provided in the lecture slides on 11/17.)

   Estimate the number of block transfers and seeks required using each of the following join strategies for employee ⋈ project:

   1. (10 pts) Nested-loop join
   2. (10 pts) Block nested-loop join
      • Please use M=3 for calculation. We will use the "improved algorithm" for this question. For reference, please see the "Worst and Best Cases" given in class (on 11/20's class slides 49, with page number 86).
   3. (10 pts) Merge join
      • (assume both relations need to be sorted first, with M = 50 memory blocks available)
   4. (8 pts) Hash join
      1. (Updated: 12/12: This question was misplaced due to mistake. We did not covered this in class, so this will be excluded from this assignment.)