Overview  Package   Class  Use  Deprecated  Index
Home >> All >> com >> hp >> hpl >> jena >> reasoner >> [ transitiveReasoner overview ]	PREV CLASS  NEXT CLASS
SUMMARY:  JAVADOC |  SOURCE |  DOWNLOAD | NESTED | FIELD | CONSTR | METHOD	DETAIL: FIELD | CONSTR | METHOD

---

com.hp.hpl.jena.reasoner.transitiveReasoner
Class TransitiveGraphCache  

java.lang.Object
  com.hp.hpl.jena.reasoner.transitiveReasoner.TransitiveGraphCache

All Implemented Interfaces:

com.hp.hpl.jena.reasoner.Finder

---

public class TransitiveGraphCache

extends java.lang.Object

implements com.hp.hpl.jena.reasoner.Finder

Datastructure used to represent a closed transitive reflexive relation. It (mostly) incrementally maintains a transitive reduction and transitive closure of the relationship and so queries should be faster than dynamically computing the closed or reduced relations.

The implementation stores the reduced and closed relations as real graph (objects linked together by pointers). For each graph node we store its direct predecessors and successors and its closed successors. A cost penalty is the storage turnover involved in turning the graph representation back into triples to answer queries. We could avoid this by optionally also storing the manifested triples for the links.

Cycles are currently handled by collapsing strongly connected components. Incremental deletes would be possible but at the price of substanially more storage and code complexity. We compromise by doing the easy cases incrementally but some deletes (those that break strongly connected components) will trigger a fresh rebuild.

TODO Combine this with interval indexes (Agrawal, Borigda and Jagadish 1989) for storing the closure of the predecessor relationship. Typical graphs will be nearly tree shaped so the successor closure is modest (L^2 where L is the depth of the tree branch) but the predecessor closure would be expensive. The interval index would handle predecessor closure nicely.

Version:

$Revision: 1.18 $

---

Nested Class Summary
private static class	TransitiveGraphCache.FullGraphWalker           Inner class used to do a complete walk over the graph
private static class	TransitiveGraphCache.GraphNode           Inner class used to represent the graph node structure.
private static class	TransitiveGraphCache.GraphWalker           Inner class used to walk backward links of the graph.
(package private) static interface	TransitiveGraphCache.Visitor           Inner class used to represent vistors than can be applied to each node in a graph walk.

 

Field Summary
protected  boolean	cacheTriples           Flag controlling the whether the triples representing the closed relation should also be cached.
protected  com.hp.hpl.jena.graph.Node	closedPredicate           The RDF predicate representing the closed relation
protected  java.util.Set	deletesPending           A list of pending deletes which break the cycle-free normal form
protected  com.hp.hpl.jena.graph.Node	directPredicate           The RDF predicate representing the direct relation
protected  java.util.HashMap	nodeMap           Map from RDF Node to the corresponding Graph node.
protected  java.util.Set	originalTriples           The original triples, needed for processing delete operations because some information is lost in the SCC process

 

Constructor Summary

TransitiveGraphCache(com.hp.hpl.jena.graph.Node directPredicate, com.hp.hpl.jena.graph.Node closedPredicate)           Constructor - create a new cache to hold the given relation information.

 

Method Summary
private  void	addRelation(com.hp.hpl.jena.graph.Node start, com.hp.hpl.jena.graph.Node end)           Register a new relation instance in the cache
void	addRelation(com.hp.hpl.jena.graph.Triple t)           Register a new relation instance in the cache
boolean	cacheAll(com.hp.hpl.jena.reasoner.Finder graph, com.hp.hpl.jena.graph.Node predicate)           Cache all instances of the given predicate which are present in the given Graph.
void	clear()           Clear the entire cache contents.
boolean	contains(com.hp.hpl.jena.reasoner.TriplePattern pattern)           Return true if the given pattern occurs somewhere in the find sequence.
TransitiveGraphCache	deepCopy()           Create a deep copy of the cache contents.
java.lang.String	dump()           Dump a description of the cache to a string for debug.
com.hp.hpl.jena.util.iterator.ExtendedIterator	find(com.hp.hpl.jena.reasoner.TriplePattern pattern)           Basic pattern lookup interface.
com.hp.hpl.jena.util.iterator.ExtendedIterator	findWithContinuation(com.hp.hpl.jena.reasoner.TriplePattern pattern, com.hp.hpl.jena.reasoner.Finder continuation)           Extended find interface used in situations where the implementator may or may not be able to answer the complete query.
com.hp.hpl.jena.graph.Node	getClosedPredicate()           Returns the closedPredicate.
com.hp.hpl.jena.graph.Node	getDirectPredicate()           Returns the directPredicate.
private  TransitiveGraphCache.GraphNode	getLead(com.hp.hpl.jena.graph.Node n)           Return the lead node of the strongly connected component corresponding to the given RDF node.
boolean	isSubject(com.hp.hpl.jena.graph.Node node)           Return true if the given Node is registered as a subject node
com.hp.hpl.jena.util.iterator.ExtendedIterator	listAllSubjects()           Return an iterator over all registered subject nodes
private  void	processDeletes()           Process outstanding delete actions
void	removeRelation(com.hp.hpl.jena.graph.Triple t)           Remove an instance of a relation from the cache.
void	setCaching(boolean enable)           Enable/disabling caching of the Triples representing the relationships.

 

