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: 864
Venue: PODS
Year: 1989
Pagerank: 5.6422249e-05
Overall Rank: 5,180 | 63.97%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Yatin P. Saraiya

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,036	Proof-Tree Transformation Theorems and Their Applications	1989	PODS	9.714898e-05
7,018	Hard problems for simple logic programs	1990	SIGMOD	4.8602644e-05
7,598	Polynomial-time program transformations in deductive databases	1990	PODS	4.7004867e-05
12,904	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS	4.1945683e-05
12,921	Semigroup techniques in recursive query optimization	1990	PODS	4.1945683e-05

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
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
296	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS	0.00028644922
365	On the Power of Magic	1987	PODS	0.00025585898
2,036	Proof-Tree Transformation Theorems and Their Applications	1989	PODS	9.714898e-05
4,555	Magic Counting Methods	1987	SIGMOD	6.0891017e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,266	Termination Detection in Logic Programs using Argument Sizes* (Extended Abstract)	1991	PODS	4.782728e-05
3,413	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS	7.1240395e-05
3,999	EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract)	1987	PODS	6.5469939e-05
3,414	Overbound and Right-Linear Queries	1991	PODS	7.1232056e-05
7,598	Polynomial-time program transformations in deductive databases	1990	PODS	4.7004867e-05
4,329	Commutativity And Its Role In The Processing Of Linear Recursion	1989	VLDB	6.2858126e-05
2,036	Proof-Tree Transformation Theorems and Their Applications	1989	PODS	9.714898e-05
2,042	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.699257e-05
6,236	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS	5.1436959e-05
12,981	A Necessary Condition For A Doubly Recursive Rule To Be Equivalent To A Linear Recursive Rule	1987	SIGMOD	4.1945683e-05