02/05/2020
COMP9315 14s2
COMP9315 14s2 Final Exam
The University of New South Wales
COMP9315 DBMS Implementation Final Exam 14s2
[Instructions] [Notes] [PostgreSQL] [C] [Q1] [Q2] [Q3] [Q4] [Q5] [Q6] [Q7] [Q8]
DBMS Implementation
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.
Key
h(Key)
A
…1010
B
…0011
C
…1110
D
…1001
E
…0000
Key
h(Key)
F
…1110
G
…0001
H
…0100
I
…1100
J
…1101
Key
h(Key)
K
…1111
L
…0000
M
…1010
N
…0101
O
…1100
Key
h(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:
a. immediately before the insert(E) request is received b. immediately after the insertion of E
c. immediately before the insert(J) request is received d. immediately after the insertion of J
e. immediately before the insert(O) request is received f. immediately after the insertion of O
g. immediately before the insert(T) request is received h. immediately after the insertion of T
Use the following notation for showing the file contents:
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 = 1
[0] k1,k2,k3 -> k4
[1] k5,k6
[2] k7,k8,k9 -> k10,k11
1/2
d = 1, sp = 0
[0] –
[1] –
https://www.cse.unsw.edu.au/~cs9315/19T2/past-exams/14s2/Q06.html
02/05/2020 COMP9315 14s2 Final Exam
After the insertion of A, B and C, the file would look like:
d = 1, sp = 0
[0] A,C
[1] B
Instructions:
Type your answer to this question into the file called q6.txt Submit via: submit q6
End of Question
Powered by TCPDF (www.tcpdf.org)
https://www.cse.unsw.edu.au/~cs9315/19T2/past-exams/14s2/Q06.html 2/2