COMP9315 21T1
Exercises 08
Query Optimisation and Execution
DBMS Implementation
[Show with no answers] [Show with all answers]
1.
2. Consider the following tables relating to trips on a suburban bus network
Trip(fromPlace:integer, toPlace:integer, tripDate:date)
3. Place(placeId:integer, address:string, suburb:string)
4.
a. Write an SQL query that returns all of the addresses in Randwick that are the destination of a trip on March 4, 2005.
[show answer]
b. Give a naive translation of the SQL query into a relational algebra expression.
[show answer]
c. Translate the naive relational algebra expression into an equivalent expression using pushing of selections and projections.
[show answer]
d. Translate the optimized relational algebra expression into the most directly corresponding SQL query.
[show answer]
5.
6.
7. What are the possible join trees (without cross-products) for each of the following queries:
a. select * from R,S,T where R.a=S.b and S.c=T.d
[show answer]
b. select * from R,S,T where R.a=S.b and T.c=R.d
[show answer]
c. select * from R,S,T where R.a=S.b and S.c=T.d and T.e=R.f
[show answer]
d. select * from R,S,T,U
where R.a=S.b and S.c=T.d and T.e=R.f and T.g=U.h and S.i=U.j
[show answer]
8.
Do not include trees/sub-trees that are reflections of other tree/subtrees.
9.
10. Consider a table R(a,b,c) and assume that
◦ all attributes have uniform distribution of data values
◦ attributes are independent of each other
◦ all attributes are NOT NULL
◦ r = 1000, V(a,R) = 10, V(b,R) = 100
11. Calculate the expected number of tuples in the result of each of the following queries:
a. select * from R where not a=k
b. select * from R where a=k and b=j
c. select * from R where a in (k,l,m,n)
12. where j, k, l, m, n are constants.
[show answer]
13.
14. Consider the following tables relating to retail sales:
create table Item (
15. iname text,
16. category text,
17. primary key (name)
18. );
19. create table Store (
20. sname text,
21. city text,
22. street text,
23. primary key (city,street)
24. );
25. create table Transaction (
26. item text references Item(iname),
27. store text references Store(sname),
28. tdate date,
29. primary key (item,store,tdate)
30. );
31.
Consider the following query (expressed as SQL and relational algebra):
select category,city
32. from Item, Store, Transaction
33. where iname=item and store=sname and
34. tdate=’20-12-2004′ and city=’Sydney’;
35.
36. JoinResult = Item Join[iname=item] Transaction Join[store=sname] Store
37. SelectResult = Sel[tdate=’20-12-2004′ and city=’Sydney’](JoinResult)
38. FinalResult = Proj[category,city](SelectResult)
39.
Show the three “most promising” relational algebra expressions that the query optimizer is likely to consider; then find the most efficient query plan and estimate its cost.
Assume 50 buffer pages and the following statistics and indices:
◦ Item: 50,000 tuples, 10 tuples/page.
Indexing: hashed on iname (assume no overflows).
◦ Store: 1,000 tuples, 5 tuples/page; 100 cities.
Index1: Unclustered hash index on sname. Index2: Clustered 2-level B+tree on city.
◦ Transaction: 500,000 tuples, 25 tuples/page; 10 items bought per store per day.
The relation stores transactions committed over a 50 day period.
Index: 2-level clustered B+tree on the pair of attributes store,ttime.
40.
[show answer]