We discussed semi-join in the context of distributed computing. A semi-join works as a reducer to...

 

Transcribed Image Text:

We discussed semi-join in the context of distributed computing. A semi-join works as a reducer to reduce a relation by removing its tuples that cannot join. Below, we focus on natural joins. Consider a join query, r₁ r₂ ... rn, where ri is a relation with schema R stored on a different site S₁. A relation r, is fully reduced to be r, if r = IIR: (r₁ r₂ .. ▷rn) for rri. In other words, it suggests that if we use r instead of r; to join, the final result remains unchanged and every tuple in r' will appear in the final result as it must be able to join with other relations. The relation r is the smallest of ri to join others such that all unnecessary tuples are removed from ri. A full reducer is a program that fully reduces every relation r; involved in a join query using semijoins. After all relations being fully reduced, we do the joins. Note that the figure (b) in the slide 22.61 in ch22.pptx is NOT an example of full reduce first followed by joins. Consider a join with three relations r₁, 72, and r3, on the schema of R₁(A, B), R₂(B, C), and R3(C, D), respectively. Answer the following questions. (a) Show that it is impossible to use 3 semijoins to fully reduce all the three relations using a concrete example. You need to justify your answer. (b) Show the smallest number of semijoins to fully reduce all the three rela- tions using the same concrete example in (a), give the details of semijoins in order, and justify your answer. We discussed semi-join in the context of distributed computing. A semi-join works as a reducer to reduce a relation by removing its tuples that cannot join. Below, we focus on natural joins. Consider a join query, r₁ r₂ ... rn, where ri is a relation with schema R stored on a different site S₁. A relation r, is fully reduced to be r, if r = IIR: (r₁ r₂ .. ▷rn) for rri. In other words, it suggests that if we use r instead of r; to join, the final result remains unchanged and every tuple in r' will appear in the final result as it must be able to join with other relations. The relation r is the smallest of ri to join others such that all unnecessary tuples are removed from ri. A full reducer is a program that fully reduces every relation r; involved in a join query using semijoins. After all relations being fully reduced, we do the joins. Note that the figure (b) in the slide 22.61 in ch22.pptx is NOT an example of full reduce first followed by joins. Consider a join with three relations r₁, 72, and r3, on the schema of R₁(A, B), R₂(B, C), and R3(C, D), respectively. Answer the following questions. (a) Show that it is impossible to use 3 semijoins to fully reduce all the three relations using a concrete example. You need to justify your answer. (b) Show the smallest number of semijoins to fully reduce all the three rela- tions using the same concrete example in (a), give the details of semijoins in order, and justify your answer.