CSE 532 Assignment #3
Due 23rd March, 2015 (before class)
Problem Set (100 points).
- (10 points) Exercise 13.2.4 (you should know how to solve 13.2.3 first, to get this right).
(20 points) Suppose that blocks hold five records, or twenty key-pointer pairs. Assume that duplicated keys
are allowed. More specifically, 1/3 of all search keys appear in one record, 1/3 appear in 2 records,
1/3 appear in 3 records. If no blocks are in memory initially, compute
the average number of disk I/O's needed to find all the records with a given search key K for the
following index structures. You may assume that the location of the
index block containing key K is known, although it is on disk.
- Sorted/sequential file with a dense index with a key-pointer pair for every record, including those with duplicate keys.
- Non-sequential file, and the bucket structure of Fig. 14.7. Assume that a block can store 100 pointers.
- (10 points) Exercise 14.2.8.
- (10 points) Exercise 14.2.9.
- (10 points) Exercise 14.3.8
- (10 points) Suppose we have a relation R(x,y) where
the range of both x and y is from 1 to 2000. We'd like to store R
in a grid file, using four grid lines in the x direction and the same
in the y direction (i.e., 25 regions). Unfortunately, the data in R is
surprising; it consists of the 2000 pairs (i,i) for i=1,2,...,2000. For
what partitions is the maximum number of points in a region is minimized?
What is that maximum?
- (10 points) Exercise 14.5.6.
- (10 points) Exercise 14.6.7.
- (10 points) Exercise 14.6.11.