Title :
An access structure for generalized transitive closure queries
Author :
Agrawal, Rakesh ; Kiernan, Jerry
Author_Institution :
IBM Almaden Res. Center, San Jose, CA, USA
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 :
database management systems; database theory; graph theory; query processing; access structure; acyclic graph; breadth-first algorithm; cyclic graph; generalized transitive closure queries; source-destination pairs; topologically sorted order; Acceleration; Buildings; Intrusion detection; Iterative algorithms; Proposals; Query processing; Relational databases; Sorting; System testing; Vehicles;
Conference_Titel :
Data Engineering, 1993. Proceedings. Ninth International Conference on
Conference_Location :
Vienna
Print_ISBN :
0-8186-3570-3
DOI :
10.1109/ICDE.1993.344038
