ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

A File Structure Supporting Traversal Recursion.

Per-Åke Larson, Vinay Deshpande: A File Structure Supporting Traversal Recursion. SIGMOD Conference 1989: 243-252
@inproceedings{DBLP:conf/sigmod/LarsonD89,
  author    = {Per-{\AA}ke Larson and
               Vinay Deshpande},
  editor    = {James Clifford and
               Bruce G. Lindsay and
               David Maier},
  title     = {A File Structure Supporting Traversal Recursion},
  booktitle = {Proceedings of the 1989 ACM SIGMOD International Conference on
               Management of Data, Portland, Oregon, May 31 - June 2, 1989},
  publisher = {ACM Press},
  year      = {1989},
  pages     = {243-252},
  ee        = {http://doi.acm.org/10.1145/67544.66949, db/conf/sigmod/LarsonD89.html},
  crossref  = {DBLP:conf/sigmod/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Traversal recursion is a class of recursive queries where the evaluation of the query involves traversal of a graph or a tree. This limited type of recursion arises in many applications. In this report we investigate a simple file structure that efficiently supports traversal recursion over large, acyclic graphs. The nodes of the graph are sorted in topological order and stored in a B-tree. Hence, traversal of the graph can be done in a single scan. Nodes and edges can also be inserted, deleted, and modified efficiently.

Copyright © 1989 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

James Clifford, Bruce G. Lindsay, David Maier (Eds.): Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, Portland, Oregon, May 31 - June 2, 1989. ACM Press 1989 BibTeX , SIGMOD Record 18(2), June 1989
Contents

Online Edition: ACM Digital Library


References

[BKKG]
Jay Banerjee, Won Kim, Sung-Jo Kim, Jorge F. Garza: Clustering a DAG for CAD Databases. IEEE Trans. Software Eng. 14(11): 1684-1699(1988) BibTeX
[BR]
François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX
[ES]
...
[Ka]
...
[RHDM]
Arnon Rosenthal, Sandra Heiler, Umeshwar Dayal, Frank Manola: Traversal Recursion: A Practical Approach to Supporting Recursive Applications. SIGMOD Conference 1986: 166-176 BibTeX
[RND]
...

Referenced by

  1. Shashi Shekhar, Duen-Ren Liu: CCAM: A Connectivity-Clustered Access Method for Networks and Network Computations. IEEE Trans. Knowl. Data Eng. 9(1): 102-119(1997)
  2. Shashi Shekhar, Duen-Ren Liu: CCAM: A Connectivity-Clustered Access Method for Aggregate Queries on Transportation Networks: A Summary of Results. ICDE 1995: 410-419
  3. Keh-Chang Guh, Clement T. Yu: Efficient Query Processing for a Subset of Linear Recursive Binary Rules. IEEE Trans. Knowl. Data Eng. 6(5): 842-849(1994)
  4. Maurice A. W. Houtsma, Annita N. Wilschut, Jan Flokstra: Implementation and Performance Evaluation of a Parallel Transitive Closure Algorithm on PRISMA/DB. VLDB 1993: 206-217
  5. Kien A. Hua, Jeffrey X. W. Su, Chau M. Hua: Efficient Evaluation of Traversal Recursive Queries Using Connectivity Index. ICDE 1993: 549-558
  6. Rakesh Agrawal, Jerry Kiernan: An Access Structure for Generalized Transitive Closure Queries. ICDE 1993: 429-438
  7. Maurice A. W. Houtsma, Peter M. G. Apers, Stefano Ceri: Distributed Transitive Closure Computations: The Disconnection Set Approach. VLDB 1990: 335-346
  8. Maurice A. W. Houtsma, Peter M. G. Apers, Stefano Ceri: Complex Transitive Closure Queries on a Fragmented Graph. ICDT 1990: 470-484
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:39:58 2009