com.bigdata.rdf.sparql.ast

Class StaticAnalysis

java.lang.Object

com.bigdata.rdf.sparql.ast.StaticAnalysisBase

com.bigdata.rdf.sparql.ast.StaticAnalysis_CanJoin

com.bigdata.rdf.sparql.ast.StaticAnalysis

public class StaticAnalysis
extends StaticAnalysis_CanJoin

Methods for static analysis of a query. There is one method which looks "up". This corresponds to how we actually evaluation things (left to right in the query plan). There are two methods which look "down". This corresponds to the bottom-up evaluation semantics of SPARQL.

When determining the "known" bound variables on entry to a node we have to look "up" the tree until we reach the outer most group. Note that named subqueries DO NOT receive bindings from the places where they are INCLUDEd into the query.

Analysis of Incoming "Known" Bound Variables (Looking Up)

Static analysis of the incoming "known" bound variables does NOT reflect bottom up evaluation semantics. If a variable binding would not be observed for bottom up evaluation semantics due to a badly designed left join pattern then the AST MUST be rewritten to lift the badly designed left join into a named subquery where it will enjoy effective bottom up evaluation semantics.

Analysis of "must" and "maybe" Bound Variables (Looking Down).

The following classes are producers of bindings and need to be handled by static analysis when looking down the AST tree:

QueryBase

The static analysis of the definitely and maybe bound variables depends on the projection and where clauses.

SubqueryRoot

SPARQL 1.1 subquery. This is just the static analysis of the QueryBase for that subquery.

NamedSubqueryRoot

This is just the static analysis of the QueryBase for that named subquery. Named subqueries are run without any visible bindings EXCEPT those which are exogenous.

NamedSubqueryInclude

The static analysis of the INCLUDE is really the static analysis of the NamedSubqueryRoot which produces that solution set. The incoming known variables are ignored when doing the static analysis of the named subquery root.

ServiceNode

The static analysis of the definitely and maybe bound variables depends on the graph pattern for that service call. This is analyzed like a normal graph pattern. Everything visible in the graph pattern is considered to be projected. As far as I can tell, ServiceNodes are not run "as-bound" and their static analysis is as if they were named subqueries (they have no known bound incoming variables other than those communicated by their BindingsClause).

StatementPatternNode

All variables are definitely bound UNLESS StatementPatternNode.isOptional() is true.

Note: we sometimes attach a simple optional join to the parent group for efficiency, at which point it becomes an "optional" statement pattern. An optional statement pattern may also have zero or more FilterNodes associated with it.

JoinGroupNode

UnionNode

The definitely bound variables is the intersection of the definitely bound variables in the child join groups. The maybe bound variables is the union of the maybe bound variables in the child join groups.

AssignmentNode

BIND(expr AS var) in a group will not bind the variable if there is an error when evaluating the value expression and does not fail the solution. Thus BIND() in a group contributes to "maybe" bound variables.

Note: BIND() in a PROJECTION is handled differently as it is non-optional (if the value expression results in an error the solution is dropped). Projections are handled when we do the analysis of a QueryBase node since we can see both the WHERE clause and the PROJECTION clauses at the same time.

See If the evaluation of the expression produces an error, the variable remains unbound for that solution.

IF()

* IF semantics : If evaluating the first argument raises an error, then an error is raised for the evaluation of the IF expression. (This greatly simplifies the analysis of the EBV of the IF value expressions, but there is still uncertainty concerning whether the THEN or the ELSE is executed for a given solution.) However, IF is not allowed to conditionally bind a variable in the THEN/ELSE expressions so we do not have to consider it here.

BOUND(var)

Filters which use BOUND() can not be pruned unless we can prove that the variable is not (or is not) bound and also collapse the filter to a constant after substituting either true or false in for the BOUND() expression.

FILTERs

FILTERs are groups based on whether they can run before any required joins (pre-), with the required join (join-), or after all joins (post-).

pre-

The pre-filters have all their required variables bound on entry to the join group. They should be lifted into the parent join group.

join-

The join-filters will have all their required variables bound by the time the required joins are done. These filters will wind up attached to the appropriate required join. The specific filter/join attachments depend on the join evaluation order.

post-

The post-filters might not have all of their required variables bound. We have to wait until the last of the optionals joins has been evaluated before we can evaluate any post-filters, so they run "last".

