Task $1$: Relational Algebra $(10$ points$)$

Write relational algebra expressions for the following queries using the company

database schema:

Retrieve the name and address of employees who work for the 'Research'

department. Do it by hand and insert screenshot

For every project located in 'Stafford', list the project number, the controlling

department number, and the department manager's last name, address, and birth

date. Do it by hand and insert screenshot

Task $2$: Query Processing and Optimization $(30$ points$)$

Construct query trees for the following SQL queries:

Retrieve the name and address of employees who work for the 'Research'

department. Do it by hand and insert screenshot

For every project located in 'Stafford', list the project number, the controlling

department number, and the department manager's last name, address, and birth

date. Do it by hand and insert screenshot

For each query tree, identify the selection, projection, and join operations.

Given the following data distribution:

Employee table has $10,000$ records.

Department table has $100$ records.

Estimate the size of the output for the following query:FROM Employee E$,$ Department D

WHERE E$.$DepartmentID $=$ D$.$DepartmentID AND

D$.$Name $=$

'Research';Discuss the different algorithms that can be used to implement selection operations in

query processing.

Task $3$: Algorithms for External Sorting $(25$ points$)$

Explain the external merge sort algorithm and its importance in database systems.

A file of $4096$ blocks is to be sorted with an available buffer space of $64$ blocks. How

many passes will be needed in the merge phase of the external sort$-$merge algorithm?

Task $4$: Implementing the JOIN Operation $(35$ points$)$

Discuss the different main strategies for implementing the Join operation.

Compare their performance based on their time complexity, advantages and

disadvantages

Consider these relations with the following properties:

Assume that there are more than $2000$ memory buffers available to facilitate this

operation, where each memory buffer can buffer one disk block

a$)$ Estimate the number of disk block accesses required for a natural join of $r$ and $s$

using a nested$-$loop join if $s$ is used as the outer relation.

b$)$ Estimate the number of disk block accesses required for a natural join of r and s

using a nested$-$loop join if $r$ is used as the outer relation.

c$)$ Conclude

Task $5$: Query Trees and Heuristics for Query Optimization $(25$ points$)$

Apply heuristic rules to optimize the query tree for the following query, show the

transformation of a non$-$optimized query tree to an optimized query tree. Do it by hand

and insert screenshots of all the stepsFROM EMPLOYEE E$,$ WORKS ON W$,$ PROJECT P

WHERE P$.$Pname $=$ 'Aquarius' AND P$.$Pnumber $=$ W$.$Pno AND

E$.$Ssn$=$W$.$Ssn AND E$.$Bdate $=\text{'}1957-12-31\text{'}$;Task $6$: Query Execution Plans $(25$ points$)$

Using a MySQL$/$Xampp$,$ generate and interpret the query execution plan for the

following query, include screenshotsFROM Employee E$,$ Department D

WHERE E$.$DepartmentID $=$ D$.$DepartmentID AND

D$.$Name $=$

'Research';