CPS 432/562 Homework #1 Solution Sketches

1. (5+5+5=15 points) Exercise 16.2.2 (parts b, c, and d) on p. 809 from [DBCB]: Give examples to show that:
   1. Projection cannot be pushed below a set or bag difference.
      The relation schemas and instances R(a,b,c)={(1,2,3), {1,3,2}) and S(a,b,c)={(1,2,3), (1,4,5)} provide an example which proves the assertion.
   2. Duplication elimination cannot be pushed below projection.
      The relation schemas and instances R(a,b,c)={(1,2,3), {1,3,2}) and S(a,b,c)={(1,2,3), (1,4,5)} provide an example which proves the assertion.
   3. Duplication elimination cannot be pushed below bag union or difference.
      The relation schemas and instances R(a)={(1),(1)} and S(a)={(1),(1)} provide an example which proves the assertion.
   
   
2. (10 points) Exercise 16.2.3 on p. 809 from [DBCB]. Prove that we can always push a projection below both branches of a bag union.
   Proof by contradition: Spoze is false. Thus, the lhs or rhs contains at least one tuple not present on the other side. Both of these cases lead to contraditions since neither bag union nor bag projection remove tuples.
   
   
3. (10+10=20 points) Exercise 16.2.4 (parts b and d) on p. 809 from [DBCB]: Some laws that hold for sets also hold for bags; other do not. For each of the laws below that are true for sets, indicate whether or not it is also true for bags. Either give a proof the law for bags is true or give a counterexample.
   1. R R = R (the idempotent law for intersection)
      True. Proof by contradition: Spoze R R = R is false. Thus, the lhs or rhs contains at least one tuple not present on the other side. Both of these cases lead to R != R which is a contradition.
   
   
   2. R (S T) = (R S) (R T) (the distribution of union over intersection)
      True. The tuples of R added to S and T (through bag union) prior to their bag intersection will only add the tuples of R to that bag intersection beyond the bag intersection of simply S and T which is just the lhs (by the idempotent law for intersection).
   
   
4. (5 points) Exercise 16.2.6 (part b) on p. 809 from [DBCB]: Push the projection in the following expression down as far as it can go.
   
   
   
5. (10 points) Required only for CPS 562 students
   Exercise 16.2.5 (part b) on p. 809 from [DBCB]: We can define for bags by: R S if and only if for every element x, the number of times x appears in R is less than or equal to the number of times it appears in S. Tell whether the statement `if R S, then R S = R' (which is true for sets) is true for bags; give either a proof or a counterexample.
   Assume R S is true. Show that R S = R must also be true. Proof by contradition: Spoze R S = R is false. Thus, the lhs or rhs contains at least one tuple not present on the other side. Both of these cases lead to contraditions as shown below.
   1. If the lhs has the unique tuple, then that tuple must be in R (by the assumption) and thus present on the lhs.
   2. If the rhs has the unique tuple, then that tuple must be present on the lhs (again, by the assumption).