Selection Operation

Posted By on December 13, 2014

Download PDF
Measures of query cost

Selection Operation

  1. Consider the query to find the assets and branch-names of all banks who have depositors living in Port Chester. In relational algebra, this is
    (customer  tex2html_wrap_inline828  deposit  tex2html_wrap_inline828  branch))
    • This expression constructs a huge relation,
       customer  tex2html_wrap_inline828  deposit  tex2html_wrap_inline828  branch 

      of which we are only interested in a few tuples.

    • We also are only interested in two attributes of this relation.
    • We can see that we only want tuples for which ccity = “Port Chester”.
    • Thus we can rewrite our query as:
       tex2html_wrap_inline828  deposit  tex2html_wrap_inline828  branch)
    • This should considerably reduce the size of the intermediate relation.
  2. Suggested Rule for Optimization:
    • Perform select operations as early as possible.
    • If our original query was restricted further to customers with a balance over $1000, the selection cannot be done directly to the customer relation above.
    • The new relational algebra query is
      (customer  tex2html_wrap_inline828  deposit  tex2html_wrap_inline828  branch))
    • The selection cannot be applied to customer, as balance is an attribute of deposit.
    • We can still rewrite as
      (customer  tex2html_wrap_inline828  deposit))
       tex2html_wrap_inline828  branch)
    • If we look further at the subquery (middle two lines above), we can split the selection predicate in two:

      (customer tex2html_wrap_inline828 deposit))

    • This rewriting gives us a chance to use our “perform selections early” rule again.
    • We can now rewrite our subquery as:
  3. Second Transformational Rule:
    • Replace expressions of the form tex2html_wrap_inline866 by tex2html_wrap_inline868 where tex2html_wrap_inline870 and tex2html_wrap_inline872 are predicates and e is a relational algebra expression.
    • Generally,
Measures of query cost

Download PDF

Posted by