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
      tex2html_wrap_inline826  
    (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_inline836  
       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
        tex2html_wrap_inline842  
       tex2html_wrap_inline844  
      (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
        tex2html_wrap_inline842 
       tex2html_wrap_inline852  
      (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:
        tex2html_wrap_inline858

      (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:
        tex2html_wrap_inline862 
       tex2html_wrap_inline864  
      
  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,
        tex2html_wrap_inline876  
Measures of query cost

Download PDF

Posted by