COMP9315 22T1 Final Exam

The University of New South Wales COMP9315 DBMS Implementation 22T1 Final Exam

DBMS Implementation

Question 6 (10 marks)

Consider a linear hashed file with the following properties

• initially with 2 (empty) pages in the file, d = 1, sp = 0
• able to hold up to 2 tuples per page
• an associated overflow file (initially empty, no pages)
• each page in the overflow file can also hold up to 2 tuples

A set of numeric keys (the numbers 1 to 32) are inserted into the file, in numeric order. Splits occur just before the insertion of the keys 6, 12, 18, 24, 30 The hash value of each key is simply the binary value of the number (e.g. hash(1) = 00000001, hash(15) = 00001111, and hash(21) = 00010101).

Show the state of the file(s) at the following points:

1. immediately before each split operation (before inserting the new value)

2. immediately after each split operation and after inserting the new value

The state should include:

• the pages of the data file, with tuples indicated by key values
• the depth of the file (d), the position of the split pointer (sp)
• any overflow pages, linked to their corresponding data pages by arrows

An abstract example (not using the above hash values) of what a state might look like:

[0] 1,2 -> 11,12
[1] 3,4
[2] 5,6 -> 13
[3] 7,8 -> 14,15 -> 16
[4] 9,10

d = 2 sp = 1

This is a sample just to show the format of states. It bears no relation to the hash values in this question.

Instructions:

• Type your answer to this question into the file called q6.txt
• Submit via:   give cs9315 exam_q6 q6.txt
  or via: Webcms3 > exams > Final Exam > Q6 submission > Make Submission