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 2012/02/11 22:25:13 UTC
svn commit: r1243155 - in
/incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql:
algebra/ algebra/optimize/ path/
Author: andy
Date: Sat Feb 11 21:25:13 2012
New Revision: 1243155
URL: http://svn.apache.org/viewvc?rev=1243155&view=rev
Log:
Provide a as-per-spec path transformation. Not used for execution as it generates op code which is inefficient.
Added:
incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformPathFlatternStd.java
Modified:
incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/algebra/AlgebraGenerator.java
incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformPathFlattern.java
incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/PathCompiler.java
incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/PathEval.java
Modified: incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/algebra/AlgebraGenerator.java
URL: http://svn.apache.org/viewvc/incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/algebra/AlgebraGenerator.java?rev=1243155&r1=1243154&r2=1243155&view=diff
==============================================================================
--- incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/algebra/AlgebraGenerator.java (original)
+++ incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/algebra/AlgebraGenerator.java Sat Feb 11 21:25:13 2012
@@ -29,58 +29,18 @@ import com.hp.hpl.jena.query.ARQ ;
import com.hp.hpl.jena.query.Query ;
import com.hp.hpl.jena.query.SortCondition ;
import com.hp.hpl.jena.sparql.ARQInternalErrorException ;
-import com.hp.hpl.jena.sparql.algebra.op.OpAssign ;
-import com.hp.hpl.jena.sparql.algebra.op.OpBGP ;
-import com.hp.hpl.jena.sparql.algebra.op.OpDistinct ;
-import com.hp.hpl.jena.sparql.algebra.op.OpExtend ;
-import com.hp.hpl.jena.sparql.algebra.op.OpFilter ;
-import com.hp.hpl.jena.sparql.algebra.op.OpGraph ;
-import com.hp.hpl.jena.sparql.algebra.op.OpGroup ;
-import com.hp.hpl.jena.sparql.algebra.op.OpJoin ;
-import com.hp.hpl.jena.sparql.algebra.op.OpLabel ;
-import com.hp.hpl.jena.sparql.algebra.op.OpLeftJoin ;
-import com.hp.hpl.jena.sparql.algebra.op.OpList ;
-import com.hp.hpl.jena.sparql.algebra.op.OpMinus ;
-import com.hp.hpl.jena.sparql.algebra.op.OpNull ;
-import com.hp.hpl.jena.sparql.algebra.op.OpOrder ;
-import com.hp.hpl.jena.sparql.algebra.op.OpProject ;
-import com.hp.hpl.jena.sparql.algebra.op.OpReduced ;
-import com.hp.hpl.jena.sparql.algebra.op.OpSequence ;
-import com.hp.hpl.jena.sparql.algebra.op.OpService ;
-import com.hp.hpl.jena.sparql.algebra.op.OpSlice ;
-import com.hp.hpl.jena.sparql.algebra.op.OpTable ;
-import com.hp.hpl.jena.sparql.algebra.op.OpUnion ;
+import com.hp.hpl.jena.sparql.algebra.op.* ;
import com.hp.hpl.jena.sparql.algebra.optimize.TransformSimplify ;
import com.hp.hpl.jena.sparql.core.BasicPattern ;
import com.hp.hpl.jena.sparql.core.PathBlock ;
import com.hp.hpl.jena.sparql.core.Var ;
import com.hp.hpl.jena.sparql.core.VarExprList ;
import com.hp.hpl.jena.sparql.engine.binding.Binding ;
-import com.hp.hpl.jena.sparql.expr.E_Exists ;
-import com.hp.hpl.jena.sparql.expr.E_LogicalNot ;
-import com.hp.hpl.jena.sparql.expr.Expr ;
-import com.hp.hpl.jena.sparql.expr.ExprLib ;
-import com.hp.hpl.jena.sparql.expr.ExprList ;
-import com.hp.hpl.jena.sparql.path.PathCompiler ;
+import com.hp.hpl.jena.sparql.expr.* ;
import com.hp.hpl.jena.sparql.path.PathLib ;
import com.hp.hpl.jena.sparql.sse.Item ;
import com.hp.hpl.jena.sparql.sse.ItemList ;
-import com.hp.hpl.jena.sparql.syntax.Element ;
-import com.hp.hpl.jena.sparql.syntax.ElementAssign ;
-import com.hp.hpl.jena.sparql.syntax.ElementBind ;
-import com.hp.hpl.jena.sparql.syntax.ElementExists ;
-import com.hp.hpl.jena.sparql.syntax.ElementFetch ;
-import com.hp.hpl.jena.sparql.syntax.ElementFilter ;
-import com.hp.hpl.jena.sparql.syntax.ElementGroup ;
-import com.hp.hpl.jena.sparql.syntax.ElementMinus ;
-import com.hp.hpl.jena.sparql.syntax.ElementNamedGraph ;
-import com.hp.hpl.jena.sparql.syntax.ElementNotExists ;
-import com.hp.hpl.jena.sparql.syntax.ElementOptional ;
-import com.hp.hpl.jena.sparql.syntax.ElementPathBlock ;
-import com.hp.hpl.jena.sparql.syntax.ElementService ;
-import com.hp.hpl.jena.sparql.syntax.ElementSubQuery ;
-import com.hp.hpl.jena.sparql.syntax.ElementTriplesBlock ;
-import com.hp.hpl.jena.sparql.syntax.ElementUnion ;
+import com.hp.hpl.jena.sparql.syntax.* ;
import com.hp.hpl.jena.sparql.util.Context ;
import com.hp.hpl.jena.sparql.util.Utils ;
@@ -90,7 +50,6 @@ public class AlgebraGenerator
// Helpful only to write exactly what you mean and test the full query compiler.
private boolean fixedFilterPosition = false ;
private Context context ;
- private PathCompiler pathCompiler = new PathCompiler() ;
private int subQueryDepth = 0 ;
// simplifyInAlgebraGeneration=true is the alternative reading of
Modified: incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformPathFlattern.java
URL: http://svn.apache.org/viewvc/incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformPathFlattern.java?rev=1243155&r1=1243154&r2=1243155&view=diff
==============================================================================
--- incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformPathFlattern.java (original)
+++ incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformPathFlattern.java Sat Feb 11 21:25:13 2012
@@ -25,9 +25,13 @@ import com.hp.hpl.jena.sparql.core.PathB
import com.hp.hpl.jena.sparql.path.PathCompiler ;
import com.hp.hpl.jena.sparql.path.PathLib ;
+/** Perform the equivalent of the trasnactions in the SPARQL 1.1 spec.
+ * ARQ regards path transformation as an optimization.
+ * ARQ does not execute the exact transformation as per spec as there are betetr ways to do it.
+ */
+
public class TransformPathFlattern extends TransformCopy
{
- // *** THE algebra generator does this ***
// This transform is also used so programmtically built queries also get converted.
// Need previous BGP for merging? Do as a separate pass (sequence, BGP collapse)
Added: incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformPathFlatternStd.java
URL: http://svn.apache.org/viewvc/incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformPathFlatternStd.java?rev=1243155&view=auto
==============================================================================
--- incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformPathFlatternStd.java (added)
+++ incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformPathFlatternStd.java Sat Feb 11 21:25:13 2012
@@ -0,0 +1,204 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.hp.hpl.jena.sparql.algebra.optimize;
+
+import com.hp.hpl.jena.graph.Node ;
+import com.hp.hpl.jena.graph.Triple ;
+import com.hp.hpl.jena.sparql.ARQConstants ;
+import com.hp.hpl.jena.sparql.ARQException ;
+import com.hp.hpl.jena.sparql.algebra.Op ;
+import com.hp.hpl.jena.sparql.algebra.TransformCopy ;
+import com.hp.hpl.jena.sparql.algebra.op.OpJoin ;
+import com.hp.hpl.jena.sparql.algebra.op.OpPath ;
+import com.hp.hpl.jena.sparql.algebra.op.OpTriple ;
+import com.hp.hpl.jena.sparql.algebra.op.OpUnion ;
+import com.hp.hpl.jena.sparql.core.TriplePath ;
+import com.hp.hpl.jena.sparql.core.Var ;
+import com.hp.hpl.jena.sparql.core.VarAlloc ;
+import com.hp.hpl.jena.sparql.path.* ;
+
+/** The path transformation step exactly as per teh SPARQL 1.1 spec.
+ * It does not produce very nice execution structyres so ARQ uses
+ * a functional equivalent, bit different, transformation.
+ */
+public class TransformPathFlatternStd extends TransformCopy
+{
+ public TransformPathFlatternStd() { }
+
+ @Override
+ public Op transform(OpPath opPath)
+ {
+ TriplePath tp = opPath.getTriplePath() ;
+ Op op = transformPath(opPath, tp.getSubject(), tp.getPath(), tp.getObject() ) ;
+ // And combine adjacent triple patterns.
+ return op ;
+ }
+
+ static Op transformPath(OpPath op, Node subject, Path path, Node object)
+ {
+ PathTransform transform = new PathTransform(subject, object) ;
+ path.visit(transform) ;
+ Op r = transform.getResult() ;
+ if ( r == null )
+ {
+ if ( op == null )
+ {
+ TriplePath tp = new TriplePath(subject, path, object) ;
+ op = new OpPath(tp) ;
+ }
+ return op ;
+ }
+
+ return r ;
+ }
+
+ static VarAlloc varAlloc = new VarAlloc(ARQConstants.allocVarAnonMarker+"Q") ;
+
+ static Op join(Op op1, Op op2)
+ {
+ if ( op1 == null )
+ return op2 ;
+ if ( op2 == null )
+ return op1 ;
+ return OpJoin.create(op1, op2) ;
+ }
+
+ static class PathTransform implements PathVisitor
+ {
+ private final Node subject ;
+ private final Node object ;
+ private Op result ;
+ Op getResult()
+ {
+ return result ;
+ }
+
+ public PathTransform(Node subject, Node object)
+ {
+ this.subject = subject ;
+ this.object = object ;
+ }
+
+ @Override
+ public void visit(P_Link pathNode)
+ {
+ Op op = new OpTriple(new Triple(subject, pathNode.getNode(), object)) ;
+ result = op ;
+ }
+
+ @Override
+ public void visit(P_ReverseLink pathNode)
+ {
+ Op op = new OpTriple(new Triple(object, pathNode.getNode(), subject)) ;
+ result = op ;
+ }
+
+ @Override
+ public void visit(P_NegPropSet pathNotOneOf)
+ {
+ // No change.
+ }
+
+ @Override
+ public void visit(P_Inverse inversePath)
+ {
+ PathTransform pt = new PathTransform(object, subject) ;
+ inversePath.getSubPath().visit(pt) ;
+ result = pt.getResult() ;
+ }
+
+ @Override
+ public void visit(P_Mod pathMod)
+ {
+ if ( pathMod.getMin() > pathMod.getMax() )
+ throw new ARQException("Bad path: "+pathMod) ;
+
+ Op op = null ;
+ for ( long i = pathMod.getMin() ; i <= pathMod.getMax() ; i++ )
+ {
+ Path p = PathFactory.pathFixedLength(pathMod.getSubPath(), i) ;
+ Op sub = transformPath(null, subject, p, object) ;
+ op = OpUnion.create(op, sub) ;
+ }
+ result = op ;
+ }
+
+ @Override
+ public void visit(P_FixedLength pFixedLength)
+ {
+ Op op = null ;
+ Var v1 = null ;
+ for ( int i = 0 ; i < pFixedLength.getCount() ; i++ )
+ {
+ Var v2 = varAlloc.allocVar() ;
+ Node s = (v1 == null) ? subject : v1 ;
+ Node o = (i == pFixedLength.getCount()-1) ? object : v2 ;
+ Op op1 = transformPath(null, s, pFixedLength.getSubPath() , o) ;
+ op = join(op, op1) ;
+ v1 = v2 ;
+ }
+ result = op ;
+ }
+
+ @Override
+ public void visit(P_Distinct pathDistinct)
+ {
+ // No change.
+ result = null ;
+ }
+
+ @Override
+ public void visit(P_ZeroOrOne path)
+ {
+ // No change.
+ result = null ;
+ }
+
+ @Override
+ public void visit(P_ZeroOrMore path)
+ {
+ // No change.
+ result = null ;
+ }
+
+ @Override
+ public void visit(P_OneOrMore path)
+ {
+ // No change.
+ result = null ;
+ }
+
+ @Override
+ public void visit(P_Alt pathAlt)
+ {
+ Op op1 = transformPath(null, subject, pathAlt.getLeft() , object) ;
+ Op op2 = transformPath(null, subject, pathAlt.getRight() , object) ;
+ result = OpUnion.create(op1, op2) ;
+ }
+
+ @Override
+ public void visit(P_Seq pathSeq)
+ {
+ Var v = varAlloc.allocVar() ;
+ Op op1 = transformPath(null, subject, pathSeq.getLeft() , v) ;
+ Op op2 = transformPath(null, v, pathSeq.getRight() , object) ;
+ result = join(op1, op2) ;
+ }
+ }
+}
Modified: incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/PathCompiler.java
URL: http://svn.apache.org/viewvc/incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/PathCompiler.java?rev=1243155&r1=1243154&r2=1243155&view=diff
==============================================================================
--- incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/PathCompiler.java (original)
+++ incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/PathCompiler.java Sat Feb 11 21:25:13 2012
@@ -79,7 +79,6 @@ public class PathCompiler
return x ;
}
-
private static void reduce(PathBlock x, VarAlloc varAlloc, Node startNode, Path path, Node endNode)
{
// V-i-s-i-t-o-r!
@@ -151,6 +150,10 @@ public class PathCompiler
// This is the rewrite of
// "x {N,} y" to "x :p{N} ?V . ?V :p* y"
// "x {N,M} y" to "x :p{N} ?V . ?V {0,M} y"
+ // The spec defines {n,m} to be
+ // {n} union {n+1} union ... union {m}
+ // which leads to a lot of repeated work.
+
if ( pMod.getMin() > 0 )
{
Path p1 = PathFactory.pathFixedLength(pMod.getSubPath(), pMod.getMin()) ;
Modified: incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/PathEval.java
URL: http://svn.apache.org/viewvc/incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/PathEval.java?rev=1243155&r1=1243154&r2=1243155&view=diff
==============================================================================
--- incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/PathEval.java (original)
+++ incubator/jena/Jena2/ARQ/trunk/src/main/java/com/hp/hpl/jena/sparql/path/PathEval.java Sat Feb 11 21:25:13 2012
@@ -567,4 +567,77 @@ public class PathEval
visited.remove(node) ;
}
}
+
+ /** Path evaluation visitor that provide distinct nodes visited, */
+ static class PathEvaluator1 implements PathVisitor
+ {
+ private final Graph graph ;
+ private final Node node ;
+ private final Collection<Node> output ;
+ private boolean forwardMode ;
+
+ public PathEvaluator1(Graph g, Node n, Collection<Node> output, boolean forward)
+ {
+ this.graph = g ;
+ this.node = n ;
+ this.output = output ;
+ this.forwardMode = forward ;
+ }
+
+ @Override
+ public void visit(P_Link pathNode)
+ {
+ Iterator<Node> nodes = doOne(pathNode.getNode()) ;
+ }
+
+ private Iterator<Node> doOne(Node node)
+ {
+ return null ;
+ }
+
+ @Override
+ public void visit(P_ReverseLink pathNode)
+ {}
+
+ @Override
+ public void visit(P_NegPropSet pathNotOneOf)
+ {}
+
+ @Override
+ public void visit(P_Inverse inversePath)
+ {}
+
+ @Override
+ public void visit(P_Mod pathMod)
+ {}
+
+ @Override
+ public void visit(P_FixedLength pFixedLength)
+ {}
+
+ @Override
+ public void visit(P_Distinct pathDistinct)
+ {}
+
+ @Override
+ public void visit(P_ZeroOrOne path)
+ {}
+
+ @Override
+ public void visit(P_ZeroOrMore path)
+ {}
+
+ @Override
+ public void visit(P_OneOrMore path)
+ {}
+
+ @Override
+ public void visit(P_Alt pathAlt)
+ {}
+
+ @Override
+ public void visit(P_Seq pathSeq)
+ {}
+
+ }
}