]> git.somenet.org - pub/jan/adbs.git/blob - ex2/main_3.tex
GITOLITE.txt
[pub/jan/adbs.git] / 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}