Relations from the previous question:

Consider two relations R and S with the following sizes:

Relation R: # Blocks = 100

# Tuples = 1000

Relation S: # Blocks = 80

# Tuples = 800

3 Multi-Pass Algorithms 3. (10 points) Consider again the relations R and S from the previous question but this time assume they have 10 times as many pages. That is, assume B(R) = 1000 and B(S) = 800. Explain how a DBMS could efficiently join these two relations given that only 11 pages can fit in main memory at a time. Your explanation should be detailed: specify how many pages are allocated in memory and what they are used for; specify what exactly is written to disk and when. Compute the cost of the join operation. (a) (5 points) Present a solution that uses a hash-based algorithm. (b) (5 points) Present a solution that uses a sort-merge-based algorithm. 3 Multi-Pass Algorithms 3. (10 points) Consider again the relations R and S from the previous question but this time assume they have 10 times as many pages. That is, assume B(R) = 1000 and B(S) = 800. Explain how a DBMS could efficiently join these two relations given that only 11 pages can fit in main memory at a time. Your explanation should be detailed: specify how many pages are allocated in memory and what they are used for; specify what exactly is written to disk and when. Compute the cost of the join operation. (a) (5 points) Present a solution that uses a hash-based algorithm. (b) (5 points) Present a solution that uses a sort-merge-based algorithm