CS5481 Data Engineering Tutorial 5
1. Suppose that we are using extendable hashing on a file that contains records with the following search-key values:
2, 3, 5, 7, 11, 17, 19, 23, 29, 31
Show the extendable hash structure for this file if the hash function is h(x) = x mod 8 and
buckets can hold three records.
2.
(a) Consider a record to be deleted from an extendable hash structure.
(i) With which bucket can this bucket be coalesced?
(ii) Under which conditions the buckets can be coalesced?
(b) Show how the extendable hash structure in Question 1 changes as the result of
deleting 11. Coalesce buckets if possible.
3. Suppose that a secondary B+-tree index on building is available on relation department, and that no other index is available. Discuss different ways to process the following selections.
(a) ¬ (building = “Watson”) (department)
(b) ¬ (building < “Watson”) (department)
(c) ¬ (building < “Watson” ∨ budget <5000) (department)
4. Suppose that an employee file has 10,000 records stored in 2,000 contiguous disk blocks and the following indices.
A 3-level B+-tree primary index on salary
A 2-level B+-tree secondary index on dept_no
Explain your choice of algorithm in evaluating the following selection, assuming that salary > 9,000 (employee)
(b) Suppose 80% of the employee has salary over 9,000 and the department number of 1% of the employees is greater than 198. Explain your choice of algorithm in evaluating the following selection, assuming that tS = 4ms and tT = 0.1ms.
salary > 9,000 AND dept_no > 198 (employee)
(a)
tS = 4ms and tT = 0.1ms.