Assignment 3

NOTES:
This assignment is meant to give you practice with foundations of database systems: Storage and Indexing, Disks and Files, and Indexing.

Problem 1

Suppose that a disk has storage capacity of 1TB and a block size of 4096 bytes. We have a table with 100,000 records each record has a size of 2050 bytes. Answer these questions:
  1. What is the total capacity of RAID 0 with 10 drives?
  2. What is the total capacity of RAID 5 with 10 drives?
  3. How many blocks are needed for spanned and unspanned records, respectively?
  4. What is the block (space) utilization in both cases?
  5. Assume that the disk has a read bandwidth of 1 GB/sec. Suppose that data is stored sequentially. What is the time to read all records in the unspanned configuration?
If records do not exactly fit in a block, we have two choices: (i) Waste the space at the end of each block and (ii) Start a record at the end of a block and continue on the next. Choice (i) is the unspanned option. Choice (ii) is the spanned option.

Problem 2

Consider a disk with the following specifications: sector size = 1024, 4000 tracks per surface, 100 sectors per track, 10 double-side platters, average seek time of 10 msec, and the disk platters rotate 7,200 rpm (revolutions per minute).
  1. What is the capacity of a track in KBs (an KB = 1024 bytes)?
  2. What is the capacity of each platter surface?
  3. What is the capacity of the disk?
  4. How many cylinders does the disk have?
  5. What is the maximum rotational delay?
  6. If an entire track of data can be transfer per revolution, what is the transfer rate?

Problem 3

Consider a B+-tree of order 2 (i.e., d = 2 and max. keys=4). Insert the following keys in order: 10, 20, 60, 7, 30, 66, 1, 73, 2, 85, 9, 88, 95, and 90.
  1. Show the final tree. Part points will be awarded for each correct insert if you show your intermediary work.
  2. Show the tree after each of the following deletions: 7, 85, 60.

Problem 4

Consider the Extendible Hashing index shown in the figure below. Answer the following questions about this index:



  1. Notice that a split occurred in the index. Denote by M the number of inserts in the index after the occurrence of the last split until the current configuration of the index. What is the minimum value of M? Argue your answer.
  2. Show the index after inserting an entry with hash value 76.
  3. Show the original index after inserting entries with hash values 25 and 101.