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)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 12 of 12 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 256 | GraphLog: a Visual Formalism for Real Life Recursion | 1990 | PODS | 0.00030259041 |
| 274 | Regular Path Queries with Constraints | 1997 | PODS | 0.00029390022 |
| 688 | Estimating the Size of Generalized Transitive Closures | 1989 | VLDB | 0.00018134733 |
| 880 | Efficient Transitive Closure Algorithms | 1988 | VLDB | 0.00015667998 |
| 2,042 | Efficient Evaluation of Right-, Left-, and Multi-Linear Rules | 1989 | SIGMOD | 9.699257e-05 |
| 2,474 | Graph-Theoretic Methods In Database Theory | 1990 | PODS | 8.7135761e-05 |
| 3,553 | Compiling Separable Recursions | 1988 | SIGMOD | 6.9779134e-05 |
| 4,178 | Argument Reduction by Factoring | 1989 | VLDB | 6.3812002e-05 |
| 4,370 | Distributed Processing Of Logic Programs | 1988 | SIGMOD | 6.2486359e-05 |
| 7,156 | Counting Methods for Cyclic Relations | 1988 | PODS | 4.8145046e-05 |
| 7,181 | A Generalized Transitive Closure for Relational Queries | 1988 | PODS | 4.8074621e-05 |
| 7,293 | On Tree-Based Techniques for Query Evaluation | 1992 | PODS | 4.7740089e-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.0010066783 |
| 77 | An Amateur's Introduction to Recursive Query Processing Strategies | 1986 | SIGMOD | 0.00057043861 |
| 200 | OPTIMIZING DATALOG PROGRAMS (Extended Abstract) | 1987 | PODS | 0.00035012858 |
| 1,185 | Data Independent Recursion in Deductive Databases | 1986 | PODS | 0.00013445831 |
| 1,648 | A Study of Transitive Closure As a Recursion Mechanism | 1987 | SIGMOD | 0.00011028408 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,185 | Data Independent Recursion in Deductive Databases | 1986 | PODS | 0.00013445831 |
| 365 | On the Power of Magic | 1987 | PODS | 0.00025585898 |
| 5,259 | On the Optimization of Recursive Relational Queries: Application to Graph Queries | 2020 | SIGMOD | 5.5984356e-05 |
| 12,962 | Classification Of Recursive Formulas In Deductive Databases | 1988 | SIGMOD | 4.1945683e-05 |
| 3,553 | Compiling Separable Recursions | 1988 | SIGMOD | 6.9779134e-05 |
| 3,999 | EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract) | 1987 | PODS | 6.5469939e-05 |
| 2,042 | Efficient Evaluation of Right-, Left-, and Multi-Linear Rules | 1989 | SIGMOD | 9.699257e-05 |
| 7,070 | On the Decidability of Containment of Recursive Datalog Queries - Preliminary report | 2004 | PODS | 4.843579e-05 |
| 1,529 | Evaluation Of Database Recursive Logic Programs As Recurrent Function Series | 1986 | SIGMOD | 0.00011496686 |
| 2,206 | A Decidable Class of Bounded Recursions | 1987 | PODS | 9.2910236e-05 |