prune-

The prune-filters are those whose required variables CAN NOT be bound. They should be pruned from the AST.

TODO We can probably cache the heck out of things on this class. There is no reason to recompute the SA of the know or maybe/must bound variables until there is an AST change, and the caller can build a new SA when that happens. However, note that we must make the cache sets unmodifiable since there are a lot of patterns which rely on computing the difference between two sets and those can not have a side-effect on the cache.

We could also attach the StaticAnalysis as an annotation on the QueryRoot and provide a factory method for accessing it. That way we would have reuse of the cached static analysis data. Each AST optimizer (or the ASTOptimizerList) would have to clear the cached StaticAnalysis when producing a new QueryRoot. Do this when we add an ASTContainer to provide a better home for the queryStr, the parse tree, the original AST, and the optimized AST.

Version:

$Id$

Author:

Bryan Thompson

Field Summary

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

evaluationContext, queryRoot

Constructor Summary

Constructors

Constructor and Description
StaticAnalysis(QueryRoot queryRoot, IEvaluationContext evaluationContext)

Method Summary

Methods

Modifier and Type	Method and Description
static List<IValueExpressionNode>	extractToplevelConjuncts(IValueExpressionNode vexp, List<IValueExpressionNode> nodes) Extracts all AND-connected conjuncts located at the top of a given value expression node (recursively, unless an operator different from AND is encountered).
IQueryNode	findParent(GraphPatternGroup<?> group) Return the parent of the GraphPatternGroup.
static IQueryNode	findParent(QueryRoot queryRoot, GraphPatternGroup<?> group)
static IQueryNode	findParent2(GraphPatternGroup<IGroupMemberNode> aGroup, GraphPatternGroup<?> theGroup) Search in aGroup for theGroup, peeking into QueryBase.getWhereClause(), ServiceNode.getGraphPattern(), and all SubqueryFunctionNodeBase instances for any FilterNodes.
JoinGroupNode	findParentJoinGroup(GraphPatternGroup<?> group) Find and return the parent JoinGroupNode which is the lowest such JoinGroupNode dominating the given GraphPatternGroup.
static INeedsMaterialization.Requirement	gatherVarsToMaterialize(BOp c, Set<IVariable<IV>> terms) Static helper used to determine materialization requirements.
static INeedsMaterialization.Requirement	gatherVarsToMaterialize(BOp c, Set<IVariable<IV>> terms, boolean includeVarsInAnnotations) Static helper used to determine materialization requirements.
static INeedsMaterialization.Requirement	gatherVarsToMaterialize(BOp c, Set<IVariable<IV>> terms, Map<IVariable<?>,IValueExpression<?>> varMap) Static helper used to determine materialization requirements.
static INeedsMaterialization.Requirement	gatherVarsToMaterialize(BOp c, Set<IVariable<IV>> terms, Map<IVariable<?>,IValueExpression<?>> varMap, boolean includeVarsInAnnotations) Static helper used to determine materialization requirements.
Set<IVariable<?>>	getAfterVars(IGroupMemberNode node, Set<IVariable<?>> vars) Return any variables which are used after the given node in the current ordering of its parent JoinGroupNode but DOES NOT consider the parent or the PROJECTION for the query in which this group appears.
Set<IVariable<?>>	getDefinitelyIncomingBindings(IGroupMemberNode node, Set<IVariable<?>> vars) Return the set of variables which MUST be bound coming into this group during top-down, left-to-right evaluation.
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.
Set<IVariable<?>>	getDefinitelyProducedBindings(QueryBase queryBase) Report "MUST" bound bindings projected by the query.
Set<IVariable<?>>	getDefinitelyProducedBindings(ServiceNode node) Report "MUST" bound bindings projected by the SERVICE.
Set<IVariable<?>>	getDefinitelyProducedBindingsAndFilterVariables(IGroupNode<? extends IGroupMemberNode> group, Set<IVariable<?>> vars) Collect all variables appearing in the group.
List<FilterNode>	getJoinFilters(JoinGroupNode group) Return only the filter child nodes in this group whose variables were not fully bound on entry into the join group but which will be fully bound no later than once we have run the required joins in this group.
Set<IVariable<?>>	getJoinVars(BindingsClause bc, ISolutionSetStats stats, Set<IVariable<?>> vars) Return the join variables for a VALUES clause (embedded only - not top-level).
Set<IVariable<?>>	getJoinVars(NamedSubqueryInclude nsi, String solutionSet, Set<IVariable<?>> vars) Return the join variables for an INCLUDE of a pre-existing named solution set.
Set<IVariable<?>>	getJoinVars(NamedSubqueryRoot aNamedSubquery, NamedSubqueryInclude anInclude, Set<IVariable<?>> vars) Identify the join variables for the specified INCLUDE for the position within the query in which it appears.
Set<IVariable<?>>	getJoinVars(ServiceNode serviceNode, Set<IVariable<?>> vars) Return the join variables for a SERVICE.
Set<IVariable<?>>	getJoinVars(SubqueryRoot subquery, Set<IVariable<?>> vars) Identify the join variables for the specified subquery for the position within the query in which it appears.
Set<IVariable<?>>	getMaybeIncomingBindings(IGroupMemberNode node, Set<IVariable<?>> vars) Return the set of variables which MIGHT be bound coming into this group during top-down, left-to-right evaluation.
Set<IVariable<?>>	getMaybeProducedBindings(IBindingProducerNode node, Set<IVariable<?>> vars, boolean recursive) Return the set of variables which MUST or MIGHT be bound after the evaluation of this join group.
Set<IVariable<?>>	getMaybeProducedBindings(QueryBase node) Report the "MUST" and "MAYBE" bound bindings projected by the query.
Set<IVariable<?>>	getMaybeProducedBindings(ServiceNode node) Report the "MUST" and "MAYBE" bound variables projected by the service.
List<FilterNode>	getPostFilters(JoinGroupNode group) Return only the filter child nodes in this group that will not be fully bound even after running the required joins in this group.
List<FilterNode>	getPreFilters(JoinGroupNode group) Return only the filter child nodes in this group that will be fully bound before running any of the joins in this group.
Set<IVariable<?>>	getProjectedVars(IGroupMemberNode proxy, GraphPatternGroup<?> groupToLift, QueryBase query, Set<IVariable<?>> exogenousVars, Set<IVariable<?>> projectedVars) Return the set of variables which must be projected if the group is to be converted into a sub-query.
List<FilterNode>	getPruneFilters(JoinGroupNode group) Deprecated. This is now handled by ASTBottomUpOptimizer. I think that we will not need this method (it is only invoked from the test suite at this point).
Set<IVariable<?>>	getVarsInBindingSet(List<IBindingSet> bss) Extract the set of variables contained in a binding set.
static boolean	isAggregate(ProjectionNode projection, GroupByNode groupBy, HavingNode having) Return true if any of the ProjectionNode, GroupByNode, or HavingNode indicate that this is an aggregation query.
static boolean	isAggregate(QueryBase query) Return true if any of the ProjectionNode, GroupByNode, or HavingNode indicate that this is an aggregation query.
static boolean	isCNF(FilterNode filter) Checks whether the filter node's value expression node is in CNF.
static boolean	isCNF(IValueExpressionNode vexpr) Checks whether the given value expression node is in CNF.
static boolean	isCNFDisjunct(FunctionNode functionNode) Check if filter node is an inner disjunct within a CNF.
static boolean	isCNFNegationOrTerminal(FunctionNode functionNode) Check if filter node is a negation (possibly recursive) or terminal within a CNF.
static boolean	isMinus(BOp node) Checks whether a given node is a MINUS node.
static boolean	isMinusOrOptional(BOp node) Checks whether a given node is a MINUS or OPTIONAL node.
static boolean	isOptional(BOp node) Checks whether a given node is an OPTIONAL node.
boolean	locatedInGroupNode(GroupNodeBase<?> theGroup, IGroupMemberNode theNode) Returns true if the current node is identical or (recursively) located inside the given group scope or is the group node itself, but not a subquery referenced in the node.
boolean	locatedInToplevelQuery(IGroupMemberNode node) Returns true if the current node is located (recursively) inside the top-level query, false if it is nested inside a subquery or a named subquery.
static IValueExpressionNode	pushDisjuncts(IValueExpressionNode vexp) Recursively pushes logical ORs below logical ANDs in the operator tree, such that in the returned node all OR expressions are situated below AND expressions.
static IValueExpressionNode	pushNegations(IValueExpressionNode vexp) Recursively pushes negations down the operator tree, such that in the returned node, negations are always at the bottom of the tree.
static boolean	requiresMaterialization(IConstraint c) Use the INeedsMaterialization interface to find and collect variables that need to be materialized for this constraint.
NamedSubqueryRoot	resolveNamedSubqueryInclude(NamedSubqueryInclude nsi, StaticAnalysis sa) Resolves the NamedSubqueryInclude in the given context, returning the associated NamedSubqueryRoot object.
static IValueExpressionNode	toCNF(IValueExpressionNode vexpr) Returns the corresponding (equivalent) value expression in CNF.
static IValueExpressionNode	toConjunctiveValueExpression(List<IValueExpressionNode> conjuncts) Constructs an (unbalanced) tree out of the list of conjuncts.

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

