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)
+        {}
+        
+    }
 }