Menu
▾
▴
[Bigdata-commit] SF.net SVN: bigdata:[7882] branches/RDR
|
From: <tho...@us...> - 2014-02-24 13:47:32
|
Revision: 7882
http://sourceforge.net/p/bigdata/code/7882
Author: thompsonbry
Date: 2014-02-24 13:47:27 +0000 (Mon, 24 Feb 2014)
Log Message:
-----------
Added a link attribute type constraint as part of the RDR support. This constraint is not yet integrated into the BigdataGASEngine. It is exposed to the GASService and can be set, but it is currently ignored.
There is now a unit test for scatter out edges with the link type constraint.
The test for the link attribute access is stil failing since that feature has not yet been implemented in the BigdataGASEngine.
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-rdf/src/java/com/bigdata/rdf/graph/impl/bd/BigdataGASEngine.java
branches/RDR/bigdata-rdf/src/java/com/bigdata/rdf/graph/impl/bd/GASService.java
branches/RDR/bigdata-rdf/src/test/com/bigdata/rdf/graph/impl/bd/AbstractBigdataGraphTestCase.java
branches/RDR/bigdata-rdf/src/test/com/bigdata/rdf/graph/impl/bd/TestSSSP.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-02-24 13:41:17 UTC (rev 7881)
+++ branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/IGASContext.java 2014-02-24 13:47:27 UTC (rev 7882)
@@ -116,13 +116,11 @@
* @return The {@link Value} for the predicate that identifies the desired
* link type (there can be many types of links - the return value
* specifies which attribute is of interest).
- *
- * FIXME define getLinkAttribType() (RDR)
*/
URI getLinkType();
/**
- * Set an optional constraint on the type of the visited links.
+ * Set an optional restriction on the type of the visited links.
* <p>
* Note: When this option is used, the scatter and gather will not visit the
* property set for the vertex. Instead, the graph is treated as if it were
@@ -136,6 +134,32 @@
void setLinkType(URI linkType);
/**
+ * Return non-<code>null</code> iff there is a single link attribute type to
+ * be visited. This imposes a restriction on which link attributes are
+ * considered by the algorithm. The link attribute type restriction may be
+ * (and often is) paired with a link type restriction.
+ *
+ * @return The {@link Value} for the predicate that identifies the desired
+ * link attribute type.
+ *
+ * @see #setLinkType(URI)
+ */
+ URI getLinkAttributeType();
+
+ /**
+ * Imposes an optional restriction on which link attributes are considered
+ * by the algorithm. The link attribute type restriction may be (and often
+ * is) paired with a link type restriction.
+ *
+ * @param linkAttributeType
+ * The link attribute type to visit (optional). When
+ * <code>null</code>, the link attributes for the visited links
+ * are NOT visited (the topology of the graph is visited, but not
+ * the attributes for the edges).
+ */
+ void setLinkAttributeType(URI linkType);
+
+ /**
* Set an optional {@link IReducer} that will run after the
* {@link IGASProgram} is terminated. This may be used to extract results
* from the visited vertices.
@@ -163,10 +187,10 @@
* TODO Rename as constrainEdgeFilter or even split into a
* constrainGatherFilter and a constraintScatterFilter.
*
- * FIXME APPLY : If we need access to the vertex property values in
- * APPLY (which we probably do, at least optionally), then there
- * should be a similar method to decide whether the property values
- * for the vertex are made available during the APPLY.
+ * 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);
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-02-24 13:41:17 UTC (rev 7881)
+++ branches/RDR/bigdata-gas/src/java/com/bigdata/rdf/graph/impl/GASContext.java 2014-02-24 13:47:27 UTC (rev 7882)
@@ -81,6 +81,11 @@
private final AtomicReference<URI> linkType = new AtomicReference<URI>(null);
/**
+ * An optional constraint on the type of the visited link attributes.
+ */
+ private final AtomicReference<URI> linkAttributeType = new AtomicReference<URI>(null);
+
+ /**
* An optional {@link IReducer} that will executed after the
* {@link IGASProgram}.
*/
@@ -824,12 +829,6 @@
}
- /**
- * {@inheritDoc}
- * <p>
- * The default implementation does not restrict the visitation to a
- * connectivity matrix (returns <code>null</code>).
- */
@Override
public URI getLinkType() {
@@ -844,6 +843,20 @@
}
+ @Override
+ public URI getLinkAttributeType() {
+
+ return linkAttributeType.get();
+
+ }
+
+ @Override
+ public void setLinkAttributeType(final URI linkAttributeType) {
+
+ this.linkAttributeType.set(linkAttributeType);
+
+ }
+
/**
* {@inheritDoc}
* <p>
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-02-24 13:41:17 UTC (rev 7881)
+++ branches/RDR/bigdata-rdf/src/java/com/bigdata/rdf/graph/impl/bd/BigdataGASEngine.java 2014-02-24 13:47:27 UTC (rev 7882)
@@ -36,6 +36,7 @@
import com.bigdata.rdf.internal.IV;
import com.bigdata.rdf.internal.IVUtility;
import com.bigdata.rdf.internal.NotMaterializedException;
+import com.bigdata.rdf.internal.impl.bnode.SidIV;
import com.bigdata.rdf.model.BigdataValue;
import com.bigdata.rdf.sail.BigdataSail;
import com.bigdata.rdf.spo.ISPO;
@@ -348,6 +349,7 @@
private final IV u;
// ctor (computed)
private final IV linkTypeIV;
+ private final IV linkAttrTypeIV;
private final boolean posOptimization;
private final SPOKeyOrder keyOrder;
private final IIndex ndx;
@@ -364,6 +366,8 @@
this.u = u;
linkTypeIV = getIV(ctx.getLinkType());
+
+ linkAttrTypeIV = getIV(ctx.getLinkAttributeType());
final IKeyBuilder keyBuilder;
/*
@@ -376,7 +380,7 @@
* We use the POS(C) index. The S values give us the in-edges
* for that [u] and the specified link type.
*
- * FIXME POS OPTIMIZATION: write unit test for this option to
+ * TODO POS OPTIMIZATION: write unit test for this option to
* make sure that the right filter is imposed. write performance
* test to verify expected benefit. Watch out for the in-edges
* vs out-edges since only one is optimized.
@@ -397,16 +401,74 @@
keyBuilder.reset();
- // Bind P as a constant.
- IVUtility.encode(keyBuilder, linkTypeIV);
+// 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 O for this key-range scan.
- IVUtility.encode(keyBuilder, u);
+ // Bind P as a constant.
+ IVUtility.encode(keyBuilder, linkTypeIV);
+ // 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.
+ *
+ * For SPO(C): S:=SID(Spo(c)), P:=linkAttributeType (must
+ * filter), O:=linkAttributeValue (read it off the index
+ * when the filter is satisfied).
+ *
+ * For OSP(C): OL=SID(Osp(c)), P:=linkAttributeType (must
+ * 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.
*/
keyOrder = getKeyOrder(kb, inEdges);
Modified: branches/RDR/bigdata-rdf/src/java/com/bigdata/rdf/graph/impl/bd/GASService.java
===================================================================
--- branches/RDR/bigdata-rdf/src/java/com/bigdata/rdf/graph/impl/bd/GASService.java 2014-02-24 13:41:17 UTC (rev 7881)
+++ branches/RDR/bigdata-rdf/src/java/com/bigdata/rdf/graph/impl/bd/GASService.java 2014-02-24 13:47:27 UTC (rev 7882)
@@ -217,9 +217,19 @@
*
* @see IGASContext#setLinkType(URI)
*/
- URI LINK_TYPE = new URIImpl(NAMESPACE+"linkType");
-
+ URI LINK_TYPE = new URIImpl(NAMESPACE + "linkType");
+
/**
+ * An optional constraint on the types of the link attributes that will
+ * be visited by the algorithm - the use of this option is required if
+ * you want to process some specific link weight rather than the simple
+ * topology of the graph.
+ *
+ * @see IGASContext#setLinkAttributeType(URI)
+ */
+ URI LINK_ATTR_TYPE = new URIImpl(NAMESPACE + "linkAttrType");
+
+ /**
* The {@link IGASScheduler} (default is {@link #DEFAULT_SCHEDULER}).
* Class must implement {@link IGASSchedulerImpl}.
*/
@@ -367,7 +377,7 @@
private final int nthreads;
private final int maxIterations;
private final int maxVisited;
- private final URI linkType;
+ private final URI linkType, linkAttrType;
private final Class<IGASProgram<VS, ES, ST>> gasClass;
private final Class<IGASSchedulerImpl> schedulerClass;
private final Value[] initialFrontier;
@@ -412,6 +422,9 @@
this.linkType = (URI) getOnlyArg(Options.PROGRAM,
Options.LINK_TYPE, null/* default */);
+ this.linkAttrType = (URI) getOnlyArg(Options.PROGRAM,
+ Options.LINK_ATTR_TYPE, null/* default */);
+
// GASProgram (required)
{
@@ -719,9 +732,14 @@
gasContext.setMaxVisited(maxVisited);
+ // Optional link type constraint.
if (linkType != null)
gasContext.setLinkType(linkType);
+ // Optional link attribute constraint.
+ if (linkAttrType != null)
+ gasContext.setLinkAttributeType(linkAttrType);
+
final IGASState<VS, ES, ST> gasState = gasContext.getGASState();
// TODO We should look at this when extracting the parameters from the SERVICE's graph pattern.
Modified: branches/RDR/bigdata-rdf/src/test/com/bigdata/rdf/graph/impl/bd/AbstractBigdataGraphTestCase.java
===================================================================
--- branches/RDR/bigdata-rdf/src/test/com/bigdata/rdf/graph/impl/bd/AbstractBigdataGraphTestCase.java 2014-02-24 13:41:17 UTC (rev 7881)
+++ branches/RDR/bigdata-rdf/src/test/com/bigdata/rdf/graph/impl/bd/AbstractBigdataGraphTestCase.java 2014-02-24 13:47:27 UTC (rev 7882)
@@ -204,7 +204,7 @@
*/
static private final String smallWeightedGraph = "bigdata-gas/src/test/com/bigdata/rdf/graph/data/smallWeightedGraph.ttl";
- private final BigdataURI foafKnows, v1, v2, v3, v4, v5;
+ private final BigdataURI foafKnows, linkWeight, v1, v2, v3, v4, v5;
public SmallWeightedGraphProblem() throws Exception {
@@ -216,6 +216,9 @@
foafKnows = (BigdataURI) vf
.createURI("http://xmlns.com/foaf/0.1/knows");
+
+ linkWeight = (BigdataURI) vf
+ .createURI("http://www.bigdata.com/weight");
v1 = (BigdataURI) vf.createURI("http://www.bigdata.com/1");
v2 = (BigdataURI) vf.createURI("http://www.bigdata.com/2");
@@ -223,8 +226,8 @@
v4 = (BigdataURI) vf.createURI("http://www.bigdata.com/4");
v5 = (BigdataURI) vf.createURI("http://www.bigdata.com/5");
- final BigdataValue[] terms = new BigdataValue[] { foafKnows, v1,
- v2, v3, v4, v5 };
+ final BigdataValue[] terms = new BigdataValue[] { foafKnows,
+ linkWeight, v1, v2, v3, v4, v5 };
// batch resolve existing IVs.
((BigdataSail) sail).getDatabase().getLexiconRelation()
@@ -243,6 +246,11 @@
}
@SuppressWarnings("rawtypes")
+ public IV getLinkWeight() {
+ return linkWeight.getIV();
+ }
+
+ @SuppressWarnings("rawtypes")
public IV getV1() {
return v1.getIV();
}
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-02-24 13:41:17 UTC (rev 7881)
+++ branches/RDR/bigdata-rdf/src/test/com/bigdata/rdf/graph/impl/bd/TestSSSP.java 2014-02-24 13:47:27 UTC (rev 7882)
@@ -23,6 +23,8 @@
*/
package com.bigdata.rdf.graph.impl.bd;
+import org.openrdf.model.URI;
+
import com.bigdata.rdf.graph.IGASContext;
import com.bigdata.rdf.graph.IGASEngine;
import com.bigdata.rdf.graph.IGASState;
@@ -84,7 +86,64 @@
}
/**
+ * A unit test based on graph with link weights - in this version of the
+ * test we constrain the link type but do not specify the link attribute
+ * type. Hence it ignores the link weights. This provides a test of the
+ * optimized access path when just the link type constraint is specified.
+ */
+ public void test_sssp_linkType_constraint() throws Exception {
+
+ final SmallWeightedGraphProblem p = setupSmallWeightedGraphProblem();
+
+ final IGASEngine gasEngine = getGraphFixture()
+ .newGASEngine(1/* nthreads */);
+
+ try {
+
+ final IGraphAccessor graphAccessor = getGraphFixture()
+ .newGraphAccessor(null/* ignored */);
+
+ final IGASContext<SSSP.VS, SSSP.ES, Integer> gasContext = gasEngine
+ .newGASContext(graphAccessor, new SSSP());
+
+ // Set constraint on the visited link types.
+ gasContext.setLinkType((URI) p.getFoafKnows());
+
+ final IGASState<SSSP.VS, SSSP.ES, Integer> gasState = gasContext.getGASState();
+
+ // Initialize the froniter.
+ gasState.setFrontier(gasContext, p.getV1());
+
+ // Converge.
+ gasContext.call();
+
+ assertEquals(0, gasState.getState(p.getV1()).dist());
+
+ assertEquals(1, gasState.getState(p.getV2()).dist());
+
+ assertEquals(1, gasState.getState(p.getV3()).dist());
+
+ assertEquals(2, gasState.getState(p.getV4()).dist());
+
+ assertEquals(2, gasState.getState(p.getV5()).dist());
+
+ } finally {
+
+ gasEngine.shutdownNow();
+
+ }
+
+ }
+
+ /**
* A unit test based on graph with link weights.
+ *
+ * FIXME Test with just the linkAttributeType constraint and with both a
+ * linkType and linkAttributeType constraint. (We already have a test with
+ * just the linkType constraint above).
+ *
+ * FIXME This is only testing the scatter AP. We also need to test the
+ * gather AP.
*/
public void test_sssp_weightedGraph() throws Exception {
@@ -101,6 +160,12 @@
final IGASContext<SSSP.VS, SSSP.ES, Integer> gasContext = gasEngine
.newGASContext(graphAccessor, new SSSP());
+ // Set constraint on the visited link types.
+ gasContext.setLinkType((URI) p.getFoafKnows());
+
+ // Set constraint on the visited link attribute types.
+ gasContext.setLinkAttributeType((URI) p.getLinkWeight());
+
final IGASState<SSSP.VS, SSSP.ES, Integer> gasState = gasContext.getGASState();
// Initialize the froniter.
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
