Page 2 Q1. b
Page 3 Q2(a):
Sample Solutions to Midterm #2
# bytes in the key = 4 + 4 = 8
floor (4096 bytes/leaf page / (8 + 10) bytes/data entry ) = 227 DE/leaf page
# of records is determined by:
200 mines * 10 years * 365.25 days/year = 730,500 records in the table
ceiling( 730,500 DE / 227 DE/leaf page) = 3219 leaf pages
Q2(b):
floor( 4096 * 0.70 bytes/page / 110 bytes/record ) = 26 records/page
Q2(c):
They probably plan to add more mines to their table/repository, complete with those mines’ 10-year historical data.
Note that simply adding more data for existing mines in the table (i.e. future dates) will cause those records to go at the end of the table. This is because the table is stored in clustering order by date. Therefore, simply adding more data to the table as time progresses would not be a reason to have 30% freespace on each page.
Page 4 Q3.
Insert 12, 15, 7, 24, 8:
Global depth nub = 1
0 → (12, 24, 8) Local depth nub = 1 1→(15,7, -) Localdepthnub=1
Page 5 Q4.
Insert 6:
Global depth nub = 2 00 → (12, 24, 8)
01 → (15, 7, -)
10 → (6, -, -)
11 →
Insert 16:
Local depth nub = 2 Local depth nub = 1 Local depth nub = 2 points to 01’s bucket
Local depth nub = 3 (we need all 3 bits to distinguish) Local depth nub = 1
Local depth nub = 2
points to 001’s bucket
Local depth nub = 3 points to 001’s bucket points to 010’s bucket points to 001’s bucket
Global 000 → 001 → 010 → 011 → 100 → 101 → 110 → 111 →
depth nub = 3 (24, 8, 16) (15, 7, -)
(6, -, -)
(12, -, -)
Solvefork: floor(4096/(k+10))≥90
4096 ≥ 90(k + 10)
4096≥90k+900
3196 ≥ 90k
35.5≥k
Therefore, k = 35 (we use the floor).
Verify: If k = 35, then floor(4096/ (35 + 10) ) = 91 If k = 36, then floor(4096/ (36 + 10) ) = 89
Q5.
ceiling(28000 DE / 140 DE/leaf page) = 200 leaf pages in the whole B+ tree
But, we’ll only need to visit:
o 1 root page + 1 level-1 page + ceiling( 10000/28000 * 200 ) leaf pages o Thisis1+1+72=74pageI/Os.
Page 6 Q6.
Parent has 3 children: A with 56 data entries, B with 56 DEs, and C with 56 DEs
Note that B is in the middle.
We can right away delete 14 keys from B. This leaves us with the minimum: 42.
We can go ahead and delete another 14 keys from B, and borrow from neighbour
A (or C). Now, A and B both have 42—the minimum.
We can go ahead and delete another 14 keys from B, and borrow from neighbour
C. Now, A, B, and C each have 42—the minimum.
Thus,wedeleted14+14+14=42keysinall.
Q7.
Level 0: The root has 10 keys—the maximum.
Level 1: The root has 11 children—the maximum. So, each of those children has
10 keys, at capacity. This is 110 keys in level 1.
Level 2 (leaf level): The Level-1 parents each had 11 children. Since each of
those children have 10 keys, this means that each of the 11 children have 11 children of their own. This means there are 112 * 10 = 1210 keys (or data entries) at the leaf level, when the leaf level is at capacity.
Page 7 Q8.
(a) Elevator Algorithm:
o 0→800→1500→2100→4000→4500→2000→1600→1300 o Distance travelled = 4500 + 3200 = 7700 cylinders
(b) SSTF Algorithm:
o 0→800→1500→2100→2000→1600→1300→4000→4500 o Distance travelled = 2100 + 100 + 400 + 300 + 2700 + 500 = 6100
cylinders
We also accepted an alternate interpretation of the question: 0 → 1500 → 2100
and then do: {4000, 800, 1300, 2000, 4500, 1600}
o In that case:
Elevator = 8200 cylinders travelled SSTF = 7100 cylinders travelled
Page 8
Q9. List the names of the tables and their creator IDs (or authID or owner or qualifier or schema)—for all the tables in the PAYROLL database that have SALARY as one of their column names.