com.bigdata.rdf.sparql.ast.optimizers

Class ASTGraphGroupOptimizer

java.lang.Object

com.bigdata.rdf.sparql.ast.optimizers.ASTGraphGroupOptimizer

All Implemented Interfaces:

IASTOptimizer

public class ASTGraphGroupOptimizer
extends Object
implements IASTOptimizer

Handles a variety of special constructions related to graph graph groups.

GRAPH ?foo

Anything nested (even if a subquery) is constrained to be from ?foo. All nested statement patterns must have ?foo as their context, even if they occur within a subquery. (This is not true for a named subquery which just projects its solutions but does not inherit the parent's graph context. However, if we lifted the named subquery out, e.g., for bottom up evaluation semantics, then we need to impose the GRAPH constraint on the named subquery which means running this optimizer before the one which lifts out the named subquery.)

GRAPH ?foo { GRAPH ?bar } }

The easy way to enforce this constraint when there are nested graph patterns is with a SameTerm(?foo,?bar) constraint inside of the nested graph pattern.

The problem with this is that it does not enforce the constraint as soon as possible under some conditions. A rewrite of the variable would have that effect but the rewrite needs to be aware of variable scope rules so we do not rewrite the variable within a subquery if it is not projected by that subquery. We would also have to add a BIND(?foo AS ?bar) to make ?bar visible in the scope of parent groups.

However, there is an INCLUDE problem too. That could be handled by moving the INCLUDE into a subgroup with a BIND to renamed the variable or by adding a "projection" to the INCLUDE so we could rename the variable there.

Since this construction of nested graph patterns is rare, and since it is complicated to make it more efficient, we are going with the SameTerm() constraint for now.

GRAPH uri

This is only allowed if the uri is in the named data set (or if no data set was given). Translation time error.

GRAPH uri { ... GRAPH uri2 ... }

It is an query error if a GRAPH uri is nested within another GRAPH uri for distinct IRIs.

GRAPH uri { ... GRAPH ?foo ... }

The outer graph imposes a constant constraint. The inner graph needs to inherit that constraint. Either a SameTerm() constraint must be added to the inner graph or context for the inner graph could be rewritten using Constant/2. Again, this is an optimization which may not contribute much value except in very rare cases. Unlike the case below, we do need to impose a SameTerm() constraint to make this case correct.

GRAPH ?foo { ... GRAPH uri ... }

If a constant is nested within a non-optional GRAPH uri then that constant could be lifted up and bound using Constant/2 on the outer graph pattern. Again, this is an optimization which may not contribute much value except in very rare cases. We do not need to do anything additional to make this case correct.

GRAPH ?g {}

This matches the distinct named graphs in the named graph portion of the data set (special case). There are several variations on this which need to be handled:

• If ?g might be bound or is not bound:
  • If there is no data set, then this should be translated into sp(_,_,_,?g)[filter=distinct] that should be recognized and evaluated using a distinct term advancer on CSPO.
  • If the named graphs are explicitly given, then annotate StatementPatternNode with an "IN" for (?g,namedGraphs).
  Either way, if there is a filter then apply the filter to the scan/list (this happens in AST2BOPUtility#toPredicate()).
• If ?g is known bound coming into graph ?g {} then we want to test for the existence of at least one statement on the CSPO index for ?g.This is basically ASK sp(_,_,_,uri) LIMIT 1, but we must run this for each binding on ?g.

GRAPH uri {}

This is an existence test for the graph. This is a CSPO iterator with C bound and a limit of one. Lift this into a named subquery since we only want to run it once. (This is basically ASK sp(_,_,_,uri) LIMIT 1.)

Note: This optimizer MUST run before optimizers which lift out named subqueries in order to correctly impose the GRAPH constraints on the named subquery.

Version:

$Id: ASTEmptyGroupOptimizer.java 5177 2011-09-12 17:49:44Z thompsonbry $ TODO If ?g can be statically analyzed as being bound to a specific constant then we would rewrite ?g using Constant/2 and then handle this as GRAPH uri {}

This is basically what AST2BOpJoins does when it follows the decision tree for named and default graphs. So, maybe that logic can be lifted into this class as a rewrite?

Author:

Bryan Thompson

See Also:

ASTEmptyGroupOptimizer, which handles {} for non-GRAPH groups.

Constructor Summary

Constructors

Constructor and Description
ASTGraphGroupOptimizer()

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

ASTGraphGroupOptimizer

public ASTGraphGroupOptimizer()

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.