[Solved] SOLVED: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, ve 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 le 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 t in one block? 2. How many blocks are required to store the entire le? 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 le 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 le sequentially? 7. What is the time required to read the whole le with random I/Os? Assume that you need to read each page of the le 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) buer management algorithms for a given workload. Here are the assumptions you must make: Assume there are four page slots your buer manager must manage: P1, P2, P3, and P4. All four slots are empty to start. When the buer 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 buer 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 Buer Page after the new page has been read. LRU Time Page Read Buer 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 Buer 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 les with the following kinds of access patterns (such as, place the le in the inside, middle, or outside tracks): 1. Frequent, random access to a small le (e.g., catalog relations). 2. Sequential scans of a large le (e.g., selection from a relation with no index) 3. Random accesses to a large le via an index (e.g., selection from a relation via the index). 4. Sequential scans of a small le. 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 rst two insertions for you.