Consider the following relational schema and SQL query. The schema captures information

about employees, departments, and company finances $($organized on a per department basis$).$

Emp$($eid: integer, did: integer, sal: integer, hobby: char$(20))$

Dept$($did: integer, dname: char$(20),$ floor: integer, phone: char$(10))$

Finance$($did: integer, budget: real, sales: real, expenses: real$)$

Consider the following query:

SELECT D$.$dname, F$.$budget

FROM Emp E$,$ Dept D$,$ Finance F

WHERE E$.$did$=$D$.$did AND D$.$did$=$F$.$did AND D$.$floor$=1$ AND E$.$sal $59000$ AND E$.$hobby $=$ 'yodeling';

a$)(4$ points$)$ Identify a relational algebra tree $($or a relational algebra expression if you prefer$)$

that reflects the order of operations a decent query optimizer would choose.

b$)$ Suppose that the following additional information is available: Non$-$clustering $B+$ tree

indexes exist on Emp.did, Emp.sal, Dept.floor, Dept.did, and Finance.did. The system's

statistics indicate that employee salaries range from $10,000$ to $60,000,$ employees enjoy $200$

different hobbies, and the company owns two floors in the building. There are a total of

$50,000$ employees and $5,000$ departments $($each with corresponding financial information$)$

in the database.

i$.(6$ points$)$ For each of the query's base relations $($Emp$,$ Dept, and Finance$)$ estimate the

number of tuples that would be initially selected from that relation if all of the non$-$join

predicates on that relation were applied to it before any join processing begins.

ii$.(2$ points$)$ Given your answer to the preceding question, list the join order $($i$.$e$.,$ the

order in which pairs of relations can be joined to compute the query result$)$ that a

relational query optimizer will consider.

iii. $(2$ points$)$ What is the estimated number of tuples returned by the query?