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.0940924e-05
Overall Rank
2,065 | 86.12%
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
297 GraphLog: a Visual Formalism for Real Life Recursion 1990 PODS 0.00021840374
356 Regular Path Queries with Constraints 1997 PODS 0.00020103855
1,363 Efficient Transitive Closure Algorithms 1988 VLDB 0.00010914322
1,416 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00010734049
1,979 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD 9.2716242e-05
3,020 Graph-Theoretic Methods In Database Theory 1990 PODS 7.7448163e-05
3,713 Compiling Separable Recursions 1988 SIGMOD 7.0770304e-05
4,187 Argument Reduction by Factoring 1989 VLDB 6.748235e-05
4,205 Distributed Processing Of Logic Programs 1988 SIGMOD 6.735459e-05
7,576 A Generalized Transitive Closure for Relational Queries 1988 PODS 5.4924986e-05
8,195 On Tree-Based Techniques for Query Evaluation 1992 PODS 5.3798301e-05
9,689 Counting Methods for Cyclic Relations 1988 PODS 5.1406988e-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.00059023577
67 An Amateur's Introduction to Recursive Query Processing Strategies 1986 SIGMOD 0.00038009523
317 OPTIMIZING DATALOG PROGRAMS (Extended Abstract) 1987 PODS 0.00021220438
1,201 Data Independent Recursion in Deductive Databases 1986 PODS 0.00011560838
2,109 A Study of Transitive Closure As a Recursion Mechanism 1987 SIGMOD 9.0238479e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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