COMP9315 14s2 The University of New South Wales
COMP9315 DBMS Implementation
Final Exam 14s2 		DBMS Implementation
[Instructions] [Notes] [PostgreSQL] [C]
[Q1] [Q2] [Q3] [Q4] [Q5] [Q6] [Q7] [Q8]

Question 6 (11 marks)

Consider a linear hashed file which can hold just 3 tuples in each page (whether a main data page or an overflow page). The file has two parameters: depth, d, indicating that the file was size 2d at the start of the last expansion phase; split pointer, sp, containing the index of the next page to be split. The hash function h() produces the following hash values for keys A .. T.

Keyh(Key)
A...1010
B...0011
C...1110
D...1001
E...0000
Keyh(Key)
F...1110
G...0001
H...0100
I...1100
J...1101
Keyh(Key)
K...1111
L...0000
M...1010
N...0101
O...1100
Keyh(Key)
P...0101
Q...1010
R...0111
S...1000
T...1110

Assume that a split occurs on every 5th insertion (i.e. just before E J O, T are inserted). So, for example, the request insert(E) is received, a split occurs, and then E is inserted.

Start with a file with two empty pages (d = 1 and sp = 0).

Show the state of the file at the following points:

  1. immediately before the insert(E) request is received
  2. immediately after the insertion of E
  3. immediately before the insert(J) request is received
  4. immediately after the insertion of J
  5. immediately before the insert(O) request is received
  6. immediately after the insertion of O
  7. immediately before the insert(T) request is received
  8. immediately after the insertion of T

Use the following notation for showing the file contents: 

d = 1, sp = 1
[0] k1,k2,k3 -> k4
[1] k5,k6
[2] k7,k8,k9 -> k10,k11

This shows that file has a depth d of 1, the split pointer sp indicates page 1, page [0] contains three tuples in the main data page and one tuple in its overflow page, page [1] contains two tuples, etc. Each ki is the key value for a tuple stored in that page.

Using the above notation, the initial empty state of the file would be shown as: 

d = 1, sp = 0
[0] -
[1] -

After the insertion of A, B and C, the file would look like: 

d = 1, sp = 0
[0] A,C
[1] B

Instructions:

End of Question