Assignment 3

NOTES:
This assignment is meant to give you practice with foundations of database systems: Storage and Indexing, Disks and Files, and Tree 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 following classes of schedules: serializable, conflict serializable, and view serializable. For each of the following schedules, state which of the preceding classes it belongs to. If you cannot decide whether a schedule belongs in a certain class, explain briefly.
  1. T1:R(X), T2:R(X), T1:W(X), T2:W(X).
  2. T1:W(X), T2:R(Y), T1:R(Y), T2:R(X).
  3. T1:R(X), T2:R(Y), T3:W(X), T2:R(X), T1:R(Y).
  4. T1:R(X), T1:R(Y), T1:W(X), T2:R(Y), T3:W(Y), T1:W(X), T2:R(Y).