in Databases
191 views
1 vote
1 vote
Let a relation R with n tuples occupying X blocks and relation S with m tuples occupying Y blocks. 5 blocks of main memory are allocated to store records of R and S to perform join.

What will be the access cost of  a) R join S b) S join R
in Databases
191 views

1 Answer

0 votes
0 votes

No of block access, completely depends on the type of JOIN algo we are using to access the blocks. 

Mainly, we have 2 types of algorithms: 

  1. Nested Loop Join
  2. Block Nested Loop Join

For (a) R JOIN S , means R is in outer loop and S is in inner loop

No of Block access (Nested Loop Join -: Record By Record): X + n*Y

No of Block access (Block Nested Loop Join -: Block By Block): X + X*Y

 

For (b) S JOIN R , means S is in outer loop and R is in inner loop

No of Block access (Nested Loop Join -: Record By Record): Y + m*X

No of Block access (Block Nested Loop Join -: Block By Block): Y + Y*X