com.bigdata.rdf.sparql.ast

Class StaticAnalysis_CanJoin

java.lang.Object

com.bigdata.rdf.sparql.ast.StaticAnalysisBase

com.bigdata.rdf.sparql.ast.StaticAnalysis_CanJoin

Direct Known Subclasses:

StaticAnalysis

public abstract class StaticAnalysis_CanJoin
extends StaticAnalysisBase

Class provides methods to determine if two IJoinNodes can join on a shared variable and if they can join on an variable which is indirectly shared through constraints which can be attached to that join.

Note: This is a port of com.bigdata.bop.joinGraph.PartitionedJoinGroup

Version:

$Id: StaticAnalysis_CanJoin.java 5378 2011-10-20 20:37:08Z thompsonbry $

Author:

Bryan Thompson

Field Summary

Fields inherited from class com.bigdata.rdf.sparql.ast.StaticAnalysisBase

evaluationContext, queryRoot

Constructor Summary

Constructors

Constructor and Description
StaticAnalysis_CanJoin(QueryRoot queryRoot, IEvaluationContext evaluationContext)

Method Summary

Methods

Modifier and Type	Method and Description
boolean	canJoin(IJoinNode p1, IJoinNode p2) Return true iff two predicates can join on the basis of at least one variable which is shared directly by those predicates.
boolean	canJoinUsingConstraints(IJoinNode[] path, IJoinNode vertex, FilterNode[] constraints) Return true iff a predicate may be used to extend a join path on the basis of at least one variable which is shared either directly or via one or more constraints which may be attached to the predicate when it is added to the join path.
abstract Set<IVariable<?>>	getDefinitelyProducedBindings(IBindingProducerNode node, Set<IVariable<?>> vars, boolean recursive) Return the set of variables which MUST be bound for solutions after the evaluation of this group.
FilterNode[][]	getJoinGraphConstraints(IJoinNode[] path, FilterNode[] joinGraphConstraints, Set<IVariable<?>> boundVars, boolean pathIsComplete) Given a join path, return the set of constraints to be associated with each join in that join path.

Methods inherited from class com.bigdata.rdf.sparql.ast.StaticAnalysisBase

addAll, getNamedSubqueryRoot, getQueryRoot, getRequiredNamedSubqueryRoot, getSolutionSetStats, getSpannedVariables, getSpannedVariables, getSPOVariables, isFullyBound

Methods inherited from class java.lang.Object

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

Constructor Detail

StaticAnalysis_CanJoin

public StaticAnalysis_CanJoin(QueryRoot queryRoot,
                      IEvaluationContext evaluationContext)

Parameters:

queryRoot - The root of the query. We need to have this on hand in order to resolve NamedSubqueryIncludes during static analysis.

evaluationContext - The evaluation context provides access to the ISolutionSetStats and the ISolutionSetManager for named solution sets.

Method Detail

canJoin

public boolean canJoin(IJoinNode p1,
              IJoinNode p2)

Return true iff two predicates can join on the basis of at least one variable which is shared directly by those predicates. Only the operands of the predicates are considered.

Note: This method will only identify joins where the predicates directly share at least one variable. However, joins are also possible when the predicates share variables via one or more constraint(s). Use canJoinUsingConstraints to identify such joins.

Note: Any two predicates may join regardless of the presence of shared variables. However, such joins will produce the full cross product of the binding sets selected by each predicate. As such, they should be run last and this method will not return true for such predicates.

Parameters:

p1 - A predicate.

p2 - Another predicate.

Returns:

true iff the predicates share at least one variable as an operand.

Throws:

IllegalArgumentException - if the two either reference is null.

canJoinUsingConstraints

public boolean canJoinUsingConstraints(IJoinNode[] path,
                              IJoinNode vertex,
                              FilterNode[] constraints)

Return true iff a predicate may be used to extend a join path on the basis of at least one variable which is shared either directly or via one or more constraints which may be attached to the predicate when it is added to the join path. The join path is used to decide which variables are known to be bound, which in turn decides which constraints may be run. Unlike the case when the variable is directly shared between the two predicates, a join involving a constraint requires us to know which variables are already bound so we can know when the constraint may be attached.

Note: Use canJoin(IJoinNode, IJoinNode) instead to identify joins based on a variable which is directly shared.

Note: Any two predicates may join regardless of the presence of shared variables. However, such joins will produce the full cross product of the binding sets selected by each predicate. As such, they should be run last and this method will not return true for such predicates.

Parameters:

path - A join path containing at least one predicate.

vertex - A predicate which is being considered as an extension of that join path.

constraints - A set of zero or more constraints (optional). Constraints are attached dynamically once the variables which they use are bound. Hence, a constraint will always share a variable with any predicate to which it is attached. If any constraints are attached to the given vertex and they share a variable which has already been bound by the join path, then the vertex may join with the join path even if it does not directly bind that variable.

Returns:

true iff the vertex can join with the join path via a shared variable.

Throws:

IllegalArgumentException - if the join path is null.

IllegalArgumentException - if the join path is empty.

IllegalArgumentException - if any element in the join path is null.

IllegalArgumentException - if the vertex is null.

IllegalArgumentException - if the vertex is already part of the join path.

IllegalArgumentException - if any element in the optional constraints array is null.

getJoinGraphConstraints

public FilterNode[][] getJoinGraphConstraints(IJoinNode[] path,
                                     FilterNode[] joinGraphConstraints,
                                     Set<IVariable<?>> boundVars,
                                     boolean pathIsComplete)

Given a join path, return the set of constraints to be associated with each join in that join path. Only those constraints whose variables are known to be bound will be attached.

Parameters:

path - The join path.

joinGraphConstraints - The constraints to be applied to the join path (optional).

knownBoundVars - Variables that are known to be bound as inputs to this join graph (parent queries).

pathIsComplete - true iff the path represents a complete join path. When true, any constraints which have not already been attached will be attached to the last predicate in the join path.

Returns:

The constraints to be paired with each element of the join path.

Throws:

IllegalArgumentException - if the join path is null.

IllegalArgumentException - if the join path is empty.

IllegalArgumentException - if any element of the join path is null.

IllegalArgumentException - if any element of the join graph constraints is null.

getDefinitelyProducedBindings

public abstract Set<IVariable<?>> getDefinitelyProducedBindings(IBindingProducerNode node,
                                              Set<IVariable<?>> vars,
                                              boolean recursive)

Return the set of variables which MUST be bound for solutions after the evaluation of this group. A group will produce "MUST" bindings for variables from its statement patterns and a LET based on an expression whose variables are known bound.

The returned collection reflects "bottom-up" evaluation semantics. This method does NOT consider variables which are already bound on entry to the group.

Note: When invoked for an OPTIONAL or MINUS join group, the variables which would become bound during the evaluation of the join group are reported. Caller's who wish to NOT have variables reported for OPTIONAL or MINUS groups MUST NOT invoke this method for those groups.

Note: The recursive analysis does not throw out variables when part of the tree will provably fail to bind anything. It is the role of query optimizers to identify those situations and prune the AST appropriately.

The class hierarchy is a little untidy at this point. This method is defined in the only subclass of this abstract class. Initially it was thought to not be needed here.

Parameters:

node - The node to be analyzed.

vars - Where to store the "MUST" bound variables.

recursive - When true, the child groups will be recursively analyzed. When false, only this group will be analyzed.

Returns:

The argument.