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.
You might also like to view...
Provide three sample questions to determine whether a project has technical feasibility. Sample questions might include:
What will be an ideal response?
The ________ function converts text to title case
Fill in the blank(s) with the appropriate word(s).
What is the correct code to create a password box?
A.
Machines that forward and store packets using any type of packet switching protocol are called packet switches.
Answer the following statement true (T) or false (F)