One-sided recursions

ABSTRACT

The performance of systems with recursive query languages can be improved by recognizing simple, easily evaluable classes of recursions and using algorithms tailored to these classes whenever possible. In this paper we identify a useful subset of recursive definitions, the one-sided recursions. We show how to detect one-sided recursions, and give two simple evaluation algorithms that cover one-sided definitions in that for any selection on a one-sided definition, at least one of the two algorithms will apply. These algorithms have simple termination conditions, maintain minimal state and use selections on the recursively defined relation whenever possible. We show that there are no similar algorithms for many-sided recursions We also prove that it is undecidable whether an arbitrary definition has an equivalent one-sided definition. However, we do present a procedure that converts many potentially one-sided recursions to one-sided form, and prove it complete for a useful class of recursions.

REFERENCES

• 1: 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]
• 2: Francois Bancilhon , David Maier , Yehoshua Sagiv , Jeffrey D Ullman, Magic sets and other strange ways to implement logic programs (extended abstract), Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.1-15, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15399]
• 3: Francois Bancilhon , Raghu Ramakrishnan, An amateur's introduction to recursive query processing strategies, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.16-52, May 28-30, 1986, Washington, D.C., United States
• 4: C Chang On the evaluation of queries containing derived relationds in a relational data base In H Gallalre, J Minker, and J Nicolas, edilors, Advances in Data Base Theory, Volume 1, Plenum Press, 1981
• 5: Hiam Gaifman, Harry Manson, Yehoshua Sagiv, and Moshe Y Vardi Undecidable optimization problems for database logic programs December 1986 Unpublsihed manuscript
• 6: Micheal R Genesereth The MRS Casebook Technical Report IIPP-83-26, Stanford University. May 1983
• 7: 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]
• 8: H V Jagadish and Rakesh Agtawal A study of transitive closure as a recutslon mechanism 1986 Unpublished Manuscript
• 9: Paris C Kanellakis Logic Programming and Parallel Complexity Technical Report CS-86 23, Brown University, October 1986
• 10: Jack Minker and Jean M Nicolas On recursive axioms in relational databases lnformation Systems, 8(1) 1 13, 1q82
• 11: Jeff Naughton, Data independent recursion in deductive databases, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.267-279, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15420]
• 12: Jeffrey F Naughton One sided recursions 1987 Stanford TR, to appear
• 13: Jeffrey F. Naughton, Optimizing function-free recursive inference rules, Stanford University, Stanford, CA, 1986
• 14: Linda Ness, Recursive Linear Recursion to Transitive Closure, University of Texas at Austin, Austin, TX, 1986
• 15: Y. Sagiv, Optimizing datalog programs, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.349-362, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28696]

INDEX TERMS

Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Program and recursion schemes
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Recursive function theory

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

General Terms:
Algorithms, Languages, Management, Performance, Theory