14 01 2022 E TS

Page 1

Databases 2 - exam S. Comai, P. Fraternali, D. Martinenghi January 14th, 2022 Multichance students do not need to answer questions A.2, B.5, and C.2. A. Ranking (7 + bonus) The admission committee for a prestigious high school needs to select the best candidate students, shown in the table, and has decided to rank them according to a combination of their previous marks, weighting English 80% and Math 20%. All marks range from 1 to 10. English Math Molly: 10.0 Timmy: 10.0 Dolly: 8.0 Dolly: 9.0 Billy: 8.0 Polly: 8.0 Polly: 7.0 Billy: 8.0 Jimmy: 7.0 Jimmy: 6.0 Timmy: 6.0 Molly: 5.0 1) Run FA to find the top student according to the given criterion. Specify the accesses that were made. 2) Do as above, but with TA. 3) Bonus. Is there a way to find the same result with fewer accesses, while still guaranteeing correctness? Solution. 1. FA proceeds by sorted access until it reaches depth 2, finding Dolly in both rankings (4 sorted accesses). Then, it completes the scores for Molly (on Math) and Timmy (on English) with 2 random accesses. Molly has the top score, computed as 10 · 0.8 + 5 · 0.2 = 9, while Dolly has 8 .2 and Timmy 6 .8. 2. TA finds Molly on English by sorted access and completes her score with a random access on Math (overall 9); similarly, it finds Timmy by s.a. and makes a r.a. on English (overall 6.8). The threshold is 10, so another round is needed. It then finds Dolly on English by s.a. and completes her score by r.a., and then finds Dolly again by s.a. on Math, so no more r.a.’s are needed. The threshold is now 8.2 (same as Dolly’s score), and TA can stop. TA makes in total 4 s.a.’s and 3 r.a.’s (note that a slightly different implementation of TA might first read a row entirely, and then make the r.a.’s for the missing pieces, and in this case this would mean saving…