One-sided recursions
- 1 June 1987
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 340-348
- https://doi.org/10.1145/28659.28695
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.Keywords
This publication has 10 references indexed in Scilit:
- Optimizing datalog programsPublished by Association for Computing Machinery (ACM) ,1987
- One-sided recursionsPublished by Association for Computing Machinery (ACM) ,1987
- An amateur's introduction to recursive query processing strategiesPublished by Association for Computing Machinery (ACM) ,1986
- Logic programming and parallel complexityPublished by Springer Nature ,1986
- Magic sets and other strange ways to implement logic programs (extended abstract)Published by Association for Computing Machinery (ACM) ,1985
- Data independent recursion in deductive databasesPublished by Association for Computing Machinery (ACM) ,1985
- On compiling queries in recursive first-order databasesJournal of the ACM, 1984
- On recursive axioms in deductive databasesInformation Systems, 1983
- Advances in Data Base TheoryPublished by Springer Nature ,1981
- Universality of data retrieval languagesPublished by Association for Computing Machinery (ACM) ,1979