Errata and Proofs for Quickr

We point out some errors in the SIGMOD version of our Quickr [2] paper. The transitivity theorem, in Proposition 1 of Quickr, has a revision in item iii. The revised version is Proposition 5 in this document. Definition 1 in Appendix B.2, which defines dominance, has a revision in the condition for c-dominance. The revised version is Definition 1 in this document. We also offer new definitions of equivalence and weak equivalence. The dominance pushdown rules in Appendix B.3 have, in general, been revised and substantially expanded. In particular, Proposition 7 in Quickr, which relates to projections that drop columns is simple but incomplete; Propositions 8 and 9 in this document consider the case of projections that rename columns and create new columns respectively. Proposition 8 in Quickr, which relates to pushing samplers past selections, is replaced with Proposition 10 in this document. Finally, we separate the Proposition 9 in Quickr, which pushes samplers past joins, into two separate propositions; Proposition 2 considers the special-case of foreign key joins and Proposition 12 considers other equijoins. Overall, we believe this document supersedes Quickr [2] in terms of accuracy analysis and proofs.