– Part III
18
Chapter 23 Query Processing
Review Questions
23.1 What are the objectives of query processing?
23.2 How does query processing in relational systems differ from the processing of low-level query
languages for network and hierarchical systems?
In first generation network and hierarchical database systems, the low-level procedural query
23.3 What are the typical phases of query processing?
23.4 What are the typical phases of query decomposition?
23.5 What is the difference between conjunctive and disjunctive normal form?
Conjunctive normal form: A sequence of conjuncts that are connected with the
– Part III
23.6 How would you check the semantic correctness of a query?
23.7 State the transformation rules that apply to:
23.8 State the heuristics that we should apply to improve the processing of a query.
See Section 23.3.2.
23.9 What type of statistics should a DBMS hold to be able to derive estimates of relational algebra
operations?
23.10 Under what circumstances would the system have to resort to a linear search when
implementing a Selection operation?
23.11 What are the main strategies for implementing the Join operation?
23.12 What are the differences between materialization and pipelining?
23.13 Discuss the difference between linear and non-linear relational algebra trees. Give examples
to illustrate your answer.
23.14 What are the advantages and disadvantages of left-deep trees?
23.15 Describe the extensions required to query processing and query optimization to fully support
the ORDBMS.
Some possible answers are as follows:
One capability we require is that the ORDBMS query processor flattens queries whenever
possible. If the function has been defined as an external function it may be to provide an
Exercises
23.16 Calculate the cost of the three strategies cited in Example 23.1 if the Staff relation has 10,000
tuples, Branch has 500 tuples, there are 500 Managers (one for each Branch), and there are
10 London branches.
21
23.17 Using the Hotel schema given at the start of the Exercises at the end of Chapter 4, determine
whether the following queries are semantically correct:
(a) SELECT r.type, r.price
(b) SELECT g.guestNo, g.name
(c) SELECT r.roomNo, h.hotelNo
23.18 Again, using the Hotel schema, draw a relational algebra tree for each of the following
queries and use the heuristic rules given in Section 23.3.2 to transform the queries into a more
efficient form:
(a) SELECT r.roomNo, r.type, r.price
(b) SELECT g.guestNo, g.guestName
– Part III
22
r.roomNo, r.type, r.price
r.roomNo, r.type, r.price
– Part III
23
g.guestNo,g.guestName
g.guestNo,g.name
G
h.hotelNo=b.hotelNo
H
g.guestNo,g.name
– Part III
24
23.19 Using the Hotel schema, assume the following indexes exist:
a hash index with no overflow on the primary key attributes, roomNo/hotelNo in Room;
nTuples(Room) = 10000 bFactor(Room) = 200
g.guestNo,g.guestName
– Part III
25
(a) Calculate the cardinality and minimum cost for each of the following Selection
operations:
S1: roomNo=1 hotelNo=1(Room)
S3: hotelNo=2(Room)
S4: price>100(Room)
S5: type hotelNo=3(Room)
(b) Calculate the cardinality and minimum cost for each of the following Join
operations:
J1: Hotel hotelNo Room
– Part III
26
J2: Hotel hotelNo Booking
Block Nested Loop 33336, buffer has only 1 block for Hotel and
J3: Room roomNo Booking
Block Nested Loop 833400, buffer has only 1 block for Room and
J4: Room hotelNo Hotel
J5: Booking hotelNo Hotel
Block Nested Loop 50001, buffer has only 1 block for Hotel and
J6: Booking roomNo Room
Block Nested Loop 850017, buffer has only 1 block for Booking and
Room.
– Part III
27
(c) Calculate the cardinality and minimum cost for each of the following Projection
operations:
P1: hotelNo(Hotel)
P2: hotelNo(Room)
P3: price(Room)
P4: type(Room)
P5: hotelNo, price(Room)
23.20 Modify the block nested loop join and the indexed nested loop join algorithms presented in
Section 23.4.3 to read (nBuffer – 2) blocks of the outer relation R at a time, rather than one
block at a time.