CSE 444

University of Washington

Winter 2000

Homework 4

See the web page for some homework guidelines and policies.

DUE: at beginning of class, Friday February 18

  1. (6 points) Exercise 7.10.

  2. (12 points) Exercise 8.2. Answer the questions for all three file organizations (heap, hash, sorted). Assume that "key" means "candidate key" and that "cost" means number of I/O operations. For heap files, assume no compaction takes place. For hashed files, assume no overflow pages exist.

  3. (12 points) Exercise 8.8. Write each of your data entries on a separate line. Data entries for Alternative 1 need not include the entire tuple; e.g. just "12" is a good data entry for part (1) -- consider it as shorthand for the pair (12, [53832,Guldu,guldu@music,12,2.0]). For Alternatives 2 and 3, a data entry example is as follows (using fictitious data this time): "17, (3, 1), (3, 2)" indicating that there are two tuples with search key value 17, and they are located on page 3 in slots 1 and 2.

  4. (12 points) Exercise 9.2, parts 1-4. For parts 2 and 3, draw the changed portions of the tree.

  5. (10 points) Exercise 9.4, part 1.

  6. (12 points) Exercise 9.8, parts 1, 2, 4. Ignore the phrase "using the bulk loading algorithm", just assume the tree was built bottom-up by filling the nodes at each level as full as possible, to minimize the number of nodes at each level.

  7. (14 points) Exercise 9.10, parts 1 and 3.

  8. (22 points) Exercise 12.4, parts 1, 2, 3, 6, 7.