PART A) Two relations R and S are having their bag-union taken by a sort-based algorithm. We have already sorted R and S, and we assume that their tuples are simply integers, 1 through 5. We also assume that there are only three tuples per block, and that R and S each consist of nine tuples, arranged in three blocks each, as shown:

	R1	R2	R3
R	1 1 2	2 3 4	4 5 5
S	1 1 1	1 2 2	2 4 5
	S1	S2	S3

If the merge process is allowed to break ties arbitrarily, i.e., take from either relation when the two tuples at the fronts of the lists are the same, then the blocks can be emptied in various orders. Determine which blocks must have all (or at least one) of their records taken before all (or at least one) record from another block. Then, identify which of the following is possible.

		a)	Some tuple of S3 is taken before any of the tuples of R1.
		b)	Every tuple of R1 is taken before the last tuple of S1.
		c)	Some tuple of R2 is taken before any of the tuples of S2.
		d)	Some tuple of S3 is taken before any of the tuples of R2.

PART B)

We wish to perform a 2-pass hash join of relations R and S, whose files require B(R) and B(S) disk blocks respectively. We have M one-block buffers available for reading input; we do not count the buffers or disk I/O needed to store or write the result. Write the formula, in terms of B(R) and B(S) for the smallest value of M for which it is possible to perform this join, assuming the hash function divides tuples into buckets as evenly as possible. Demonstrate that you have the correct function by giving the minimum number of needed buffers when the two relations have files requiring 100 and 200 blocks.

a)

99

b)

15

c)

10

d)

11