com.bigdata.rdf.graph.impl

Class GASState<VS,ES,ST>

java.lang.Object

com.bigdata.rdf.graph.impl.GASState<VS,ES,ST>

All Implemented Interfaces:

IGASState<VS,ES,ST>

Direct Known Subclasses:

BigdataGASState

public class GASState<VS,ES,ST>
extends Object
implements IGASState<VS,ES,ST>

Field Summary

Fields

Modifier and Type	Field and Description
protected ConcurrentMap<org.openrdf.model.Statement,ES>	edgeState TODO EDGE STATE: state needs to be configurable.
protected ConcurrentMap<org.openrdf.model.Value,VS>	vertexState The state associated with each visited vertex.

Constructor Summary

Constructors

Constructor and Description
GASState(IGASEngine gasEngine, IGraphAccessor graphAccessor, IStaticFrontier frontier, IGASSchedulerImpl gasScheduler, IGASProgram<VS,ES,ST> gasProgram)

Method Summary

Methods

Modifier and Type	Method and Description
org.openrdf.model.Value	asValue(org.openrdf.model.Value value) Convert a value into an appropriate internal form.
int	compareTo(org.openrdf.model.Value u, org.openrdf.model.Value v) Return -1, o, or 1 if u is LT, EQ, or GT v.
org.openrdf.model.Statement	decodeStatement(org.openrdf.model.Value v) If the vertex is actually an edge, then return the decoded edge.
void	endRound() End the current round, advance the round counter, and compact the new frontier.
IStaticFrontier	frontier() The current frontier.
protected IGraphAccessor	getGraphAccessor() Provides access to the backing graph.
org.openrdf.model.Literal	getLinkAttr(org.openrdf.model.Value u, org.openrdf.model.Statement e) This will only work for the BigdataGASState.
org.openrdf.model.Value	getOtherVertex(org.openrdf.model.Value u, org.openrdf.model.Statement e) Return the other end of a link.
IGASSchedulerImpl	getScheduler() Return the IGASSchedulerImpl.
ES	getState(org.openrdf.model.Statement e) Get the state for the edge using the appropriate factory.
VS	getState(org.openrdf.model.Value v) Get the state for the vertex using the appropriate factory.
boolean	isAttrib(org.openrdf.model.Statement e) Return true iff the given Statement models an property value for a vertex of the graph (Statements also model edges).
boolean	isEdge(org.openrdf.model.Statement e) Return true iff the given Statement models an edge that connects two vertices (Statements also model property values).
boolean	isLinkAttrib(org.openrdf.model.Statement e, org.openrdf.model.URI linkAttribType) Return true iff the statement models a link attribute having the specified link type.
boolean	isVisited(Set<org.openrdf.model.Value> v) Return true iff the specified vertices all have an associated vertex state object - this is interpreted as meaning that the vertex has been "visited".
boolean	isVisited(org.openrdf.model.Value v) Return true iff the specified vertex has an associated vertex state object - this is interpreted as meaning that the vertex has been "visited".
<T> T	reduce(IReducer<VS,ES,ST,T> op) Compute a reduction over the vertex state table (all vertices that have had their vertex state materialized).
void	reset() Discard computation state (the frontier, vertex state, and edge state) and reset the round counter.
void	retainAll(Set<org.openrdf.model.Value> retainSet) Retain only those vertices in the visited set that are found in the specified collection.
int	round() Return the current evaluation round (origin ZERO).
void	setFrontier(IGASContext<VS,ES,ST> ctx, org.openrdf.model.Value... vertices) IGASState.reset() the computation state and populate the initial frontier.
String	toString(org.openrdf.model.Statement e) Return a useful representation of an edge (non-batch API, debug only).
void	traceState() Conditionally log various interesting information about the state of the computation.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

vertexState

protected final ConcurrentMap<org.openrdf.model.Value,VS> vertexState

The state associated with each visited vertex. TODO Offer scalable backend with high throughput, e.g., using a batched striped lock as per DISTINCT (we might be better off with such large visited sets using a full traveral strategy, but overflow to an HTree or (if fixed stride) a MemStore or BigArray could help).

edgeState

protected final ConcurrentMap<org.openrdf.model.Statement,ES> edgeState

TODO EDGE STATE: state needs to be configurable. When disabled, leave this as null.

Constructor Detail

GASState

public GASState(IGASEngine gasEngine,
        IGraphAccessor graphAccessor,
        IStaticFrontier frontier,
        IGASSchedulerImpl gasScheduler,
        IGASProgram<VS,ES,ST> gasProgram)

Method Detail

getGraphAccessor

