An access structure for generalized transitive closure queries

30 December 2002

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

p. 429-438
https://doi.org/10.1109/icde.1993.344038

Abstract

An access structure that accelerates the processing of generalized transitive closure queries is presented. For an acyclic graph, the access structure consists of source-destination pairs arranged in a topologically sorted order. For a cyclic graph, entries in the structure are approximately topologically sorted. The authors present a breadth-first algorithm for creating such a structure, show how it can be used to process queries, and describe incremental techniques for maintaining it.<>

Keywords

This publication has 11 references indexed in Scilit:

Materialization and incremental update of path information
Published by Institute of Electrical and Electronics Engineers (IEEE) ,2003
A suitable algorithm for computing partial transitive closures in databases
Published by Institute of Electrical and Electronics Engineers (IEEE) ,2002
Efficient management of materialized generalized transitive closure in centralized and parallel environments
IEEE Transactions on Knowledge and Data Engineering, 1992
Direct transitive closure algorithms: design and performance evaluation
ACM Transactions on Database Systems, 1990
Efficient management of transitive relationships in large data and knowledge bases
Published by Association for Computing Machinery (ACM) ,1989
A file structure supporting traversal recursion
Published by Association for Computing Machinery (ACM) ,1989
Alpha: an extension of relational algebra to express a class of recursive queries
IEEE Transactions on Software Engineering, 1988
Traversal recursion: a practical approach to supporting recursive applications
Published by Association for Computing Machinery (ACM) ,1986
Depth-First Search and Linear Graph Algorithms
SIAM Journal on Computing, 1972
Reducibility among Combinatorial Problems
Published by Springer Nature ,1972