Efficient management of transitive relationships in large data and knowledge bases
Authors:
Open Access
- 1 June 1989
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGMOD Record
- Vol. 18 (2) , 253-262
Abstract
We argue that accessing the transitive closure of relationships 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.Keywords
This publication has 11 references indexed in Scilit:
- Efficient implementation of lattice operationsACM Transactions on Programming Languages and Systems, 1989
- CLASSIC: a structural data model for objects1989
- Alpha: an extension of relational algebra to express a class of recursive queriesIEEE Transactions on Software Engineering, 1988
- A performance analysis of view materialization strategies1987
- A graphical query language supporting recursion1987
- Traversal recursion: a practical approach to supporting recursive applications1986
- Efficiently updating materialized views1986
- Amortized efficiency of a path retrieval data structureTheoretical Computer Science, 1986
- An Overview of the KL‐ONE Knowledge Representation System*Cognitive Science, 1985
- Determining Type, Part, Color, and Time RelationshipsComputer, 1983