protected IGraphAccessor getGraphAccessor()

Provides access to the backing graph. Used to decode vertices and edges for traceState().

frontier

public IStaticFrontier frontier()

Description copied from interface: IGASState

The current frontier.

Specified by:

frontier in interface IGASState<VS,ES,ST>

getScheduler

public IGASSchedulerImpl getScheduler()

Description copied from interface: IGASState

Return the IGASSchedulerImpl.

Specified by:

getScheduler in interface IGASState<VS,ES,ST>

getState

public VS getState(org.openrdf.model.Value v)

Description copied from interface: IGASState

Get the state for the vertex using the appropriate factory. If this is the first visit for that vertex, then the state is initialized using the factory. Otherwise the existing state is returned.

Specified by:

getState in interface IGASState<VS,ES,ST>

Parameters:

v - The vertex.

Returns:

The state for that vertex.

See Also:

IGASOptions.getVertexStateFactory()

isVisited

public boolean isVisited(org.openrdf.model.Value v)

Description copied from interface: IGASState

Return true iff the specified vertex has an associated vertex state object - this is interpreted as meaning that the vertex has been "visited".

Specified by:

isVisited in interface IGASState<VS,ES,ST>

Parameters:

v - The vertex.

Returns:

true iff there is vertex state associated with that vertex.

isVisited

public boolean isVisited(Set<org.openrdf.model.Value> v)

Description copied from interface: IGASState

Return true iff the specified vertices all have an associated vertex state object - this is interpreted as meaning that the vertex has been "visited".

Specified by:

isVisited in interface IGASState<VS,ES,ST>

Parameters:

v - The vertices.

Returns:

true iff there is vertex state associated with all specified vertices.

getState

public ES getState(org.openrdf.model.Statement e)

Description copied from interface: IGASState

Get the state for the edge using the appropriate factory. If this is the first visit for that vertex, then the state is initialized using the factory. Otherwise the existing state is returned.

Specified by:

getState in interface IGASState<VS,ES,ST>

Returns:

The state for that vertex.

See Also:

IGASOptions.getEdgeStateFactory()

retainAll

public void retainAll(Set<org.openrdf.model.Value> retainSet)

Description copied from interface: IGASState

Retain only those vertices in the visited set that are found in the specified collection.

Specified by:

retainAll in interface IGASState<VS,ES,ST>

Parameters:

retainSet - The set of vertices to be retained.

round

public int round()

Description copied from interface: IGASState

Return the current evaluation round (origin ZERO).

Specified by:

round in interface IGASState<VS,ES,ST>

reset

public void reset()

Description copied from interface: IGASState

Discard computation state (the frontier, vertex state, and edge state) and reset the round counter.

Note: The graph is NOT part of the computation and is not discared by this method.

Specified by:

reset in interface IGASState<VS,ES,ST>

setFrontier

public void setFrontier(IGASContext<VS,ES,ST> ctx,
               org.openrdf.model.Value... vertices)

Description copied from interface: IGASState

IGASState.reset() the computation state and populate the initial frontier.

Specified by:

setFrontier in interface IGASState<VS,ES,ST>

Parameters:

ctx - The execution context.

vertices - One or more vertices that will be included in the initial frontier.

traceState

public void traceState()

Description copied from interface: IGASState

Conditionally log various interesting information about the state of the computation.

Specified by:

traceState in interface IGASState<VS,ES,ST>

endRound

public void endRound()

Description copied from interface: IGASState

End the current round, advance the round counter, and compact the new frontier.

Specified by:

endRound in interface IGASState<VS,ES,ST>

reduce

public <T> T reduce(IReducer<VS,ES,ST,T> op)

Compute a reduction over the vertex state table (all vertices that have had their vertex state materialized). FIXME REDUCE : parallelize with nthreads. The reduce operations are often lightweight, so maybe a fork/join pool would work better?

Note: We can not do a parallel reduction right now because the backing class does not expose a parallel iterator, e.g., a segment-wise iterator. The reduction over the vertexState is quite slow as a result.

It looks like bulk parallel operators will be eventually introduced into the Java concurrency collections. For now, it seems like the short term solution would be to drop them onto stripped lists at the same time that they are first inserted into the CHM. I could then read over those striped lists in parallel during the reduction.

The IReducer should run with parallel threads. This is a huge serial bottleneck right now. Fixing this will require a data structure with a parallel iterator, not the CHM. See http://stackoverflow.com/questions/20164690 /using-scalas-parhashmap-in-javas-project-instead-of-concurrenthashmap

It seems like the short term solution would be to drop them onto striped lists at the same time that they are first inserted into the CHM. I could then read over those striped lists in parallel during the reduction.

