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

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 ...

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

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, 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
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[AHO79]
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BANC86]
...
[BAYE85]
...
[CARR79]
...
[CHAK82]
Upen S. Chakravarthy, Jack Minker, Duc Tran: Interfacing Predicate Logic Languages and Relational Databases. ICLP 1982: 91-98 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CHAN82]
Ashok K. Chandra, David Harel: Horn Clauses and the Fixpoint Query Hierarchy. PODS 1982: 158-163 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CLOC81]
...
[DAYA85]
...
[DAYA86]
...
[HEIL85]
Sandra Heiler, Arnon Rosenthal: G-WHIZ, a Visual Interface for the Functional Model with Recursion. VLDB 1985: 209-218 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HENS84]
Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[IOAN85]
Yannis E. Ioannidis: A Time Bound on the Materialization of some Recursively Defined Views. VLDB 1985: 219-226 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[JAME82]
...
[JARK84]
Matthias Jarke, James Clifford, Yannis Vassiliou: An Optimizing Prolog Front-End to a Relational Query System. SIGMOD Conference 1984: 296-306 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[JARK85]
Matthias Jarke, Volker Linnemann, Joachim W. Schmidt: Data Constructors: On the Integration of Rules and Relations. VLDB 1985: 227-240 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MERR84]
...
[OREN86]
Jack A. Orenstein: Spatial Query Processing in an Object-Oriented Database System. SIGMOD Conference 1986: 326-336 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ROSE84]
Arnon Rosenthal, Sandra Heiler, Frank Manola: An Example of Knowledge-Based Query Processing in a CAD/CAM DBMS. VLDB 1984: 363-370 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ROSE85]
...
[SHIP81]
David W. Shipman: The Functional Data Model and the Data Language DAPLEX. ACM Trans. Database Syst. 6(1): 140-173(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ULLM85]
Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ZLOO75]
...

Copyright © Mon Mar 15 03:54:27 2010 by Michael Ley (ley@uni-trier.de)