org.semanticweb.HermiT.tableau
Class ExtensionTable

java.lang.Object
  extended by org.semanticweb.HermiT.tableau.ExtensionTable
All Implemented Interfaces:
java.io.Serializable
Direct Known Subclasses:
ExtensionTableWithFullIndex, ExtensionTableWithTupleIndexes

public abstract class ExtensionTable
extends java.lang.Object
implements java.io.Serializable

An extension table keeps track of the assertions in the ABox during a run of the tableau. For this purpose, it holds a binary (concept, node) and a ternary (role, node, node) tuple table, which represent concept and role assertions respectively. Since this is one of the most crucial parts regarding memory usage, reusing already allocated space is the main design goal. In case of backtracking during the expansion, we just set the pointer to a previous entry in the table that then becomes the current one. When merging or pruning, we leave the entries for the merged/pruned nodes in the table so that we do not have holes in there. The tuple tables are indexed (tries/prefix trees) to speed-up the search for matching atoms during rule applications.

See Also:
Serialized Form

Nested Class Summary
protected static interface ExtensionTable.DependencySetManager
           
protected static class ExtensionTable.DeterministicDependencySetManager
           
protected  class ExtensionTable.LastObjectDependencySetManager
           
static interface ExtensionTable.Retrieval
           
protected  class ExtensionTable.UnindexedRetrieval
           
static class ExtensionTable.View
           
 
Field Summary
protected  int m_afterDeltaNewTupleIndex
           
protected  int m_afterExtensionOldTupleIndex
           
protected  int m_afterExtensionThisTupleIndex
           
protected  java.lang.Object[] m_binaryAuxiliaryTuple
           
protected  UnionDependencySet m_binaryUnionDependencySet
           
protected  ExtensionTable.DependencySetManager m_dependencySetManager
           
protected  ExtensionManager m_extensionManager
           
protected  int[] m_indicesByBranchingPoint
           
protected  Tableau m_tableau
           
protected  TableauMonitor m_tableauMonitor
           
protected  int m_tupleArity
           
protected  TupleTable m_tupleTable
           
private static long serialVersionUID
           
 
Constructor Summary
ExtensionTable(Tableau tableau, ExtensionManager extensionManager, int tupleArity, boolean needsDependencySets)
           
 
Method Summary
abstract  boolean addTuple(java.lang.Object[] tuple, DependencySet dependencySet)
           
 void backtrack()
           
 void branchingPointPushed()
           
 void clear()
           
abstract  boolean containsTuple(java.lang.Object[] tuple)
           
 ExtensionTable.Retrieval createRetrieval(boolean[] bindingPattern, ExtensionTable.View extensionView)
           
abstract  ExtensionTable.Retrieval createRetrieval(int[] bindingPositions, java.lang.Object[] bindingsBuffer, ExtensionTable.View extensionView)
           
 int getArity()
           
 DependencySet getDependencySet(int tupleIndex)
           
abstract  DependencySet getDependencySet(java.lang.Object[] tuple)
           
 java.lang.Object getTupleObject(int tupleIndex, int objectIndex)
           
 boolean isTupleActive(int tupleIndex)
           
 boolean isTupleActive(java.lang.Object[] tuple)
           
protected  void postAdd(java.lang.Object[] tuple, DependencySet dependencySet, int tupleIndex)
          Performs a few tests depending on the type of the added tuple (concept, role, inequality, description graph) to see whether adding the tuple caused a clash.
protected  void postRemove(java.lang.Object[] tuple, int tupleIndex)
           
 boolean propagateDeltaNew()
           
protected abstract  void removeTuple(int tupleIndex)
           
 void retrieveTuple(java.lang.Object[] tupleBuffer, int tupleIndex)
           
abstract  int sizeInMemory()
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

serialVersionUID

private static final long serialVersionUID
See Also:
Constant Field Values

m_tableau

protected final Tableau m_tableau

m_extensionManager

protected final ExtensionManager m_extensionManager

m_tableauMonitor

protected final TableauMonitor m_tableauMonitor

m_tupleArity

protected final int m_tupleArity

m_tupleTable

protected final TupleTable m_tupleTable

m_dependencySetManager

protected final ExtensionTable.DependencySetManager m_dependencySetManager

m_binaryAuxiliaryTuple

protected final java.lang.Object[] m_binaryAuxiliaryTuple

m_binaryUnionDependencySet

protected final UnionDependencySet m_binaryUnionDependencySet

m_afterExtensionOldTupleIndex

protected int m_afterExtensionOldTupleIndex

m_afterExtensionThisTupleIndex

protected int m_afterExtensionThisTupleIndex

m_afterDeltaNewTupleIndex

protected int m_afterDeltaNewTupleIndex

m_indicesByBranchingPoint

protected int[] m_indicesByBranchingPoint
Constructor Detail

ExtensionTable

public ExtensionTable(Tableau tableau,
                      ExtensionManager extensionManager,
                      int tupleArity,
                      boolean needsDependencySets)
Method Detail

sizeInMemory

public abstract int sizeInMemory()

getArity

public int getArity()

retrieveTuple

public void retrieveTuple(java.lang.Object[] tupleBuffer,
                          int tupleIndex)

getTupleObject

public java.lang.Object getTupleObject(int tupleIndex,
                                       int objectIndex)

getDependencySet

public DependencySet getDependencySet(int tupleIndex)

addTuple

public abstract boolean addTuple(java.lang.Object[] tuple,
                                 DependencySet dependencySet)

postAdd

protected void postAdd(java.lang.Object[] tuple,
                       DependencySet dependencySet,
                       int tupleIndex)
Performs a few tests depending on the type of the added tuple (concept, role, inequality, description graph) to see whether adding the tuple caused a clash.

Parameters:
tuple -
dependencySet -
tupleIndex -

containsTuple

public abstract boolean containsTuple(java.lang.Object[] tuple)

createRetrieval

public ExtensionTable.Retrieval createRetrieval(boolean[] bindingPattern,
                                                ExtensionTable.View extensionView)

createRetrieval

public abstract ExtensionTable.Retrieval createRetrieval(int[] bindingPositions,
                                                         java.lang.Object[] bindingsBuffer,
                                                         ExtensionTable.View extensionView)

getDependencySet

public abstract DependencySet getDependencySet(java.lang.Object[] tuple)

propagateDeltaNew

public boolean propagateDeltaNew()

branchingPointPushed

public void branchingPointPushed()

backtrack

public void backtrack()

removeTuple

protected abstract void removeTuple(int tupleIndex)

postRemove

protected void postRemove(java.lang.Object[] tuple,
                          int tupleIndex)

clear

public void clear()

isTupleActive

public boolean isTupleActive(java.lang.Object[] tuple)

isTupleActive

public boolean isTupleActive(int tupleIndex)