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?
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
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. Assume that there are 110,000 blocks available in the main memory. We like to have the output sorted based on...
Question 1 (5 marks) Consider two relations called Item and Orderltem. Imagine that relation Item has 160,000 tuples and Orderltem has 200,000 tuples. Both relations store 100 tuples per a page. Consider the following SQL statement SELECT * FROM Item INNER JOIN OrderItem ON Item.ItemID-OrderItem. ItemID; We wish to evaluate an equijoin between Orderltem and Item, with an equality condition Item.ltemID Orderltem.ItemID. There are 802 buffer pages available in memory for this operation. Both relations are stored as (unsorted) heap...
! Exercise 15.4.4: In Example 15.6 we discussed the join of two relations R and S, with 1000 and 500 blocks, respectively, and M = 101. However, we need additional additional disk I/O's if there are so many tuples with a given value that neither relation's tuples could fit in main memory. Calculate the total number of disk I/O's needed if: a) There are only two Y-values, each appearing in half the tuples of R and half the tuples of...
1) Consider a relation R(A,B) with r tuples, all unique within R, and a relation S(B,C) with s tuples, all unique within S. Let t represent the number of tuples in R natural-join S. What is the value range of t? What is the value of t for R natural-join R (assuming no null values in R)? Explain your answer.
[1] [30 points] Consider the relation R City, Street, Zip Code), where a tuple (c, s, z) is in R only if city c has a building with street s, and z is the zipcode for that address in that city. It is assumed that the nontrivial functional dependencies are: Street → Zip Code ZipCode → City City, [a] [b] [C] [d] [e] Determine all possible keys for R. Indicate all possible BCNF and 3NF violations. Decompose R as necessary...
Consider a relation schema R with attributes ABCDEFGH with functional dependencies S: S={B→CD, BF→H, C→AG, CEH→F, CH→B} Employ the BCNF decomposition algorithm to obtain a lossless decomposition of R into a collection of relations that are in BCNF. Make sure it is clear which relations are in the final decomposition and project the dependencies onto each relation in that final decomposition.