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 T(a,b3) respectively.)
(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 done?
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 state.
(B) [8%] For each of the following schedules, give its isolation level and explain the anomaly that it displays:
(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.