Q$1[50\%]$ Consider two relations r$($A$,$B$)$ and s$($C$,$D$).$ Relation r has $150000$ tuples, and s has

$6000$ tuples. $25$ tuples of r fit in one block, $60$ tuples of s fit in one block. Assume that the

system has a memory of M $=100$ blocks.

$($a$)[32\%]$ Estimate the minimum cost $($in number of block accesses$)$ of the equi$-$join with

r$.$B$=$s$.$C using the following algorithms:

$($a$)$ nested$-$loops join, $(8\%)$

$($b$)$ block nested$-$loops join, $(8\%)$

$($c$)$ merge$-$join $($assume that relations r and s are initially sorted$),(8\%)$

$($d$)$ hash$-$join $($assume no overflow occurs and no recursive partitioning occurs.$)(8\%)$

$($b$)[18\%]$ Assume that the block size is $4096$ bytes. Suppose there are B$+-$tree indexes on

both r$.$B and s$.$C$.$ Neither of these two B$+-$tree indexes is primary index. For each block in the

two B$+-$tree indexes, $96$ bytes space is reserved for block header information $($e$.$g$.,$ is$\_$leaf

flag and number of entries$).$ Except one sibling access pointer, only key values and recordids

are stored in leaf nodes. Both key values, r$.$B and s$.$C$,$ are $12$ bytes long. A record$-$id and a

block$-$id each occupies $12$ bytes. Please estimate the minimum cost $($in number of block

accesses$)$ of running the index nested loops equi$-$join algorithm with r$.$B $=$s$.$C$.($Assume that

the join result contains N$=30000$ tuples.$)$