Sample Solutions to Midterm #4
Page 2 Q1. b
Page 3 Q2a.
LHS = 100 * (1.2 + 1) = 220 page I/Os
RHS = 100 *(3 + 125) = 12800 page I/Os, where the “125” comes from: 5,000,000 Reserves records / 40,000 Sailors records =
125 reserves records per sailor on average Total = 200 + 12,800 = 13,020 page I/Os
Q2b.
Yes.
RHS = 100(3 + 2) = 500 page I/Os. (We accepted 1 or 2 or 1.25 in place of “2”.)
Q2c.
Yes.
LHS = 500 pages for a table scan of Sailors. (OK if you used a table scan here and said there was “no change” from Q2a because you used already used a table scan there.)
Page 4
Q3.
Sort Table X: ceiling(24,000 / 370) = 65 sorted runs; ceiling(65 / (370 – 1)) = 1 SR So, we use 2 passes to sort X.
SMJ formula: cost = sort X + sort Y + merge X & Y
= 24,000(2)(2 passes) + Y(2)(p passes) + (24,000 + Y)
Therefore, 120,150 ≥ 96,000 + 2Yp + 24,000 + Y 120,150 ≥ 120,000 + 2Yp + Y
150 ≥2Yp+Y
Note that “≤ 150 pages” can easily be done in one pass; so, p must be 1.
150 ≥2Y+Y
150 ≥ 3Y In conclusion, Y = 50 pages.
Q4.
R = ceiling(20,000 / 100) = 200 pages S = ceiling(60,000 / 200) = 300 pages B = 31
Size of partitions of R: ceiling(200 / (31 – 1)) = 7 pages each on average Size of partitions of S: ceiling(300 / (31 – 1)) = 10 pages each on average
Cost = 3(M + N) = 3(200 + 300) = 1500 page I/Os.
Page 5
Q5a.
floor(4096 / (4 + 10)) = 292 pairs per page for the table ceiling(250,000 / 292) = 857 pages needed
Q5b.
ceiling(250,000 bits / (4096 bytes/page * 8 bits/byte)) = 8 pages per bit vector Note that there is one bit vector per candy (one for “licorice nibs”, one for “Kit- Kat”, etc.)
Q5c.
The indexes will allow us to determine which customers’ favourite candy is “Kit- Kat”, for example.
B+ tree:
Solve:
floor(4096 / (15 + 10)) = 163 data entries / leaf page ceiling(250,000 DE / 163 DE/leaf page) = 1534 leaf pages ceiling(1534 / (163 + 1 )) = 10 level-1 pages
ceiling(10 / (163 + 1)) = 1 root page
Sum of all index pages (internal + leaf) = 1545 pages
8x + 857 + 1 > 1545 … where 8x is from (b), and 857 is from (a) 8x > 687 (OK if you used 1534 in place of 1545)
x > 85.9
x = 86 kinds of candy (We accepted 84, 85, 86, or 87.)
Page 6
Q6.
— OK to include the keyword “DISTINCT” in the following SELECT clause
SELECT FROM WHERE
S.RATING, R.DAY, R.BID SAILORS S, RESERVES R S.SID = R.SID
AND
S.YEARS >= 58 AND
R.BID > 30;
— S. and R. are not necessary
— S. or SAILORS., etc. is necessary
Page 7 Q7.
Q7a. Left Child:
Read all of S = 500 pages.
Keep 2/60 of its rows or pages (approx..)
Keep fraction ((4 + 4) / 50) of the record, which is 8 bytes out of 50 bytes when writing to T1.
500 * 2/60 * 8/50 = 3 pages to write to T1
Q7b. Right Child:
Read all of R = 1000 pages.
Keep 270/300 of its rows (for R.bid > 30).
Keep fraction ((10 + 4 + 4) / 40) of the record = 18 bytes out of 40 bytes when writing to T2.
1000 * 270/300 * 18/40 = 405 pages to write to T2 Q7c. Rest of the Work (i.e., BNL and grand total):
BNL = 3 + ceiling(3 / (25 – 2)) * 405 = 408 page I/Os.
Grand Total = (500 + 3) + (1000 + 405) + (408) page I/Os = 2316 page I/Os
Note: The equivalent solution when done using tuples is: (500 + 3) + (1000 + 397) + (3 + 397) = 2300 page I/Os (or very close to it).
We need to retain sid from both R & S.
We need to retain rating from S.
We need to retain day, bid, & sid from R.
(By the way, it’s OK if you compute pages or tuples in what follows.)