DBScholar

Back to papers

One-Sided Recursions

Summary: Introduce 'one-sided recursions', a subset of recursive definitions that allows simple, selection-aware evaluation using minimal state. Present detection and two complementary algorithms (one applies per selection), prove many-sided impossibility and undecidability of equivalence, and give a practical conversion procedure complete for a useful class. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
807
Venue
PODS
Year
1987
Pagerank
9.2819369e-05
Overall Rank
2,033 | 86.06%
DOI
10.1145/28659.28695

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{naughton_pods87,
        address = {New York, NY, USA},
        series = {{PODS} '87},
        title = {{One-Sided Recursions}},
        url = {https://dl.acm.org/doi/10.1145/28659.28695},
        doi = {10.1145/28659.28695},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Naughton, Jeffrey F.},
        year = {1987}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank Citing Paper Year Venue Pagerank
300 GraphLog: a Visual Formalism for Real Life Recursion 1990 PODS 0.00022046803
348 Regular Path Queries with Constraints 1997 PODS 0.00020518814
1,330 Efficient Transitive Closure Algorithms 1988 VLDB 0.00011140171
1,382 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00010965236
1,921 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD 9.4809066e-05
2,957 Graph-Theoretic Methods In Database Theory 1990 PODS 7.9200375e-05
3,629 Compiling Separable Recursions 1988 SIGMOD 7.2392728e-05
4,099 Argument Reduction by Factoring 1989 VLDB 6.9030568e-05
4,121 Distributed Processing Of Logic Programs 1988 SIGMOD 6.8889854e-05
7,438 A Generalized Transitive Closure for Relational Queries 1988 PODS 5.6184826e-05
8,035 On Tree-Based Techniques for Query Evaluation 1992 PODS 5.5028526e-05
9,503 Counting Methods for Cyclic Relations 1988 PODS 5.2586367e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
16 MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract) 1986 PODS 0.00060089598
63 An Amateur's Introduction to Recursive Query Processing Strategies 1986 SIGMOD 0.00038782376
313 OPTIMIZING DATALOG PROGRAMS (Extended Abstract) 1987 PODS 0.0002168869
1,173 Data Independent Recursion in Deductive Databases 1986 PODS 0.00011822695
2,076 A Study of Transitive Closure As a Recursion Mechanism 1987 SIGMOD 9.212586e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 13,099 Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases 1991 PODS
2 344 On the Power of Magic 1987 PODS
3 4,972 On the Optimization of Recursive Relational Queries: Application to Graph Queries 2020 SIGMOD
4 13,158 Classification Of Recursive Formulas In Deductive Databases 1988 SIGMOD
5 3,629 Compiling Separable Recursions 1988 SIGMOD
6 4,425 EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract) 1987 PODS
7 1,921 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD
8 6,926 On the Decidability of Containment of Recursive Datalog Queries - Preliminary report 2004 PODS
9 2,054 Evaluation Of Database Recursive Logic Programs As Recurrent Function Series 1986 SIGMOD
10 2,015 A Decidable Class of Bounded Recursions 1987 PODS