1,217 views
3 votes
3 votes
Consider two relations R and S of size 600 and 500 bytes respectively.The size of a tuple in both relations is 20B. The block size of the system is 200B.  How would many extra block transfers be required, in the worst case, if nested loop join is used instead of block nested loop join technique to compute R⋈S?

1. 78
2. 93
3. 66
4. 105

2 Answers

3 votes
3 votes

Relation R size = 600 B 

Relation S size = 500 B 

Size of tuple in both relation = 20 B

number of tuples in relation R ($n_{r}$) = 600/20 = 30

number of tuples in relation S ($n_{s}$) = 500/20 = 25

Block Size = 200 B

So  we find the number of blocks in relation R ($b_{r}$) and S($b_{s}$)

$b_{r}$= 600/200 = 3 and $b_{s}$ = 500/200 = 2.5 = 3 approx

According to nested loop join concept In worst case it  will involve $n_{r}$*bs+ br block transfers plus nr+br seeks.

Block transfers in nested loop join = 25 * 3 + 3 = 78 (In nested loop join, S will be in outer as it has min tuples so we take 
  $n_{s}$ in place of $n_{r}$ .For each record/tuple in S we'll scan a block of R)

According to Block nested loop join concept In worst case it  will involve $b_{r}$ * $b_{s}$ + $b_{r}$ block transfers

 plus 2 br seeks

Block transfers in Block nested loop join = 3 * 3 + 3 = 12

Extra block transfers be required, in the worst case, if nested loop join is used instead of block nested loop join technique to compute R⋈S = 66

Hence option 3 is correct.

edited by

Related questions

1 votes
1 votes
0 answers
4
gulsanchouhan asked Sep 28, 2017
332 views
Which of the following can be described as a programming model used to develop applications processing massive amounts of data in a distributed and/or parallel manner?1. ...