Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: 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:
  Finder

    public class TransitiveGraphCache

extends java.lang.Object
implements 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.24 $
Author:
  Dave Reynolds

Constructor Summary
`TransitiveGraphCache(Node directPredicate, Node closedPredicate)` Constructor - create a new cache to hold the given relation information.

Method Summary
`void` | `addRelation(Triple t)` Register a new relation instance in the cache
`boolean` | `cacheAll(Finder 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(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.
`ExtendedIterator` | `find(TriplePattern pattern)` Basic pattern lookup interface.
`ExtendedIterator` | `findWithContinuation(TriplePattern pattern, Finder continuation)` Extended find interface used in situations where the implementator may or may not be able to answer the complete query.
`Node` | `getClosedPredicate()` Returns the closedPredicate.
`Node` | `getDirectPredicate()` Returns the directPredicate.
`boolean` | `isSubject(Node node)` Return true if the given Node is registered as a subject node
`ExtendedIterator` | `listAllSubjects()` Return an iterator over all registered subject nodes
`void` | `removeRelation(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
`equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Constructor Detail

### TransitiveGraphCache

    public TransitiveGraphCache(Node directPredicate,
                                Node closedPredicate)

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

  Parameters:
    `directPredicate` - The RDF predicate representing the direct relation
    `closedPredicate` - The RDF predicate representing the closed relation

Method Detail

### getClosedPredicate

    public Node getClosedPredicate()

  Returns the closedPredicate.

  Returns:
    Node

### getDirectPredicate

    public Node getDirectPredicate()

  Returns the directPredicate.

  Returns:
    Node

### addRelation

    public void addRelation(Triple t)

  Register a new relation instance in the cache

### removeRelation

    public void removeRelation(Triple t)

  Remove an instance of a relation from the cache.

### findWithContinuation

    public ExtendedIterator findWithContinuation(TriplePattern pattern,
                                                 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 `Finder`
  Parameters:
    `pattern` - a TriplePattern to be matched against the data
    `continuation` - either a Finder or a normal Graph which will be asked for additional match results if the implementor may not have completely satisfied the query.

### contains

    public boolean contains(TriplePattern pattern)

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

  Specified by:
    `contains` in interface `Finder`

### listAllSubjects

    public ExtendedIterator listAllSubjects()

  Return an iterator over all registered subject nodes

### isSubject

    public boolean isSubject(Node node)

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

### cacheAll

    public boolean cacheAll(Finder graph,
                            Node predicate)

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

  Parameters:
    `graph` - the searchable set of triples to cache
    `predicate` - the predicate to cache, need not be the registered predicate due to subProperty declarations
  Returns:
    returns true if new information has been cached

### find

    public ExtendedIterator find(TriplePattern pattern)

  Basic pattern lookup interface.

  Specified by:
    `find` in interface `Finder`
  Parameters:
    `pattern` - a TriplePattern to be matched against the data
  Returns:
    a ExtendedIterator over all Triples in the data set that match the pattern

### 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.

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

Copyright © 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008 Hewlett-Packard Development Company, LP