Consider the following schema, where the keys are underlined:
The SSN attribute in Project is the Id of the employee working on the project and PID is the
Id of the project. There can be several employees per project, but the functional dependency
PID ! Name,Budget holds (so the relation is not normalized). Consider the query.
SELECT P.Budget, P.Name, E.Name
FROM Employee E, Project P
WHERE E.SSN = P.SSN AND
P.Budget > 99 AND
E.Name = 'John'
ORDER BY P.Budget
Assume the following statistical information:
10,000 tuples in Employee relation
20,000 tuples in Project relation
40 tuples/page in each relation
10-page bu er
1,000 di erent values for E.Name
The domain of Budget consists of integers in the range of 1 to 100
Indices:
? Employee relation:
On Name: Unclustered, hash
? Project relation:
On SSN: Unclustered, hash
On Budget: Clustered, 2-level B+ tree
Question: Find the best execution plan, draw it, and estimate its cost.
Solution:
There are three possible candidates to consider: (1) push both selections; (2) push selection to
Employee only; (3) push selection to Project only. Option (1) yields the least number of I/Os.
Selection Name=0John0(Employee): Since Name can have 1000 values and assuming they are
uniformly distributed, the result will have 10000/1000 = 10 tuples. Since the index on Name
is unclustered hash, this takes 1.2+10 = 12 I/Os.
Selection Budget>99(Project): Since the range of Budget is 100, this reduces the size by 100.
That is, 20000/100 = 200 tuples, 5 pages. Since the index is a 2-level clustered B+ tree, this
will take 2 + ?the number of result pages? I/Os. The result ts in 5 pages, but the rst tuple
may start in the middle of a page. So, we may have to fetch 6 pages. Thus, the cost is 2+6=8
pages.
Since we have a 10 page bu er, we can keep both selections in main memory and perform the
join in main memory. Therefore, the nal cost is 12+8=20 I/Os.
The query plan is shown below.
You might also like to view...
Match the following keyboard shortcuts or keystrokes to their task
I. F5 II. Alt + F5 III. Tab IV. Esc V. Ctrl + E A. Displays in Presenter View B. Displays a presentation from the beginning C. Centers text in a placeholder D. Ends a slide show E. Indents to the next bullet level
The CheckBox control in Visual Basic is used when you want to user to select one or more options at the same time
Indicate whether the statement is true or false
?A(n) _________ is an entity within the browser or web page that has properties that define it and methods that can be acted upon it.
Fill in the blank(s) with the appropriate word(s).
The ALU tells the rest of the computer system how to carry out a program's instructions.
Answer the following statement true (T) or false (F)