Efficient Management of Transitive Relationships

We argue that accessing the transitive closure of relationsbips is an important component of both databases and knowledge representation systems in Artificial Intelligence. The demands for efficient access and management of large relationships motivate the need for explicitly storing the transitive closure in a compressed and local way, while allowing updates to the base relation to be propagated incrementally. We present a transitive closure compression technique, based on labeling spanning trees with numeric intervals, and provide both analytical and empirical evidence of its efficacy, including a proof of optimality. 1. OVERVlEW The significance of transitive relationships has long been acknowledged in varied fields. Recently, database researchers have recognized its utility in querying databases- in fact, it has been argued that transitivity is the dominant form of recursion that is of practical utility [2,24,27]. After briefly reviewing the motivation for managing large transitive relationships in databases, we present a second application arex the management and use of subclass (IS-A) hierarchie