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 2013/11/19 17:53:03 UTC
svn commit: r1543490 - in /jena/Scratch/AFS/Dev/src-dev/opt:
OpVarsFixed.java OptMain.java
Author: andy
Date: Tue Nov 19 16:53:03 2013
New Revision: 1543490
URL: http://svn.apache.org/r1543490
Log:
Determine variables taht must occur in any solution of an Op
Added:
jena/Scratch/AFS/Dev/src-dev/opt/OpVarsFixed.java
Modified:
jena/Scratch/AFS/Dev/src-dev/opt/OptMain.java
Added: jena/Scratch/AFS/Dev/src-dev/opt/OpVarsFixed.java
URL: http://svn.apache.org/viewvc/jena/Scratch/AFS/Dev/src-dev/opt/OpVarsFixed.java?rev=1543490&view=auto
==============================================================================
--- jena/Scratch/AFS/Dev/src-dev/opt/OpVarsFixed.java (added)
+++ jena/Scratch/AFS/Dev/src-dev/opt/OpVarsFixed.java Tue Nov 19 16:53:03 2013
@@ -0,0 +1,366 @@
+/**
+ * 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 opt;
+
+import static com.hp.hpl.jena.sparql.core.Vars.addVar ;
+import static com.hp.hpl.jena.sparql.core.Vars.addVarsFromTriple ;
+
+import java.util.* ;
+
+import org.apache.jena.atlas.lib.SetUtils ;
+
+import com.hp.hpl.jena.graph.Node ;
+import com.hp.hpl.jena.graph.Triple ;
+import com.hp.hpl.jena.query.SortCondition ;
+import com.hp.hpl.jena.sparql.algebra.* ;
+import com.hp.hpl.jena.sparql.algebra.OpWalker.WalkerVisitor ;
+import com.hp.hpl.jena.sparql.algebra.op.* ;
+import com.hp.hpl.jena.sparql.core.BasicPattern ;
+import com.hp.hpl.jena.sparql.core.Var ;
+import com.hp.hpl.jena.sparql.pfunction.PropFuncArg ;
+
+public class OpVarsFixed {
+ // Not to be confused with VarFinder.fixed
+
+ /** The set of variables that wil be in every solution of this Op */
+ public static Set<Var> fixed(Op op) {
+ Set<Var> acc = collector() ;
+ visibleVars(op, acc) ;
+ return acc ;
+ }
+
+ public static void visibleVars(Op op, Set<Var> acc) {
+ OpVarsPattern visitor = new OpVarsPattern(acc, true) ;
+ OpWalker.walk(new WalkerVisitorFixed(visitor, acc), op) ;
+ }
+
+ // Choose the default collector - LinkedHashSet is predictable and
+ // keeps the "found" order
+ private static Set<Var> collector() {
+ return new LinkedHashSet<Var>() ;
+ }
+
+
+ // Only consider variables that are visible and definitely defined.
+ // OPTIONAL (2 forms) and UNION are the interesting cases.
+ private static class WalkerVisitorFixed extends WalkerVisitor
+ {
+ private final Collection<Var> acc ;
+
+ public WalkerVisitorFixed(OpVarsPattern visitor, Collection<Var> acc) {
+ super(visitor) ;
+ this.acc = acc ;
+ }
+
+ @Override
+ public void visit(OpLeftJoin x) {
+ x.getLeft().visit(this);
+ }
+
+ @Override
+ public void visit(OpConditional x) {
+ x.getLeft().visit(this);
+ }
+
+ @Override
+ public void visit(OpUnion x) {
+ Set<Var> left = OpVarsFixed.fixed(x.getLeft()) ;
+ Set<Var> right = OpVarsFixed.fixed(x.getRight()) ;
+ Set<Var> r = SetUtils.intersection(left, right) ;
+ acc.addAll(r) ;
+ }
+
+ @Override
+ public void visit(OpProject op) {
+ before(op) ;
+ // Skip Project subop.
+ acc.addAll(op.getVars()) ;
+ after(op) ;
+ }
+
+ @Override
+ public void visit(OpMinus op) {
+ before(op) ;
+ if (op.getLeft() != null)
+ op.getLeft().visit(this) ;
+ // Skip right.
+ // if ( op.getRight() != null ) op.getRight().visit(this) ;
+ if (visitor != null)
+ op.visit(visitor) ;
+ after(op) ;
+ }
+ }
+
+
+ // Somewhere.
+ public static Collection<Var> vars(BasicPattern pattern) {
+ Set<Var> acc = collector() ;
+ vars(pattern, acc) ;
+ return acc ;
+ }
+
+ public static void vars(BasicPattern pattern, Collection<Var> acc) {
+ for (Triple triple : pattern)
+ addVarsFromTriple(acc, triple) ;
+ }
+
+ private static class OpVarsPattern extends OpVisitorBase
+ {
+ // The must-be-set-vars
+ protected Set<Var> acc ;
+ final boolean visibleOnly ;
+
+ OpVarsPattern(Set<Var> acc, boolean visibleOnly) {
+ this.acc = acc ;
+ this.visibleOnly = visibleOnly ;
+ }
+
+ @Override
+ public void visit(OpBGP opBGP) {
+ vars(opBGP.getPattern(), acc) ;
+ }
+
+ @Override
+ public void visit(OpPath opPath) {
+ addVar(acc, opPath.getTriplePath().getSubject()) ;
+ addVar(acc, opPath.getTriplePath().getObject()) ;
+ }
+
+ @Override
+ public void visit(OpQuadPattern quadPattern) {
+ addVar(acc, quadPattern.getGraphNode()) ;
+ vars(quadPattern.getBasicPattern(), acc) ;
+// // Pure quading
+// for (Iterator<Quad> iter = quadPattern.getQuads().iterator(); iter.hasNext();) {
+// Quad quad = iter.next() ;
+// addVarsFromQuad(acc, quad) ;
+// }
+ }
+
+ @Override
+ public void visit(OpGraph opGraph) {
+ addVar(acc, opGraph.getNode()) ;
+ }
+
+ @Override
+ public void visit(OpDatasetNames dsNames) {
+ addVar(acc, dsNames.getGraphNode()) ;
+ }
+
+ @Override
+ public void visit(OpTable opTable) {
+ // Only the variables with values in the tables
+ // (When building, undefs didn't get into bindings so no variable
+ // mentioned)
+ Table t = opTable.getTable() ;
+ acc.addAll(t.getVars()) ;
+ }
+
+ @Override
+ public void visit(OpProject opProject) {
+ // The walker (WalkerVisitorVisible) handles this
+ // for visible variables, not mentioned variable colelcting.
+ // The visibleOnly/clear is simply to be as general as possible.
+ if (visibleOnly)
+ acc.clear() ;
+ acc.addAll(opProject.getVars()) ;
+ }
+
+ @Override
+ public void visit(OpAssign opAssign) {
+ acc.addAll(opAssign.getVarExprList().getVars()) ;
+ }
+
+ @Override
+ public void visit(OpExtend opExtend) {
+ acc.addAll(opExtend.getVarExprList().getVars()) ;
+ }
+
+ @Override
+ public void visit(OpPropFunc opPropFunc) {
+ addvars(opPropFunc.getSubjectArgs()) ;
+ addvars(opPropFunc.getObjectArgs()) ;
+ }
+
+ private void addvars(PropFuncArg pfArg) {
+ if (pfArg.isNode()) {
+ addVar(acc, pfArg.getArg()) ;
+ return ;
+ }
+ for (Node n : pfArg.getArgList())
+ addVar(acc, n) ;
+ }
+
+ @Override
+ public void visit(OpProcedure opProc) {
+ opProc.getArgs().varsMentioned(acc) ;
+ }
+
+ }
+
+ private static class OpVarsPatternWithPositions extends OpVisitorBase
+ {
+ // The possibly-set-vars
+ protected Set<Var> graphAcc, subjAcc, predAcc, objAcc, unknownAcc ;
+ final boolean visibleOnly ;
+
+ OpVarsPatternWithPositions(Set<Var> graphAcc, Set<Var> subjAcc, Set<Var> predAcc, Set<Var> objAcc, Set<Var> unknownAcc, boolean visibleOnly) {
+ this.graphAcc = graphAcc;
+ this.subjAcc = subjAcc;
+ this.predAcc = predAcc;
+ this.objAcc = objAcc;
+ this.unknownAcc = unknownAcc;
+ this.visibleOnly = visibleOnly ;
+ }
+
+ @Override
+ public void visit(OpBGP opBGP) {
+ vars(opBGP.getPattern()) ;
+ }
+
+ @Override
+ public void visit(OpPath opPath) {
+ addVar(subjAcc, opPath.getTriplePath().getSubject()) ;
+ addVar(objAcc, opPath.getTriplePath().getObject()) ;
+ }
+
+ @Override
+ public void visit(OpQuadPattern quadPattern) {
+ addVar(graphAcc, quadPattern.getGraphNode()) ;
+ vars(quadPattern.getBasicPattern()) ;
+ }
+
+ @Override
+ public void visit(OpGraph opGraph) {
+ addVar(graphAcc, opGraph.getNode()) ;
+ }
+
+ @Override
+ public void visit(OpDatasetNames dsNames) {
+ addVar(graphAcc, dsNames.getGraphNode()) ;
+ }
+
+ @Override
+ public void visit(OpTable opTable) {
+ // Only the variables with values in the tables
+ // (When building, undefs didn't get into bindings so no variable
+ // mentioned)
+ Table t = opTable.getTable() ;
+ // Treat as unknown position
+ unknownAcc.addAll(t.getVars()) ;
+ }
+
+ @Override
+ public void visit(OpProject opProject) {
+ // The walker (WalkerVisitorVisible) handles this
+ // for visible variables, not mentioned variable collecting.
+ // The visibleOnly/clear is simply to be as general as possible.
+ List<Var> vs = opProject.getVars();
+ if (visibleOnly) {
+ clear(graphAcc, vs);
+ clear(subjAcc, vs);
+ clear(predAcc, vs);
+ clear(objAcc, vs);
+
+ }
+ for (Var v : vs) {
+ if (!graphAcc.contains(v) && !subjAcc.contains(v) && !predAcc.contains(v) && !objAcc.contains(v)) {
+ addVar(unknownAcc, v);
+ }
+ }
+ }
+
+ @Override
+ public void visit(OpAssign opAssign) {
+ // Unknown position
+ unknownAcc.addAll(opAssign.getVarExprList().getVars()) ;
+ }
+
+ @Override
+ public void visit(OpExtend opExtend) {
+ // Unknown position
+ unknownAcc.addAll(opExtend.getVarExprList().getVars()) ;
+ }
+
+ @Override
+ public void visit(OpPropFunc opPropFunc) {
+ addvars(subjAcc, opPropFunc.getSubjectArgs()) ;
+ addvars(objAcc, opPropFunc.getObjectArgs()) ;
+ }
+
+ private void addvars(Set<Var> acc, PropFuncArg pfArg) {
+ if (pfArg.isNode()) {
+ addVar(acc, pfArg.getArg()) ;
+ return ;
+ }
+ for (Node n : pfArg.getArgList())
+ addVar(acc, n) ;
+ }
+
+ @Override
+ public void visit(OpProcedure opProc) {
+ unknownAcc.addAll(OpVars.mentionedVars(opProc));
+ }
+
+ private void vars(BasicPattern bp) {
+ for (Triple t : bp.getList())
+ {
+ addVar(subjAcc, t.getSubject());
+ addVar(predAcc, t.getPredicate());
+ addVar(objAcc, t.getObject());
+ }
+ }
+
+ private void clear(Set<Var> acc, List<Var> visible) {
+ List<Var> toRemove = new ArrayList<Var>();
+ for (Var found : acc)
+ {
+ if (!visible.contains(found)) {
+ toRemove.add(found);
+ }
+ }
+ for (Var v : toRemove) {
+ acc.remove(v);
+ }
+ }
+
+ }
+
+ private static class OpVarsMentioned extends OpVarsPattern
+ {
+ OpVarsMentioned(Set<Var> acc) {
+ super(acc, false) ;
+ }
+
+ @Override
+ public void visit(OpFilter opFilter) {
+ opFilter.getExprs().varsMentioned(acc) ;
+ }
+
+ @Override
+ public void visit(OpOrder opOrder) {
+ for (Iterator<SortCondition> iter = opOrder.getConditions().iterator(); iter.hasNext();) {
+ SortCondition sc = iter.next() ;
+ Set<Var> x = sc.getExpression().getVarsMentioned() ;
+ acc.addAll(x) ;
+ }
+ }
+ }
+}
+
Modified: jena/Scratch/AFS/Dev/src-dev/opt/OptMain.java
URL: http://svn.apache.org/viewvc/jena/Scratch/AFS/Dev/src-dev/opt/OptMain.java?rev=1543490&r1=1543489&r2=1543490&view=diff
==============================================================================
--- jena/Scratch/AFS/Dev/src-dev/opt/OptMain.java (original)
+++ jena/Scratch/AFS/Dev/src-dev/opt/OptMain.java Tue Nov 19 16:53:03 2013
@@ -19,6 +19,9 @@
package opt;
import static com.hp.hpl.jena.sparql.algebra.optimize.Optimize.apply ;
+
+import java.util.Set ;
+
import org.apache.jena.atlas.lib.StrUtils ;
import com.hp.hpl.jena.query.ARQ ;
@@ -30,6 +33,7 @@ import com.hp.hpl.jena.sparql.algebra.op
import com.hp.hpl.jena.sparql.algebra.op.OpLabel ;
import com.hp.hpl.jena.sparql.algebra.optimize.* ;
import com.hp.hpl.jena.sparql.algebra.optimize.Optimize.RewriterFactory ;
+import com.hp.hpl.jena.sparql.core.Var ;
import com.hp.hpl.jena.sparql.engine.main.JoinClassifier ;
import com.hp.hpl.jena.sparql.sse.SSE ;
import com.hp.hpl.jena.sparql.util.Context ;
@@ -62,9 +66,28 @@ public class OptMain {
// JoinStartegy and FilterPlacement interaction.
public static void main(String... argv) {
- testFailure() ;
+ fixedVars() ;
+ placement() ;
}
+ public static void fixedVars() {
+ //. FILTERs
+ // See alt VarFinder
+// String sx = StrUtils.strjoinNL
+// ("(union",
+// " (leftJoin (filter (= ?x 123) (bgp (?s ?p ?o1))) (bgp (?s ?p ?o2)) )",
+// " (leftJoin (bgp (?s ?p2 ?o1)) (bgp (?x ?p1 ?o2)) )",
+// ")"
+// ) ;
+ String sx = "(filter (= ?x 123) (extend (?x 567) (bgp (?s ?p ?o1)) ))" ;
+ //Op op = SSE.parseOp("(union (bgp (?s ?p ?o1)) (bgp (?s ?p ?o2)))") ;
+ Op op = SSE.parseOp(sx) ;
+ System.out.println(op);
+ Set<Var> x = OpVarsFixed.fixed(op) ;
+ System.out.println(x) ;
+ System.exit(0) ;
+ }
+
public static void testFailure() {
String DIR = "/home/afs/Jena/jena-arq/testing/ARQ/OptFilterEquality" ;
@@ -177,6 +200,18 @@ Rewrite2
// Order dependency.
// Push LHS and RHS on a JOIN then sequence => Filter twice in sequence. No harm but ...
+ /*
+ * PREFIX : <http://example.org/>
+
+SELECT *
+{
+ OPTIONAL { ?x :qq ?o2 }
+ FILTER(?x = :x1)
+ ?x :p ?o1 .
+}
+
+ */
+
String qs3 = StrUtils.strjoinNL
( "PREFIX : <http://example/> SELECT * {"
, " OPTIONAL { ?x :q ?o }"
@@ -195,12 +230,20 @@ Rewrite2
Op op2 = Algebra.optimize(op1) ;
System.out.println(op2) ;
}
- System.out.println("** NEW") ;
+ System.out.println("** NEW : Place/Join") ;
+ rewire() ;
//Op op2 = new Rewrite2(ARQ.getContext()).rewrite(op1) ;
Op op2 = op1 ;
op2 = Transformer.transform(new TransformJoinStrategy(), op2) ;
op2 = placement(op2) ;
System.out.println(op2) ;
+ System.out.println("** NEW : Join/Place") ;
+
+ op2 = op1 ;
+ op2 = placement(op2) ;
+ op2 = Transformer.transform(new TransformJoinStrategy(), op2) ;
+
+ System.out.println(op2) ;
System.exit(0) ;
}