1. Suppose you need to sort a relation of 40 gigabytes, with 4 kilobyte blocks, using a memory size of 40 megabytes. Suppose the cost of a seek is 5 milliseconds, while the disk transfer rate is 40 megabytes per second.
a. Find the cost of sorting the relation, in seconds, with bb = 1 and with bb = 100.
b. In each case, how many merge passes are required?
c. Suppose a flash storage device is used instead of a disk, and it has a seek time of 1 microsecond, and a transfer rate of 40 megabytes per second. Recompute the cost of sorting the relation, in seconds, with bb = 1 andwith bb = 100, in this setting.
2. Consider the following extended relational-algebra operators. Describe how to implement each operation using sorting, and using hashing.
a. Semijoin (): r s is defined as R(r s), where R is the set of attributes in the schema of r ; that it it selects those tuples ri in r for which there is a tuple s j in s such that ri and s j satisfy predicate.
b. Anti-semijoin (¯ ): r¯ s is defined as r-R(r s); that it it selects those tuples ri in r for which there is no tuple s j in s such that ri and s j satisfy predicate.