04 02 2022 E TS

Page 1

Databases 2 - exam S. Comai, P. Fraternali, D. Martinenghi February 4th, 2022 A. Ranking (8 points) The following ranked lists report salaries of employees (in K e) and their departmental budgets (in M e), respectively, in descending order. 1. Use TA to find the top-1 employee according to the salary/budget ratio. 2. Use now FA for the same purpose. salary (Ke) budget (Me) Dan: 60.0 Pam: 40.0 Abe: 50.0 Joe: 30.0 Pam: 30.0 Dan: 30.0 Joe: 20.0 Abe: 10.0 3. Discuss correctness of TA and FA for this problem: a) using the data shown above; b) in general. In Steps 1 and 2, provide enough details for us to check correctness of your execution with TA and FA. Solution. 1. With TA, we make one sorted access to salary retrieving Dan (60), and one random access to budget to retrieve Dan’s budget (30); simmetrically, one s.a. to budget (Pam, 40) and a corresponding r.a. to salary (30). With this, Dan’s score is 2, Pam’s is 0.75, while the threshold point (60,40) has a score of 1.5. So TA stops and recognizes Dan as the top-1 employee. 2. With FA, we make sorted accesses to both lists until a common object is found, which happens at depth 3 (both Dan and Pam are in common, so their score can be computed); when the sorted access phase stops, all employees have been seen. For Abe and Joe, FA determines their missing partial score through random access. The highest score is Abe’s (5), which is the top-1 employee by FA. 3. Clearly, TA fails to recognize the top employee (Abe), while FA succeeds. The problem is the use of a scoring function that is not monotonic in its arguments, so the determination of the threshold is meaningless, particularly because budgets decrease, so overall scores may increase. However, FA may also fail with this scoring function: if we swapped Pam’s and Dan’s…