CSE 532 Assignment #3

Due 23rd March, 2015 (before class)

Problem Set (100 points).

  1. (10 points) Exercise 13.2.4 (you should know how to solve 13.2.3 first, to get this right).
  2. (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.
    1. Sorted/sequential file with a dense index with a key-pointer pair for every record, including those with duplicate keys.
    2. Non-sequential file, and the bucket structure of Fig. 14.7. Assume that a block can store 100 pointers.
  3. (10 points) Exercise 14.2.8.
  4. (10 points) Exercise 14.2.9.
  5. (10 points) Exercise 14.3.8
  6. (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?
  7. (10 points) Exercise 14.5.6.
  8. (10 points) Exercise 14.6.7.
  9. (10 points) Exercise 14.6.11.