Query Equivalence

Any two relational expressions are said to be equivalent if both the expression generates the same set of records. When two expressions are equivalent we can use them interchangeably.

EQUIVALENCE RULES IN DBMS

1. Conjunctive selection operations can be deconstructed into a sequence of individual selections. This transformation is referred to as a cascade of σ.

$\sigma_{\theta_{1}\Lambda\theta_{2} }(E)=\sigma_{\theta_{1}}(\sigma_{\theta_{2}}(E))$

2. Selection operations are commutative.

$\sigma_{\theta_{1}}(\sigma_{\theta_{2}}(E))=\sigma_{\theta_{2}}(\sigma_{\theta_{1}}(E))$

3. Only the final operations in a sequence of projection operations are needed, the others can be omitted. This transformation can also be referred to as a cascade of Π.

$\pi_{L_{1}}(\pi_{L_{2}}(...(\pi_{L_{n}}(E))...)) = \pi_{L_{1}}(E)$

4. Selections can be combined with Cartesian products and theta joins.

a. $\sigma_{\theta}(E_{1} \times E_{2}) = E_{1} \bowtie_{\theta} E_{2}$

This expression is just the definition of the theta join.

b. $\sigma_{\theta}(E_{1} \times E_{2}) = E_{1} \bowtie_{\theta} E_{2}$

5. Theta-join operations are commutative.

$E_{1} \bowtie_{\theta} E_{2} = E_{2} \bowtie_{\theta} E_{1}$

Actually, the order of attributes differs between the left-hand side and the righthand side, so the equivalence does not hold if the order of attributes is taken into account. A projection operation can be added to one of the sides of the equivalence to appropriately reorder attributes, but for simplicity, we omit the projection and ignore the attribute order in most of our examples.

6. a. Natural-join operations are associative.

$(E_{1} \bowtie E_{2}) \bowtie E_{3} = E_{1} \bowtie (E_{2} \bowtie E_{3})$

b. Theta joins are associative in the following manner:

$(E_{1} \bowtie_{\theta_{1}} E_{2}) \bowtie_{\theta_{2} \Lambda \theta_{3}} E_{3} = E_{1} \bowtie_{\theta_{1} \Lambda \theta_{3}} (E_{2} \bowtie_{\theta_{2}} E_{3})$

where θ2 involves attributes from only E2 and E3. Any of these conditions may be empty; hence, it follows that the Cartesian product (×) operation is also associative. The commutativity and associativity of join operations are important to join reordering in query optimization.

7. The selection operation distributes over the theta-join operation under the following two conditions:

a. It distributes when all the attributes in selection condition θ0 involve only the attributes of one of the expressions (say, E1) being joined.

$\sigma_{\theta_{1}\Lambda\theta_{2}}(E_{1}\bowtie_{\theta}E_{2})=(\sigma_{\theta_{1}}(E_{1}))\bowtie_{\theta}(\sigma_{\theta_{2}}(E_{2}))$

b. It distributes when selection condition θ1 involves only the attributes of E1 and θ2 involve only the attributes of E2.

$\sigma_{\theta_{0}}(E_{1}\bowtie_{\theta}E_{2})=(\sigma_{\theta_{0}}(E_{1}))\bowtie_{\theta}E_{2}$

8. The projection operation distributes over the theta-join operation under the following conditions.

a. Let L1 and L2 be attributes of E1 and E2, respectively. Suppose that the join condition θ involves only attributes in L1 ∪ L2. Then,

$\pi_{L_{1}\cup L_{2}}(E_{1}\bowtie_{\theta}E_{2})=(\pi_{L_{1}}(E_{1}))\bowtie_{\theta}(\pi_{L_{2}}(E_{2}))$

b. Consider a join E1 􀀀θ E2. Let L1 and L2 be sets of attributes from E1 and E2, respectively. Let L3 be attributes of E1 that are involved in join condition θ, but are not in L1 ∪ L2, and let L4 be attributes of E2 that are involved in join condition θ, but are not in L1 ∪ L2. Then,

$\pi_{L_{1}\cup L_{2}}(E_{1}\bowtie_{\theta}E_{2})=\pi_{L_{1}\cup L_{2}}((\pi_{L_{1}\cup L_{3}}))\bowtie_{\theta}(\pi_{L_{2}\cup L_{4}}(E_{2})))$