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) buﬀer management algorithms for a given workload. Here are the assumptions you must make: • Assume there are four page slots your buﬀer manager must manage: P1, P2, P3, and P4. • All four slots are empty to start. • When the buﬀer 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 buﬀer 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 Buﬀer Page after the new page has been read. LRU Time Page Read Buﬀer 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 Buﬀer 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.
You'll get 1 file (298.2KB)