Assignment #4 Database Systems_ SOLUTION

Problem 1. [20pts] Consider a disk with a sector size of 512 bytes, 100 sectors per track, 2000 tracks per surface, five double-sided platters (i.e., 10 surfaces). The disk platters rotate at 7400 rpm (revolutions/rotations per minute). The average seek time is 8 ms (millisecond). Suppose that the block size is 1024 bytes. Consider a file containing 100,000 records of 200 bytes each that is to be stored on such a disk and that no record is allowed to span two blocks.1. How many records can fit in one block? 2. How many blocks are required to store the entire file? 3. How many tracks and how many cylinders are needed? 4. How many records can be stored on the disk? 5. Assume that the pages of the file are stored sequentially on the disk, with page 1 on block 1 of track 1 of surface 1, page 2 on block 2 of track 1 of surface 1, etc. What page is stored on the block 1 of track 1 of the next surface (surface 2)? 6. What is the time that is required to read the whole file sequentially? 7. What is the time required to read the whole file with random I/Os? Assume that you need to read each page of the file once and that each page access is a random block access. Problem 2. [20pts] In this exercise, you will compare the LRU (least recent used) and MRU (most recent used) buffer management algorithms for a given workload. Here are the assumptions you must make: • Assume there are four page slots your buffer manager must manage: P1, P2, P3, and P4. • All four slots are empty to start. • When the buffer pool has unused slots (such as at the beginning, when all four slots are empty), it will put newly read data in the leftmost empty slot (e.g., if slots 2 and 3 are free, it will use slot 2). • The pages to be read from disk are labeled A through G. • For each access the page is pinned, and then immediately unpinned. Below are two tables for describing the contents of the buffer pool at each time step. A page is read at the beginning of each time step. You should record, in the table, the contents of each Buffer Page after the new page has been read. LRU Time Page Read Buffer Frame P1 P2 P3 P4 1 G 2 F 3 E 4 D 5 G 6 C 7 F 8 E 9 D 10 C 11 D 12 B 13 A 14 D 15 F No. of Pages Evicted: MRU Time Page Read Buffer Frame P1 P2 P3 P4 1 G 2 F 3 E 4 D 5 G 6 C 7 F 8 E 9 D 10 C 11 D 12 B 13 A 14 D 15 F No. of Pages Evicted: Problem 4. [30pts] Modern disk drives store more sectors on the outer tracks than the inner tracks. Since the rotation speed of the disk is constant, the sequential data transfer rate is also higher on the outer tracks. The seek time and rotation delay are unchanged. Given this information, explain good strategies for placing files with the following kinds of access patterns (such as, place the file in the inside, middle, or outside tracks): 1. Frequent, random access to a small file (e.g., catalog relations). 2. Sequential scans of a large file (e.g., selection from a relation with no index) 3. Random accesses to a large file via an index (e.g., selection from a relation via the index). 4. Sequential scans of a small file. Problem 5. [30pts] Consider a B+-tree of order 2. The maximum number of pointer per node is 5 and the maximum number of entries is 4. Show the results of entering the keys 1,2,..., 15 (in that order) to an initially empty B+-tree. Show the state of the tree after every 2 insertions. Below I have done the first two insertions for you.