Q$3.[21$ marks$]$ Consider the following two relations $R_1$ and $R_2$ :

We would like to merge$-$join $R_1$ and $R_2$ on attribute $b.$ However, $R_1$ is unsorted on $b,$ so we have to

sort $R_1$ before joining the relations. The records $R_2$ are stored on attribute $b$ in ascending order

sequentially from top to bottom. Assume $1$ record fits into $1$ block of memory. Please show how an

external sort$-$merge on $R_1$ on the attribute $b$ is conducted, by illustrating the following steps:

$($a$)[6$ marks$]$ Create sorted runs, assuming $4$ blocks are allocated to the memory buffer.

Draw figures as in p$.35$ of Ch$.12$ lecture slides

There should be $2$ runs. Label them sequentially as $r_1,r_2.$

$($b$)[12$ marks$]$ Merge the sorted runs created above via $2-$way merge $($p$.36$ of Ch$.12$ lecture

slides$).$ The memory buffer has $3$ blocks denoted as $M_1,M_2$ and $0,$ respectively.

Memory buffer

$($blocks$)$:

Show this process by stating the read$/$write operations in the form of

$[Rea\frac{d}{W}$rite $]x$

For instance, "Read $r_1$ to $M_1"$ stands for reading a block of $r_1$ from disk to thememory block

$M_1,$ "Write $M_1$ to $0"$ stands for writing the record in $M_1$ to the output buffer, and "Write $0$

to Disk" stands for writing the record in $0$ to disk. The first seven operations are shown

as a reference:

Read $r_1$ to $M_1$

Read $r_2$ to $M_2$

Write $M_1$ to $0$

Write $0$ to Disk

Read $r_1$ to $M_1$

Write $M_1$ to $0$

Write $0$ to Disk

$($c$)[3$ marks$]$ Show the resulting joined relation.