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 keypointer 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 keypointer pair for every record, including those with duplicate keys.
 Nonsequential 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.