Traversal recursion: a practical approach to supporting recursive applications

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.

REFERENCES

• AHO76: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• AHO79: Alfred V. Aho , Jeffrey D. Ullman, Universality of data retrieval languages, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.110-119, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567763]
• BANC86: Francois Bancilhon, Naive evaluation of recursively defined relations, On knowledge base management systems: integrating artificial intelligence and d atabase technologies, Springer-Verlag New York, Inc., New York, NY, 1986
• BAYE85: Bayer R "Query Evaluation and Recurslon m Deductive Database Systems " 1985
• CARR79: Carre B Graphs and Networks Oxford Umverslty Press New York NY 1979 ch 3
• CHAK82: Chakravarthy U S J Minker and D Tran "interfacing Predicate Logic Languages and Relational Databases" Proc of the 1st Intl Logic Programming Conf France Sept 1982
• CHAN82: Chandra A and D Harel "Horn Clause Quenes and Generalization" ACM SIGACT-SIGMOD Symp on Principles of Database Systems Conf 1982
• CLEM81: Eric K. Clemons, Design of an external schema facility to define and process recursive structures, ACM Transactions on Database Systems (TODS), v.6 n.2, p.295-311, June 1981 [doi>10.1145/319566.319576]
• CLOC81: Clocksm W F and C S Melhsh Programming m PROLOG Spnnger-Verlag New York NY 1981
• DAYA85: Dayal U et al "Probe -A Knowledge-Oriented Database Sys tern Prehmmary Analysis" Technical Report CCA 85-03 Corn puter Corporation of America July 1985
• DAYA86: Umeshwar Dayal , John M Smith, PROBE: a knowledge-oriented database management system, On knowledge base management systems: integrating artificial intelligence and d atabase technologies, Springer-Verlag New York, Inc., New York, NY, 1986
• HEIL85: Heder S I and A Rosenthat "G Whiz A Visual Interface for the Functional Model with Recursion " Proc of the 11th Conf on VLDB 1985
• HENS84: Lawrence J. Henschen , Shamim A. Naqvi, On compiling queries in recursive first-order databases, Journal of the ACM (JACM), v.31 n.1, p.47-85, Jan. 1984 [doi>10.1145/2422.2423]
• IOAN85: Ioanntdes Y "A Time Bound on the Matenahzatlon of some Recursively Defined Views" Proc of the 11th Conf on VLDB 1985
• JAME82: James G and W Stoeller "Operattons on Tree Structured Tables " X3H2-26-15 Standards Committee Working Paper 1982 pp 81 92
• JARK84: Matthias Jarke , Jim Clifford , Yannis Vassiliou, An optimizing prolog front-end to a relational query system, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• JARK85: Jarke M Lmnemann V and Schmldt J "Data Constructors On the Integrahon of Rules and Relations" Proc of the Hth Conf on VLDB 1985
• MERR84: T H Merrett, Relational Information Systems, Reston Publishing Co., Reston, VA, 1984
• OREN86: Jack A. Orenstein, Spatial query processing in an object-oriented database system, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.326-336, May 28-30, 1986, Washington, D.C., United States
• ROSE84: Arnon Rosenthal , Sandra Heiler , Frank Manola, An Example of Knowledge-Based Query Processing in a CAD/CAM DBMS, Proceedings of the 10th International Conference on Very Large Data Bases, p.363-370, August 27-31, 1984
• ROSE85: Rosenthal A "Traversal Recurslons " Probe Project Working Paper Computer Corporation of America 1985
• SHIP81: David W. Shipman, The functional data model and the data languages DAPLEX, ACM Transactions on Database Systems (TODS), v.6 n.1, p.140-173, March 1981 [doi>10.1145/319540.319561]
• ULLM85: Jeffrey D. Ullman, Implementation of logical query languages for databases, ACM Transactions on Database Systems (TODS), v.10 n.3, p.289-321, Sept. 1985 [doi>10.1145/3979.3980]
• YOKO84: Haruo Yokota , Susumu Kunifuji , Takeo Kakuta , Nobuyoshi Miyazaki , Shigeki Shibayama , Kunio Murakami, An enhanced inference mechanism for generating relational algebra queries, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588045]
• ZLOO75: Zloof M "Query By Example Proc of the NCC44 May 1975

INDEX TERMS

Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Performance