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.