Assignment 3
NOTES:
- Hard deadline! Sunday, March 22.
- This is an individual homework; no groups allowed.
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:
What is the total capacity of RAID 0 with 10 drives?
What is the total capacity of RAID 5 with 10 drives?
How many blocks are needed for spanned and unspanned records, respectively?
What is the block (space) utilization in both cases?
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).
- What is the capacity of a track in KBs (an KB = 1024 bytes)?
- What is the capacity of each platter surface?
- What is the capacity of the disk?
- How many cylinders does the disk have?
- What is the maximum rotational delay?
- 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.
- Show the final tree. Part points will be awarded for each correct insert if you show your intermediary work.
- 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.
- T1:R(X), T2:R(X), T1:W(X), T2:W(X).
- T1:W(X), T2:R(Y), T1:R(Y), T2:R(X).
- T1:R(X), T2:R(Y), T3:W(X), T2:R(X), T1:R(Y).
- T1:R(X), T1:R(Y), T1:W(X), T2:R(Y), T3:W(Y), T1:W(X), T2:R(Y).