Question

Consider the natural join of the relation R(A,B) and S(A,C) on attribute A. Neither relations have...

Consider the natural join of the relation R(A,B) and S(A,C) on attribute A. Neither relations have any indexes built on them. Assume that R and S have 80,000 and 20,000 blocks, respectively. The cost of a join is the number of its block I/Os accesses. If the algorithms need to sort the relations, they must use two-pass multi-way merge sort.

QUESTION:

Assume that there are 10 blocks available in the main memory. What is the fastest join algorithm for computing the join of R and S? What is the cost of this algorithm?

0 0
Add a comment Improve this question Transcribed image text
Answer #1

Hi,

Answer:

Solution-:

sort-merge:
This join algorithm is used for implementing the relational database and for every distinct value of the attribute and the set of the tuples through which every relation to be displayed.

Hash-join:
Hash join algorithm is used for implementing the nested loops joins except the probe side of the joins which can be very small.

Now if there are 10 blocks available in the main memory.
Lets consider M = 10.
As we should know that the Hash-join and the optimized sort-merge join are the fastest algorithm in the given setting and have equal costs.

Hence we apply both algorithm one by one to check the condition:
Then On applying the sort-merge join:
B(R) + B(S) >= M^2
80000 + 20000 >= 100
We found that the relations of B(R) + B(S) is not greater than the M^2.So, we cannot use to optimize the sort-merge join algorithm.

Now apply the hash-join which will be required that B(R) + B(S) <= M^2.
Hence B(R) + B(S) is smaller than M^2.So, we can optimize the hash-join algorithm.

So, hash-join is the fastest join algorithm for computing the join of R and S.

And, the cost for hash-join will be:
3(R blocks + S blocks)
3 * (80,000 + 20,000)
3 * 10,000
30,000

Hence cost of the algorithm = 30,000 number of I/O access

Add a comment
Know the answer?
Add Answer to:
Consider the natural join of the relation R(A,B) and S(A,C) on attribute A. Neither relations have...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT