Using the matrix-vector multiplication described in Section 2.3.1, applied to the matrix and vector:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

1 2 3 4

apply the Map function to this matrix and vector. Then, identify in the list below, one of the key-value pairs that are output of Map.

Suppose we use the algorithm of Section 2.3.10 to compute the product of matrices M and N. Let M have x rows and y columns, while N has y rows and z columns. As a function of x, y, and z, express the answers to the following questions:

1. The output of the Map function has how many different keys? How many key-value pairs are there with each key? How many key-value pairs are there in all?

2. The input to the Reduce function has how many keys? What is the length of the value (a list) associated with each key?

Then, identify the true statement in the list below.

Suppose we use the two-stage algorithm of Section 2.3.9 to compute the product of matrices M and N. Let M have x rows and y columns, while N has y rows and z columns. As a function of x, y, and z, express the answers to the following questions:

1. The output of the first Map function has how many different keys? How many key-value pairs are there with each key? How many key-value pairs are there in all?

2. The output of the first Reduce function has how many keys? What is the length of the value (a list) associated with each key?

3. The output of the second Map function has how many different keys? How many key-value pairs are there with each key? How many key-value pairs are there in all?

Then, identify the true statement in the list below.

Suppose we have the following relations:

R A B 0 1 1 2 2 3

S B C 0 1 1 2 2 3

and we take their natural join by the algorithm of Section 2.3.7. Apply the Map function to the tuples of these relations. Then, construct the elements that are input to the Reduce function. Identify one of these elements in the list below.