Full exam for Data Bases 2 in the Computer Engineering degree programme at Politecnico di Milano. The document covers: 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
Full exam for Data Bases 2 in the Computer Engineering degree programme at Politecnico di Milano. The document covers: 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
Import quality: text was extracted directly from the original document.
Representative passages recognised in different parts of the material. The full extracted text remains available to search, while this compact preview makes the page easier to read.
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…
First page of the document.
