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
hcb93f619363a4a70
Venue
PODS
Year
1987
Pagerank
9.0898007e-05
Overall Rank
2,067 | 86.11%
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
298 GraphLog: a Visual Formalism for Real Life Recursion 1990 PODS 0.00021830158
356 Regular Path Queries with Constraints 1997 PODS 0.0002009439
1,364 Efficient Transitive Closure Algorithms 1988 VLDB 0.00010909199
1,416 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00010729775
1,981 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD 9.267247e-05
3,021 Graph-Theoretic Methods In Database Theory 1990 PODS 7.741152e-05
3,715 Compiling Separable Recursions 1988 SIGMOD 7.0736815e-05
4,187 Argument Reduction by Factoring 1989 VLDB 6.7450426e-05
4,206 Distributed Processing Of Logic Programs 1988 SIGMOD 6.7322742e-05
7,583 A Generalized Transitive Closure for Relational Queries 1988 PODS 5.4898987e-05
8,203 On Tree-Based Techniques for Query Evaluation 1992 PODS 5.3772846e-05
9,695 Counting Methods for Cyclic Relations 1988 PODS 5.1382653e-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
18 MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract) 1986 PODS 0.00058997063
67 An Amateur's Introduction to Recursive Query Processing Strategies 1986 SIGMOD 0.00037991902
317 OPTIMIZING DATALOG PROGRAMS (Extended Abstract) 1987 PODS 0.00021210493
1,201 Data Independent Recursion in Deductive Databases 1986 PODS 0.00011555372
2,110 A Study of Transitive Closure As a Recursion Mechanism 1987 SIGMOD 9.0195865e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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