From c3830495d7c429e5c59da2e5e8ae1106b333ac8f Mon Sep 17 00:00:00 2001
From: Jan Vales <jan@jvales.net>
Date: Mon, 17 Jun 2019 05:56:33 +0200
Subject: [PATCH] [ex3.1] communication costs.

---
 ex3/main_1.tex | 48 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 48 insertions(+)

diff --git a/ex3/main_1.tex b/ex3/main_1.tex
index 55336e9..f8e1607 100644
--- a/ex3/main_1.tex
+++ b/ex3/main_1.tex
@@ -1 +1,49 @@
 %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}
\ No newline at end of file
-- 
2.43.0