Always Good Transformations

Push selections:

${\sigma }_{\phi }(E_1{\bowtie }_{\theta }{E}_2)={\sigma }_{\phi }(E_1){\bowtie }_{\theta }{E}_2$

• for $\phi$ involving columns of $E_1$ only

Push projections:

${\pi }_V(E_1{\bowtie }_{\theta }{E}_2)={\pi }_V({\pi }_{V_1}(E_1){\bowtie }_{\theta }{\pi }_{V_2}(E_2))$

• where $V_1$ is the set of all columns of $R$ involved in $\theta$ and $V$
• Similarly for $V_2$

Replace products by joins:

${\sigma }_{\phi }(R\times S)=R{\bowtie }_{\theta }S$

These rewrites also reduce the space of plans to search