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
  author    = {Arnon Rosenthal and
               Sandra Heiler and
               Umeshwar Dayal and
               Frank Manola},
  editor    = {Carlo Zaniolo},
  title     = {Traversal Recursion: A Practical Approach to Supporting Recursive
  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        = {, db/conf/sigmod/RosenthalHDM86.html},
  crossref  = {DBLP:conf/sigmod/86},
  bibsource = {DBLP,}


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

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 BibTeX , SIGMOD Record 15(2)

Online Edition: ACM Digital Library


Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX
Upen S. Chakravarthy, Jack Minker, Duc Tran: Interfacing Predicate Logic Languages and Relational Databases. ICLP 1982: 91-98 BibTeX
Ashok K. Chandra, David Harel: Horn Clauses and the Fixpoint Query Hierarchy. PODS 1982: 158-163 BibTeX
Eric K. Clemons: Design of an External Schema Facility to Define and Process Recursive Structures. ACM Trans. Database Syst. 6(2): 295-311(1981) BibTeX
Sandra Heiler, Arnon Rosenthal: G-WHIZ, a Visual Interface for the Functional Model with Recursion. VLDB 1985: 209-218 BibTeX
Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) BibTeX
Yannis E. Ioannidis: A Time Bound on the Materialization of some Recursively Defined Views. VLDB 1985: 219-226 BibTeX
Matthias Jarke, James Clifford, Yannis Vassiliou: An Optimizing Prolog Front-End to a Relational Query System. SIGMOD Conference 1984: 296-306 BibTeX
Matthias Jarke, Volker Linnemann, Joachim W. Schmidt: Data Constructors: On the Integration of Rules and Relations. VLDB 1985: 227-240 BibTeX
Jack A. Orenstein: Spatial Query Processing in an Object-Oriented Database System. SIGMOD Conference 1986: 326-336 BibTeX
Arnon Rosenthal, Sandra Heiler, Frank Manola: An Example of Knowledge-Based Query Processing in a CAD/CAM DBMS. VLDB 1984: 363-370 BibTeX
David W. Shipman: The Functional Data Model and the Data Language DAPLEX. ACM Trans. Database Syst. 6(1): 140-173(1981) BibTeX
Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) BibTeX
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 BibTeX

