Menu
▾
▴
[Bigdata-commit] SF.net SVN: bigdata:[7964] branches/RDR
|
From: <tho...@us...> - 2014-03-14 15:05:28
|
Revision: 7964
http://sourceforge.net/p/bigdata/code/7964
Author: thompsonbry
Date: 2014-03-14 15:05:24 +0000 (Fri, 14 Mar 2014)
Log Message:
-----------
Checkpoint on refactor to support RDR style constraint on the link attribute type to be visited by the GAS algorithm.
There is a known problem (http://trac.bigdata.com/ticket/851) where the RDR link attribute statements are not correctly decomposed. This causes visitation algorithms which impose the link attribute type constraint to fail. #851 lays out the issue and the approach for a fix.
See #810 (Expose GAS as a SERVICE).
Modified Paths:
--------------
branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/IGASContext.java
branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/impl/GASContext.java
branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/impl/ram/RAMGASEngine.java
branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/impl/sail/SAILGASEngine.java
branches/RDR/bigdata-rdf/src/java/com/bigdata/rdf/graph/impl/bd/BigdataGASEngine.java
branches/RDR/bigdata-rdf/src/test/com/bigdata/rdf/graph/impl/bd/TestSSSP.java
Added Paths:
-----------
branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/impl/EdgeOnlyFilter.java
Modified: branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/IGASContext.java
===================================================================
--- branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/IGASContext.java 2014-03-14 00:44:09 UTC (rev 7963)
+++ branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/IGASContext.java 2014-03-14 15:05:24 UTC (rev 7964)
@@ -21,8 +21,6 @@
import org.openrdf.model.URI;
import org.openrdf.model.Value;
-import cutthecrap.utils.striterators.IStriterator;
-
/**
* Execution context for an {@link IGASProgram}. This is distinct from the
* {@link IGASEngine} so we can support distributed evaluation and concurrent
@@ -176,23 +174,23 @@
*/
<T> IReducer<VS, ES, ST, T> getRunAfterOp();
- /**
- * Hook to impose a constraint on the visited edges and/or property values.
- *
- * @param itr
- * The iterator visiting those edges and/or property values.
- *
- * @return Either the same iterator or a constrained iterator.
- *
- * TODO Rename as constrainEdgeFilter or even split into a
- * constrainGatherFilter and a constraintScatterFilter.
- *
- * TODO APPLY : If we need access to the vertex property values in
- * APPLY (which we probably do, at least optionally), then perhaps
- * there should be a similar method to decide whether the property
- * values for the vertex are made available during the APPLY.
- */
- IStriterator constrainFilter(IStriterator eitr);
+// /**
+// * Hook to impose a constraint on the visited edges and/or property values.
+// *
+// * @param itr
+// * The iterator visiting those edges and/or property values.
+// *
+// * @return Either the same iterator or a constrained iterator.
+// *
+// * TODO Split into a constrainGatherFilter and a
+// * constraintScatterFilter?
+// *
+// * TODO APPLY : If we need access to the vertex property values in
+// * APPLY (which we probably do, at least optionally), then perhaps
+// * there should be a similar method to decide whether the property
+// * values for the vertex are made available during the APPLY.
+// */
+// IStriterator getConstrainEdgeFilter(IStriterator eitr);
/**
* Execute one iteration.
Added: branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/impl/EdgeOnlyFilter.java
===================================================================
--- branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/impl/EdgeOnlyFilter.java (rev 0)
+++ branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/impl/EdgeOnlyFilter.java 2014-03-14 15:05:24 UTC (rev 7964)
@@ -0,0 +1,49 @@
+/**
+ Copyright (C) SYSTAP, LLC 2006-2012. All rights reserved.
+
+ Licensed 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.bigdata.rdf.graph.impl;
+
+import org.openrdf.model.Statement;
+
+import com.bigdata.rdf.graph.IGASContext;
+import com.bigdata.rdf.graph.IGASState;
+
+import cutthecrap.utils.striterators.Filter;
+
+/**
+ * Filter visits only edges (filters out attribute values).
+ * <p>
+ * Note: This filter is pushed down onto the AP and evaluated close to the data.
+ */
+public class EdgeOnlyFilter<VS, ES, ST> extends Filter {
+
+ private static final long serialVersionUID = 1L;
+
+ private final IGASState<VS, ES, ST> gasState;
+
+ public EdgeOnlyFilter(final IGASContext<VS, ES, ST> ctx) {
+
+ this.gasState = ctx.getGASState();
+
+ }
+
+ @Override
+ public boolean isValid(final Object e) {
+
+ return gasState.isEdge((Statement) e);
+
+ }
+
+}
Modified: branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/impl/GASContext.java
===================================================================
--- branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/impl/GASContext.java 2014-03-14 00:44:09 UTC (rev 7963)
+++ branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/impl/GASContext.java 2014-03-14 15:05:24 UTC (rev 7964)
@@ -40,7 +40,6 @@
import cutthecrap.utils.striterators.Filter;
import cutthecrap.utils.striterators.IFilter;
-import cutthecrap.utils.striterators.IStriterator;
public class GASContext<VS, ES, ST> implements IGASContext<VS, ES, ST> {
@@ -857,48 +856,48 @@
}
- /**
- * {@inheritDoc}
- * <p>
- * The default implementation only visits the edges.
- */
- @Override
- public IStriterator constrainFilter(final IStriterator itr) {
+// /**
+// * {@inheritDoc}
+// * <p>
+// * The default implementation only visits the edges.
+// */
+// @Override
+// public IStriterator getConstrainEdgeFilter(final IStriterator itr) {
+//
+// return itr.addFilter(getEdgeOnlyFilter());
+//
+// }
- return itr.addFilter(getEdgeOnlyFilter());
-
- }
-
- /**
- * Return an {@link IFilter} that will only visit the edges of the graph.
- *
- * @see IGASState#isEdge(Statement)
- */
- protected IFilter getEdgeOnlyFilter() {
-
- return new EdgeOnlyFilter(this);
-
- }
+// /**
+// * Return an {@link IFilter} that will only visit the edges of the graph.
+// *
+// * @see IGASState#isEdge(Statement)
+// */
+// protected IFilter getEdgeOnlyFilter() {
+//
+// return new EdgeOnlyFilter(this);
+//
+// }
+//
+// /**
+// * Filter visits only edges (filters out attribute values).
+// * <p>
+// * Note: This filter is pushed down onto the AP and evaluated close to the
+// * data.
+// */
+// private class EdgeOnlyFilter extends Filter {
+// private static final long serialVersionUID = 1L;
+// private final IGASState<VS, ES, ST> gasState;
+// private EdgeOnlyFilter(final IGASContext<VS, ES, ST> ctx) {
+// this.gasState = ctx.getGASState();
+// }
+// @Override
+// public boolean isValid(final Object e) {
+// return gasState.isEdge((Statement) e);
+// }
+// };
/**
- * Filter visits only edges (filters out attribute values).
- * <p>
- * Note: This filter is pushed down onto the AP and evaluated close to the
- * data.
- */
- private class EdgeOnlyFilter extends Filter {
- private static final long serialVersionUID = 1L;
- private final IGASState<VS, ES, ST> gasState;
- private EdgeOnlyFilter(final IGASContext<VS, ES, ST> ctx) {
- this.gasState = ctx.getGASState();
- }
- @Override
- public boolean isValid(final Object e) {
- return gasState.isEdge((Statement) e);
- }
- };
-
- /**
* Return a filter that only visits the edges of graph that are instances of
* the specified link attribute type.
* <p>
Modified: branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/impl/ram/RAMGASEngine.java
===================================================================
--- branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/impl/ram/RAMGASEngine.java 2014-03-14 00:44:09 UTC (rev 7963)
+++ branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/impl/ram/RAMGASEngine.java 2014-03-14 15:05:24 UTC (rev 7964)
@@ -33,6 +33,7 @@
import com.bigdata.rdf.graph.EdgesEnum;
import com.bigdata.rdf.graph.IGASContext;
import com.bigdata.rdf.graph.IGraphAccessor;
+import com.bigdata.rdf.graph.impl.EdgeOnlyFilter;
import com.bigdata.rdf.graph.impl.GASEngine;
import com.bigdata.rdf.graph.impl.util.VertexDistribution;
@@ -349,7 +350,10 @@
/*
* Optionally wrap the program specified filter.
*/
- return ctx.constrainFilter(sitr);
+// return ctx.getConstrainEdgeFilter(sitr);
+ sitr.addFilter(new EdgeOnlyFilter(ctx));
+
+ return sitr;
}
Modified: branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/impl/sail/SAILGASEngine.java
===================================================================
--- branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/impl/sail/SAILGASEngine.java 2014-03-14 00:44:09 UTC (rev 7963)
+++ branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/impl/sail/SAILGASEngine.java 2014-03-14 15:05:24 UTC (rev 7964)
@@ -32,6 +32,7 @@
import com.bigdata.rdf.graph.EdgesEnum;
import com.bigdata.rdf.graph.IGASContext;
import com.bigdata.rdf.graph.IGraphAccessor;
+import com.bigdata.rdf.graph.impl.EdgeOnlyFilter;
import com.bigdata.rdf.graph.impl.GASEngine;
import com.bigdata.rdf.graph.impl.util.VertexDistribution;
@@ -238,8 +239,11 @@
* striterators is just as efficient.)
*/
- return ctx.constrainFilter(sitr);
+// return ctx.getConstrainEdgeFilter(sitr);
+ sitr.addFilter(new EdgeOnlyFilter(ctx));
+ return sitr;
+
}
@Override
Modified: branches/RDR/bigdata-rdf/src/java/com/bigdata/rdf/graph/impl/bd/BigdataGASEngine.java
===================================================================
--- branches/RDR/bigdata-rdf/src/java/com/bigdata/rdf/graph/impl/bd/BigdataGASEngine.java 2014-03-14 00:44:09 UTC (rev 7963)
+++ branches/RDR/bigdata-rdf/src/java/com/bigdata/rdf/graph/impl/bd/BigdataGASEngine.java 2014-03-14 15:05:24 UTC (rev 7964)
@@ -31,6 +31,7 @@
import com.bigdata.rdf.graph.IGASState;
import com.bigdata.rdf.graph.IGraphAccessor;
import com.bigdata.rdf.graph.IStaticFrontier;
+import com.bigdata.rdf.graph.impl.EdgeOnlyFilter;
import com.bigdata.rdf.graph.impl.GASEngine;
import com.bigdata.rdf.graph.impl.util.VertexDistribution;
import com.bigdata.rdf.internal.IV;
@@ -385,7 +386,8 @@
* test to verify expected benefit. Watch out for the in-edges
* vs out-edges since only one is optimized.
*/
- posOptimization = linkTypeIV != null && inEdges;
+ posOptimization = linkTypeIV != null && linkAttrTypeIV == null
+ && inEdges;
if (posOptimization) {
@@ -401,62 +403,20 @@
keyBuilder.reset();
-// if (linkAttrTypeIV != null) {
-//
-// /*
-// * RDR optimization for POS(C) index:
-// *
-// * P:= linkAttributeType
-// *
-// * O:= unbound (the SID is in SPO(C) order, but we do
-// * not have S. P would be the linkType, but without S we
-// * can not form a prefix).
-// *
-// * S:= unbound
-// *
-// * C:= unbound
-// *
-// * Note: We can only optimize this when both the
-// * linkType and linkAttributeType are specified.
-// */
-//
-// // P
-// IVUtility.encode(keyBuilder, linkAttrTypeIV);
-//
-// // O is a SID prefix.
-// {
-//
-// // RDR prefix byte.
-// keyBuilder.append(SidIV.toFlags());
-//
-// // SID.P:=linkType
-// IVUtility.encode(keyBuilder, linkTypeIV);
-//
-// // SID.O:=u
-// IVUtility.encode(keyBuilder, u);
-//
-// }
-//
-// // The rest of the key is unbound.
-//
-// } else {
+ // Bind P as a constant.
+ IVUtility.encode(keyBuilder, linkTypeIV);
- // Bind P as a constant.
- IVUtility.encode(keyBuilder, linkTypeIV);
+ // Bind O for this key-range scan.
+ IVUtility.encode(keyBuilder, u);
- // Bind O for this key-range scan.
- IVUtility.encode(keyBuilder, u);
-
-// }
-
} else {
/*
* SPO(C) or OSP(C)
*
- * FIXME RDR: For RDR link attribute access, the keys are
- * formed differently. Lower case letters are used for
- * variables. Upper case letters for constants.
+ * Note: For RDR link attribute access, the keys are formed
+ * differently. Lower case letters are used for variables.
+ * Upper case letters for constants.
*
* For SPO(C): S:=SID(Spo(c)), P:=linkAttributeType (must
* filter), O:=linkAttributeValue (read it off the index
@@ -466,9 +426,9 @@
* filter), S:=linkAttributeValue (read it off the index
* when the filter is satisfied).
*
- * FIXME RDR should also be supported in the SAIL and RAM
- * GAS engine implementations. The statements about
- * statements would be modeled as reified statement models.
+ * TODO RDR should also be supported in the SAIL and RAM GAS
+ * engine implementations. The statements about statements
+ * would be modeled as reified statement models.
*/
keyOrder = getKeyOrder(kb, inEdges);
@@ -478,7 +438,18 @@
keyBuilder = ndx.getIndexMetadata().getKeyBuilder();
keyBuilder.reset();
+
+ if (linkAttrTypeIV != null) {
+
+ /*
+ * Restrict to the SID region of the index. See
+ * SidIV.encode().
+ */
+ keyBuilder.appendSigned(SidIV.toFlags());
+
+ }
+ // Append [u] to the key.
IVUtility.encode(keyBuilder, u);
}
@@ -557,32 +528,100 @@
if (linkTypeIV != null && !posOptimization) {
/*
- * A link type constraint was specified, but we were not able to
- * use the POS(C) index optimization. In this case we have to
- * add a filter to impose that link type constraint.
+ * A link type constraint was specified, but we were not
+ * able to use the POS(C) index optimization. In this case
+ * we have to add a filter to impose that link type
+ * constraint.
*/
+ if (linkAttrTypeIV == null) {
+ /*
+ * The linkTypeIV is the Predicate.
+ */
+ sitr.addFilter(new Filter() {
+ private static final long serialVersionUID = 1L;
+
+ @Override
+ public boolean isValid(final Object e) {
+ return ((ISPO) e).p().equals(linkTypeIV);
+ }
+ });
+ } else {
+ /*
+ * The linkTypeIV is part of the SIDIV of the Subject.
+ */
+ sitr.addFilter(new Filter() {
+ private static final long serialVersionUID = 1L;
+ @Override
+ public boolean isValid(final Object e) {
+ final SidIV<?> subj = (SidIV<?>) ((ISPO) e).s();
+ final ISPO linkAttr = subj.getInlineValue();
+ final IV<?, ?> p = linkAttr.p();
+ final boolean matched = p.equals(linkTypeIV);
+ return matched;
+ }
+ });
+ }
+ }
+
+ if (linkAttrTypeIV != null) {
+ /*
+ * A link attribute type constraint was specified.
+ */
sitr.addFilter(new Filter() {
private static final long serialVersionUID = 1L;
@Override
public boolean isValid(final Object e) {
- return ((ISPO) e).p().equals(linkTypeIV);
+ final IV<?,?> p = ((ISPO) e).p();
+ final boolean matched = p.equals(linkAttrTypeIV);
+ return matched;
}
});
}
- /*
- * Optionally wrap the specified filter. This filter will be
- * pushed down onto the index. If the index is remote, then this
- * is much more efficient. (If the index is local, then simply
- * stacking striterators is just as efficient.)
- */
+ if (linkTypeIV == null && linkAttrTypeIV == null) {
- return ctx.constrainFilter(sitr);
+ /*
+ * Wrap the iterator with a filter that will exclude any
+ * non-link Statements.
+ *
+ * Note: This is handled automatically by the fromkey, toKey
+ * constraint if the linkTypeIV is specified.
+ *
+ * TODO This is NOT handled automatically by the fromKey,
+ * toKey constraint if the linkAttrTypeIV is specified. In
+ * fact, it might not be handled.
+ */
+
+ sitr.addFilter(new EdgeOnlyFilter(ctx));
+ }
+
+ return sitr;
+
+// /*
+// * Optionally wrap the specified filter. This filter will be
+// * pushed down onto the index. If the index is remote, then this
+// * is much more efficient. (If the index is local, then simply
+// * stacking striterators is just as efficient.)
+// */
+//
+// return ctx.getConstrainEdgeFilter(sitr);
+
}
} // class AP
+// /**
+// * Return an {@link IFilter} that will only visit the edges of the graph.
+// *
+// * @see IGASState#isEdge(Statement)
+// */
+// protected IFilter getEdgeOnlyFilter() {
+//
+// return new EdgeOnlyFilter(this);
+//
+// }
+
@SuppressWarnings({ "rawtypes" })
private IStriterator getEdges(final AbstractTripleStore kb,
final boolean inEdges, final IGASContext<?, ?, ?> ctx,
@@ -601,7 +640,7 @@
}
- @SuppressWarnings({ "unchecked", "rawtypes" })
+ @SuppressWarnings("unchecked")
@Override
public Iterator<Statement> getEdges(final IGASContext<?, ?, ?> ctx,
final Value u, final EdgesEnum edges) {
Modified: branches/RDR/bigdata-rdf/src/test/com/bigdata/rdf/graph/impl/bd/TestSSSP.java
===================================================================
--- branches/RDR/bigdata-rdf/src/test/com/bigdata/rdf/graph/impl/bd/TestSSSP.java 2014-03-14 00:44:09 UTC (rev 7963)
+++ branches/RDR/bigdata-rdf/src/test/com/bigdata/rdf/graph/impl/bd/TestSSSP.java 2014-03-14 15:05:24 UTC (rev 7964)
@@ -175,6 +175,7 @@
// Converge.
gasContext.call();
+ // Check weighted distance.
assertEquals(0, gasState.getState(p.getV1()).dist());
assertEquals(100, gasState.getState(p.getV2()).dist());
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
