CPS 432/562 Homework #1

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.
   2. Duplication elimination cannot be pushed below projection.
   3. Duplication elimination cannot be pushed below bag union or difference.
   
   
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.
   
   
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 union)
   2. R (S T) = (R S) (R T) (the distribution of union over 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.