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/08/20 13:42:12 UTC
svn commit: r1374977 - in /jena/Scratch/AFS/Jena-Dev/trunk/src/dev: Run.java
TransformFilterEquality2.java
Author: andy
Date: Mon Aug 20 11:42:11 2012
New Revision: 1374977
URL: http://svn.apache.org/viewvc?rev=1374977&view=rev
Log: (empty)
Modified:
jena/Scratch/AFS/Jena-Dev/trunk/src/dev/Run.java
jena/Scratch/AFS/Jena-Dev/trunk/src/dev/TransformFilterEquality2.java
Modified: jena/Scratch/AFS/Jena-Dev/trunk/src/dev/Run.java
URL: http://svn.apache.org/viewvc/jena/Scratch/AFS/Jena-Dev/trunk/src/dev/Run.java?rev=1374977&r1=1374976&r2=1374977&view=diff
==============================================================================
--- jena/Scratch/AFS/Jena-Dev/trunk/src/dev/Run.java (original)
+++ jena/Scratch/AFS/Jena-Dev/trunk/src/dev/Run.java Mon Aug 20 11:42:11 2012
@@ -18,8 +18,6 @@
package dev;
-import java.util.IdentityHashMap ;
-
import org.openjena.atlas.lib.StrUtils ;
import org.openjena.atlas.logging.Log ;
@@ -61,19 +59,47 @@ public class Run extends RunBase
public static void main(String[] argv) throws Exception
{
- String x = StrUtils.strjoinNL(
- "PREFIX : <http://example.org/>" ,
- "SELECT *" ,
- "{ ",
- //" OPTIONAL { ?x :zpp ?o1 }",
- " OPTIONAL { ?x :zqq ?o2 }" ,
- " FILTER ( ?x = :x )",
- "}") ;
- // Consider building a mapping of op to scope.
- // Either cheaper(caching) hash or
- // Op.fix() -- makes immutable, caches hash, changes equality (!)
- System.identityHashCode(x) ;
- new IdentityHashMap<Op, Object/*ScopeMap*/>() ;
+ String x0 = StrUtils.strjoinNL(
+ "PREFIX : <http://example.org/>" ,
+ "SELECT *" ,
+ "{ ",
+ " ?x :p ?o " ,
+ " FILTER ( ?x = :x )",
+ "}") ;
+ String x1 = StrUtils.strjoinNL(
+ "PREFIX : <http://example.org/>" ,
+ "SELECT *" ,
+ "{ ",
+ //" OPTIONAL { ?x :zpp ?o1 }",
+ " OPTIONAL { ?x :zqq ?o2 }" ,
+ " FILTER ( ?x = :x )",
+ "}") ;
+ String x2 = StrUtils.strjoinNL(
+ "PREFIX : <http://example.org/>" ,
+ "SELECT *" ,
+ "{ ",
+ " OPTIONAL { ?x :zpp ?o1 }",
+ " OPTIONAL { ?x :zqq ?o2 }" ,
+ " FILTER ( ?x = :x )",
+ "}") ;
+ String x3 = StrUtils.strjoinNL(
+ "PREFIX : <http://example.org/>" ,
+ "SELECT *" ,
+ "{ ",
+ " OPTIONAL { ?x :zpp ?o1 }",
+ " OPTIONAL { ?x :zqq ?o2 }" ,
+ " OPTIONAL { ?x :zrr ?o3 }" ,
+ " FILTER ( ?x = :x )",
+ "}") ;
+
+
+// // Consider building a mapping of op to scope.
+// // Either cheaper(caching) hash or
+// // Op.fix() -- makes immutable, caches hash, changes equality (!)
+// System.identityHashCode(x) ;
+// new IdentityHashMap<Op, Object/*ScopeMap*/>() ;
+
+ String x = x3 ;
//Query query = QueryFactory.read("FilterEquality/filter-equality-08.rq") ;
Query query = QueryFactory.create(x) ;
@@ -86,7 +112,7 @@ public class Run extends RunBase
WriterOp.output(System.out, op, sCxt) ;
- Op op2 = Optimize.apply(new TransformFilterEquality2(false), op) ;
+ Op op2 = Optimize.apply(new TransformFilterEquality2(), op) ;
System.out.println() ;
WriterOp.output(System.out, op2, sCxt) ;
//System.out.println(op2) ;
Modified: jena/Scratch/AFS/Jena-Dev/trunk/src/dev/TransformFilterEquality2.java
URL: http://svn.apache.org/viewvc/jena/Scratch/AFS/Jena-Dev/trunk/src/dev/TransformFilterEquality2.java?rev=1374977&r1=1374976&r2=1374977&view=diff
==============================================================================
--- jena/Scratch/AFS/Jena-Dev/trunk/src/dev/TransformFilterEquality2.java (original)
+++ jena/Scratch/AFS/Jena-Dev/trunk/src/dev/TransformFilterEquality2.java Mon Aug 20 11:42:11 2012
@@ -18,14 +18,16 @@
package dev;
-import java.util.Set ;
+import java.util.* ;
-import org.openjena.atlas.lib.SetUtils ;
+import org.openjena.atlas.lib.Pair ;
import com.hp.hpl.jena.query.ARQ ;
+import com.hp.hpl.jena.sparql.ARQNotImplemented ;
import com.hp.hpl.jena.sparql.algebra.Op ;
import com.hp.hpl.jena.sparql.algebra.OpVars ;
import com.hp.hpl.jena.sparql.algebra.TransformCopy ;
+import com.hp.hpl.jena.sparql.algebra.Transformer ;
import com.hp.hpl.jena.sparql.algebra.op.* ;
import com.hp.hpl.jena.sparql.core.Substitute ;
import com.hp.hpl.jena.sparql.core.Var ;
@@ -34,67 +36,124 @@ import com.hp.hpl.jena.sparql.expr.* ;
public class TransformFilterEquality2 extends TransformCopy
{
// See LeftJoinClassifier
-
- // TODO (Carefully) transformPlainStrings
- // Aggressive on strings goes for efficient over exactlness of xsd:string/plain literal.
-
- private boolean stringsAsTerms ;
-
- public TransformFilterEquality2(boolean stringsAsTerms)
- {
- // XSD string is not a simple literal
- // Inactive.
- // What about numbers?
- this.stringsAsTerms = stringsAsTerms ;
- }
+ public TransformFilterEquality2()
+ { }
@Override
public Op transform(OpFilter opFilter, Op subOp)
- {
+ {
ExprList exprs = opFilter.getExprs() ;
-
- if ( ! safeToTransform(exprs, subOp) )
- return super.transform(opFilter, subOp) ;
-
- Op op = subOp ;
- // Variables set
- Set<Var> patternVars = OpVars.patternVars(op) ;
-
- // Any assignments must go inside filters so the filters see the assignments.
- // For each filter in the expr list ...
- ExprList exprs2 = new ExprList() ; // Unchanged filters. Put around the result.
+ // ---- Find and extract any equality filters.
+ Pair<List<Pair<Var, NodeValue>>, ExprList> p = preprocessFilterEquality(exprs) ;
+ if ( p == null || p.getLeft().size() == 0 )
+ return super.transform(opFilter, subOp) ;
+ List<Pair<Var, NodeValue>> equalities = p.getLeft() ;
+ Collection<Var> varsMentioned = varsMentionedInEqualityFilters(equalities) ;
+ ExprList remaining = p.getRight() ;
+
+ // ---- Check if the subOp is the right shape to transform.
+
+ // Special case: the deep left op of a OpConditional/OpLeftJoin is unit table.
+ // Given the there is an equality filter, if the right does not match,
+ // the empty row wil be rejected by the filter.
+ // So the bottom is in fact a normal join; and "(join unit P)" is equal to P.
+
+ // ---- Transform
+ Op op ;
+ if ( testSpecialCase1(subOp))
+ {
+ System.out.println("Specialcase1") ;
+ op = processSpecialCase1(subOp, equalities) ;
+
+ }
+ else
+ {
+ if ( ! safeToTransform(varsMentioned, subOp) )
+ return super.transform(opFilter, subOp) ;
+ op = subOp ;
+ for ( Pair<Var, NodeValue> equalityTest : equalities )
+ op = processFilterWorker(op, equalityTest.getLeft(), equalityTest.getRight()) ;
+ }
+ // ---- Place any filter expressions around the processed sub op.
+ if ( remaining.size() > 0 )
+ op = OpFilter.filter(remaining, op) ;
+ return op ;
+ }
+
+ // --- find and extract
+ private static Pair<List<Pair<Var, NodeValue>>, ExprList> preprocessFilterEquality(ExprList exprs)
+ {
+ List<Pair<Var, NodeValue>> exprsFilterEquality = new ArrayList<Pair<Var, NodeValue>>() ;
+ ExprList exprsOther = new ExprList() ;
for ( Expr e : exprs.getList() )
{
- Op op2 = processFilterWorker(e, op, patternVars) ;
- if ( op2 == null )
- exprs2.add(e) ;
+ Pair<Var, NodeValue> p = preprocess(e) ;
+ if ( p != null )
+ exprsFilterEquality.add(p) ;
else
- op = op2 ;
+ exprsOther.add(e) ;
}
-
- // Place any filter expressions around the processed sub op.
- if ( exprs2.size() > 0 )
- op = OpFilter.filter(exprs2, op) ;
- return op ;
+ if ( exprsFilterEquality.size() == 0 )
+ return null ;
+ return Pair.create(exprsFilterEquality, exprsOther) ;
}
- /** Return an optimized filter for equality expressions */
- public static Op processFilterOrOpFilter(Expr e, Op subOp)
+ private static Pair<Var, NodeValue> preprocess(Expr e)
{
- Op op2 = processFilterWorker(e, subOp, null) ;
- if ( op2 == null )
- op2 = OpFilter.filter(e, subOp) ;
- return op2 ;
+ if ( !(e instanceof E_Equals) && !(e instanceof E_SameTerm) )
+ return null ;
+
+ ExprFunction2 eq = (ExprFunction2)e ;
+ Expr left = eq.getArg1() ;
+ Expr right = eq.getArg2() ;
+
+ Var var = null ;
+ NodeValue constant = null ;
+
+ if ( left.isVariable() && right.isConstant() )
+ {
+ var = left.asVar() ;
+ constant = right.getConstant() ;
+ }
+ else if ( right.isVariable() && left.isConstant() )
+ {
+ var = right.asVar() ;
+ constant = left.getConstant() ;
+ }
+
+ if ( var == null || constant == null )
+ return null ;
+
+ // Corner case: sameTerm is false for string/plain literal,
+ // but true in the graph for graph matching.
+ if (e instanceof E_SameTerm)
+ {
+ if ( ! ARQ.isStrictMode() && constant.isString() )
+ return null ;
+ }
+
+ // Final check for "=" where a FILTER = can do value matching when the graph does not.
+ if ( e instanceof E_Equals )
+ {
+ // Value based?
+ if ( ! ARQ.isStrictMode() && constant.isLiteral() )
+ return null ;
+ }
+
+ return Pair.create(var, constant) ;
}
-
- private static boolean safeToTransform(Expr expr, Op op)
+
+ private Collection<Var> varsMentionedInEqualityFilters(List<Pair<Var, NodeValue>> equalities)
{
- return safeToTransform(new ExprList(expr), op) ;
+ List<Var> vars = new ArrayList<Var>() ;
+ for ( Pair<Var, NodeValue> p : equalities )
+ vars.add(p.getLeft()) ;
+ return vars ;
}
-
- private static boolean safeToTransform(ExprList exprs, Op op)
+
+ private static boolean safeToTransform(Collection<Var> varsEquality, Op op)
{
if ( op instanceof OpBGP || op instanceof OpQuadPattern )
return true ;
@@ -106,7 +165,7 @@ public class TransformFilterEquality2 ex
OpN opN = (OpN)op ;
for ( Op subOp : opN.getElements() )
{
- if ( ! safeToTransform(exprs, subOp) )
+ if ( ! safeToTransform(varsEquality, subOp) )
return false ;
}
return true ;
@@ -115,7 +174,7 @@ public class TransformFilterEquality2 ex
if ( op instanceof OpJoin || op instanceof OpUnion)
{
Op2 op2 = (Op2)op ;
- return safeToTransform(exprs, op2.getLeft()) && safeToTransform(exprs, op2.getRight()) ;
+ return safeToTransform(varsEquality, op2.getLeft()) && safeToTransform(varsEquality, op2.getRight()) ;
}
// Not safe unless filter variables are mentioned on the LHS.
@@ -123,128 +182,118 @@ public class TransformFilterEquality2 ex
{
Op2 opleftjoin = (Op2)op ;
- if ( ! safeToTransform(exprs, opleftjoin.getLeft()) ||
- ! safeToTransform(exprs, opleftjoin.getRight()) )
+ if ( ! safeToTransform(varsEquality, opleftjoin.getLeft()) ||
+ ! safeToTransform(varsEquality, opleftjoin.getRight()) )
return false ;
- Op opLeft = opleftjoin.getLeft() ;
- // Special case: { OPTIONAL {...} }
-// if ( isUnitTable(opLeft) )
-// return true ;
-
- //Op opRight = opleftjoin.getRight() ;
- // See also transform condition for OpConditional transformation.
-
- Set<Var> varsLeft = OpVars.patternVars(opLeft) ;
- //Set<Var> varsRight = OpVars.patternVars(opRight) ;
- Set<Var> y = ExprVars.getVarsMentioned(exprs) ;
+ // Not only must the left and right be safe to transform,
+ // but the equality variable must be known to be always set.
// If the varsLeft are disjoint from assigned vars,
// we may be able to push assign down right
- // (generalises the unit table case above)
- // Needs more investigation
+ // (this generalises the unit table case specialcase1)
+ // Needs more investigation.
-// if ( SetUtils.isDisjoint(varsLeft, y) ||
-// varsLeft.containsAll(y) )
- if ( varsLeft.containsAll(y) )
+ Op opLeft = opleftjoin.getLeft() ;
+ Set<Var> varsLeft = OpVars.patternVars(opLeft) ;
+ if ( varsLeft.containsAll(varsEquality) )
return true ;
return false ;
- }
+ }
if ( op instanceof OpGraph )
{
OpGraph opg = (OpGraph)op ;
- return safeToTransform(exprs, opg.getSubOp()) ;
+ return safeToTransform(varsEquality, opg.getSubOp()) ;
}
- if (isUnitTable(op) )
- return true;
-
return false ;
}
- private static boolean isUnitTable(Op op)
+ private static boolean testSpecialCase1(Op op)
{
- if (op instanceof OpTable )
+ while ( op instanceof OpConditional || op instanceof OpLeftJoin )
{
- if ( ((OpTable)op).isJoinIdentity() )
- return true;
+ Op2 opleftjoin2 = (Op2)op ;
+ op = opleftjoin2.getLeft() ;
}
- return false ;
+ return isUnitTable(op) ;
}
-
- // ++ called by TransformFilterDisjunction
- /** Return null for "no change" */
- public static Op processFilter(Expr e, Op subOp)
+ static class TransformSpecialCase1 extends TransformCopy
{
- if ( ! safeToTransform(e, subOp) )
- return null ;
- return processFilterWorker(e, subOp, null) ;
+ @Override public Op transform(OpLeftJoin op, Op left, Op right)
+ {
+ return worker(op, left, right) ;
+ }
+
+ @Override public Op transform(OpConditional op, Op left, Op right)
+ {
+ return worker(op, left, right) ;
+ }
+
+ private Op worker(Op2 op, Op left, Op right)
+ {
+ if ( left instanceof OpTable )
+ return right ;
+ return op.copy(left, right) ;
+ }
}
+
+ static TransformSpecialCase1 tsc1 = new TransformSpecialCase1() ;
- private static Op processFilterWorker(Expr e, Op subOp, Set<Var> patternVars)
+ private Op processSpecialCase1(Op op, List<Pair<Var, NodeValue>> equalities)
{
- if ( patternVars == null )
- patternVars = OpVars.patternVars(subOp) ;
- // Rewrites:
- // FILTER ( ?x = ?y )
- // FILTER ( ?x = :x ) for IRIs and bNodes, not literals
- // (to preserve value testing in the filter, and not in the graph).
- // FILTER ( sameTerm(?x, :x ) ) etc
+ Op opx = Transformer.transform(tsc1, op) ;
+ System.out.println(opx) ;
+ throw new ARQNotImplemented("TransformFilterEquality.processSpecialCase1") ;
- if ( !(e instanceof E_Equals) && !(e instanceof E_SameTerm) )
- return null ;
-
- // Corner case: sameTerm is false for string/plain literal,
- // but true in the graph for graphs with
+ //Step one - find base of chain.
- ExprFunction2 eq = (ExprFunction2)e ;
- Expr left = eq.getArg1() ;
- Expr right = eq.getArg2() ;
-
- Var var = null ;
- NodeValue constant = null ;
+ //return null ;
+ }
- if ( left.isVariable() && right.isConstant() )
- {
- var = left.asVar() ;
- constant = right.getConstant() ;
- }
- else if ( right.isVariable() && left.isConstant() )
+ private static boolean isUnitTable(Op op)
+ {
+ if (op instanceof OpTable )
{
- var = right.asVar() ;
- constant = left.getConstant() ;
+ if ( ((OpTable)op).isJoinIdentity() )
+ return true;
}
-
- if ( var == null || constant == null )
+ return false ;
+ }
+
+ // ---- Transformation
+
+// /** Return an optimized filter for equality expressions */
+// public static Op processFilterOrOpFilter(Op op, Pair<Var, NodeValue> equality)
+// {
+// Op op2 = processFilterWorker(op, equality) ;
+// if ( op2 == null )
+// op2 = OpFilter.filter(e, op) ;
+// return op2 ;
+// }
+
+ // ++ called by TransformFilterDisjunction
+ /** Return null for "no change" */
+ public static Op processFilter(Expr e, Op op)
+ {
+ Pair<Var, NodeValue> p = preprocess(e) ;
+ if ( p == null )
return null ;
- if ( !patternVars.contains(var) )
- // The underlying op does not define the variable.
- // The filter will fail. Could remove all together.
- //return OpTable.empty() ;
- // For now, play safe in this (rare?) case.
+ // TODO Special case 1
+ List<Var> x = Arrays.asList(p.getLeft()) ;
+ if ( ! safeToTransform(x, op) )
return null ;
-
- // Corner case: sameTerm is false for string/plain literal,
- // but true in the graph for graph matching.
- if (e instanceof E_SameTerm)
- {
- if ( ! ARQ.isStrictMode() && constant.isString() )
- return null ;
- }
-
- // Final check for "=" where a FILTER = can do value matching when the graph does not.
- if ( e instanceof E_Equals )
- {
- // Value based?
- // XXX Optimize here.
- if ( ! ARQ.isStrictMode() && constant.isLiteral() )
- return null ;
- }
+ List<Pair<Var, NodeValue>> y = Arrays.asList(p) ;
+ return processFilterWorker(op, p.getLeft(), p.getRight()) ;
+ }
- return subst(subOp, var, constant) ;
+ private static Op processFilterWorker(Op op, Var var, NodeValue constant)
+ {
+ // unit table case.
+ return subst(op, var, constant) ;
}
private static Op subst(Op subOp , Var var, NodeValue nv)