Editing Relational algebra (section)

=== Selection ===

Rules about selection operators play the most important role in query optimization. Selection is an operator that very effectively decreases the number of rows in its operand, so if the selections in an expression tree are moved towards the leaves, the internal [[relation (database)|relation]]s (yielded by subexpressions) will likely shrink.

==== Basic selection properties ====

Selection is [[idempotent]] (multiple applications of the same selection have no additional effect beyond the first one), and [[commutative]] (the order selections are applied in has no effect on the eventual result).

#<math>\sigma_{A}(R)=\sigma_{A}\sigma_{A}(R)\,\!</math>
#<math>\sigma_{A}\sigma_{B}(R)=\sigma_{B}\sigma_{A}(R)\,\!</math>

==== Breaking up selections with complex conditions ====

A selection whose condition is a [[Logical conjunction|conjunction]] of simpler conditions is equivalent to a sequence of selections with those same individual conditions, and selection whose condition is a [[Logical disjunction|disjunction]] is equivalent to a union of selections.  These identities can be used to merge selections so that fewer selections need to be evaluated, or to split them so that the component selections may be moved or optimized separately.

#<math>\sigma_{A \land B}(R)=\sigma_{A}(\sigma_{B}(R))=\sigma_{B}(\sigma_{A}(R))</math>
#<math>\sigma_{A \lor B}(R)=\sigma_{A}(R)\cup\sigma_{B}(R)</math>

==== Selection and cross product ====
Cross product is the costliest operator to evaluate. If the input [[relation (database)|relation]]s have ''N'' and ''M'' rows, the result will contain <math>NM</math> rows. Therefore, it is important to decrease the size of both operands before applying the cross product operator.

This can be effectively done if the cross product is followed by a selection operator, e.g. <math>\sigma_{A}(R \times P)</math>. Considering the definition of join, this is the most likely case. If the cross product is not followed by a selection operator, we can try to push down a selection from higher levels of the expression tree using the other selection rules.

In the above case the condition ''A'' is broken up in to conditions ''B'', ''C'' and ''D'' using the split rules about complex selection conditions, so that <math>A = B \wedge C \wedge D</math> and ''B'' contains attributes only from ''R'', ''C'' contains attributes only from ''P'', and ''D'' contains the part of ''A'' that contains attributes from both ''R'' and ''P''. Note, that ''B'', ''C'' or ''D'' are possibly empty. Then the following holds:
:<math>\sigma_{A}(R \times P) = \sigma_{B \wedge C \wedge D}(R \times P) = \sigma_{D}(\sigma_{B}(R) \times \sigma_{C}(P))</math>

==== Selection and set operators ====
Selection is [[distributive property|distributive]] over the set difference, intersection, and union operators.  The following three rules are used to push selection below set operations in the expression tree. For the set difference and the intersection operators, it is possible to apply the selection operator to just one of the operands following the transformation. This can be beneficial where one of the operands is small, and the overhead of evaluating the selection operator outweighs the benefits of using a smaller [[relation (database)|relation]] as an operand.

#<math>\sigma_{A}(R\setminus P)=\sigma_{A}(R)\setminus \sigma_{A}(P) =\sigma_{A}(R)\setminus P</math>
#<math>\sigma_{A}(R\cup P)=\sigma_{A}(R)\cup\sigma_{A}(P)</math>
#<math>\sigma_{A}(R\cap P)=\sigma_{A}(R)\cap\sigma_{A}(P)=\sigma_{A}(R)\cap P=R\cap \sigma_{A}(P)</math>

==== Selection and projection ====

Selection commutes with projection if and only if the fields referenced in the selection condition are a subset of the fields in the projection.  Performing selection before projection may be useful if the operand is a cross product or join.  In other cases, if the selection condition is relatively expensive to compute, moving selection outside the projection may reduce the number of tuples which must be tested (since projection may produce fewer tuples due to the elimination of duplicates resulting from omitted fields).

:<math>\pi_{a_1, \ldots ,a_n}(\sigma_A( R )) = \sigma_A(\pi_{a_1, \ldots,a_n}( R ))\text{ where fields in }A \subseteq \{a_1,\ldots,a_n\}</math>