Database management, Autumn 2005, Exercise 2 (19.9.-23.9.2005)

• A file of 200000 blocks is stored optimally on a disk having 10 disk surfaces. Every surface has 3000 tracks and every track may contain 24 (each 4KB) blocks. Disk adjust time is 1-12ms (average 6ms) and block transfer time is 0.2ms. One rotation takes 24*0.2= 4.8 ms.
  • How long does it take to read the hole file if the blocks are read sequentially?
  • How long does it take to read all blocks in a random order ?
  • How many blocks shoud be accessed at most so that reading them in random order is more efficient than reading them sequentially.
• Let the page size be 4KB. Page header takes 128 bytes and the record index 2 bytes for each record storen in a page. Each record has a 4 byte header. Table 'Student' has 16000 rows and it is defined as follows:

  create table student (
    personal_number char(11),
    student_number char(15),
    last_name varchar(80),    /* average length 9 */
    first_name varchar(80),    /* average length 12 */
    previous_name varchar(80), /*average length 2, mostly null */
    email varchar(80), /*average 20 */
    phone varchar(15), /*average 6 */
    major_studies char(3),
    last_visit date  /* length 7 bytes*/
  )
  

  Records are not split among pages.
  • How many pages are needed to store the student file when fixed size fields and records are used?
  • How many pages are needed to store the student file when fields are stored in a variable length format where each field has a length byte in front of it?
• The Student table of task 2 is stored as an sequential file ordered by student number. 20% free space is left in each page. The disk of task 1 is used.
  • What is the average search time for a random student record when seached by student number.
  • What is the average search time for a random student record when seached by personal number.
  • What is the search time when binary search is used when searched by student number? .
z
• A hash file has B = 10 buckets and the hash function h is defined as h(v) = v mod B. Each page may contain 3 records. A bucket has a home page and overflow pages if needed.
  • Give the contents of the pages after the records with the following keys have been inserted 60, 86, 40, 18, 92, 50, 30, 22, 36, 35, 46, 66, 11, 15, 65, 32, 76, 16, 21 and 56 in this sequence. Records with keys 18, 40, 46 and 56 are deleted. Give the contents of pages after the deletions.
  • After the insertions, how many page accesses are needed in average when a record with an existing key value is searched. What is the average number of accesses after the deletes?
• Table registration(StudentNumber, CourseCode, CourseNumber, GraupId, Year, Term, RegistrationTime, etc) containa data about course registrations. It is stored as a hash file with StudentNumber as the hash key. The address space consists of B= 5000 buckets of which 500 are empty. 5000 pages are reserved for overflows. Only 400 pages are used. There are 40000 records. How would you implement the query

  	select StudentNumber, count(CourseCode) from  registration 
  	where year=2003 and term='K' 
  	group by StudentNumber;
  

  (explain how you would read the file). How many disk accesses are needed? Estimate the amout of memory needed for the operation.