1. What do you mean by the term query processing? What are its objectives?
2. What are the typical phases of query processing? With a neat sketch discuss these phases in high-level query processing.
3. Discuss the reasons for converting SQL queries into relational algebra queries before query optimization is done.
4. What is syntax analyser? Explain with an example.
5. What is the objective of query decomposer? What are the typical phases of query decomposition? Describe these phases with a neat sketch.
6. What is a query execution plan?
7. What is query optimization? Why is it needed?
8. With a detailed block diagram, explain the function of query optimization.
9. What is meant by the term heuristic optimization? Discuss the main heuristics that are applied during query optimization to improve the processing of query.
10. Explain how heuristic query optimization is performed with an example.
11. How does a query tree represent a relational algebra expression?
12. Write and justify an efficient relational algebra expression that is equivalent to the following given query:
|
SELECT
|
B1.BANK-NAME
|
|
FROM
|
BANK1 AS B1, BANK2 AS B2
|
|
WHERE
|
B1.ASSETS > B2.ASSETS AND
B2.BANK-LOCATION = 'Jamshedpur'
|
13. What is query tree? What is meant by an execution of a query tree? Explain with an example.
14. What is relational algebra query tree?
15. What is the objective of query normalization. What are its equivalence rules?
16. What is the purpose of syntax analyser? Explain with an example.
17. What is the objective of a query simplifier? What are the idempotence rules used by query simplifier? Give an example to explain the concept.
18. What are query transformation rules?
19. Discuss the rules for transformation of query trees and identify when each rule should be applied during optimization.
20. Discuss the main cost components for a cost function that is used to estimate query execution cost.
21. What cost components are used most often as the basis for cost functions?
22. List the cost functions for the SELECT and JOIN operations.
23. What are the cost functions of the SELECT operation for a linear search and a binary search?
24. Consider the relations R(A, B, C), S(C, D, E) and T(E, F), with primary keys A, C and E, respectively. Assume that R has 2000 tuples, S has 3000 tuples, and T has 1000 tuples. Estimate the size of R ? S ? T and give an efficient strategy for computing the join.
25. What is meant by semantic query optimization?
26. What are heuristic optimization algorithms? Discuss various steps in heuristic optimization algorithm.
27. What is a query evaluation plan? What are its advantages and disadvantages?
28. Discuss the different types of query evaluation trees with the help of a neat sketch.
29. What is materialization?
30. What is pipelining? What are its advantages?
31. Let us consider the following relations (tables) that form part of a database of a relational DBMS:
|
HOTEL
|
(HOTEL-NO, HOTEL-NAME, CITY)
|
|
ROOM
|
(ROOM-NO, HOTEL-NO, TYPE, PRICE)
|
|
BOOKING
|
(HOTEL-NO, GUEST-NO, DATE-FROM, DATE-TO, ROOM-NO)
|
|
GUEST
|
(GUEST-NO, GUEST-NAME, GUEST-ADDRESS)
|
Using the above HOTEL schema, determine whether the following queries are semantically correct:
|
SELECT
|
R.TYPE, R.PRICE
|
|
FROM
|
ROOM AS R, HOTEL AS H
|
|
WHERE
|
R.HOTEL-NUM = H.HOTEL-NUM AND
H.HOTEL-NAME = 'Taj Residency' AND
R.TYPE > 100;
|
|
SELECT
|
G.GUEST-NO, G.GUEST-NAME
|
|
FROM
|
GUEST AS G, BOOKING AS B, HOTEL AS H
|
|
WHERE
|
R.HOTEL-NO = B.HOTEL-NO AND
H.HOTEL-NAME = 'Taj Residency';
|
|
SELECT
|
R.ROOM-NO, H.HOTEL-NO
|
|
FROM
|
ROOM AS R, HOTEL AS H, BOOKING AS H
|
|
WHERE
|
H.HOTEL-NO = B.HOTEL-NO AND
H.HOTEL-NO = 'H40' AND
B.ROOM-NO = R.ROOM-NO AND
R.TYPE > 'S' AND B.HOTEL-NO = 'H50';
|
32. Using the hotel schema of exercise 31, draw a relational algebra tree for each of the following queries. Use the heuristic rules to transform the queries into a more efficient form.
|
SELECT
|
R.ROOM-NO, R.TYPE, R.PRICE
|
|
FROM
|
ROOM AS R, HOTEL AS H, BOOKING AS H
|
|
WHERE
|
R.ROOM-NO = B.ROOM-NO AND
B.HOTEL-NO = H.HOTEL-NO AND
H.HOTEL-NAME = 'Taj Residency' AND
R.PRICE > 1000;
|
|
SELECT
|
G.GUEST-NO, G.GUEST-NAME
|
|
FROM
|
GUEST AS G, BOOKING AS B, HOTEL AS H, ROOM AS R
|
|
WHERE
|
H.HOTEL-NO = B.HOTEL-NO AND
G.GUEST-NO = B.GUEST-NO AND
H.HOTEL-NO = R.HOTEL-NO AND
H.HOTEL-NAME = 'TajResidnecy' AND
B.DATE-FROM >= '1-Jan-05' AND
B.DATE-TO <= '31-Dec-05';
|
33. Using the hotel schema of exercise 31, let us consider the following assumptions:
• There is a hash index with no overflow on the primary key attributes ROOM-NO, HOTEL-NO in the relation ROOM.
• There is a clustering index on the foreign key attribute HOTEL-NO in the relation ROOM.
• There is B+-tree index on the PRICE attribute in the relation ROOM.
• There is a secondary index on the attribute type in the relation ROOM.
Let us also assume that the schema has the following statistics stored in the system catalogue:
nTuples(ROOM) = 10,000
nTuples(HOTEL) = 50
nTuples(BOOKING) = 100000
nDistinctHOTEL-NO (ROOM) = 50
nDistinctTYPE (ROOM) = 10
nDistinctPRICE (ROOM) = 500
minPRICE (ROOM) = 200
maxPRICE (ROOM) = 50
nLevelsHOTEL-NO (I) = 2
nLevelPRICE (I) = 2
nLfBlocksPRICE(I) = 50
bFactor(ROOM) = 200
bFactor(HOTEL) = 40
bFactor(BOOKING) = 60
a. Calculate the cardinality and minimum cost for each of the following Selection operations:
Selection 1: σROOM-NO = 1 ∧HOTEL-NO = ‘H040' (ROOM)
Selection 2: σTYPE-‘D' (ROOM)
Selection 3: σHOME-NO = ‘H050' (ROOM)
Selection 4: σPRICE>100' (ROOM)
Selection 5: σTYPE = ‘S' ∧ HOTEL-NO = ‘H060' (ROOM)
Selection 6: σTYPE = ‘S' v PRICE < 100' (ROOM)
b. Calculate the cardinality and minimum cost for each of the following Join operations:
Selection 1: HOTEL?HOTEL-NO ROOM
Selection 2: HOTEL?HOTEL-NO BOOKING
Selection 3: ROOM?ROOM-NO BOOKING
Selection 4: ROOM?HOTEL-NO HOTEL
Selection 5: BOOKING?HOTEL-NO HOTEL
Selection 6: BOOKING?ROOM-NO ROOM.