Traversal Recursion: A Practical Approach to Supporting Recursive Applications.

Arnon Rosenthal, Sandra Heiler, Umeshwar Dayal, Frank Manola: Traversal Recursion: A Practical Approach to Supporting Recursive Applications. SIGMOD Conference 1986: 166-176

@inproceedings{DBLP:conf/sigmod/RosenthalHDM86,
  author    = {Arnon Rosenthal and
               Sandra Heiler and
               Umeshwar Dayal and
               Frank Manola},
  editor    = {Carlo Zaniolo},
  title     = {Traversal Recursion: A Practical Approach to Supporting Recursive
               Applications},
  booktitle = {Proceedings of the 1986 ACM SIGMOD International Conference on
               Management of Data, Washington, D.C., May 28-30, 1986},
  publisher = {ACM Press},
  year      = {1986},
  pages     = {166-176},
  ee        = {http://doi.acm.org/10.1145/16894.16871, db/conf/sigmod/RosenthalHDM86.html},
  crossref  = {DBLP:conf/sigmod/86},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Many capabilities that are needed for recursive applications in engineering and project management are not well supported by the usual formulations of recursion. We identify a class of recursions called "traversal recursions" (which model traversals of a directed graph) that have two important properties: they can supply the necessary capabilities and efficient processing algorithms have been defined for them. First we present a taxonomy of traversal recursions based on properties of the recursion on graph structure and on unusual types of metadata. This taxonomy is exploited to identify solvable recursions and to select an execution algorithm. We show how graph traversal can sometimes outperform the more general iteration algorithm. Finally we show how a conventional query optimizer architecture can be extended to handle recursive queries and views.

Copyright © 1986 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 ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/smod7592 or /cdrom

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

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

Carlo Zaniolo (Ed.): Proceedings of the 1986 ACM SIGMOD International Conference on Management of Data, Washington, D.C., May 28-30, 1986. ACM Press 1986

, SIGMOD Record 15(2)
Contents

Online Edition: ACM Digital Library

References

[AHO76]: Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
[AHO79]: Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120
[BANC86]: ...
[BAYE85]: ...
[CARR79]: ...
[CHAK82]: Upen S. Chakravarthy, Jack Minker, Duc Tran: Interfacing Predicate Logic Languages and Relational Databases. ICLP 1982: 91-98
[CHAN82]: Ashok K. Chandra, David Harel: Horn Clauses and the Fixpoint Query Hierarchy. PODS 1982: 158-163
[CLEM81]: Eric K. Clemons: Design of an External Schema Facility to Define and Process Recursive Structures. ACM Trans. Database Syst. 6(2): 295-311(1981)
[CLOC81]: ...
[DAYA85]: ...
[DAYA86]: ...
[HEIL85]: Sandra Heiler, Arnon Rosenthal: G-WHIZ, a Visual Interface for the Functional Model with Recursion. VLDB 1985: 209-218
[HENS84]: Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984)
[IOAN85]: Yannis E. Ioannidis: A Time Bound on the Materialization of some Recursively Defined Views. VLDB 1985: 219-226
[JAME82]: ...
[JARK84]: Matthias Jarke, James Clifford, Yannis Vassiliou: An Optimizing Prolog Front-End to a Relational Query System. SIGMOD Conference 1984: 296-306
[JARK85]: Matthias Jarke, Volker Linnemann, Joachim W. Schmidt: Data Constructors: On the Integration of Rules and Relations. VLDB 1985: 227-240
[MERR84]: ...
[OREN86]: Jack A. Orenstein: Spatial Query Processing in an Object-Oriented Database System. SIGMOD Conference 1986: 326-336
[ROSE84]: Arnon Rosenthal, Sandra Heiler, Frank Manola: An Example of Knowledge-Based Query Processing in a CAD/CAM DBMS. VLDB 1984: 363-370
[ROSE85]: ...
[SHIP81]: David W. Shipman: The Functional Data Model and the Data Language DAPLEX. ACM Trans. Database Syst. 6(1): 140-173(1981)
[ULLM85]: Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985)
[YOKO84]: Haruo Yokota, Susumu Kunifuji, Takeo Kakuta, Nobuyoshi Miyazaki, Shigeki Shibayama, Kunio Murakami: An Enhanced Inference Mechanism for Generating Relational Algebra Queries. PODS 1984: 229-238
[ZLOO75]: ...