COS 425, Spring 2003 - Problem Set 4 -

Due at 11am, Thursday, March 13, 2003.

Collaboration Policy

You may discuss problems with other students in the class. However, each student must write up his or her own solution to each problem independently. That is, while you may formulate the solutions to problems in collaboration with classmates, you must be able to articulate the solutions on your own.

Problem 1 In Database Management Systems by Ramakrishnan and Gehrke, Chapter 8, exercise 8.10 pg. 302.

Problem 2 When discussing I/O costs in class, we used parameters D, the average time to read or write a page from disk, and B, the number of data pages in a file. Parameter D reflects seek time, rotational latency and transfer time. Suppose we introduce additional parameters T, which is only the transfer time of a data page, and P, the number of data pages per cylinder of disk.

Part a: Using parameters D, B, T, and P, give an equation for the I/O cost of a range search on a sorted file stored contiguously on disk. (Assume there is no rotational latency in reading from one track to the next within a cylinder when reading a file stored contiguously.)

Part b: Now consider the index structure shown in Figure 10.2 on page 340 of Database Management Systems by Ramakrishnan and Gehrke. Suppose that the index file is sorted by key values (Ki's) and stored contiguously on disk. Let I be the number of data pages in the index file. Assume that the data file has B pages and that these are not stored contiguously on disk. What is the equation for the I/O cost of range search for this index file and data file configuration? When is this a savings over your answer of part a?

Problem 3 In Database Management Systems by Ramakrishnan and Gehrke, Chapter 10, exercise 10.2, pgs. 365-366, Parts 1 through 4.

Problem 4 In Database Management Systems by Ramakrishnan and Gehrke, Chapter 10, exercise 10.8 pgs 367-368.

Problem 5 In Database Management Systems by Ramakrishnan and Gehrke, Chapter 10, pg. 368-369:
Part a Exercise 10.10, part 2.
Part b Exercise 10.12, part 2.  (Text errata:  "... alternate approach suggested in Section 9.7",  should be "10.7")