You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@jena.apache.org by an...@apache.org on 2020/03/02 16:52:38 UTC
[jena] branch master updated: JENA-1843,
JENA-1844: Fixes for OpAsQuery
This is an automated email from the ASF dual-hosted git repository.
andy pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/jena.git
The following commit(s) were added to refs/heads/master by this push:
new 1934159 JENA-1843, JENA-1844: Fixes for OpAsQuery
new e76bb09 Merge pull request #701 from afs/op-as-query
1934159 is described below
commit 1934159d40d07362bb6ee756cc736c9d6dd658a0
Author: Andy Seaborne <an...@apache.org>
AuthorDate: Thu Feb 27 11:02:02 2020 +0000
JENA-1843, JENA-1844: Fixes for OpAsQuery
---
.../org/apache/jena/sparql/algebra/OpAsQuery.java | 223 ++++++++++++---------
.../apache/jena/sparql/algebra/TestOpAsQuery.java | 39 +++-
2 files changed, 168 insertions(+), 94 deletions(-)
diff --git a/jena-arq/src/main/java/org/apache/jena/sparql/algebra/OpAsQuery.java b/jena-arq/src/main/java/org/apache/jena/sparql/algebra/OpAsQuery.java
index 71e12ef..3ef23a2 100644
--- a/jena-arq/src/main/java/org/apache/jena/sparql/algebra/OpAsQuery.java
+++ b/jena-arq/src/main/java/org/apache/jena/sparql/algebra/OpAsQuery.java
@@ -41,10 +41,7 @@ import org.apache.jena.sparql.expr.* ;
import org.apache.jena.sparql.expr.aggregate.Aggregator ;
import org.apache.jena.sparql.pfunction.PropFuncArg ;
import org.apache.jena.sparql.syntax.* ;
-import org.apache.jena.sparql.syntax.syntaxtransform.ElementTransform ;
-import org.apache.jena.sparql.syntax.syntaxtransform.ElementTransformCleanGroupsOfOne ;
-import org.apache.jena.sparql.syntax.syntaxtransform.ElementTransformer ;
-import org.apache.jena.sparql.syntax.syntaxtransform.ExprTransformApplyElementTransform ;
+import org.apache.jena.sparql.syntax.syntaxtransform.*;
import org.apache.jena.sparql.util.graph.GraphList ;
import org.apache.jena.vocabulary.RDF ;
@@ -55,29 +52,33 @@ import org.apache.jena.vocabulary.RDF ;
* The contract is to return an "equivalent query" - generates the same answers -
* to the original query that generated the algebra.
* That may be the same query (the code aims for this, assuming the original query
- * didn't have additonal, unnecessary {}),
+ * didn't have additional, unnecessary {}),
* different queries with the same alegra forms,
* or different equivalent queries - same answers, different algebra -
* usually where extra {} are added in and not easiely cleaned out.
* <p>
- * Some attempt is made to handle algrebra expressions with operators from the optimizer.
+ * Some attempt is made to handle algebra expressions with operators from the optimizer.
* <p>
* It is possible to build algrebra expressions directly for which there is no SPARQL query
* that generates that algebra. This code may produce an equivalent query but that is
- * not gauranteed.
+ * not guaranteed.
*/
public class OpAsQuery {
- // Query cleaning is done in fixupGroupsOfOne by applying an ElementTransform.
-
- // Some thigns that can be done further:
-
+ // Some things that can be done further:
+
// TODO Optimization formats like OpTopN (which is an optimizer additional algebra operator).
- // TODO More group flattening.
- // OPTIONAL (LeftJoin) unbundles the LHS to avoid { { P OPTIONAL{} } OPTIONAL{} }
- // This is actually a general situation.
- // Adding onto the end of a group when the item added can not merge into the existing last element.
+ // TODO More group flattening. This is better presentation, not chanage in algebra.
+ // OPTIONAL (LeftJoin) unbundles the LHS to avoid { { P OPTIONAL{} } OPTIONAL{} }
+ // { { ... } BIND } -- the inner { } is not necessary
+ // This is actually a general situation.
+ // Adding onto the end of a group when the item added can not merge into the existing last element.
// e.g. BIND, VALUES.
+ public static Query asQuery(Op op) {
+ Converter converter = new Converter(op) ;
+ return converter.convert() ;
+ }
+
static class /* struct */ QueryLevelDetails {
// The stack of processing in a query is:
// slice-distinct/reduce-project-order-filter[having]-extend*[AS and aggregate naming]-group-pattern
@@ -90,12 +91,12 @@ public class OpAsQuery {
OpFilter opHaving = null ;
List<OpExtend> opExtends = new ArrayList<>() ;
OpGroup opGroup = null ;
- // End of the modifiers.
+ // End of the modifiers.
// The pattern of the group or query itself if not grouped.
Op pattern = null ;
-
+
private QueryLevelDetails() {}
-
+
// Debugging help.
void info() {
if ( opSlice != null )
@@ -123,6 +124,8 @@ public class OpAsQuery {
}
static QueryLevelDetails analyse(Op operation) {
+ // Walk inwards, collecting the query level information.
+ // slice-distinct/reduce-project-order-filter[having]-extend*[AS and aggregate naming]-group-pattern
QueryLevelDetails details = new QueryLevelDetails() ;
Op op = operation ;
@@ -149,10 +152,16 @@ public class OpAsQuery {
}
// Lookahead to see if an opGroup can be found.
+ // If no group, leave and process as in WHERE clause.
details.opGroup = getGroup(op) ;
if ( details.opGroup == null ) {
- op = processExtend(op, details.opExtends) ;
- details.pattern = op ;
+ // If project, deal with as AS.
+ // Else as regular WHERE
+ if ( details.opProject != null ) {
+ op = processExtend(op, details.opExtends) ;
+ details.pattern = op ;
+ } else
+ details.pattern = op ;
return details ;
}
// (group) found.
@@ -163,10 +172,10 @@ public class OpAsQuery {
}
// Can't tell if it's an "aggregation" except by looking at the
// assignment variables.
-
+
// AS and aggregate renames.
op = processExtend(op, details.opExtends) ;
-
+
if ( !(op instanceof OpGroup) ) {
System.out.println("Expected (group), got " + op.getName()) ;
}
@@ -174,41 +183,6 @@ public class OpAsQuery {
return details ;
}
}
-
- public static Op processExtend(Op op, List<OpExtend> assignments) {
- while ( op instanceof OpExtend ) {
- OpExtend opExtend = (OpExtend)op ;
- assignments.add(opExtend) ;
- op = opExtend.getSubOp() ;
- }
- return op ;
- }
- /**
- * Allows multiple filters and any number of extend
- */
- private static OpGroup getGroup(Op op) {
- // Unwind tail recursion to protected against extreme queries.
- for ( ; ; ) {
- if ( op instanceof OpGroup )
- return (OpGroup)op ;
- if ( op instanceof OpFilter ) {
- OpFilter opFilter = (OpFilter)op ;
- op = opFilter.getSubOp() ;
- continue ;
- }
- if ( op instanceof OpExtend ) { // AS or Aggregate naming
- OpExtend opExtend = (OpExtend)op ;
- op = opExtend.getSubOp() ;
- continue ;
- }
- return null ;
- }
- }
-
- public static Query asQuery(Op op) {
- Converter converter = new Converter(op) ;
- return converter.convert() ;
- }
public static class Converter implements OpVisitor {
private Query query ;
@@ -244,10 +218,10 @@ public class OpAsQuery {
Op op = processExtend(queryOp, assignments) ;
processQueryPattern(op, assignments) ;
query.setQueryResultStar(true) ;
- query.setResultVars();
+ query.setResultVars();
return query ;
}
-
+
// There is a projection.
QueryLevelDetails level = QueryLevelDetails.analyse(queryOp) ;
processQueryPattern(level) ;
@@ -268,7 +242,7 @@ public class OpAsQuery {
}) ;
query.getAggregators().addAll(level.opGroup.getAggregators()) ;
}
-
+
ExprTransform varToExpr = new ExprTransformCopy() {
@Override
public Expr transform(ExprVar nv) {
@@ -278,7 +252,7 @@ public class OpAsQuery {
}
} ;
- // The assignments will become part of the project.
+ // The assignments will become part of the project.
Map<Var, Expr> assignments = new HashMap<>() ;
if ( level.opExtends != null ) {
processExtends(level.opExtends, (var,expr)->{
@@ -286,8 +260,9 @@ public class OpAsQuery {
expr = rewrite(expr, varToExpr) ;
assignments.put(var, expr) ;
}) ;
+
}
-
+
if ( level.opHaving != null ) {
level.opHaving.getExprs().getList().forEach(expr -> {
expr = rewrite(expr, varToExpr) ;
@@ -305,17 +280,23 @@ public class OpAsQuery {
query.addOrderBy(new SortCondition(expr, sc.getDirection())) ;
}) ;
}
-
- if ( level.opProject != null ) {
+
+ if ( level.opProject == null ) {
+ query.setQueryResultStar(true) ;
+ // No project, Make BINDs
+ //processQueryPattern(op, assignments) ;
+
+
+ } else {
level.opProject.getVars().forEach(v -> {
if ( assignments.containsKey(v) ) {
query.addResultVar(v, assignments.get(v)) ;
} else
query.getProjectVars().add(v) ;
-
+
}) ;
- } else
- query.setQueryResultStar(true) ;
+ }
+
if ( level.opDistinct != null )
query.setDistinct(true) ;
@@ -330,12 +311,27 @@ public class OpAsQuery {
return query ;
}
+ /**
+ * Collect the OpExtend in a stack of OpExtend into a list for later
+ * processing. (Processing only uses opExtend in the list, not inner one
+ * which wil also be in the list.)
+ */
+ private static Op processExtend(Op op, List<OpExtend> assignments) {
+ while ( op instanceof OpExtend ) {
+ OpExtend opExtend = (OpExtend)op ;
+ // JENA-1843
+ assignments.add(0, opExtend) ;
+ op = opExtend.getSubOp() ;
+ }
+ return op ;
+ }
+
private static void processExtends(List<OpExtend> ext, BiConsumer<Var, Expr> action) {
ext.forEach(extend->{
- extend.getVarExprList().forEachExpr(action) ;
+ extend.getVarExprList().forEachVarExpr(action) ;
});
}
-
+
private static void processAssigns(List<OpAssign> assigns, BiConsumer<Var, Expr> action) {
assigns.forEach(assign->{
assign.getVarExprList().forEachExpr(action) ;
@@ -345,12 +341,11 @@ public class OpAsQuery {
private static Expr rewrite(Expr expr, ExprTransform transform) {
return ExprTransformer.transform(transform, expr) ;
}
-
+
/**
* Process for a single pattern below the modifiers.
* Cleans up the ElementGroup produced.
*/
-
private void processQueryPattern(QueryLevelDetails level) {
Op op = level.pattern ;
op.visit(this) ;
@@ -359,22 +354,28 @@ public class OpAsQuery {
query.setQueryPattern(e) ;
query.setQuerySelectType() ;
}
-
+
// Can't distinguish
- // SELECT * { ... BIND ( ?v AS ...) }
- // from
+ // SELECT * { ... BIND ( ?v AS ...) }
+ // from
// SELECT ( ?v AS ...) { ... }.
- // They have the same algebra.
- // This code chooses to use the second form.
+ // They have the same algebra.
+ // This code chooses to use the second form.
private void processQueryPattern(Op op, List<OpExtend> assignments) {
op.visit(this) ;
ElementGroup eg = this.currentGroup ;
processExtends(assignments,(v,e)->eg.addElement(new ElementBind(v, e)) ) ;
- Element e = fixupGroupsOfOne(eg) ;
+ Element e = cleanupGroup(eg) ;
query.setQueryPattern(e) ;
query.setQuerySelectType() ;
}
+ private Element cleanupGroup(ElementGroup eg) {
+ Element el = fixupGroupsOfOne(eg);
+ // Other cleanups.
+ return el;
+ }
+
private Element fixupGroupsOfOne(ElementGroup eg) {
ElementTransform transform = new ElementTransformCleanGroupsOfOne() ;
ExprTransform exprTransform = new ExprTransformApplyElementTransform(transform) ;
@@ -387,7 +388,7 @@ public class OpAsQuery {
}
return el2 ;
}
-
+
private Element asElement(Op op) {
ElementGroup g = asElementGroup(op) ;
if ( g.size() == 1 )
@@ -461,7 +462,7 @@ public class OpAsQuery {
Element e = asElement(op) ;
insertIntoGroup(g, e) ;
}
-
+
if ( nestGroup )
endSubGroup() ;
return ;
@@ -545,10 +546,10 @@ public class OpAsQuery {
ElementGroup eRightGroup = asElementGroup(opJoin.getRight()) ;
Element eRight = eRightGroup ;
// Very special case. If the RHS is not something that risks
- // reparsing into a combined element of a group, strip the group-of-one.
+ // reparsing into a combined element of a group, strip the group-of-one.
// See also ElementTransformCleanGroupsOfOne
if ( eRightGroup.size() == 1 ) {
- // This always was a {} around it but it's unnecessary in a group of one.
+ // This always was a {} around it but it's unnecessary in a group of one.
if ( eRightGroup.get(0) instanceof ElementSubQuery )
eRight = eRightGroup.get(0) ;
}
@@ -563,14 +564,14 @@ public class OpAsQuery {
public void visit(OpLeftJoin opLeftJoin) {
Element eLeft = asElement(opLeftJoin.getLeft()) ;
ElementGroup eRight = asElementGroup(opLeftJoin.getRight()) ;
-
+
// If the RHS is (filter) we need to protect it from becoming
// part of the expr for the LeftJoin.
// OPTIONAL {{ ?s ?p ?o FILTER (?o>34) }} is not the same as
// OPTIONAL { ?s ?p ?o FILTER (?o>34) }
-
+
boolean mustProtect = eRight.getElements().stream().anyMatch(el -> el instanceof ElementFilter ) ;
-
+
if ( mustProtect ) {
ElementGroup eRight2 = new ElementGroup() ;
eRight2.addElement(eRight);
@@ -590,7 +591,7 @@ public class OpAsQuery {
else
g.addElement(eLeft) ;
}
-
+
ElementOptional opt = new ElementOptional(eRight) ;
g.addElement(opt) ;
}
@@ -732,7 +733,7 @@ public class OpAsQuery {
currentGroup().addElement(new ElementAssign(var,expr)) ;
}) ;
}
-
+
@Override
public void visit(OpExtend opExtend) {
Element e = asElement(opExtend.getSubOp()) ;
@@ -749,8 +750,8 @@ public class OpAsQuery {
}
// When some modifers (e.g. OpDistinct) are met in a pattern, they signal
- // a new query level (new innser SELECT), where we switch back to
- // looking for the level start in
+ // a new query level (new inner SELECT), where we switch back to
+ // looking for the level start in
private void newLevel(Op op) {
convertAsSubQuery(op) ;
@@ -823,10 +824,10 @@ public class OpAsQuery {
eg.addElement(e);
return ;
}
-
+
Element eltTop = eg.getLast() ;
if ( ! ( eltTop instanceof ElementPathBlock ) ) {
- // Not working on a ElementPathBlock - no need to group-of-one
+ // Not working on a ElementPathBlock - no need to group-of-one
// when inserting ElementPathBlock.
e = unwrapGroupOfOnePathBlock(e) ;
eg.addElement(e);
@@ -856,10 +857,10 @@ public class OpAsQuery {
}
return null ;
}
-
+
private Element lastElement() {
ElementGroup g = currentGroup ;
- return g.getLast() ;
+ return g.getLast() ;
}
private void startSubGroup() {
@@ -895,4 +896,40 @@ public class OpAsQuery {
stack.push(el) ;
}
}
-}
\ No newline at end of file
+
+
+ /**
+ * Allows multiple filters and any number of extend
+ */
+ private static OpGroup getGroup(Op op) {
+ // Unwind tail recursion to protected against extreme queries.
+ for ( ; ; ) {
+ if ( op instanceof OpGroup )
+ return (OpGroup)op ;
+ if ( op instanceof OpFilter ) {
+ OpFilter opFilter = (OpFilter)op ;
+ op = opFilter.getSubOp() ;
+ continue ;
+ }
+ if ( op instanceof OpExtend ) { // AS or Aggregate naming
+ OpExtend opExtend = (OpExtend)op ;
+ op = opExtend.getSubOp() ;
+ continue ;
+ }
+ return null ;
+ }
+ }
+
+ private static Op processExtend(Op op, List<OpExtend> assignments) {
+ while (op instanceof OpExtend) {
+ OpExtend opExtend = (OpExtend)op;
+ assignments.add(opExtend);
+ op = opExtend.getSubOp();
+ }
+ // JENA-1843
+ if ( assignments.size() > 1 )
+ Collections.reverse(assignments);
+
+ return op;
+ }
+}
diff --git a/jena-arq/src/test/java/org/apache/jena/sparql/algebra/TestOpAsQuery.java b/jena-arq/src/test/java/org/apache/jena/sparql/algebra/TestOpAsQuery.java
index 2033ba8..cdcf8e1 100644
--- a/jena-arq/src/test/java/org/apache/jena/sparql/algebra/TestOpAsQuery.java
+++ b/jena-arq/src/test/java/org/apache/jena/sparql/algebra/TestOpAsQuery.java
@@ -44,7 +44,28 @@ public class TestOpAsQuery {
@Test public void testBasic02() { test_roundTripQuery("SELECT * { ?s ?p ?o }") ; }
@Test public void testBasic03() { test_roundTripQuery("SELECT * { ?s ?p ?o FILTER(?o > 5) }") ; }
@Test public void testBasic04() { test_roundTripQuery("SELECT ?s { ?s ?p ?o FILTER(?o > 5) }") ; }
- @Test public void testBasic05() { test_roundTripQuery("SELECT ?s (?o + 5 AS ?B) { ?s ?p ?o }") ; }
+
+ // 01, 02: Same algebra.
+ @Test public void testBind01() { test_roundTripQuery("SELECT ?s (?o + 5 AS ?B) { ?s ?p ?o }") ; }
+ @Test public void testBind02() { test_roundTripAlegbra("SELECT ?o ?B { ?s ?p ?o BIND (?o + 5 AS ?B) }") ; }
+ // No project
+ @Test public void testBind03() { test_roundTripQuery("SELECT * { ?s ?p ?o BIND (?o + 5 AS ?B) }") ; }
+
+ // Over nested.
+ @Test public void testBind04() {
+ test_roundTripQuery("SELECT * { ?s ?p ?o BIND(?o+1 AS ?a1) ?x ?q ?v BIND(?v+2 AS ?a2) }",
+ "SELECT * { { ?s ?p ?o BIND(( ?o + 1 ) AS ?a1) } ?x ?q ?v BIND(( ?v + 2 ) AS ?a2) } ");
+ }
+
+ // Over nested.
+ @Test public void testBind05() {
+ test_roundTripQuery("SELECT * { ?s ?p ?o BIND(?o+1 AS ?a1) ?x ?q ?v BIND(2 AS ?a2) } ORDER BY ?s",
+ "SELECT * { { { ?s ?p ?o BIND(( ?o + 1 ) AS ?a1) } ?x ?q ?v } BIND(2 AS ?a2) } ORDER BY ?s");
+ }
+
+ // https://issues.apache.org/jira/browse/JENA-1843
+ @Test public void testBind06() { test_roundTripQuery("SELECT * { ?s ?p ?o BIND(?o + 1 AS ?a1) BIND(?v+2 as ?a2) }"); }
+ @Test public void testBind07() { test_roundTripQuery("SELECT * { BIND(?o + 1 AS ?a1) BIND(?v+2 as ?a2) }"); }
@Test public void testOptional01()
{ test_roundTripQuery("SELECT * WHERE { ?s ?p ?o OPTIONAL { ?s ?q ?z FILTER (?foo) } }") ; }
@@ -126,6 +147,10 @@ public class TestOpAsQuery {
@Test public void testGroupBy_12()
{ test_roundTripQuery("SELECT * { ?s ?q ?z {SELECT DISTINCT * { ?s ?p ?o }} }"); }
+ // https://issues.apache.org/jira/browse/JENA-1844
+ @Test public void testGroupBy_13()
+ { test_roundTripQuery("SELECT * { ?s ?p ?o BIND(?o+1 AS ?a1) } ORDER BY ?s"); }
+
@Test public void testSubQuery_01()
{ test_roundTripQuery("SELECT ?s { SELECT (count(*) as ?cp) { ?s ?p ?o } }") ; }
@@ -464,6 +489,7 @@ public class TestOpAsQuery {
// to produce an output that is .equals the input.
/** query->algebra->OpAsQuery->query */
public static Query[] test_roundTripQuery(String query) {
+ // [original, got]
Query[] r = roundTripQuery(query) ;
stripNamespacesAndBase(r[0]) ;
stripNamespacesAndBase(r[1]) ;
@@ -471,6 +497,17 @@ public class TestOpAsQuery {
return r ;
}
+ public static void test_roundTripQuery(String query, String outcome) {
+ Query[] r = roundTripQuery(query) ;
+ Query orig = r[0];
+ Query output = r[1];
+ Query q2 = QueryFactory.create(outcome);
+ stripNamespacesAndBase(orig) ;
+ stripNamespacesAndBase(output) ;
+ stripNamespacesAndBase(q2) ;
+ assertEquals(q2, output) ;
+ }
+
// Test via quads
public static Query[] test_roundTripQueryQuads(String query) {
Query[] r = roundTripQueryQuad(query) ;