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, r1 r2 rn, where ri is a relation with schema Ri stored on a different site Si. A relation ri is fully reduced to be ri, if ri = Ri(r1 r2 rn) for ri ri. In other words, it suggests that if we use ri instead of ri to join, the final result remains unchanged and every tuple in ri will appear in the final result as it must be able to join with other relations. The relation ri 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 ri 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 r1, r2, and r3, on the schema of R1(A,B), R2(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.

Question 1: 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, r1r2rn, where ri is a relation with schema Ri stored on a different site Si. A relation ri is fully reduced to be ri, if ri=Ri(r1r2rn) for riri. In other words, it suggests that if we use ri instead of ri to join, the final result remains unchanged and every tuple in ri will appear in the final result as it must be able to join with other relations. The relation ri 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 ri 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 r1,r2, and r3, on the schema of R1(A,B), R2(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 relations using the same concrete example in (a), give the details of semijoins in order, and justify your answer. Question 1: 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, r1r2rn, where ri is a relation with schema Ri stored on a different site Si. A relation ri is fully reduced to be ri, if ri=Ri(r1r2rn) for riri. In other words, it suggests that if we use ri instead of ri to join, the final result remains unchanged and every tuple in ri will appear in the final result as it must be able to join with other relations. The relation ri 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 ri 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 r1,r2, and r3, on the schema of R1(A,B), R2(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 relations using the same concrete example in (a), give the details of semijoins in order, and justify your