Part C: Relational Algebra $\backslash$& Heuristic Optimization $[20$ Marks$]$

Question $4.$

Consider the relations:

EMPLOYEE$($ID$,$ SURNAME, LINE$\_$ID$)$

CAR$($EID$,$ MAKE$)$

For each employee, we store their unique ID and the ID of their line manager $($if exists$)$ LINE$\_$ID$.$ If an employee has a line manager then the corresponding LINE$\_$ID is not NULL. A line manager does not have a line manager, i$.$e$.,$ the corresponding LINE$\_$ID is NULL. The LINE$\_$ID is a foreign key referencing to the ID primary key in the relation Employee. In the relation Car, we store the car$($s$)$ make of an employee, if exist$($s$).$ Specifically, for each car, we store its make $($e$.$g$.,$ BMW$,$ Jaguar, Aston Martin, Toyota$)$ and the ID of its owner$/$employee $($EID$).$ The EID is a foreign key referencing to the ID in the relation Employee. The primary keys are underlined.

Assume the following query:

SELECT E$.$SURNAME, L$.$SURNAME

FROM EMPLOYEE E$,$ EMPLOYEE L$,$ CAR C

WHERE E$.$LINE$\_$ID $=$ L$.$ID AND C$.$EID $=$ L$.$ID

We know that: $($i$)$ there are $20$ line managers, each one being the line manager of $10$ employees;

$($ii$)$ there are $120$ employees, who have $1$ car each, i$.$e$.,$ the CAR relation has $120$ tuples, each one corresponds to different employee.

$($a$)$ Provide the canonical tree of the query and estimate the expected number of tuples retrieved.

$($b$)$ Optimize the query using heuristic optimization by providing the optimal tree. Show and explain the heuristic rules you used.

$($c$)$ Provide the optimal relational algebra expression from the Question $4($b$).$

$($d$)$ Estimate the expected number of tuples retrieved at each operator in your optimal tree from the Question $4($b$).$ Compare this number with the Question $4($a$).$