Referenced by

  1. Sungwon Jung, Sakti Pramanik: HiTi Graph Model of Topographical Roadmaps in Navigation Systems. ICDE 1996: 76-84
  2. Ralf Hartmut Güting: An Introduction to Spatial Database Systems. VLDB J. 3(4): 357-399(1994)
  3. Jiawei Han: Constraint-Based Query Evaluation in Deductive Databases. IEEE Trans. Knowl. Data Eng. 6(1): 96-107(1994)
  4. 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)
  5. Martin Erwig, Ralf Hartmut Güting: Explicit Graphs in a Functional Model for Spatial Databases. IEEE Trans. Knowl. Data Eng. 6(5): 787-804(1994)
  6. Rakesh Agrawal, H. V. Jagadish: Algorithms for Searching Massive Graphs. IEEE Trans. Knowl. Data Eng. 6(2): 225-238(1994)
  7. Ralf Hartmut Güting: GraphDB: Modeling and Querying Graphs in Databases. VLDB 1994: 297-308
  8. Yannis E. Ioannidis, Yezdi Lashkari: Incomplete Path Expressions and their Disambiguation. SIGMOD Conference 1994: 138-149
  9. Venu Vasudevan: Supporting High-Bandwidth Navigation in Object-Bases. ICDE 1994: 294-301
  10. Yannis E. Ioannidis, Raghu Ramakrishnan, Linda Winger: Transitive Closure Algorithms Based on Graph Traversal. ACM Trans. Database Syst. 18(3): 512-576(1993)
  11. Shaul Dar, Rakesh Agrawal: Extending SQL with Generalized Transitive Closure Functionality. IEEE Trans. Knowl. Data Eng. 5(5): 799-812(1993)
  12. Rafiul Ahad, Bing Yao: RQL: A Recursive Query Language. IEEE Trans. Knowl. Data Eng. 5(3): 451-461(1993)
  13. Kien A. Hua, Jeffrey X. W. Su, Chau M. Hua: Efficient Evaluation of Traversal Recursive Queries Using Connectivity Index. ICDE 1993: 549-558
  14. Rakesh Agrawal, Jerry Kiernan: An Access Structure for Generalized Transitive Closure Queries. ICDE 1993: 429-438
  15. Shu-Shang Wei, Yao-Nan Lien, Dik Lun Lee, Ten-Hwang Lai: Hot-Spot Based Compostion Algorithm. ICDE 1992: 48-55
  16. Bin Jiang: I/O-Efficiency of Shortest Path Algorithms: An Analysis. ICDE 1992: 12-19
  17. Shaul Dar, H. V. Jagadish: A Spanning Tree Transitive Closure Algorithm. ICDE 1992: 2-11
  18. Jiawei Han: Compilation-Based List Processing in Deductive Databases. EDBT 1992: 104-119
  19. S. Sudarshan, Raghu Ramakrishnan: Aggregation and Relevance in Deductive Databases. VLDB 1991: 501-511
  20. Yan-Nong Huang, Jean-Pierre Cheiney: Parallel Computation of Direct Transitive Closures. ICDE 1991: 192-199
  21. Jiawei Han: Constraint-Based Reasoning in Deductive Databases. ICDE 1991: 257-265
  22. Sumit Ganguly, Ravi Krishnamurthy, Abraham Silberschatz: An Analysis Technique for Transitive Closure Algorithms: A Statistical Approach. ICDE 1991: 728-735
  23. Shaul Dar, Rakesh Agrawal, H. V. Jagadish: Optimization of Generalized Transitive Closure Queries. ICDE 1991: 345-354
  24. H. V. Jagadish: A Compression Technique to Materialize Transitive Closure. ACM Trans. Database Syst. 15(4): 558-598(1990)
  25. Rakesh Agrawal, Shaul Dar, H. V. Jagadish: Direct Transitive Closure Algorithms: Design and Performance Evaluation. ACM Trans. Database Syst. 15(3): 427-458(1990)
  26. Michael V. Mannino, Leonard D. Shapiro: Extensions to Query Languages for Graph Traversal Problems. IEEE Trans. Knowl. Data Eng. 2(3): 353-363(1990)
  27. Johann Eder: Extending SQL with General Transitive Closure and Extreme Value Selections. IEEE Trans. Knowl. Data Eng. 2(4): 381-390(1990)
  28. Philippe Pucheral, Jean-Marc Thévenin, Patrick Valduriez: Efficient Main Memory Data Management Using the DBGraph Storage Model. VLDB 1990: 683-695
  29. Maurice A. W. Houtsma, Peter M. G. Apers, Stefano Ceri: Distributed Transitive Closure Computations: The Disconnection Set Approach. VLDB 1990: 335-346
  30. Rakesh Agrawal, H. V. Jagadish: Hybrid Transitive Closure Algorithms. VLDB 1990: 326-334
  31. Mariano P. Consens, Alberto O. Mendelzon: Low Complexity Aggregation in GraphLog and Datalog. ICDT 1990: 379-394
  32. Bin Jiang: A Suitable Algorithm for Computing Partial Transitive Closures in Databases. ICDE 1990: 264-271
  33. Sharma Chakravarthy, Susan Nesson: Making an Object-Oriented DBMS Active: Design, Implementation, and Evaluation of a Prototype. EDBT 1990: 393-406
  34. Michael Stonebraker: Future Trends in Database Systems. IEEE Trans. Knowl. Data Eng. 1(1): 33-44(1989)
  35. Martin Hardwick, David L. Spooner: The ROSE Data Manager: Using Object Technology to Support Interactive Engineering Applications. IEEE Trans. Knowl. Data Eng. 1(2): 285-289(1989)
  36. Stefano Ceri, Georg Gottlob, Letizia Tanca: What you Always Wanted to Know About Datalog (And Never Dared to Ask). IEEE Trans. Knowl. Data Eng. 1(1): 146-166(1989)
  37. Alberto O. Mendelzon, Peter T. Wood: Finding Regular Simple Paths in Graph Databases. VLDB 1989: 185-193
  38. Richard J. Lipton, Jeffrey F. Naughton: Estimating the Size of Generalized Transitive Closures. VLDB 1989: 165-171
  39. Jeffrey F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Evaluation of Right-, Left-, and Mult-Lineare Rules. SIGMOD Conference 1989: 235-242
  40. Per-Åke Larson, Vinay Deshpande: A File Structure Supporting Traversal Recursion. SIGMOD Conference 1989: 243-252
  41. Richard Hull, Jianwen Su: On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions (Extended Abstract). SIGMOD Conference 1989: 147-158
  42. Laura M. Haas, Johann Christoph Freytag, Guy M. Lohman, Hamid Pirahesh: Extensible Query Processing in Starburst. SIGMOD Conference 1989: 377-388
  43. Rakesh Agrawal, Alexander Borgida, H. V. Jagadish: Efficient Management of Transitive Relationships in Large Data and Knowledge Bases. SIGMOD Conference 1989: 253-262
  44. Isabel F. Cruz, Theodore S. Norvell: Aggregative Closure: An Extension of Transitive Closure. ICDE 1989: 384-391
  45. Rakesh Agrawal, H. V. Jagadish: Materialization and Incremental Update of Path Information. ICDE 1989: 374-383
  46. Rakesh Agrawal, Shaul Dar, H. V. Jagadish: Composition of Database Relations. ICDE 1989: 102-108
  47. Umeshwar Dayal: Queries and Views in an Object-Oriented Data Model. DBPL 1989: 80-102
  48. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
  49. Yannis E. Ioannidis, Raghu Ramakrishnan: Efficient Transitive Closure Algorithms. VLDB 1988: 382-394
  50. Rakesh Agrawal, H. V. Jagadish: Efficient Search in Very Large Databases. VLDB 1988: 407-418
  51. Seppo Sippu, Eljas Soisalon-Soininen: A Generalized Transitive Closure for Relational Queries. PODS 1988: 325-332
  52. Michael Stonebraker: Future Trends in Data Base Systems. ICDE 1988: 222-231
  53. Malcolm P. Atkinson, Peter Buneman: Types and Persistence in Database Programming Languages. ACM Comput. Surv. 19(2): 105-190(1987)
  54. Hongjun Lu: New Strategies for Computing the Transitive Closure of a Database Relation. VLDB 1987: 267-274
  55. Rakesh Agrawal, H. V. Jagadish: Direct Algorithms for Computing the Transitive Closure of Database Relations. VLDB 1987: 255-266
  56. Jiawei Han, Lawrence J. Henschen: Handling Redundancy in the Processing of Recursive Database Queries. SIGMOD Conference 1987: 73-81
  57. Isabel F. Cruz, Alberto O. Mendelzon, Peter T. Wood: A Graphical Query Language Supporting Recursion. SIGMOD Conference 1987: 323-330
  58. Rakesh Agrawal: Alpha: An Extension of Relational Algebra to Express a Class of Recursive Queries. ICDE 1987: 580-590
  59. Frank Manola, Jack A. Orenstein: Toward a General Spatial Data Model for an Object-Oriented DBMS. VLDB 1986: 328-335
  60. Yannis E. Ioannidis: On the Computation of the Transitive Closure of Relational Operators. VLDB 1986: 403-411
  61. Don S. Batory, Michael V. Mannino: Panel on Extensible Database Systems. SIGMOD Conference 1986: 187-190
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:39:45 2009