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.0607099e-05
Overall Rank
2,078 | 86.08%
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
299 GraphLog: a Visual Formalism for Real Life Recursion 1990 PODS 0.00021766741
358 Regular Path Queries with Constraints 1997 PODS 0.00020030407
1,368 Efficient Transitive Closure Algorithms 1988 VLDB 0.00010877284
1,423 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00010696781
1,986 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD 9.2371562e-05
3,030 Graph-Theoretic Methods In Database Theory 1990 PODS 7.7156987e-05
3,722 Compiling Separable Recursions 1988 SIGMOD 7.0503269e-05
4,206 Argument Reduction by Factoring 1989 VLDB 6.722747e-05
4,224 Distributed Processing Of Logic Programs 1988 SIGMOD 6.710075e-05
7,599 A Generalized Transitive Closure for Relational Queries 1988 PODS 5.4717527e-05
8,218 On Tree-Based Techniques for Query Evaluation 1992 PODS 5.3595692e-05
9,724 Counting Methods for Cyclic Relations 1988 PODS 5.121278e-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.00058816744
67 An Amateur's Introduction to Recursive Query Processing Strategies 1986 SIGMOD 0.0003786983
319 OPTIMIZING DATALOG PROGRAMS (Extended Abstract) 1987 PODS 0.00021142713
1,204 Data Independent Recursion in Deductive Databases 1986 PODS 0.00011517335
2,126 A Study of Transitive Closure As a Recursion Mechanism 1987 SIGMOD 8.9903441e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 1,204 Data Independent Recursion in Deductive Databases 1986 PODS
2 353 On the Power of Magic 1987 PODS
3 13,495 Classification Of Recursive Formulas In Deductive Databases 1988 SIGMOD
4 5,073 On the Optimization of Recursive Relational Queries: Application to Graph Queries 2020 SIGMOD
5 3,722 Compiling Separable Recursions 1988 SIGMOD
6 4,501 EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract) 1987 PODS
7 1,986 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD
8 7,086 On the Decidability of Containment of Recursive Datalog Queries - Preliminary report 2004 PODS
9 2,112 Evaluation Of Database Recursive Logic Programs As Recurrent Function Series 1986 SIGMOD
10 2,075 A Decidable Class of Bounded Recursions 1987 PODS