CS631  Homework 1

DUE: Tue Aug 8, 2006 in class

NOTE: All assignments must be handwritten in your own handwriting, on large
sized paper (please avoid notebook size paper).  Assignments must be
done individually.  If you are stuck on a problem after trying hard,
you can consult a friend, but in that case please mention against that
problem who you discussed it with.  There are negative points for doing 
this, but there will be negative points for copying without attribution,
so please be honest.


Write your name and rollnumber on every sheet.

----------------------

1) Consider the bitmap based technique for managing free space, described in
   Exercise 11.7.   (Try solving 11.7 yourself, but later check the answer
   online, no need to submit the solution to 11.7 though.)

   a) What are the benefits and drawbacks of allocating more bits per page 
      in the bitmap?
   b) A dumb way of finding a free block is to start search from the beginning
      of the bitmap each time.  Suggest a better way.

2) Suppose you have a workload where each transaction requires 2 IOs (one read
   and one write), and you need to support 1000 transactions per second.
   Suppose also that the total data size is 200 GB, and you have disks
   of 100 GB capacity, with average block access time (including seek, 
   latency and read/write transfer time) of 10 msec.  Design a disk 
   subsystem which can support the required workload, with 20 percent 
   spare capacity, i.e. design the system to support 1200 transactions per 
   second.

   Note: It's fine to assume that there will be no redundancy.
   Extra points (up to maximum for the assignment) if you also give an 
   answer with redundancy.

3)  (Exercise 11.8 from DBConcepts 5th ed):
   Standard buffer managers assume each page is of the
   same size and costs the same to read.  Consider a buffer
   manager that, instead of LRU, uses the rate of reference to objects, 
   that is, how often an object has been accessed in the last $n$ seconds.  
   Suppose we want to store in the buffer objects of varying sizes, and 
   varying read costs (such as Web pages, whose read cost depends on the 
   site from which they are fetched).

   Suggest how a buffer manager may choose which page to evict
   from the buffer.