Menu
▾
▴
[Bigdata-commit] SF.net SVN: bigdata:[7604] branches/MINUS_REFACTOR
|
From: <jer...@us...> - 2013-12-03 21:27:36
|
Revision: 7604
http://bigdata.svn.sourceforge.net/bigdata/?rev=7604&view=rev
Author: jeremy_carroll
Date: 2013-12-03 21:27:25 +0000 (Tue, 03 Dec 2013)
Log Message:
-----------
Renamed JoinType NotExists as Minus, to reflect actual use, and patched up implementation of BOpContext.bind().
Added about a dozen tests for MINUS and fixed issues in various optimizers related to these tests.
Added some lifting of badly formed MINUS groups into subqueries.
Provided inline style for Data Driven SPARQL Test Cases.
Added new Optimizer for MINUS { {} UNION {} }
Substantial refactoring of StaticAnalysis using a strategy pattern to eliminate code duplication.
Modified Paths:
--------------
branches/MINUS_REFACTOR/bigdata/src/java/com/bigdata/bop/BOpContext.java
branches/MINUS_REFACTOR/bigdata/src/java/com/bigdata/bop/join/HTreeHashJoinUtility.java
branches/MINUS_REFACTOR/bigdata/src/java/com/bigdata/bop/join/HashJoinOp.java
branches/MINUS_REFACTOR/bigdata/src/java/com/bigdata/bop/join/JVMHashJoinUtility.java
branches/MINUS_REFACTOR/bigdata/src/java/com/bigdata/bop/join/JoinTypeEnum.java
branches/MINUS_REFACTOR/bigdata/src/java/com/bigdata/bop/join/SolutionSetHashJoinOp.java
branches/MINUS_REFACTOR/bigdata/src/test/com/bigdata/bop/join/AbstractHashJoinUtilityTestCase.java
branches/MINUS_REFACTOR/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/ArbitraryLengthPathNode.java
branches/MINUS_REFACTOR/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/GroupNodeBase.java
branches/MINUS_REFACTOR/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/IGroupNode.java
branches/MINUS_REFACTOR/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/StaticAnalysis.java
branches/MINUS_REFACTOR/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/eval/AST2BOpUtility.java
branches/MINUS_REFACTOR/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/optimizers/ASTBottomUpOptimizer.java
branches/MINUS_REFACTOR/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/optimizers/ASTEmptyGroupOptimizer.java
branches/MINUS_REFACTOR/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/optimizers/DefaultOptimizerList.java
branches/MINUS_REFACTOR/bigdata-rdf/src/test/com/bigdata/rdf/sparql/ast/eval/AbstractDataDrivenSPARQLTestCase.java
branches/MINUS_REFACTOR/bigdata-rdf/src/test/com/bigdata/rdf/sparql/ast/eval/AbstractInlineSELECTTestCase.java
branches/MINUS_REFACTOR/bigdata-rdf/src/test/com/bigdata/rdf/sparql/ast/eval/TestAll.java
branches/MINUS_REFACTOR/bigdata-rdf/src/test/com/bigdata/rdf/sparql/ast/eval/TestCustomFunction.java
branches/MINUS_REFACTOR/bigdata-rdf/src/test/com/bigdata/rdf/sparql/ast/eval/TestMergeJoin.java
branches/MINUS_REFACTOR/bigdata-rdf/src/test/com/bigdata/rdf/sparql/ast/eval/TestNegation.java
branches/MINUS_REFACTOR/bigdata-rdf/src/test/com/bigdata/rdf/sparql/ast/eval/TestUnionMinus.java
branches/MINUS_REFACTOR/bigdata-rdf/src/test/com/bigdata/rdf/sparql/ast/optimizers/AbstractOptimizerTestCase.java
branches/MINUS_REFACTOR/bigdata-rdf/src/test/com/bigdata/rdf/sparql/ast/optimizers/TestALPPinTrac773.java
branches/MINUS_REFACTOR/bigdata-rdf/src/test/com/bigdata/rdf/sparql/ast/optimizers/TestASTBottomUpOptimizer.java
branches/MINUS_REFACTOR/bigdata-rdf/src/test/com/bigdata/rdf/sparql/ast/optimizers/TestASTEmptyGroupOptimizer.java
Added Paths:
-----------
branches/MINUS_REFACTOR/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/optimizers/ASTFlattenMinusUnionOptimizer.java
Removed Paths:
-------------
branches/MINUS_REFACTOR/bigdata-rdf/src/test/com/bigdata/rdf/sparql/ast/eval/union_minus_01.rq
branches/MINUS_REFACTOR/bigdata-rdf/src/test/com/bigdata/rdf/sparql/ast/eval/union_minus_01.srx
branches/MINUS_REFACTOR/bigdata-rdf/src/test/com/bigdata/rdf/sparql/ast/eval/union_minus_01.trig
branches/MINUS_REFACTOR/bigdata-rdf/src/test/com/bigdata/rdf/sparql/ast/eval/union_minus_02.rq
branches/MINUS_REFACTOR/bigdata-rdf/src/test/com/bigdata/rdf/sparql/ast/eval/union_minus_02.srx
branches/MINUS_REFACTOR/bigdata-rdf/src/test/com/bigdata/rdf/sparql/ast/eval/union_minus_02.trig
Modified: branches/MINUS_REFACTOR/bigdata/src/java/com/bigdata/bop/BOpContext.java
===================================================================
--- branches/MINUS_REFACTOR/bigdata/src/java/com/bigdata/bop/BOpContext.java 2013-12-03 19:53:27 UTC (rev 7603)
+++ branches/MINUS_REFACTOR/bigdata/src/java/com/bigdata/bop/BOpContext.java 2013-12-03 21:27:25 UTC (rev 7604)
@@ -921,12 +921,36 @@
* etc. Note that either <code>left</code> or <code>right</code> MAY
* be returned if the other solution set is empty (optimization).
*/
+ @SuppressWarnings({ "rawtypes" })
+ static public IBindingSet bind(//
+ final IBindingSet left,//
+ final IBindingSet right,//
+ final IConstraint[] constraints, //
+ final IVariable[] varsToKeep
+ ) {
+ return bind(left,right,constraints,varsToKeep, false);
+ }
+ /**
+ * This is like {@link #bind(IBindingSet, IBindingSet, IConstraint[], IVariable[])}
+ * except for the additional argument failIfDisjoint. If this is true,
+ * and left and right have no bound variables in common, then we return null.
+ * This is to implement:
+ * http://www.w3.org/TR/2013/REC-sparql11-query-20130321/#defn_algMinus
+ *
+ * @param left
+ * @param right
+ * @param constraints
+ * @param varsToKeep
+ * @param failIfDisjoint
+ * @return
+ */
@SuppressWarnings({ "rawtypes", "unchecked" })
static public IBindingSet bind(//
final IBindingSet left,//
final IBindingSet right,//
final IConstraint[] constraints, //
- final IVariable[] varsToKeep//
+ final IVariable[] varsToKeep,
+ final boolean failIfDisjoint
) {
if (constraints == null && varsToKeep == null) {
@@ -938,10 +962,10 @@
*/
if (left.isEmpty())
- return right;
+ return failIfDisjoint ? null : right;
if (right.isEmpty())
- return left;
+ return failIfDisjoint ? null : left;
}
@@ -958,6 +982,7 @@
// final IBindingSet dst = leftIsPipeline ? left.clone() : right.clone();
final IBindingSet src = right;
final IBindingSet dst = left.clone();
+ boolean seenNonDisjointVar = false;
// log.error("LEFT :" + left);
// log.error("RIGHT:" + right);
@@ -1002,6 +1027,7 @@
// Propagate the cached Value to the dst.
div.setValue(siv.getValue());
}
+ seenNonDisjointVar = true;
}
} else {
@@ -1016,6 +1042,11 @@
}
+ // check for the MINUS condition
+ if (failIfDisjoint && !seenNonDisjointVar) {
+ return null;
+ }
+
// Test constraint(s)
if (constraints != null && !BOpUtility.isConsistent(constraints, dst)) {
Modified: branches/MINUS_REFACTOR/bigdata/src/java/com/bigdata/bop/join/HTreeHashJoinUtility.java
===================================================================
--- branches/MINUS_REFACTOR/bigdata/src/java/com/bigdata/bop/join/HTreeHashJoinUtility.java 2013-12-03 19:53:27 UTC (rev 7603)
+++ branches/MINUS_REFACTOR/bigdata/src/java/com/bigdata/bop/join/HTreeHashJoinUtility.java 2013-12-03 21:27:25 UTC (rev 7604)
@@ -576,7 +576,7 @@
switch (joinType) {
case Optional:
case Exists:
- case NotExists:
+ case Minus:
// The join set is used to handle optionals.
joinSet.set(HTree.create(store, getIndexMetadata(op)));
break;
@@ -1067,7 +1067,7 @@
switch (joinType) {
case Optional:
case Exists:
- case NotExists:
+ case Minus:
joined = new LinkedList<BS2>();
break;
default:
@@ -1116,7 +1116,7 @@
final IBindingSet outSolution = BOpContext
.bind(leftSolution, rightSolution,
constraints,
- selectVars);
+ selectVars, joinType == JoinTypeEnum.Minus);
nJoinsConsidered.increment();
@@ -1206,7 +1206,7 @@
}
break;
}
- case NotExists: {
+ case Minus: {
/*
* The right solution is output iff there
* does not exist any left solution which
Modified: branches/MINUS_REFACTOR/bigdata/src/java/com/bigdata/bop/join/HashJoinOp.java
===================================================================
--- branches/MINUS_REFACTOR/bigdata/src/java/com/bigdata/bop/join/HashJoinOp.java 2013-12-03 19:53:27 UTC (rev 7603)
+++ branches/MINUS_REFACTOR/bigdata/src/java/com/bigdata/bop/join/HashJoinOp.java 2013-12-03 21:27:25 UTC (rev 7604)
@@ -394,7 +394,7 @@
*/
break;
case Optional:
- case NotExists: {
+ case Minus: {
/*
* Output the optional solutions.
*/
Modified: branches/MINUS_REFACTOR/bigdata/src/java/com/bigdata/bop/join/JVMHashJoinUtility.java
===================================================================
--- branches/MINUS_REFACTOR/bigdata/src/java/com/bigdata/bop/join/JVMHashJoinUtility.java 2013-12-03 19:53:27 UTC (rev 7603)
+++ branches/MINUS_REFACTOR/bigdata/src/java/com/bigdata/bop/join/JVMHashJoinUtility.java 2013-12-03 21:27:25 UTC (rev 7604)
@@ -257,7 +257,7 @@
indexSolutionsHavingUnboundJoinVars = false;
break;
case Optional: // OPTIONAL join.
- case NotExists: // NOT EXISTS and MINUS
+ case Minus: // MINUS
case Filter: // SELECT DISTINCT
indexSolutionsHavingUnboundJoinVars = true;
break;
@@ -587,7 +587,8 @@
right.solution,//
left,//
constraints,//
- selectVars//
+ selectVars, //
+ joinType == JoinTypeEnum.Minus //
);
switch(joinType) {
@@ -625,7 +626,7 @@
}
break;
}
- case NotExists: {
+ case Minus: {
/*
* The right solution is output iff there does not exist
* any left solution which joins with that right
Modified: branches/MINUS_REFACTOR/bigdata/src/java/com/bigdata/bop/join/JoinTypeEnum.java
===================================================================
--- branches/MINUS_REFACTOR/bigdata/src/java/com/bigdata/bop/join/JoinTypeEnum.java 2013-12-03 19:53:27 UTC (rev 7603)
+++ branches/MINUS_REFACTOR/bigdata/src/java/com/bigdata/bop/join/JoinTypeEnum.java 2013-12-03 21:27:25 UTC (rev 7604)
@@ -59,14 +59,14 @@
*/
Exists,
/**
- * A join where the left solution is output iff there is no right solution
- * which joins with that left solution. This basically an optional join
- * where the solutions which join are not output.
- * <p>
- * Note: This is also used for "MINUS" since the only difference between
- * "NotExists" and "MINUS" deals with the scope of the variables.
+ * A join implementing the SPARQL Minus operator: where the left solution is output iff
+ * every right solution either does not join with that left solution or has no
+ * bound variables in common with the left solution.
+ *
+ * This basically is an optional join where the solutions which join are not output,
+ * modified by the SPARQL rule concerning no variables in common.
*/
- NotExists,
+ Minus,
/**
* A distinct filter (not a join). Only the distinct left solutions are
* output. Various annotations pertaining to JOIN processing are ignored
Modified: branches/MINUS_REFACTOR/bigdata/src/java/com/bigdata/bop/join/SolutionSetHashJoinOp.java
===================================================================
--- branches/MINUS_REFACTOR/bigdata/src/java/com/bigdata/bop/join/SolutionSetHashJoinOp.java 2013-12-03 19:53:27 UTC (rev 7603)
+++ branches/MINUS_REFACTOR/bigdata/src/java/com/bigdata/bop/join/SolutionSetHashJoinOp.java 2013-12-03 21:27:25 UTC (rev 7604)
@@ -350,7 +350,7 @@
*/
break;
case Optional:
- case NotExists: {
+ case Minus: {
/*
* Output the optional solutions.
*/
Modified: branches/MINUS_REFACTOR/bigdata/src/test/com/bigdata/bop/join/AbstractHashJoinUtilityTestCase.java
===================================================================
--- branches/MINUS_REFACTOR/bigdata/src/test/com/bigdata/bop/join/AbstractHashJoinUtilityTestCase.java 2013-12-03 19:53:27 UTC (rev 7603)
+++ branches/MINUS_REFACTOR/bigdata/src/test/com/bigdata/bop/join/AbstractHashJoinUtilityTestCase.java 2013-12-03 21:27:25 UTC (rev 7604)
@@ -617,7 +617,7 @@
case Normal:
break;
case Optional:
- case NotExists:
+ case Minus:
// Output the optional solutions.
state.outputOptionals(outputBuffer);
break;
@@ -1942,7 +1942,7 @@
),//
};
- doHashJoinTest(JoinTypeEnum.NotExists, joinVars, selectVars,
+ doHashJoinTest(JoinTypeEnum.Minus, joinVars, selectVars,
constraints, left, right, expected);
}
Modified: branches/MINUS_REFACTOR/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/ArbitraryLengthPathNode.java
===================================================================
--- branches/MINUS_REFACTOR/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/ArbitraryLengthPathNode.java 2013-12-03 19:53:27 UTC (rev 7603)
+++ branches/MINUS_REFACTOR/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/ArbitraryLengthPathNode.java 2013-12-03 21:27:25 UTC (rev 7604)
@@ -258,7 +258,7 @@
zeroMatchAdjustment = Long.MAX_VALUE / 2;
// The following is more accurate, but more expensive and unnecessary.
// db.getURICount() + db.getBNodeCount();
- System.err.println("adj: "+zeroMatchAdjustment);
+ //System.err.println("adj: "+zeroMatchAdjustment);
break;
}
}
Modified: branches/MINUS_REFACTOR/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/GroupNodeBase.java
===================================================================
--- branches/MINUS_REFACTOR/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/GroupNodeBase.java 2013-12-03 19:53:27 UTC (rev 7603)
+++ branches/MINUS_REFACTOR/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/GroupNodeBase.java 2013-12-03 21:27:25 UTC (rev 7604)
@@ -361,7 +361,7 @@
*/
@SuppressWarnings("unchecked")
@Override
- public int replaceWith(final BOp oldChild, final BOp newChild) {
+ public int replaceWith(final E oldChild, final E newChild) {
final int i = super.replaceWith(oldChild, newChild);
Modified: branches/MINUS_REFACTOR/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/IGroupNode.java
===================================================================
--- branches/MINUS_REFACTOR/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/IGroupNode.java 2013-12-03 19:53:27 UTC (rev 7603)
+++ branches/MINUS_REFACTOR/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/IGroupNode.java 2013-12-03 21:27:25 UTC (rev 7604)
@@ -33,6 +33,18 @@
*/
int size();
+ /**
+ * Replace a child of a node with another reference (destructive
+ * modification). All arguments which point to the oldChild will be replaced
+ * by references to the newChild.
+ *
+ * @param oldChild
+ * @param newChild
+ *
+ * @return The #of references which were replaced.
+ */
+ int replaceWith(E old, E replacement);
+
// /**
// * Return whether or not this is an optional group. Optional groups may or
// * may not produce variable bindings, but will not prune incoming solutions
Modified: branches/MINUS_REFACTOR/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/StaticAnalysis.java
===================================================================
--- branches/MINUS_REFACTOR/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/StaticAnalysis.java 2013-12-03 19:53:27 UTC (rev 7603)
+++ branches/MINUS_REFACTOR/bigdata-rdf/src/java/com/bigdata/rdf/sparql/ast/StaticAnalysis.java 2013-12-03 21:27:25 UTC (rev 7604)
@@ -28,6 +28,7 @@
package com.bigdata.rdf.sparql.ast;
import java.util.Collection;
+import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.LinkedList;
@@ -58,9 +59,9 @@
import com.bigdata.rdf.sparql.ast.ssets.ISolutionSetManager;
/**
- * Methods for static analysis of a query. There is one method which looks "up".
+ * Methods for static analysis of a query. Some of the methods look "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
+ * query plan). Other methods look "down". This corresponds to the
* bottom-up evaluation semantics of SPARQL.
* <p>
* When determining the "known" bound variables on entry to a node we have to
@@ -199,7 +200,637 @@
* @version $Id$
*/
public class StaticAnalysis extends StaticAnalysis_CanJoin {
+
+ /**
+ * The various methods forming the API for StaticAnalysis, can be executed in somewhat different fashion
+ * as to whether we are looking for MUST or MAYBE bindings,
+ * and as to whether we want a recursive analysis or just one level.
+ *
+ * This abstract class and its subclasses follow the strategy pattern,
+ * with the subclasses determining MUST or MAYBE, and recursive or not: giving four concrete subclasses.
+ *
+ * Since all five classes are private (to StaticAnalysis) we can use the scope of the member methods
+ * to indicate intent: private methods are used within the defining class only, non-final methods
+ * are redefined in at least one subclasses, public methods are used by methods from within StaticAnalysis and
+ * hence exposed through the API, protected methods are used in at least one subclass.
+ *
+ * For any one API call to StaticAnalysis, at least one new instance of GetBindings is used.
+ *
+ *
+ * @author jeremycarroll
+ *
+ */
+
+ private abstract class GetBindings {
+ /**
+ * The results of the API call being evaluated.
+ */
+ final Set<IVariable<?>> results;
+
+ /** An instance of GetBindings which shares the result set and is either {@link GetRecursiveMaybeBindings} or
+ * {@link GetRecursiveDefiniteBindings}
+ * It is assigned once, lazily:
+ *
+ */
+ private GetBindings recursive;
+ private GetBindings(Set<IVariable<?>> vars) {
+ this.results = vars != null ? vars : new LinkedHashSet<IVariable<?>>();
+ }
+
+ public final Set<IVariable<?>> getIncomingBindings(IGroupMemberNode node) {
+ /*
+ * Start by adding the exogenous variables.
+ */
+ getIncomingExognousBindings();
+
+ final GraphPatternGroup<?> parent = node.getParentGraphPatternGroup();
+
+ /*
+ * We've reached the root.
+ */
+ if (parent == null) {
+
+ /*
+ * FIXME This is unable to look upwards when the group is the graph
+ * pattern of a subquery, a service, or a (NOT) EXISTS filter. Unit
+ * tests. This could be fixed using a method which searched the
+ * QueryRoot for the node having a given join group as its
+ * annotation. However, that would not resolve the question of
+ * evaluation order versus "in scope" visibility.
+ *
+ * Use findParent(...) to fix this, but build up the test coverage
+ * before making the code changes.
+ */
+ return results;
+
+ }
+
+ getIncomingSiblingBindings(node);
+
+ /*
+ * Next we recurse upwards to figure out what is definitely bound
+ * coming into the parent.
+ */
+ return getIncomingBindings(parent);
+ }
+
+ public final Set<IVariable<?>> getIncomingSiblingBindings(IGroupMemberNode node) {
+ final GraphPatternGroup<?> parent = node.getParentGraphPatternGroup();
+ /*
+ * Do the siblings of the node first. Unless it is a Union. Siblings
+ * don't see each other's bindings in a Union.
+ */
+ if (!(parent instanceof UnionNode)) {
+
+ for (IGroupMemberNode child : parent) {
+
+ /*
+ * We've found ourself. Stop collecting vars.
+ */
+ if (child == node) {
+ break;
+ }
+
+ if (child instanceof IBindingProducerNode) {
+ if (includeBindings(child)) {
+ recursive().getProducedBindings( (IBindingProducerNode) child);
+ }
+ }
+ }
+ }
+ return results;
+
+ }
+
+ public final Set<IVariable<?>> getProducedBindings(IBindingProducerNode node) {
+ if (node instanceof GraphPatternGroup<?>) {
+
+ if (node instanceof JoinGroupNode) {
+
+ getProducedBindings((JoinGroupNode) node);
+
+ } else if (node instanceof UnionNode) {
+
+ getProducedBindings((UnionNode) node);
+
+ } else {
+ throw new AssertionError(node.toString());
+ }
+
+ } else if(node instanceof StatementPatternNode) {
+
+ final StatementPatternNode sp = (StatementPatternNode) node;
+
+ results.addAll(sp.getProducedBindings());
+
+ } else if (node instanceof ArbitraryLengthPathNode) {
+
+ results.addAll(((ArbitraryLengthPathNode) node).getProducedBindings());
+
+ } else if (node instanceof ZeroLengthPathNode) {
+
+ results.addAll(((ZeroLengthPathNode) node).getProducedBindings());
+
+ } else if(node instanceof SubqueryRoot) {
+
+ final SubqueryRoot subquery = (SubqueryRoot) node;
+
+ getProducedBindings(subquery);
+
+ } else if (node instanceof NamedSubqueryInclude) {
+
+ final NamedSubqueryInclude nsi = (NamedSubqueryInclude) node;
+
+ final String name = nsi.getName();
+
+ final NamedSubqueryRoot nsr = getNamedSubqueryRoot(name);
+
+ if (nsr != null) {
+
+ getProducedBindings(nsr);
+
+ } else {
+
+ final ISolutionSetStats stats = getSolutionSetStats(name);
+
+ getProducedBindings(stats);
+
+ }
+
+ } else if(node instanceof ServiceNode) {
+
+ getProducedBindings((ServiceNode) node);
+
+ } else if(node instanceof AssignmentNode) {
+
+ getProducedBindings((AssignmentNode)node);
+
+ } else if(node instanceof FilterNode) {
+
+ // NOP.
+
+ } else {
+
+ throw new AssertionError(node.toString());
+
+ }
+
+ return results;
+
+ }
+
+ public final Set<IVariable<?>> getProducedBindings(ServiceNode node) {
+ final GraphPatternGroup<IGroupMemberNode> graphPattern =
+ (GraphPatternGroup<IGroupMemberNode>) node.getGraphPattern();
+
+ if (graphPattern != null) {
+
+ recursive().getProducedBindings(graphPattern);
+
+ }
+ return results;
+
+ }
+
+ protected void getProducedBindings(UnionNode node) {
+ // not recursive - nothing
+ }
+
+ final Set<IVariable<?>> getProducedBindings(JoinGroupNode node) {
+
+ // Note: always report what is bound when we enter a group. The caller
+ // needs to avoid entering a group which is optional if they do not want
+ // it's bindings.
+// if(node.isOptional())
+// return vars;
+
+ for (IGroupMemberNode child : node) {
+
+ if(!(child instanceof IBindingProducerNode))
+ continue;
+
+ if (!includeBindings(child))
+ continue;
+
+ IBindingProducerNode bpn = (IBindingProducerNode)child;
+
+ // if the child is itself a JoinGroupNode and we are non-recusive, we are not interested
+ if (skipRecursiveJoinGroup(bpn))
+ continue;
+
+
+ // otherwise get the bindings
+
+ getProducedBindings(bpn);
+ }
+ return results;
+ }
+ /**
+ * Return true if the child is a join group that the algorithm should skip
+ * when analyzing a parent join group. This method is overriden in the
+ * subclasses implementing recursive algorithms.
+ * @param bpn
+ * @return
+ */
+ protected boolean skipRecursiveJoinGroup(IBindingProducerNode bpn) {
+ return bpn instanceof JoinGroupNode;
+ }
+
+ public abstract Set<IVariable<?>> getProducedBindings(QueryBase nsr) ;
+
+ protected abstract void getProducedBindings(AssignmentNode node) ;
+
+ protected abstract void getProducedBindings(ISolutionSetStats stats) ;
+
+ GetBindings recursive() {
+ if (recursive==null) {
+ recursive = constructRecursive();
+ }
+ return recursive;
+ }
+
+ protected abstract GetBindings constructRecursive();
+
+ protected abstract boolean includeBindings(IGroupMemberNode child);
+
+ protected final boolean isMinus(IGroupMemberNode child) {
+ return child instanceof IJoinNode
+ && ((IJoinNode) child).isMinus();
+ }
+
+ private void getIncomingExognousBindings() {
+ if (evaluationContext != null) {
+ getProducedBindings(evaluationContext.getSolutionSetStats());
+ }
+ }
+
+ }
+ private class GetDefiniteBindings extends GetBindings {
+
+ private GetDefiniteBindings(Set<IVariable<?>> vars) {
+ super(vars);
+ }
+ @Override
+ protected boolean includeBindings(IGroupMemberNode child) {
+ return !(isMinus(child)||isOptional(child));
+ }
+ private boolean isOptional(IGroupMemberNode child) {
+ return child instanceof IJoinNode && ((IJoinNode) child).isOptional();
+ }
+ @Override
+ protected GetBindings constructRecursive() {
+ return new GetRecursiveDefiniteBindings(results);
+ }
+
+
+ @Override
+ protected void getProducedBindings(AssignmentNode node) {
+
+ /*
+ * Note: BIND() in a group is only a "maybe" because the spec says
+ * that an error when evaluating a BIND() in a group will not fail
+ * the solution.
+ *
+ * @see http://www.w3.org/TR/sparql11-query/#assignment (
+ * "If the evaluation of the expression produces an error, the
+ * variable remains unbound for that solution.")
+ */
+ }
+
+
+
+ @Override
+ protected void getProducedBindings(ISolutionSetStats stats) {
+ /*
+ * Note: This is all variables which are bound in ALL solutions.
+ */
+
+ results.addAll(stats.getAlwaysBound());
+ }
+ /**
+ * Report "MUST" bound bindings projected by the query. This involves
+ * checking the WHERE clause and the {@link 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
+ * @return
+ *
+ *
+ * @see http://sourceforge.net/apps/trac/bigdata/ticket/430 (StaticAnalysis
+ * does not follow renames of projected variables)
+ *
+ * @see http://sourceforge.net/apps/trac/bigdata/ticket/750
+ * artificial test case fails, currently wontfix
+ */
+ @Override
+ public Set<IVariable<?>> getProducedBindings(QueryBase queryBase) {
+ final ProjectionNode projection = queryBase.getProjection();
+
+ if(projection == null) {
+
+ // If there is no projection then there is nothing to report.
+ return results;
+
+ }
+
+
+ // The set of definitely bound variables in the query.
+ final Set<IVariable<?>> definitelyBound;
+ @SuppressWarnings("unchecked")
+ final GraphPatternGroup<IGroupMemberNode> whereClause = queryBase.getWhereClause();
+
+
+
+ if (whereClause != null) {
+ definitelyBound = getDefiniteRecursive(null).getProducedBindings(whereClause);
+
+ if (log.isInfoEnabled()) {
+ log.info(whereClause);
+ log.info(definitelyBound);
+ }
+
+ } else {
+
+ definitelyBound = Collections.EMPTY_SET;
+ }
+
+ /*
+ * Now, we need to consider each select expression in turn. There are
+ * several cases:
+ *
+ * 1. Projection of a constant.
+ *
+ * 2. Projection of a variable under the same name.
+ *
+ * 3. Projection of a variable under a different name.
+ *
+ * 4. Projection of a select expression which is not an aggregate.
+ *
+ * This case is the one explored in trac750, and the code
+ * below while usually correct is incorrect if the expression
+ * can evaluate with an error - in which case the variable
+ * will remain unbound.
+ *
+ * 5. Projection of a select expression which is an aggregate. This case
+ * is tricky. A select expression that is an aggregate which evaluates
+ * to an error will cause an unbound value for to be reported for the
+ * projected variable for the solution in which the error is computed.
+ * Therefore, we must not assume that aggregation expressions MUST be
+ * bound. (Given the schema flexible nature of RDF data, it is very
+ * difficult to prove that an aggregate expression will never result in
+ * an error without actually running the aggregation query. COUNT seems
+ * OK, )
+ *
+ * 6. Projection of an exogenously bound variable which is in scope.
+ *
+ * TODO (6) is not yet handled! We need to know what variables are in
+ * scope at each level as we descend into subqueries. Even if we know
+ * the set of exogenous variables, the in scope exogenous varaibles are
+ * not available in the typical invocation context.
+ */
+ {
+
+ final boolean isAggregate = isAggregate(queryBase);
+
+
+ for (AssignmentNode bind : projection) {
+
+ if (isBoundProjection(bind, definitelyBound, isAggregate)) {
+ IVariable<IV> var = bind.getVar();
+ results.add(var);
+ definitelyBound.add(var);
+ }
+
+ }
+
+ }
+
+ return results;
+
+ }
+ private boolean isBoundProjection(AssignmentNode bind, final Set<IVariable<?>> definitelyBound,
+ final boolean isAggregate) {
+ if (bind.getValueExpression() instanceof IConstant<?>) {
+
+ /*
+ * 1. The projection of a constant.
+ *
+ * Note: This depends on pre-evaluation of constant
+ * expressions. If the expression has not been reduced to a
+ * constant then it will not be detected by this test!
+ */
+ return true;
+
+ }
+
+ if (bind.getValueExpression() instanceof IVariable<?>) {
+
+ /*
+ * 2. The projection of a definitely bound variable
+ * under the same name.
+ *
+ * OR
+ *
+ * 3. The projection of a definitely bound variable
+ * under a different name.
+ */
+
+ return definitelyBound.contains(bind.getValueExpression());
+ }
+
+ if (!isAggregate) {
+
+ /*
+ * 4. The projection of a select expression which is not an
+ * aggregate. Normally, the projected variable will be
+ * bound if all components of the select expression are
+ * definitely bound: this comment ignores the possibility
+ * that the expression may raise an error, in which case
+ * this block of code is incorrect.
+ * As of Oct 11, 2013 - we are no-fixing this
+ * because of caution about the performance impact,
+ * and it seeming to be a corner case. See trac 750.
+ *
+ * TODO Does coalesce() change the semantics for this
+ * analysis? If any of the values for coalesce() is
+ * definitely bound, then the coalesce() will produce a
+ * value. Can coalesce() be used to propagate an unbound
+ * value? If so, then we must either not assume that any
+ * value expression involving coalesce() is definitely bound
+ * or we must do a more detailed analysis of the value
+ * expression.
+ */
+ final Set<IVariable<?>> usedVars = getSpannedVariables(
+ (BOp) bind.getValueExpression(),
+ new LinkedHashSet<IVariable<?>>());
+
+ usedVars.removeAll(definitelyBound);
+ /*
+ * If all variables used by the select expression are
+ * definitely bound so the projected variable for that
+ * select expression will be definitely bound.
+ */
+
+ return !usedVars.isEmpty();
+
+ }
+ /* 5. Projection of a select expression which is an aggregate.
+ * We dubiously do nothing:
+ * - COUNT always gives a value
+ * ... MIN MAX SAMPLE are only errors if there are no solutions
+ * ... GROUP_CONCAT SUM and AVG may have type errors which perhaps
+ * could be excluded by static analysis
+ */
+
+ /* 6. Projection of an exogenously bound variable which is in scope.
+ * We incorrectly do nothing
+ */
+ return false;
+ }
+
+ }
+ class GetMaybeBindings extends GetBindings {
+
+ public GetMaybeBindings(Set<IVariable<?>> vars) {
+ super(vars);
+ }
+ @Override
+ protected boolean includeBindings(IGroupMemberNode child) {
+ return !isMinus(child);
+ }
+ @Override
+ protected GetBindings constructRecursive() {
+ return new GetRecursiveMaybeBindings(results);
+ }
+ @Override
+ protected void getProducedBindings(AssignmentNode node) {
+ results.add(((AssignmentNode) node).getVar());
+ }
+ @Override
+ protected void getProducedBindings(ISolutionSetStats stats) {
+
+ /*
+ * Note: This is all variables bound in ANY solution. It MAY
+ * include variables which are NOT bound in some solutions.
+ */
+
+ results.addAll(stats.getUsedVars());
+ }
+
+ /**
+ * 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.
+ * @return
+ */
+ @Override
+ public Set<IVariable<?>> getProducedBindings(QueryBase node) {
+
+ final ProjectionNode projection = node.getProjection();
+
+ if(projection != null) {
+ projection.getProjectionVars(results);
+ }
+ return results;
+
+ }
+ }
+ private class GetRecursiveDefiniteBindings extends GetDefiniteBindings {
+
+ private GetRecursiveDefiniteBindings(Set<IVariable<?>> vars) {
+ super(vars);
+ }
+ @Override
+ protected GetBindings constructRecursive() {
+ return this;
+ }
+ @Override
+ protected void getProducedBindings(UnionNode node) {
+
+
+ final Set<IVariable<?>> perChildSets[] = new Set[node.arity()];
+ int i = 0;
+
+ for (JoinGroupNode child : node) {
+ perChildSets[i++] = getDefiniteRecursive(null).getProducedBindings(child);
+ }
+
+ results.addAll(intersection(perChildSets));
+
+ }
+
+ @Override
+ protected boolean skipRecursiveJoinGroup(IBindingProducerNode bpn) {
+ return false;
+ }
+ }
+ private class GetRecursiveMaybeBindings extends GetMaybeBindings {
+
+ public GetRecursiveMaybeBindings(Set<IVariable<?>> vars) {
+ super(vars);
+ }
+ @Override
+ protected GetBindings constructRecursive() {
+ return this;
+ }
+ @Override
+ protected void getProducedBindings(UnionNode node) {
+
+ /*
+ * Collect all "maybe" bindings from each of the children.
+ */
+ for (JoinGroupNode child : node) {
+
+ getProducedBindings(child);
+
+ }
+ }
+ @Override
+ protected boolean skipRecursiveJoinGroup(IBindingProducerNode bpn) {
+ return false;
+ }
+
+ }
+
+ private GetBindings get(boolean definite, boolean recursive, Set<IVariable<?>> vars) {
+ if (definite) {
+ if (recursive) {
+ return new GetRecursiveDefiniteBindings(vars);
+ } else {
+ return new GetDefiniteBindings(vars);
+ }
+ } else {
+ if (recursive) {
+ return new GetRecursiveMaybeBindings(vars);
+ } else {
+ return new GetMaybeBindings(vars);
+ }
+ }
+ }
+ private GetBindings getDefinite(boolean recursive, Set<IVariable<?>> vars) {
+ return get(true, recursive, vars);
+ }
+ private GetBindings getDefiniteRecursive(Set<IVariable<?>> vars) {
+ return get(true, true, vars);
+ }
+ private GetBindings getMaybe(boolean recursive, Set<IVariable<?>> vars) {
+ return get(false, recursive, vars);
+ }
+ private GetBindings getMaybeRecursive(Set<IVariable<?>> vars) {
+ return get(false, true, vars);
+ }
+
private static final Logger log = Logger.getLogger(StaticAnalysis.class);
/**
@@ -232,8 +863,6 @@
* {@link ISolutionSetStats} and the {@link ISolutionSetManager} for
* named solution sets.
*
- * @see https://sourceforge.net/apps/trac/bigdata/ticket/412
- * (StaticAnalysis#getDefinitelyBound() ignores exogenous variables.)
*/
public StaticAnalysis(final QueryRoot queryRoot,
final IEvaluationContext evaluationContext) {
@@ -559,6 +1188,33 @@
//
// }
+ /*
+ *
+
+ Main interface methods - these have the words
+ Definitely or Maybe
+ and
+ Produced or Incoming
+
+ The first indicates the difference between variables that are known to be bound
+ versus those that might be bound, e.g. because of an optional, or an expression
+ that might fail in a BIND.
+
+ The second indices a distinction between a declarative semantics typically bottom-up,
+ or the procedural left-to-right top-down evaluation
+
+ For the former (definitely or maybe), many of the methods are fairly similar in which
+ case a third parameterized form is used. The result is somewhat ugly code
+ where:
+ - if the implementations for 'definitely' and for 'maybe' are sufficiently similar then
+ both methods delegate to a third parameterized method
+ - if, on the other hand, the implementations for 'definitely' and for 'maybe' are
+ sufficiently different, then the two methods are written explicitly and the
+ third parameterized method delegates to them.
+
+
+ *
+ */
/**
* 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
@@ -578,11 +1234,6 @@
*
* @return The argument.
*
- * FIXME Both this and
- * {@link #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
@@ -590,88 +1241,10 @@
* scope, we need to consider whether there exists some evaluation
* order for which the variable would be in scope.
*
- * @see https://sourceforge.net/apps/trac/bigdata/ticket/412
- * (StaticAnalysis#getDefinitelyBound() ignores exogenous variables.)
*/
public Set<IVariable<?>> getDefinitelyIncomingBindings(
final IGroupMemberNode node, final Set<IVariable<?>> vars) {
-
- /*
- * Start by adding the exogenous variables.
- */
- if (evaluationContext != null) {
-
- final ISolutionSetStats stats = evaluationContext.getSolutionSetStats();
-
- // only add the vars that are always bound
- vars.addAll(stats.getAlwaysBound());
-
- }
-
- final GraphPatternGroup<?> parent = node.getParentGraphPatternGroup();
-
- /*
- * We've reached the root.
- */
- if (parent == null) {
-
- /*
- * FIXME This is unable to look upwards when the group is the graph
- * pattern of a subquery, a service, or a (NOT) EXISTS filter. Unit
- * tests. This could be fixed using a method which searched the
- * QueryRoot for the node having a given join group as its
- * annotation. However, that would not resolve the question of
- * evaluation order versus "in scope" visibility.
- *
- * Use findParent(...) to fix this, but build up the test coverage
- * before making the code changes.
- */
- return vars;
-
- }
-
- /*
- * Do the siblings of the node first. Unless it is a Union. Siblings
- * don't see each other's bindings in a Union.
- */
- if (!(parent instanceof UnionNode)) {
-
- for (IGroupMemberNode child : parent) {
-
- /*
- * We've found ourself. Stop collecting vars.
- */
- if (child == node) {
-
- break;
-
- }
-
- if (child instanceof IBindingProducerNode) {
-
- final boolean optional = child instanceof IJoinNode
- && ((IJoinNode) child).isOptional();
-
- final boolean minus = child instanceof IJoinNode
- && ((IJoinNode) child).isMinus();
-
- if (!optional && !minus) {
- getDefinitelyProducedBindings(
- (IBindingProducerNode) child, vars, true/* recursive */);
- }
-
- }
-
- }
-
- }
-
- /*
- * Next we recurse upwards to figure out what is definitely bound
- * coming into the parent.
- */
- return getDefinitelyIncomingBindings(parent, vars);
-
+ return getDefiniteRecursive(vars).getIncomingBindings(node);
}
/**
@@ -694,94 +1267,27 @@
*
* @return The argument.
*
- * FIXME Both this and
- * {@link #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 https://sourceforge.net/apps/trac/bigdata/ticket/412
*/
public Set<IVariable<?>> getMaybeIncomingBindings(
final IGroupMemberNode node, final Set<IVariable<?>> vars) {
-
- /*
- * Start by adding the exogenous variables.
- */
- if (evaluationContext != null) {
-
- final ISolutionSetStats stats = evaluationContext.getSolutionSetStats();
-
- // add the vars that are always bound
- vars.addAll(stats.getAlwaysBound());
-
- // also add the vars that might be bound
- vars.addAll(stats.getNotAlwaysBound());
-
- }
-
- final GraphPatternGroup<?> parent = node.getParentGraphPatternGroup();
+ return getMaybeRecursive(vars).getIncomingBindings(node);
- /*
- * We've reached the root.
- */
- if (parent == null) {
-
- return vars;
-
- }
+ }
- /*
- * Do the siblings of the node first. Unless it is a Union. Siblings
- * don't see each other's bindings in a Union.
- */
- if (!(parent instanceof UnionNode)) {
-
- for (IGroupMemberNode child : parent) {
-
- /*
- * We've found ourself. Stop collecting vars.
- */
- if (child == node) {
-
- break;
-
- }
-
- if (child instanceof IBindingProducerNode) {
-
-// final boolean optional = child instanceof IJoinNode
-// && ((IJoinNode) child).isOptional();
- final boolean minus = child instanceof IJoinNode
- && ((IJoinNode) child).isMinus();
+ public Set<IVariable<?>> getMaybeIncomingSiblingBindings(final IGroupMemberNode node,
+ final Set<IVariable<?>> vars) {
+ return getMaybeRecursive(vars).getIncomingSiblingBindings(node);
+ }
- if (/* !optional && */!minus) {
- /*
- * MINUS does not produce any bindings, it just removes
- * solutions. On the other hand, OPTIONAL joins DO
- * produce bindings, they are just "maybe" bindings.
- */
- getMaybeProducedBindings(
- (IBindingProducerNode) child, vars, true/* recursive */);
- }
-
- }
-
- }
-
- }
-
- /*
- * Next we recurse upwards to figure out what is definitely bound
- * coming into the parent.
- */
- return getMaybeIncomingBindings(parent, vars);
-
- }
+ public Set<IVariable<?>> getDefinitelyIncomingSiblingBindings(final IGroupMemberNode node,
+ final Set<IVariable<?>> vars) {
+ return getDefiniteRecursive(vars).getIncomingSiblingBindings(node);
+ }
/**
* Return the set of variables which MUST be bound for solutions after the
@@ -817,101 +1323,32 @@
final IBindingProducerNode node, final Set<IVariable<?>> vars,
final boolean recursive) {
- if (node instanceof GraphPatternGroup<?>) {
-
- if (node instanceof JoinGroupNode) {
-
- getDefinitelyProducedBindings((JoinGroupNode) node, vars,
- recursive);
-
- } else if (node instanceof UnionNode) {
-
- getDefinitelyProducedBindings((UnionNode) node, vars, recursive);
-
- } else {
-
- throw new AssertionError(node.toString());
-
- }
+ return this.getDefinite(recursive, vars).getProducedBindings(node);
+
+ }
+ /**
+ * Return the set of variables which MUST or MIGHT be bound after the
+ * evaluation of this join group.
+ * <p>
+ * The returned collection reflects "bottom-up" evaluation semantics. This
+ * method does NOT consider variables which are already bound on entry to
+ * the group.
+ *
+ * @param vars
+ * Where to store the "MUST" and "MIGHT" be bound variables.
+ * @param recursive
+ * When <code>true</code>, the child groups will be recursively
+ * analyzed. When <code>false</code>, only <i>this</i> group will
+ * be analyzed.
+ *
+ * @return The caller's set.
+ */
+ public Set<IVariable<?>> getMaybeProducedBindings(
+ final IBindingProducerNode node,//
+ final Set<IVariable<?>> vars,//
+ final boolean recursive) {
+ return this.getMaybe(recursive, vars).getProducedBindings(node);
- } else if(node instanceof StatementPatternNode) {
-
- final StatementPatternNode sp = (StatementPatternNode) node;
-
-// if(!sp.isOptional()) {
-//
-// // Only if the statement pattern node is a required join.
- vars.addAll(sp.getProducedBindings());
-//
-// }
-
- } else if (node instanceof ArbitraryLengthPathNode) {
-
- vars.addAll(((ArbitraryLengthPathNode) node).getProducedBindings());
-
- } else if (node instanceof ZeroLengthPathNode) {
-
- vars.addAll(((ZeroLengthPathNode) node).getProducedBindings());
-
- } else if(node instanceof SubqueryRoot) {
-
- final SubqueryRoot subquery = (SubqueryRoot) node;
-
- vars.addAll(getDefinitelyProducedBindings(subquery));
-
- } else if (node instanceof NamedSubqueryInclude) {
-
- final NamedSubqueryInclude nsi = (NamedSubqueryInclude) node;
-
- final String name = nsi.getName();
-
- final NamedSubqueryRoot nsr = getNamedSubqueryRoot(name);
-
- if (nsr != null) {
-
- vars.addAll(getDefinitelyProducedBindings(nsr));
-
- } else {
-
- final ISolutionSetStats stats = getSolutionSetStats(name);
-
- /*
- * Note: This is all variables which are bound in ALL solutions.
- */
-
- vars.addAll(stats.getAlwaysBound());
-
- }
-
- } else if(node instanceof ServiceNode) {
-
- final ServiceNode service = (ServiceNode) node;
-
- vars.addAll(getDefinitelyProducedBindings(service));
-
- } else if(node instanceof AssignmentNode) {
-
- /*
- * Note: BIND() in a group is only a "maybe" because the spec says
- * that an error when evaluating a BIND() in a group will not fail
- * the solution.
- *
- * @see http://www.w3.org/TR/sparql11-query/#assignment (
- * "If the evaluation of the expression produces an error, the
- * variable remains unbound for that solution.")
- */
-
- } else if(node instanceof FilterNode) {
-
- // NOP.
-
- } else {
-
- throw new AssertionError(node.toString());
-
- }
-
- return vars;
}
@@ -953,363 +1390,31 @@
}
+
+
+
/**
- * Return the set of variables which MUST or MIGHT be bound after the
- * evaluation of this join group.
- * <p>
- * The returned collection reflects "bottom-up" evaluation semantics. This
- * method does NOT consider variables which are already bound on entry to
- * the group.
- *
- * @param vars
- * Where to store the "MUST" and "MIGHT" be bound variables.
- * @param recursive
- * When <code>true</code>, the child groups will be recursively
- * analyzed. When <code>false</code>, only <i>this</i> group will
- * be analyzed.
- *
- * @return The caller's set.
+ * Report "MUST" bound bindings projected by the SERVICE. This involves
+ * checking the graph pattern reported by
+ * {@link ServiceNode#getGraphPattern()} .
*/
- public Set<IVariable<?>> getMaybeProducedBindings(
- final IBindingProducerNode node,//
- final Set<IVariable<?>> vars,//
- final boolean recursive) {
+ // MUST : ServiceNode
+ public Set<IVariable<?>> getDefinitelyProducedBindings(final ServiceNode node) {
+ return getDefiniteRecursive(null).getProducedBindings(node);
- if (node instanceof GraphPatternGroup<?>) {
-
- if (node instanceof JoinGroupNode) {
-
- getMaybeProducedBindings((JoinGroupNode) node, vars,
- recursive);
-
- } else if (node instanceof UnionNode) {
-
- getMaybeProducedBindings((UnionNode) node, vars, recursive);
-
- } else {
-
- throw new AssertionError(node.toString());
-
- }
-
- } else if( node instanceof StatementPatternNode) {
-
- final StatementPatternNode sp = (StatementPatternNode) node;
-
-// if(sp.isOptional()) {
-//
-// // Only if the statement pattern node is an optional join.
- vars.addAll(sp.getProducedBindings());
-//
-// }
-
- } else if (node instanceof ArbitraryLengthPathNode) {
-
- vars.addAll(((ArbitraryLengthPathNode) node).getProducedBindings());
-
- } else if (node instanceof ZeroLengthPathNode) {
-
- vars.addAll(((ZeroLengthPathNode) node).getProducedBindings());
-
- } else if(node instanceof SubqueryRoot) {
-
- final SubqueryRoot subquery = (SubqueryRoot) node;
-
- vars.addAll(getMaybeProducedBindings(subquery));
-
- } else if (node instanceof NamedSubqueryInclude) {
-
- final NamedSubqueryInclude nsi = (NamedSubqueryInclude) node;
-
- final String name = nsi.getName();
-
- final NamedSubqueryRoot nsr = getNamedSubqueryRoot(name);
-
- if (nsr != null) {
-
- vars.addAll(getMaybeProducedBindings(nsr));
-
- } else {
-
- final ISolutionSetStats stats = getSolutionSetStats(name);
-
- /*
- * Note: This is all variables bound in ANY solution. It MAY
- * include variables which are NOT bound in some solutions.
- */
-
- vars.addAll(stats.getUsedVars());
-
- }
-
- } else if(node instanceof ServiceNode) {
-
- final ServiceNode service = (ServiceNode) node;
-
- vars.addAll(getMaybeProducedBindings(service));
-
- } else if(node instanceof AssignmentNode) {
-
- /*
- * Note: BIND() in a group is only a "maybe" because the spec says
- * that an error when evaluating a BIND() in a group will not fail
- * the solution.
- *
- * @see http://www.w3.org/TR/sparql11-query/#assignment (
- * "If the evaluation of the expression produces an error, the
- * variable remains unbound for that solution.")
- */
-
- vars.add(((AssignmentNode) node).getVar());
-
- } else if(node instanceof FilterNode) {
-
- // NOP
-
- } else {
-
- throw new AssertionError(node.toString());
-
- }
-
- return vars;
-
}
- /*
- * Private type specific helper methods.
+ /**
+ * Report the "MUST" and "MAYBE" bound variables projected by the service.
+ * This involves checking the graph pattern reported by
+ * {@link ServiceNode#getGraphPattern()}. A SERVICE does NOT have an
+ * explicit PROJECTION so it can not rename the projected bindings.
*/
+ // MAY : ServiceNode
+ public Set<IVariable<?>> getMaybeProducedBindings(final ServiceNode node) {
+ return getMaybeRecursive(null).getProducedBindings(node);
- // MUST : JOIN GROUP
- private Set<IVariable<?>> getDefinitelyProducedBindings(
- final JoinGroupNode node, final Set<IVariable<?>> vars,
- final boolean recursive) {
- // Note: always report what is bound when we enter a group. The caller
- // needs to avoid entering a group which is optional if they do not want
- // it's bindings.
-// if(node.isOptional())
-// return vars;
-
- for (IGroupMemberNode child : node) {
-
- if(!(child instanceof IBindingProducerNode))
- continue;
-
- if (child instanceof StatementPatternNode) {
-
- final StatementPatternNode sp = (StatementPatternNode) child;
-
- if (!sp.isOptional()) {
-
- /*
- * Required JOIN (statement pattern).
- */
-
- getDefinitelyProducedBindings(sp, vars, recursive);
-
- }
-
- } else if (child instanceof ArbitraryLengthPathNode) {
-
- vars.addAll(((ArbitraryLengthPathNode) child).getProducedBindings());
-
- } else if (child instanceof ZeroLengthPathNode) {
-
- vars.addAll(((ZeroLengthPathNode) child).getProducedBindings());
-
- } else if (child instanceof NamedSubqueryInclude
- || child instanceof SubqueryRoot
- || child instanceof ServiceNode) {
-
- /*
- * Required JOIN (Named solution set, SPARQL 1.1 subquery,
- * EXISTS, or SERVICE).
- *
- * Note: We have to descend recursively into these structures in
- * order to determine anything.
- */
-
- vars.addAll(getDefinitelyProducedBindings(
- (IBindingProducerNode) child,
- new LinkedHashSet<IVariable<?>>(), true/* recursive */));
-
- } else if (child instanceof GraphPatternGroup<?>) {
-
- if (recursive) {
-
- // Add anything bound by a child group.
-
- final GraphPatternGroup<?> group = (GraphPatternGroup<?>) child;
-
- if (!group.isOptional() && !group.isMinus()) {
-
- getDefinitelyProducedBindings(group, vars, recursive);
-
- }
-
- }
-
- } else if (child instanceof AssignmentNode) {
-
- /*
- * Note: BIND() in a group is only a "maybe" because the spec says
- * that an error when evaluating a BIND() in a group will not fail
- * the solution.
- *
- * @see http://www.w3.org/TR/sparql11-query/#assignment (
- * "If the evaluation of the expression produces an error, the
- * variable remains...
[truncated message content] |
