com.bigdata.rdf.sparql.ast.optimizers

Class ASTBottomUpOptimizer

java.lang.Object

com.bigdata.rdf.sparql.ast.optimizers.ASTBottomUpOptimizer

All Implemented Interfaces:

IASTOptimizer

public class ASTBottomUpOptimizer
extends Object
implements IASTOptimizer

Rewrites aspects of queries where bottom-up evaluation would produce different results. This includes joins which are not "well designed" as defined in section 4.2 of "Semantics and Complexity of SPARQL", 2006, Jorge Prez et al and also FILTERs on variables whose bindings are not in scope.

Note: The test suite for this class is a set of DAWG tests which focus on bottom up evaluation semantics, including:

Nested Optionals - 1 (Query is not well designed because there are no shared variables in the intermediate join group and there is an embedded OPTIONAL join group. Since ?v is not present in the intermediate join group the (:x3 :q ?w . OPTIONAL { :x2 :p ?v }) solutions must be computed first and then joined against the (:x1 :p ?v) solutions.)

 SELECT *
 { 
     :x1 :p ?v .
     OPTIONAL
     {
       :x3 :q ?w .
       OPTIONAL { :x2 :p ?v }
     }
 }
 

Filter-scope - 1 (Query is not well designed because there are no shared variables in the intermediate join group and there is an embedded OPTIONAL join group. Also, ?v is used in the FILTER but is not visible in that scope.)

 SELECT *
 { 
     :x :p ?v . 
     { :x :q ?w 
       OPTIONAL {  :x :p ?v2 FILTER(?v = 1) }
     }
 }
 

Join-scope - 1 (Query is not well designed because there are no shared variables in the intermediate group and there is an embedded OPTIONAL join group.)

 SELECT *
 { 
   ?X  :name "paul"
   {?Y :name "george" . OPTIONAL { ?X :email ?Z } }
 }
 

Filter-nested - 2 (Filter on variable ?v which is not in scope)

 SELECT ?v
 { :x :p ?v . { FILTER(?v = 1) } }
 

bind07 - BIND (?o not in scope for bind)

 SELECT ?s ?p ?o ?z
 {
   ?s ?p ?o .
   { BIND(?o+1 AS ?z) } UNION { BIND(?o+2 AS ?z) }
 }
 

Nested groups which do not share variables with their parent can be lifted out into a named subquery. This has the same effect as bottom up evaluation since we will run the named subquery first and then perform the join against the parent group. However, in this case an exogenous binding which causes a shared variable to exist would mean that the query could run normally since the value in the outer group and the inner group would now be correlated through the exogenous binding. E.g., in the last example above.

Version:

$Id: ASTBottomUpOptimizer.java 5189 2011-09-14 17:56:53Z thompsonbry $ TODO I have been assuming that the presence of any shared variable is enough to enforce correlation between the solution sets and cause the results of bottom up evaluation to be the same as our standard evaluation model. If this is not true then we could just lift everything into a named subquery, order the named subqueries by their dependencies and just let it run.

Author:

Bryan Thompson

See Also:

https://sourceforge.net/apps/trac/bigdata/ticket/232, http://www.dcc.uchile.cl/~cgutierr/papers/sparql.pdf

Constructor Summary

Constructors

Constructor and Description
ASTBottomUpOptimizer()

Method Summary

Methods

Modifier and Type	Method and Description
QueryNodeWithBindingSet	optimize(AST2BOpContext context, QueryNodeWithBindingSet input) Optimize the AST.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

ASTBottomUpOptimizer

public ASTBottomUpOptimizer()

Method Detail

optimize

public QueryNodeWithBindingSet optimize(AST2BOpContext context,
                               QueryNodeWithBindingSet input)

Description copied from interface: IASTOptimizer

Optimize the AST.

Specified by:

optimize in interface IASTOptimizer

Parameters:

context - The evaluation context.

input - The input to the optimizer, consisting of a queryNode and input binding set.

Returns:

An instance of type QueryNodeWithBindingSet.