Exercise  14.4   Consider   the   join    given   the  following   information  about   the relations to be joined.  The  cost  metric  is  the  number  of page  l/Os  unless  otherwise  noted, and  the  cost  of writing out  the  result  should  be  uniformly ignored.

 

Relation  R  contains  10,000  tuples and  has  10  tuples  per page.

Relation S contains 2000 tuples and also has 10 tuples per page. Attribute b of relation  S  is  the  primary  key  for  S.

Both  relations  are stored      simple  heap files. Neither relation  has  any  indexes  built  on it.

52  buffer pages  are available.

 

1.    What is the cost of joining Rand S using a page-oriented simple nested loops join? What is the minimum number of buffer pages required for this cost to remain unchanged?

2.    What is the cost of joining Rand S using a block nested loops join? What is the minimum number of buffer pages required for this cost to remain unchanged?

3.     What is the cost of joining Rand S using a sort-merge join? What  is  the minimum number of buffer pages required for this cost to remain unchanged?

4.     What is the cost of joining Rand S using a hash join? What is the minimum number of buffer pages required for this cost to remain unchanged?

5.    What would be the lowest possible I/O cost for joining Rand S using any join algorithm, and how much buffer space would be needed to achieve this cost? Explain briefly.

6.     How many tuples does the join of R. and S produce, at most, and how many pages are required to store the result of the join back on disk?

7.     Would your answers to any of the previous questions in this exercise change if you were told that R.a is a foreign key that refers to S.b?