Specified by:

reduce in interface IGASState<VS,ES,ST>

Parameters:

op - The reduction operation.

Returns:

The reduction.

toString

public String toString(org.openrdf.model.Statement e)

Description copied from interface: IGASState

Return a useful representation of an edge (non-batch API, debug only). This method is only required when the edge objects are internal database objects lacking fully materialized RDF Values. In this case, it will materialize the RDF Values and present a pleasant view of the edge. The materialization step is a random access, which is why this method is for debug only. Efficient, vectored mechanisms exist to materialize RDF Values for other purposes, e.g., when exporting a set of edges as as graph in a standard interchange syntax.

Specified by:

toString in interface IGASState<VS,ES,ST>

Parameters:

e - The edge.

Returns:

The representation of that edge.

getOtherVertex

public org.openrdf.model.Value getOtherVertex(org.openrdf.model.Value u,
                                     org.openrdf.model.Statement e)

Return the other end of a link.

FIXME We can optimize this to use reference testing if we are careful in the GATHER and SCATTER implementations to impose a canonical mapping over the vertex objects for the edges that are exposed to the IGASProgram during a single round.

Specified by:

getOtherVertex in interface IGASState<VS,ES,ST>

Parameters:

u - One end of the link.

e - The link.

Returns:

The other end of the link.

getLinkAttr

public org.openrdf.model.Literal getLinkAttr(org.openrdf.model.Value u,
                                    org.openrdf.model.Statement e)

This will only work for the BigdataGASState.

Specified by:

getLinkAttr in interface IGASState<VS,ES,ST>

Parameters:

u - One end of the link.

e - The link.

Returns:

The other end of the link.

isEdge

public boolean isEdge(org.openrdf.model.Statement e)

Description copied from interface: IGASState

Return true iff the given Statement models an edge that connects two vertices (Statements also model property values).

Specified by:

isEdge in interface IGASState<VS,ES,ST>

Parameters:

e - The statement.

Returns:

true iff that Statement is an edge of the graph.

isAttrib

public boolean isAttrib(org.openrdf.model.Statement e)

Description copied from interface: IGASState

Return true iff the given Statement models an property value for a vertex of the graph (Statements also model edges).

Specified by:

isAttrib in interface IGASState<VS,ES,ST>

Parameters:

e - The statement.

Returns:

true iff that Statement is an edge of the graph.

isLinkAttrib

public boolean isLinkAttrib(org.openrdf.model.Statement e,
                   org.openrdf.model.URI linkAttribType)

Return true iff the statement models a link attribute having the specified link type. When this method returns true, the Statement.getSubject() may be decoded to obtain the link described by that link attribute using IGASState.decodeStatement(Value).

The openrdf implementation does not support link attributes and this method always returns false.

Specified by:

isLinkAttrib in interface IGASState<VS,ES,ST>

Parameters:

e - The statement.

linkAttribType - The type for the link attribute.

Returns:

false

decodeStatement

public org.openrdf.model.Statement decodeStatement(org.openrdf.model.Value v)

If the vertex is actually an edge, then return the decoded edge.

Note: A vertex may be an edge. A link attribute is modeled by treating the link as a vertex and then asserting a property value about that "link vertex". For bigdata, this is handled efficiently as inline statements about statements. This approach subsumes the property graph model (property graphs do not permit recursive nesting of these relationships) and is 100% consistent with RDF reification, except that the link attributes are modeled efficiently inline with the links. This is what we call Reification Done Right .

The openrdf implementation does not support link attributes and this method always returns null.

Specified by:

decodeStatement in interface IGASState<VS,ES,ST>

Parameters:

v - The vertex.

Returns:

null

See Also:

Reification Done Right , RDF GAS API

compareTo

public int compareTo(org.openrdf.model.Value u,
            org.openrdf.model.Value v)

Description copied from interface: IGASState

Return -1, o, or 1 if u is LT, EQ, or GT v. A number of GAS programs depend on the ability to place an order over the vertex identifiers, as does 2D partitioning. The ordering provided by this method MAY be arbitrary, but it MUST be total and stable across the life-cycle of the GAS program evaluation.

Specified by:

compareTo in interface IGASState<VS,ES,ST>

Parameters:

u - A vertex.

v - Another vertex.

asValue

public org.openrdf.model.Value asValue(org.openrdf.model.Value value)

Description copied from interface: IGASState

Convert a value into an appropriate internal form.

Specified by:

asValue in interface IGASState<VS,ES,ST>

Parameters:

value - The value.

Returns:

The internal form and null if the argument is null.