| 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.
author:
Dave Reynolds
version:
$Revision: 1.24 $ | 