edited by
20,614 views
45 votes
45 votes

Consider a join (relation algebra) between relations $r(R)$ and $s(S)$ using the nested loop method. There are $3$ buffers each of size equal to disk block size, out of which one buffer is reserved for intermediate results. Assuming $\text{size}(r(R))<\text{size}(s(S)),$ the join will have fewer number of disk block accesses if

  1. relation $r(R)$ is in the outer loop.
  2. relation $s(S)$ is in the outer loop.
  3. join selection factor between $r(R)$ and $s(S)$ is more than $0.5$.
  4. join selection factor between $r(R)$ and $s(S)$ is less than $0.5$.
edited by

6 Answers

Best answer
35 votes
35 votes

In joining A and B using nested loop method, with A in outer loop two factors are involved.

  1. No. of  blocks containing all rows in A should be fetched.
  2. No. of rows of A times no. of blocks containing all rows of B.

(in worst case all rows of B are matched with all rows of A).

In above ques, $|R|<|S|$

(i) will be less when number of rows in outer table is less, since less no. of rows will take less no. of blocks

(ii) if we keep $R$ in outer loop, no. of rows in $R$ are less and no. of blocks in $S$ are more

If we keep $S$ in outer loop, no of rows in $S$ are more and no. of blocks in $R$ are less.

In (ii) block accesses will be multiplication and will come same in both cases.

So, (i) will determine no of block accesses

So, answer is A.

edited by
5 votes
5 votes

Nested loop join Algo: https://en.wikipedia.org/wiki/Nested_loop_join

No. of block transfers, N(B) = $n_r*b_s+b_r$ ; when R is in outer loop and S is in inner loop

Where, $n_r$ are number of tuples in relation R.

$b_s$ and $b_r$ are number of blocks in relation S and R respectively.

size(r(R))<size(s(S)) blocks occupied by R are less ($b_r<b_s$). Also, ($n_r<n_s$). As, less no of blocks acquire less no. of rows. 

For minimizing N(B), product term must be minimum and it will be minimum when R is in the outer loop.

For Example: let $b_r=10 , b_s=20; n_r=50, n_s=100$ since size(r(R))<size(s(S))

1. when R is in the Outer loop: N(B) = $n_r*b_s+b_r$ = 50*20+10 = 1010.

2. when S is in the outer loop: N(B) = $n_s*b_r+b_s$ = 100*10+20 = 1020.

So, relation R should be in outer loop.

Option(A).

0 votes
0 votes

The join between r(R) and s(S) which is using nested loop will be as follows,
For each tuple r in R do
    For each tuple s in S do
        If r and s satisfy the join condition then output the tuple 

The above algorithm involves (nr*bs+br ) block transfer and (nr+br ) seeks.
where,
br → no. of blocks in R
bs → no. of blocks in S
nr → no. of tuples in R
To have less block accesses in nr should be less and in question it is given that size(r(R)) < size(s(S)).
To have fewer no. of disk block accesses the relation r(R) should be in outer loop.   

Answer:

Related questions

61 votes
61 votes
3 answers
2
33 votes
33 votes
3 answers
3
go_editor asked Sep 28, 2014
7,204 views
Given an instance of the STUDENTS relation as shown as below$$\begin{array}{|c|c|c|c|c|} \hline \textbf {StudentID} & \textbf{StudentName} & \textbf{StudentEmail} & \text...
34 votes
34 votes
8 answers
4
go_editor asked Sep 28, 2014
11,327 views
The maximum number of superkeys for the relation schema $R(E,F,G,H)$ with $E$ as the key is _____.