GATE CS 2014 Set 2 Q30 — Normal Forms

To perform a block-nested loop join with $3$ available buffers where $1$ buffer is reserved for the output (intermediate results), we have $3 - 1 = 2$ buffers remaining for the relations.

With $2$ buffers available for the join:

• $1$ buffer is allocated to hold a block of the outer relation.
• $1$ buffer is allocated to scan the blocks of the inner relation.

Let $B_r$ and $B_s$ be the number of disk blocks occupied by relations $r(R)$ and $s(S)$ respectively. Since $\text{size}(r(R)) < \text{size}(s(S))$, we have $B_r < B_s$.

Let's compare the total disk block accesses for both configurations:

1. Case 1: $r(R)$ is in the outer loop

   Each block of $r(R)$ is read once, and for each of these blocks, the entire relation $s(S)$ is scanned.

   $$\text{Total Accesses}_1 = B_r + (B_r \times B_s)$$
2. Case 2: $s(S)$ is in the outer loop

   Each block of $s(S)$ is read once, and for each of these blocks, the entire relation $r(R)$ is scanned.

   $$\text{Total Accesses}_2 = B_s + (B_s \times B_r)$$

Comparing the two costs:

Since $B_r < B_s$, we have:

Thus, the join will require fewer disk block accesses if the smaller relation $r(R)$ is kept in the outer loop.