canJoin, canJoinUsingConstraints, getJoinGraphConstraints

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

public StaticAnalysis(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.

See Also:

(StaticAnalysis#getDefinitelyBound() ignores exogenous variables.)

Method Detail

findParentJoinGroup

public JoinGroupNode findParentJoinGroup(GraphPatternGroup<?> group)

Find and return the parent JoinGroupNode which is the lowest such JoinGroupNode dominating the given GraphPatternGroup. This will search the tree to locate the parent when the GraphPatternGroup appears as the annotation of a QueryBase, ServiceNode, or a FilterNode having a ExistsNode or NotExistsNode.

Parameters:

group - The given group.

Returns:

The lowest dominating JoinGroupNode above that group.

findParent

public IQueryNode findParent(GraphPatternGroup<?> group)

Return the parent of the GraphPatternGroup. When the group has an explicit parent reference, that reference is returned immediately. Otherwise the QueryRoot is searched for a node having the given group as an annotation. This makes it possible to locate a QueryBase, ServiceNode, ExistsNode, or NotExistsNode given its GraphPatternGroup.

Note: The parent of a SubqueryRoot is obtained by SubqueryBase.getParent() and is simply the JoinGroupNode in which the SubqueryRoot appears.

Parameters:

group - The group.

Returns:

The parent of that group. This can be any of GraphPatternGroup, QueryBase, ServiceNode , or a FilterNode. This will be null iff the group does not appear anywhere in the QueryRoot. TODO The parent of a NamedSubqueryRoot is less well defined. A NamedSubqueryRoot may be included in multiple positions within the AST. Each of those could be considered a parent of the NamedSubqueryRoot in the sense that it provides a context within which the result of the query may be included. However, for the purposes of bottom up analysis, there is no parent of a NamedSubqueryRoot. It runs as if it were a top-level query (except that it might not have visibility into exogenous variables?).

findParent

public static IQueryNode findParent(QueryRoot queryRoot,
                    GraphPatternGroup<?> group)

findParent2

public static IQueryNode findParent2(GraphPatternGroup<IGroupMemberNode> aGroup,
                     GraphPatternGroup<?> theGroup)

Search in aGroup for theGroup, peeking into QueryBase.getWhereClause(), ServiceNode.getGraphPattern(), and all SubqueryFunctionNodeBase instances for any FilterNodes.

Parameters:

aGroup - A group which might be the "parent" of the group you are looking for.

theGroup - The group which you are looking for.

Returns:

The QueryBase, ServiceNode, or FilterNode which is the "parent" of theGroup.

getDefinitelyIncomingBindings

public Set<IVariable<?>> getDefinitelyIncomingBindings(IGroupMemberNode node,
                                              Set<IVariable<?>> vars)

Return the set of variables which MUST be bound coming into this group during top-down, left-to-right evaluation. The returned set is based on a non-recursive analysis of the definitely (MUST) bound variables in each of the parent groups. The analysis is non-recursive for each parent group, but all parents of this group are considered. This approach excludes information about variables which MUST or MIGHT be bound from both this group and child groups.

This method DOES NOT pay attention to bottom up variable scoping rules. Queries which are badly designed MUST be rewritten (by lifting out named subqueries) such that they become well designed and adhere to bottom-up evaluation semantics.

Parameters:

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

Returns:

The argument. FIXME Both this and getMaybeIncomingBindings(IGroupMemberNode, Set) need to consider the exogenous variables. Perhaps modify the StaticAnalysis constructor to pass in the exogenous IBindingSet[]? FIXME For some purposes we need to consider the top-down, left-to-right evaluation order. However, for others, such as when considering whether a variable appearing in a filter will be in scope, we need to consider whether there exists some evaluation order for which the variable would be in scope.

See Also:

(StaticAnalysis#getDefinitelyBound() ignores exogenous variables.)

locatedInToplevelQuery

public boolean locatedInToplevelQuery(IGroupMemberNode node)

Returns true if the current node is located (recursively) inside the top-level query, false if it is nested inside a subquery or a named subquery. The method does not look into FilterNodes, but only recurses into GroupNodeBase nodes.

Parameters:

node -

Returns:

locatedInGroupNode

public boolean locatedInGroupNode(GroupNodeBase<?> theGroup,
                         IGroupMemberNode theNode)

Returns true if the current node is identical or (recursively) located inside the given group scope or is the group node itself, but not a subquery referenced in the node. The method does not look into FilterNodes, but only recurses into GroupNodeBase nodes.

Parameters:

theNode - the group we're looking in

theNode - the node we're looking for

Returns:

getMaybeIncomingBindings

public Set<IVariable<?>> getMaybeIncomingBindings(IGroupMemberNode node,
                                         Set<IVariable<?>> vars)

Return the set of variables which MIGHT be bound coming into this group during top-down, left-to-right evaluation. The returned set is based on a non-recursive analysis of the "maybe" bound variables in each of the parent groups. The analysis is non-recursive for each parent group, but all parents of this group are considered. This approach excludes information about variables which MUST or MIGHT be bound from both this group and child groups.

This method DOES NOT pay attention to bottom up variable scoping rules. Queries which are badly designed MUST be rewritten (by lifting out named subqueries) such that they become well designed and adhere to bottom-up evaluation semantics.

Parameters:

vars - Where to store the "maybe" bound variables. This includes ANY variable which MIGHT or MUST be bound.

Returns:

The argument. FIXME Both this and getDefinitelyIncomingBindings(IGroupMemberNode, Set) need to consider the exogenous variables. Perhaps modify the StaticAnalysis constructor to pass in the exogenous IBindingSet[]? FIXME This is unable to look upwards when the group is the graph pattern of a subquery, a service, or a (NOT) EXISTS filter.

See Also:

https://sourceforge.net/apps/trac/bigdata/ticket/412

getDefinitelyProducedBindings

public 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.

Specified by:

getDefinitelyProducedBindings in class StaticAnalysis_CanJoin

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.

getDefinitelyProducedBindingsAndFilterVariables

public Set<IVariable<?>> getDefinitelyProducedBindingsAndFilterVariables(IGroupNode<? extends IGroupMemberNode> group,
                                                                Set<IVariable<?>> vars)

Collect all variables appearing in the group. This DOES NOT descend recursively into groups. It DOES report variables projected out of named subqueries, SPARQL 1.1 subqueries, and SERVICE calls.

This has the same behavior as a non-recursive call obtain the definitely bound variables PLUS the variables used by the filters in the group.

Parameters:

vars - The variables are added to this set.

group - The group whose variables will be reported.

includeFilters - When true, variables appearing in FILTERs are also reported.

Returns:

The caller's set.

getMaybeProducedBindings

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

Return the set of variables which MUST or MIGHT be bound after the evaluation of this join group.

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

Parameters:

vars - Where to store the "MUST" and "MIGHT" be bound variables.

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

Returns:

The caller's set.

getDefinitelyProducedBindings

public Set<IVariable<?>> getDefinitelyProducedBindings(QueryBase queryBase)

Report "MUST" bound bindings projected by the query. This involves checking the WHERE clause and the ProjectionNode for the query. Note that the projection can rename variables. It can also bind a constant on a variable. Variables which are not projected by the query will NOT be reported. FIXME For a top-level query, any exogenously bound variables are also definitely bound (in a subquery they are definitely bound if they are projected into the subquery). TODO In the case when the variable is bound to an expression and the expression may execute with an error, this method incorrectly reports that variable as definitely bound see trac 750

See Also:

(StaticAnalysis#getDefinitelyBound() ignores exogenous variables.), (StaticAnalysis does not follow renames of projected variables), artificial test case fails, currently wontfix

getMaybeProducedBindings

public Set<IVariable<?>> getMaybeProducedBindings(QueryBase node)

Report the "MUST" and "MAYBE" bound bindings projected by the query. This reduces to reporting the projected variables. We do not need to analyze the whereClause or projection any further in order to know what "might" be projected.

getDefinitelyProducedBindings

public Set<IVariable<?>> getDefinitelyProducedBindings(ServiceNode node)

Report "MUST" bound bindings projected by the SERVICE. This involves checking the graph pattern reported by ServiceNode.getGraphPattern().

Note: If the SERVICE URI is a variable, then it can only become bound through some other operation. If the SERVICE variable never becomes bound, then the SERVICE call can not run.

getMaybeProducedBindings

public Set<IVariable<?>> getMaybeProducedBindings(ServiceNode node)

Report the "MUST" and "MAYBE" bound variables projected by the service. This involves checking the graph pattern reported by ServiceNode.getGraphPattern(). A SERVICE does NOT have an explicit PROJECTION so it can not rename the projected bindings.

getPreFilters

public List<FilterNode> getPreFilters(JoinGroupNode group)

Return only the filter child nodes in this group that will be fully bound before running any of the joins in this group.

Note: Anything returned by this method should be lifted into the parent group since it can be run before this group is evaluated. By lifting the pre-filters into the parent group we can avoid issuing as many as-bound subqueries for this group since those which fail the filter will not be issued.

Parameters:

group - The JoinGroupNode.

Returns:

The filters which should either be run before the non-optional join graph or (preferably) lifted into the parent group.

See Also:

ASTLiftPreFiltersOptimizer

getJoinFilters

public List<FilterNode> getJoinFilters(JoinGroupNode group)

Return only the filter child nodes in this group whose variables were not fully bound on entry into the join group but which will be fully bound no later than once we have run the required joins in this group.

Parameters:

group - The JoinGroupNode.

Returns:

The filters to be attached to the non-optional join graph for this group.

getPostFilters

public List<FilterNode> getPostFilters(JoinGroupNode group)

Return only the filter child nodes in this group that will not be fully bound even after running the required joins in this group.

Note: It is possible that some of these filters will be fully bound due to nested optionals and unions.

Note: This will report any filters which are not pre-filters and are not-join filters, including filters which are prune-filters. An AST optimizer is responsible for identifying and removing filters which should be pruned. Until they have been pruned, they will continue to be reported by this method.

Parameters:

group - The JoinGroupNode.

Returns:

The filters to be run last in the group (after the nested optionals and unions).

getPruneFilters

public List<FilterNode> getPruneFilters(JoinGroupNode group)

Deprecated. This is now handled by ASTBottomUpOptimizer. I think that we will not need this method (it is only invoked from the test suite at this point).

Return any filters can not succeed based on the "incoming", "must" and "may" bound variables for this group. These filters are candidates for pruning.

Note: Filters containing a FunctionNode for FunctionRegistry.BOUND MUST NOT be pruned and are NOT reported by this method.

Parameters:

group - The JoinGroupNode.

Returns:

The filters which are known to fail. TODO It is possible to prune a BOUND(?x) or NOT BOUND(?x) filter through a more detailed analysis of the value expression. If the variable ?x simply does not appear in the group or any child of that group, then BOUND(?x) can be replaced by false and NOT BOUND(?x) by true.

However, in order to do this we must also look at any exogenous solution(s) (those supplied with the query when it is being evaluated). If the variable is bound in some exogenous solutions then it could be bound when the FILTER is run and the filter can not be pruned.

requiresMaterialization

public static boolean requiresMaterialization(IConstraint c)

Use the INeedsMaterialization interface to find and collect variables that need to be materialized for this constraint.

gatherVarsToMaterialize

public static INeedsMaterialization.Requirement gatherVarsToMaterialize(BOp c,
                                                        Set<IVariable<IV>> terms)

Static helper used to determine materialization requirements.

gatherVarsToMaterialize

public static INeedsMaterialization.Requirement gatherVarsToMaterialize(BOp c,
                                                        Set<IVariable<IV>> terms,
                                                        Map<IVariable<?>,IValueExpression<?>> varMap)

Static helper used to determine materialization requirements.

gatherVarsToMaterialize

public static INeedsMaterialization.Requirement gatherVarsToMaterialize(BOp c,
                                                        Set<IVariable<IV>> terms,
                                                        boolean includeVarsInAnnotations)

Static helper used to determine materialization requirements.

gatherVarsToMaterialize

public static INeedsMaterialization.Requirement gatherVarsToMaterialize(BOp c,
                                                        Set<IVariable<IV>> terms,
                                                        Map<IVariable<?>,IValueExpression<?>> varMap,
                                                        boolean includeVarsInAnnotations)

Static helper used to determine materialization requirements. TODO This should also reason about datatype constraints on variables. If we know that a variable is constrained in a given scope to only take on a data type which is associated with an FullyInlineTypedLiteralIV or a specific numeric data type, then some operators may be able to operate directly on that IV. This is especially interesting for aggregates.

getJoinVars

public Set<IVariable<?>> getJoinVars(NamedSubqueryRoot aNamedSubquery,
                            NamedSubqueryInclude anInclude,
                            Set<IVariable<?>> vars)

Identify the join variables for the specified INCLUDE for the position within the query in which it appears.

Parameters:

aNamedSubquery - The named subquery.

anInclude - An include for that subquery.

getJoinVars

public Set<IVariable<?>> getJoinVars(SubqueryRoot subquery,
                            Set<IVariable<?>> vars)

Identify the join variables for the specified subquery for the position within the query in which it appears.

Parameters:

aSubquery - The subquery.

vars -

Returns:

The join variables.

getJoinVars

public Set<IVariable<?>> getJoinVars(ServiceNode serviceNode,
                            Set<IVariable<?>> vars)

Return the join variables for a SERVICE.

Parameters:

serviceNode -

vars -

Returns:

getJoinVars

public Set<IVariable<?>> getJoinVars(BindingsClause bc,
                            ISolutionSetStats stats,
                            Set<IVariable<?>> vars)

Return the join variables for a VALUES clause (embedded only - not top-level).

Parameters:

bc - The VALUES clause (a bunch of solutions)

stats - A static analysis of those solutions.

vars -

Returns:

getJoinVars

public Set<IVariable<?>> getJoinVars(NamedSubqueryInclude nsi,
                            String solutionSet,
                            Set<IVariable<?>> vars)

Return the join variables for an INCLUDE of a pre-existing named solution set.

Parameters:

nsi - The NamedSubqueryInclude

solutionSet - The name of a pre-existing solution set.

vars - The caller's collection.

Returns:

The caller's collection.

getAfterVars

public Set<IVariable<?>> getAfterVars(IGroupMemberNode node,
                             Set<IVariable<?>> vars)

Return any variables which are used after the given node in the current ordering of its parent JoinGroupNode but DOES NOT consider the parent or the PROJECTION for the query in which this group appears.

Parameters:

node - A node which is a direct child of some JoinGroupNode.

vars - Where to store the variables.

Returns:

The caller's set.

Throws:

IllegalArgumentException - if the node is not the direct child of some JoinGroupNode.

getProjectedVars

public Set<IVariable<?>> getProjectedVars(IGroupMemberNode proxy,
                                 GraphPatternGroup<?> groupToLift,
                                 QueryBase query,
                                 Set<IVariable<?>> exogenousVars,
                                 Set<IVariable<?>> projectedVars)

Return the set of variables which must be projected if the group is to be converted into a sub-query. This method identifies variables which are either MUST or MIGHT bound outside of the group which are also used within the group and includes them in the projection. It also identified variables used after the group (in the current evaluation order) which are also used within the group and include them in the projection.

When considering the projection of the (sub-)query in which the group appears, the SELECT EXPRESSIONS are consulted to identify variables which we need to project out of the group.

Parameters:

proxy - The join group which will be replaced by a sub-query. This is used to decide which variables are known bound (and hence should be projected into the WHERE clause if they are used within that WHERE clause). It is also used to decide which variables which become bound in the WHERE clause will be used outside of its scope and hence must be projected out of the WHERE clause. (The parent of this proxy MUST be a JoinGroupNode, not a UnionNode and not null. This condition is readily satisified if the rewrite is considering the children of some join group node as the parent of the proxy will be that join group node.)

groupToLift - The group which is being lifted out and whose projection will be computed.

query - The query (or sub-query) in which that proxy node exists. This is used to identify anything which is PROJECTed out of the query.

exogenousVars - Any variables which are bound outside of the query AND known to be in scope (exogenous variables in a sub-select are only in scope if they are projected into the sub-select).

projectedVars - The variables which must be projected will be added to this collection.

Returns:

The projection. TODO We should recognize conditions under which this can be made into a DISTINCT projection. This involves a somewhat tricky analysis of the context in which each projected variable is used. There is *substantial* benefit to be gained from this analysis as a DISTINCT projection can radically reduce the size of the intermediate solution sets and the work performed by the overall query. However, if the analysis is incorrect and we mark the PROJECTION as DISTINCT when that is not allowed by the semantics of the query, then the query will not have the same behavior. So, getting this analysis correct is very important.

isAggregate

public static boolean isAggregate(QueryBase query)

Return true if any of the ProjectionNode, GroupByNode, or HavingNode indicate that this is an aggregation query.

Parameters:

query - The query.

Returns:

trueif it is an aggregation query.

isAggregate

public static boolean isAggregate(ProjectionNode projection,
                  GroupByNode groupBy,
                  HavingNode having)

Return true if any of the ProjectionNode, GroupByNode, or HavingNode indicate that this is an aggregation query. All arguments are optional.

getVarsInBindingSet

public Set<IVariable<?>> getVarsInBindingSet(List<IBindingSet> bss)

Extract the set of variables contained in a binding set.

Parameters:

bss -

Returns:

isCNF

public static boolean isCNF(FilterNode filter)

Checks whether the filter node's value expression node is in CNF.

isCNF

public static boolean isCNF(IValueExpressionNode vexpr)

Checks whether the given value expression node is in CNF.

Parameters:

vexpr -

isCNFDisjunct

public static boolean isCNFDisjunct(FunctionNode functionNode)

Check if filter node is an inner disjunct within a CNF. In particular, it must not contain any other conjunctive nodes.

Parameters:

functionNode -

Returns:

isCNFNegationOrTerminal

public static boolean isCNFNegationOrTerminal(FunctionNode functionNode)

Check if filter node is a negation (possibly recursive) or terminal within a CNF. In particular, it must not contain any other disjuncts or conjuncts.

Parameters:

functionNode -

toCNF

public static IValueExpressionNode toCNF(IValueExpressionNode vexpr)

Returns the corresponding (equivalent) value expression in CNF. Makes a copy of the original value expression, leaving it unmodified.

Parameters:

vexpr -

Returns:

null if the value expression is already in CNF, an equivalent value expression in CNF otherwise

pushNegations

public static IValueExpressionNode pushNegations(IValueExpressionNode vexp)

Recursively pushes negations down the operator tree, such that in the returned node, negations are always at the bottom of the tree. In particular, all AND and OR value expressions will be situated above negations. The resulting IValueExpressionNode is logically equivalent.

pushDisjuncts

public static IValueExpressionNode pushDisjuncts(IValueExpressionNode vexp)

Recursively pushes logical ORs below logical ANDs in the operator tree, such that in the returned node all OR expressions are situated below AND expressions. Expectes that all NOT expressions have been pushed down to the bottom already (otherwise, the behavior is undertermined). The resulting IValueExpressionNode is logically equivalent.

extractToplevelConjuncts

public static List<IValueExpressionNode> extractToplevelConjuncts(IValueExpressionNode vexp,
                                                  List<IValueExpressionNode> nodes)

Extracts all AND-connected conjuncts located at the top of a given value expression node (recursively, unless an operator different from AND is encountered).

Parameters:

vexpNode - the value expression node

nodes - set where to store the top level conjuncts in

Returns:

the array of filters

toConjunctiveValueExpression

public static IValueExpressionNode toConjunctiveValueExpression(List<IValueExpressionNode> conjuncts)

Constructs an (unbalanced) tree out of the list of conjuncts. If the conjuncts that are passed in are null or empty, null is returned.

Parameters:

conjuncts -

Returns:

resolveNamedSubqueryInclude

public NamedSubqueryRoot resolveNamedSubqueryInclude(NamedSubqueryInclude nsi,
                                            StaticAnalysis sa)

Resolves the NamedSubqueryInclude in the given context, returning the associated NamedSubqueryRoot object. Returns null if resolval fails.

isOptional

public static boolean isOptional(BOp node)

Checks whether a given node is an OPTIONAL node.

isMinus

public static boolean isMinus(BOp node)

Checks whether a given node is a MINUS node.

isMinusOrOptional

public static boolean isMinusOrOptional(BOp node)

Checks whether a given node is a MINUS or OPTIONAL node.