QUESTION I. [Query Processing: 20%]
(A) [10%] Write pseudocode for an iterator that implements nested-loop join, where the outer
relation is pipelined. Your pseudocode must define the standard iterator functions open(),
next(), and close(). Show what state information the iterator must maintain between calls.
(B) [5%] Pipelining is used to avoid writing intermediate results to disk. Suppose you are merge
joining the results of two sorts. Describe how the output of the sort can be effectively pipelined
to the merge join without being written back to disk.
(C)[5%] Suppose I want to provide an iterator interface to external sorting. Outline what should be
done in the open(), getnext() and close() functions.
QUESTION II. [Query Optimization: 20%]
(A)[10%] Why are the following equivalences incorrect? Describe the reason either in words or
through a small example. Assume that initially relations have no duplicates or nulls. (Some of
the expressions below can generate tuples with nulls.)
(a) 3 A(R S) l 3 A(R) 3 A(S).
(b) (R S) T l R (S T ). ( denotes the natural left outer join).
(Hint: assume that the schemas of the three relations are R(a,b1), S(a,b2) and
(B) [10%] Describe how to incrementally maintain the results of the left outer join view on both
insertions and deletions. That is, given materialized view v = r༔s, when a set of tuples ir is
inserted in r or in s, what should be done? And when ir is deleted from r or s, what should be
QUESTION III. [Transactions and Concurrency Control: 30%]
(A)[8%] Consider two transactions, one transferring $50 from account A to account B and
another computing 15% interests on both accounts.
(a) Show a schedule which is not serial, but is conflict serializable.
(b). Show a schedule which is not conflict serializable and results in an inconsistent database
(B) [8%] For each of the following schedules, give its isolation level and explain the anomaly that
(C)[8%] Consider the following four schedules:
For each one of them, state whether it is conflict serializable, recoverable or avoids cascading
aborts. ,IWKHDQVZHULV³12´VD\EULHIO\ZK\. Use a table like the one below.