[Join] (30) Consider Schema R(A,B) and S(B,C) and a join query R _R.A=S.B S. We ignore the cost of outputting the result and measure the cost with the number of data blocks that need to be transferred.

(10) Relation S contains 20K tuples and has 10 tuples per block; Relation R contains 100K tuples and has 10 tuples per block. Attribute B of S is the primary key of S. Assume neither relation has any index. Describe a block nested join algorithm to evaluate the query. Give the cost of joining R and S with a block nested loops join.

(10) You are allowed to build an index on the attribute of your choice. Re-estimate the cost for (a) with index-based nested loop join, given your design of the index.

(10) Assume R contains 1000 blocks, 10,000 tuples; S contains 10,000 blocks, 50,000 tuples. There are clustering B+ tree index on R.A and S.B. Both indexes contain two levels with the root note in the first level and all leaf nodes in the second level. The indexes on R.A has 25 leaf nodes; the index on S.B contain 250 leaf nodes. Describe *two* algorithms that can correctly compute _R.A R _R.A=S.B S and give the corresponding cost measured by the number of block transfers. (There are multiple solutions; describing any two correct algorithms with cost analysis suffice).