Methods inherited from class java.lang.Object

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

 

Field Detail

cacheTriples

protected boolean cacheTriples

Flag controlling the whether the triples representing the closed relation should also be cached.

---

nodeMap

protected java.util.HashMap nodeMap

Map from RDF Node to the corresponding Graph node.

---

directPredicate

protected com.hp.hpl.jena.graph.Node directPredicate

The RDF predicate representing the direct relation

---

closedPredicate

protected com.hp.hpl.jena.graph.Node closedPredicate

The RDF predicate representing the closed relation

---

deletesPending

protected java.util.Set deletesPending

A list of pending deletes which break the cycle-free normal form

---

originalTriples

protected java.util.Set originalTriples

The original triples, needed for processing delete operations because some information is lost in the SCC process

Constructor Detail

TransitiveGraphCache

public TransitiveGraphCache(com.hp.hpl.jena.graph.Node directPredicate,
                            com.hp.hpl.jena.graph.Node closedPredicate)

Constructor - create a new cache to hold the given relation information.

Method Detail

getClosedPredicate

public com.hp.hpl.jena.graph.Node getClosedPredicate()

Returns the closedPredicate.

---

getDirectPredicate

public com.hp.hpl.jena.graph.Node getDirectPredicate()

Returns the directPredicate.

---

addRelation

public void addRelation(com.hp.hpl.jena.graph.Triple t)

Register a new relation instance in the cache

---

addRelation

private void addRelation(com.hp.hpl.jena.graph.Node start,
                         com.hp.hpl.jena.graph.Node end)

Register a new relation instance in the cache

---

removeRelation

public void removeRelation(com.hp.hpl.jena.graph.Triple t)

Remove an instance of a relation from the cache.

---

processDeletes

private void processDeletes()

Process outstanding delete actions

---

findWithContinuation

public com.hp.hpl.jena.util.iterator.ExtendedIterator findWithContinuation(com.hp.hpl.jena.reasoner.TriplePattern pattern,
                                                                           com.hp.hpl.jena.reasoner.Finder continuation)

Extended find interface used in situations where the implementator may or may not be able to answer the complete query.

In this case any query on the direct or closed predicates will be assumed complete, any other query will pass on to the continuation.

Specified by:

findWithContinuation in interface com.hp.hpl.jena.reasoner.Finder

---

contains

public boolean contains(com.hp.hpl.jena.reasoner.TriplePattern pattern)

Return true if the given pattern occurs somewhere in the find sequence.

Specified by:

contains in interface com.hp.hpl.jena.reasoner.Finder

---

listAllSubjects

public com.hp.hpl.jena.util.iterator.ExtendedIterator listAllSubjects()

Return an iterator over all registered subject nodes

---

isSubject

public boolean isSubject(com.hp.hpl.jena.graph.Node node)

Return true if the given Node is registered as a subject node

---

cacheAll

public boolean cacheAll(com.hp.hpl.jena.reasoner.Finder graph,
                        com.hp.hpl.jena.graph.Node predicate)

Cache all instances of the given predicate which are present in the given Graph.

---

find

public com.hp.hpl.jena.util.iterator.ExtendedIterator find(com.hp.hpl.jena.reasoner.TriplePattern pattern)

Basic pattern lookup interface.

Specified by:

find in interface com.hp.hpl.jena.reasoner.Finder

---

deepCopy

public TransitiveGraphCache deepCopy()

Create a deep copy of the cache contents. Works by creating a completely new cache and just adding in the direct links.

---

clear

public void clear()

Clear the entire cache contents.

---

setCaching

public void setCaching(boolean enable)

Enable/disabling caching of the Triples representing the relationships. If this is enabled then a number of triples quadratic in the graph depth will be stored. If it is disabled then all queries will turn over storage dynamically creating the result triples.

---

dump

public java.lang.String dump()

Dump a description of the cache to a string for debug.

---

getLead

private TransitiveGraphCache.GraphNode getLead(com.hp.hpl.jena.graph.Node n)

Return the lead node of the strongly connected component corresponding to the given RDF node.

---

Overview  Package   Class  Use  Deprecated  Index
Home >> All >> com >> hp >> hpl >> jena >> reasoner >> [ transitiveReasoner overview ]	PREV CLASS  NEXT CLASS
SUMMARY:  JAVADOC |  SOURCE |  DOWNLOAD | NESTED | FIELD | CONSTR | METHOD	DETAIL: FIELD | CONSTR | METHOD

---