Question

In: Advanced Math

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?

Solutions

Expert Solution

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


Related Solutions

QUERY PROCESSING JOIN 1) Let the schema of a relation r as R(A,B,C), and a relation...
QUERY PROCESSING JOIN 1) Let the schema of a relation r as R(A,B,C), and a relation s has schema S(C,D,E). Relation table r has 40K tuples, relation s has 60K tuples. The block factor of r is 25. The block factor of s is 30. Let the average seek time is t S and average block transfer time is t T . Assume you have a memory that contains M pages, but M< 40K/25 (indicating that s cannot be entirely...
Consider the relation R= {A, B, C, D, E, F, G, H} and the set of...
Consider the relation R= {A, B, C, D, E, F, G, H} and the set of functional dependencies: FD= {{B}—> {A}, {G}—> {D, H}, {C, H}—> {E}, {B, D}—> {F}, {D}—>{C}, {C}—> {G}} 1) Draw FD using the diagrammatic notation. 2) What are all candidate keys for R? 3) If delete {C}—>{G} and change {C, H}—> {E} to {C, H}—> {E, G}, what are all candidate keys for R
S = Z (integers), R = {(a,b) : a = b mod 5}. Is this relation...
S = Z (integers), R = {(a,b) : a = b mod 5}. Is this relation an equivalence relation on S? S = Z (integers), R = {(a,b) : a = b mod 3}. Is this relation an equivalence relation on S? If so, what are the equivalence classes?
Let R be the relation on Z+× Z+ such that (a, b) R (c, d) if...
Let R be the relation on Z+× Z+ such that (a, b) R (c, d) if and only if ad=bc. (a) Show that R is an equivalence relation. (b) What is the equivalence class of (1,2)? List out at least five elements of the equivalence class. (c) Give an interpretation of the equivalence classes for R. [Here, an interpretation is a description of the equivalence classes that is more meaningful than a mere repetition of the definition of R. Hint:...
Consider the following relation R(A, B, C, D, E, G) and the set of functional dependencies...
Consider the following relation R(A, B, C, D, E, G) and the set of functional dependencies F={ A → BCD, BC → DE, B→D, D → A} Note: Show the steps for each answer. (a) Compute B+ . (b) Prove (using Armstrong’s axioms) that AG is superkey. (c) Compute Fc. (d) Give a 3NF decomposition of the given schema based on a canonical cover. (e) Give a BCNF decomposition of the given schema based on F. Use the first functional...
On the set S of all real numbers, define a relation R = {(a, b):a ≤ b}. Show that R is transitive.
On the set S of all real numbers, define a relation R = {(a, b):a ≤ b}. Show that R is transitive.
For the relation R(A,B,C,D,E) with the following Functional Dependencies: A → B, A → C, BC...
For the relation R(A,B,C,D,E) with the following Functional Dependencies: A → B, A → C, BC → D, AC → E, CE → A, list all non-trivial FDs following from the above.    Generate all possible keys for R. Check whether R is in 3NF. If it is in 3NF, explain the criteria you used. If it is not in 3NF, convert it into 3NF, showing the new relations and their FDs.
Let L = {x = a r b s c t | r + s =...
Let L = {x = a r b s c t | r + s = t, r, s, t ≥ 0}. Give the simplest proof you can that L is not regular using the pumping lemma.
Consider a group of individuals A, B and C and the relation as wealthy as as...
Consider a group of individuals A, B and C and the relation as wealthy as as in A is as wealthy as B. Does this relation satisfy the completeness and transitivity properties? If the relation of the same group of individuals as above was strictly wealthier than, would this relation be transitive?
Consider this set A = { a, b, c, d } and the following relations R6...
Consider this set A = { a, b, c, d } and the following relations R6 = { ( a, a ), ( a, b), ( b, b), ( c, d ) } R7 = { ( a, a), ( b, b ), ( b, c ), ( c, c ), ( c, d), (d, d) } R8 = { (a, b), (a, d), ( b, a), ( d, a) , ( b, d) , (d, b) } R9 =...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT