ex2/main_3.tex

   1 %ex2.3
   2
   3 \begin{enumerate}[label=(\alph*)]
   4         \item\textbf{Bag Union, defined to be the bag of tuples in which tuple t appears the sum of the
   5                 numbers of times it appears in R and S, e.g. if tuple t occurs in R 3 times, and in S 4
   6                 times, then it should occur in the bag union R and S 7 times.}\\
   7
   8                 \textbf{Map function:} for every tuple t in R and for every tuple t in
   9                 S, produce the key-value pair (t,t);
  10
  11                 \textbf{Reduce function:} Receives input of the form (t; [t, t, …, t])\\
  12                 outputs (t,t) k-times\\
  13
  14         \item\textbf{Bag Difference, defined to be the bag of tuples in which the number of times a tuple
  15                 t appears is equal to the number of times it appears in R minus the number of times it
  16                 appears in S. A tuple that appears more times in S than in R does not appear in the
  17                 difference, e.g. if tuple t occurs in R 4 times, and in S 3 times, then it should occur in
  18                 the bag difference of R with S only once.}\\
  19
  20                 \textbf{Map function:} for every tuple t in R and for every tuple t in
  21                 S, produce the key-value pair (t; ''R'') or (t; ''S''), respectively.
  22
  23                 \textbf{Reduce function:} Receives input of the form (t; [$x_{1}$,…,$x_{n}$]), where each $x_{i}$ is either the form of ''R'' or ''S''.\\
  24                 Outputs (t,t) if the input contains ''R'' but not ''S''.\\
  25                 Outputs nothing otherwise.
  26
  27                 \textbf{Alternative Reduce function:} Receives input of the form (t; [$x_{1}$,…,$x_{n}$]), where each $x_{i}$ is either the form of ''R'' or ''S''.\\
  28                 Initialize a counter k = 0. For each ''R'' increment k. For each ''S'' decrement k.\\
  29                 Outputs (t,t) k times, if k > 0.
  30 \end{enumerate}