COMP9315 21T1 Final Exam

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

DBMS Implementation

Question 4 (9 marks)

Consider a linear hashed file with the following properties

• initially empty (0 pages) data file
• able to hold up to 3 tuples per page
• an associated overflow file (also initially empty)
• a set of keys with the following hash values:

  Key	Hash	Key	Hash	Key	Hash	Key	Hash
  'a'	10001	'g'	00111	'm'	11101	's'	01100
  'b'	00010	'h'	11000	'n'	01110	't'	00001
  'c'	10011	'i'	01001	'o'	01111	'u'	00010
  'd'	00100	'j'	11010	'p'	11000	'v'	11111
  'e'	10101	'k'	01011	'q'	01001	'w'	01010
  'f'	00110	'l'	11100	'r'	01010	'x'	10101

The keys are inserted in alphabetical order starting from 'a'.

Use this trigger for splitting: split before inserting every fifth tuple (i.e. just before inserting 'e', 'j', 'o', 't')

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

3. after inserting 'x'

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 example (not using the above hash values) of what a state might look like:

[0] a,b,c -> n,o
[1] d,e,f -> p,q,r -> s,t
[2] g,h   -> u
[3] i,j,k
[4] l,m   -> v,w,x -> y,z

d = 2 sp = 1

Instructions:

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