Consider the following relational schema:

Assume that keys are underlined and:

The relation Employee is sorted on the Id attribute.

In Department: Unclustered index on DeptName; clustered on Building. No other

indices.

Dozens of departments can reside in the same building.

(a) Write an SQL query that generates a table of employee names who work for department

?Sales? in building E213.

(b) Give the ?naive? translation of your SQL query into the relational algebra (as given by

the general translation of SQL to relational algebra.)

(c) Describe carefully and completely how you would actually most eciently evaluate the

above query. That is, list the precise sequence of relational operations to be performed,

the relations on which these operations are to be performed, and the methods to be used

to compute the result of each operation. (As part of the solution you will need to decide

which index to use and why.)

(a) Write an SQL query that generates a table of employee names who work for department

?Sales? in building E213.

Solution:




SELECT E.Name


FROM Employee E, WorksIn W, Department D


WHERE E.Id = W.EmpId AND W.DeptName = D.DeptName


AND D.Building = 'E213' AND D.DeptName = 'Sales'

(b) Give the ?naive? translation of your SQL query into the relational algebra (as given by

the general translation of SQL to relational algebra.)

Solution:

(c) Describe carefully and completely how you would actually most eciently evaluate the

above query. That is, list the precise sequence of relational operations to be performed,

the relations on which these operations are to be performed, and the methods to be used

to compute the result of each operation. (As part of the solution you will need to decide

which index to use and why.)

Solution:

Since there are no indices onWorksIn and this relation is potentially large, we should try

to reduce Department as much as possible and as cheaply as possible. Since DeptName

is a key in Department and we have an index on this attribute, we can apply the selection

DeptName=0Sales0(Department) rst. This is supposed to produce a single tuple. Selection

Building=0E2130 is applied next. It will either leave the selected tuple intact or will

eliminate it completely (in the latter case the query will return empty set).

The next step is to join the result with WorksIn. (Since we are joining WorksIn with a

single tuple, this operation is essentially a selection.) We can use block-nested loops join

here, which can be computed in 1 scan of WorksIn. Finally, we can join the result with

Employee. Since Employee is sorted on Id and what is left of WorksIn is presumably

small (since this result contains only the employees from one department out of many

dozens), it is probably best to use sort-merge join here.