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.

Due Date

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

Question Set

A. B+ tree (36 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

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

   1. (7 pts) Nested-loop join
   2. (8 pts) Block nested-loop join
   3. (7 pts) Merge join (assume both relations need to be sorted first, with M = 50 memory blocks available)
   4. (8 pts) Hash join

C. Query Processing - Cost estimation (30 pts)

1. Query Size Estimation with RA Tree (18 pts): Consider the relations Student(student_id, name, major) and Enrollment(student_id, course_id, grade) with the following properties: