DBScholar

Back to papers

Linearizing nonlinear recursions in polynomial time (Extended Abstract)

Summary: Characterizes when bilinear recursions admit equivalent linear recursions: iff a designated partial proof tree is contained in a bounded set of generated partial proof trees. Replaces exponential CQ-containment tests by necessary-and-sufficient syntactic checks decidable in polynomial time, enabling efficient linear-logic evaluation. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
h6eef652caec84caa
Venue
PODS
Year
1989
Pagerank
6.1401229e-05
Overall Rank
5,413 | 63.61%
DOI
10.1145/73721.73740

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{saraiya_pods89,
        address = {New York, NY, USA},
        series = {{PODS} '89},
        title = {{Linearizing nonlinear recursions in polynomial time (Extended Abstract)}},
        url = {https://dl.acm.org/doi/10.1145/73721.73740},
        doi = {10.1145/73721.73740},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Saraiya, Yatin P.},
        year = {1989}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank Citing Paper Year Venue Pagerank
2,024 Proof-Tree Transformation Theorems and Their Applications 1989 PODS 9.166955e-05
7,696 Hard problems for simple logic programs 1990 SIGMOD 5.4755041e-05
8,053 Polynomial-time program transformations in deductive databases 1990 PODS 5.3986864e-05
13,389 Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases 1991 PODS 4.9793485e-05
13,406 Semigroup techniques in recursive query optimization 1990 PODS 4.9793485e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 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
352 On the Power of Magic 1987 PODS 0.00020223279
440 On the Implementation of a Simple Class of Logic Queries for Databases 1986 PODS 0.00018227953
2,024 Proof-Tree Transformation Theorems and Their Applications 1989 PODS 9.166955e-05
4,425 Magic Counting Methods 1987 SIGMOD 6.6039832e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 7,984 Termination Detection in Logic Programs using Argument Sizes* (Extended Abstract) 1991 PODS
2 3,315 On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs 1994 PODS
3 4,479 EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract) 1987 PODS
4 3,675 Overbound and Right-Linear Queries 1991 PODS
5 8,053 Polynomial-time program transformations in deductive databases 1990 PODS
6 4,228 Commutativity and Its Role in the Processing of Linear Recursion 1989 VLDB
7 2,024 Proof-Tree Transformation Theorems and Their Applications 1989 PODS
8 1,979 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD
9 6,741 Inherent Complexity of Recursive Queries (Extended Abstract) 1999 PODS
10 13,469 A Necessary Condition For A Doubly Recursive Rule To Be Equivalent To A Linear Recursive Rule 1987 SIGMOD