%ex3.1

\begin{enumerate}[label=(\alph*)]
	\item\textbf{Compute the communication cost of all strategies from the slides (and listed below)}\\
	Query: $ \pi_{name,price}(Users \bowtie_{uid=user} Orders)$
	
	Strategies:
	\begin{enumerate}[label=(\roman*)]
		\item\textbf{Send both tables to site 4 and join there.}\\
		40000 * 800 + 900000 * 30 = \underline{\textbf{59 000 000}}
		
		\item\textbf{Send Users to site 2, join there and send the result to site 4.}\\
		40000 * 800 + (40000 * 900000 / 360000) * 104 = \underline{\textbf{42 400 000}}
		
		\item\textbf{Symmetrically: Send Orders to site 1, join there and send the result to site 4.}\\
		900000 * 30 + (40000 * 900000 / 360000) * 104 = \underline{\textbf{37 400 000}}
		
		\item\textbf{Send only the join attributes of Users to site 2, semi join with Orders.}\\
		40000 * 8 + min(40000, (40000 * 900000 / 360000)) * 30 + min(40000, (40000 * 900000 / 360000)) * 104 = \underline{\textbf{5 680 000}}
		
		\item\textbf{The semi-join strategy in the opposite direction.}\\
		900000 * 8 + min(900000, (40000 * 900000 / 360000)) * 800 + min(900000, (40000 * 900000 / 360000)) * 104 = \underline{\textbf{97 600 000}}
	\end{enumerate}

	\item[(a*)]\textbf{Vary the strategies above in such a way, that you always project to only the necessary
		columns as early as possible.}\\
	Strategies:
	\begin{enumerate}[label=(\roman*)]
		\item\textbf{Send both tables to site 4 and join there.}\\
		40000 * 108 + 900000 * 12 = \underline{\textbf{15 120 000}}
		
		\item\textbf{Send Users to site 2, join there and send the result to site 4.}\\
		40000 * 108 + (40000 * 900000 / 360000) * 104 = \underline{\textbf{14 720 000}}
		
		\item\textbf{Symmetrically: Send Orders to site 1, join there and send the result to site 4.}\\
		900000 * 12 + (40000 * 900000 / 360000) * 104 = \underline{\textbf{21 200 000}}
		
		\item\textbf{Send only the join attributes of Users to site 2, semi join with Orders.}\\
		40000 * 8 + min(40000, (40000 * 900000 / 360000)) * 12 + min(40000, (40000 * 900000 / 360000)) * 104 = \underline{\textbf{4 960 000}}
		
		\item\textbf{The semi-join strategy in the opposite direction.}\\
		900000 * 8 + min(900000, (40000 * 900000 / 360000)) * 108 + min(900000, (40000 * 900000 / 360000)) * 104 = \underline{\textbf{28 400 000}}
	\end{enumerate}

	\item\textbf{Now consider how to generalize the strategies of task (a*) above to situations with more
		than 2 relations and the strategy with optimal communication cost for Query 2 given below}\\
		Query: $ Products \bowtie_{pid=prod} \pi_{name,price,prod}(Users \bowtie_{uid=user} Orders)$
		
\end{enumerate}