Proof-Tree Transformation Theorems and Their Applications

Summary: Reduces existence of normal-form proof trees to conjunctive-query containment and to containment in the infinite union-of-CQs obtained by expanding recursive rules. Uses these tests to decide commutativity of linear rules—implying polynomial (vs exponential) counting complexity and separability—and to discover linear rule sets equivalent to nonlinear ones. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 863
Venue: PODS
Year: 1989
Pagerank: 9.714898e-05
Overall Rank: 2,036 | 85.84%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
532	Answering Recursive Queries Using Views	1997	PODS	0.00020778506
909	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00015428222
3,345	QuickFOIL: Scalable Inductive Logic Programming	2015	VLDB	7.1958815e-05
3,832	Describing and Using Query Capabilities of Heterogeneous Sources	1997	VLDB	6.7178862e-05
4,329	Commutativity And Its Role In The Processing Of Linear Recursion	1989	VLDB	6.2858126e-05
5,180	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS	5.6422249e-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,905	Detecting Redundant Tuples During Query Evaluation	1991	PODS	4.1945683e-05
12,921	Semigroup techniques in recursive query optimization	1990	PODS	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 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
172	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00038808816
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
537	Parallel Evaluation of Recursive Rule Queries	1986	PODS	0.0002068591
3,553	Compiling Separable Recursions	1988	SIGMOD	6.9779134e-05
4,329	Commutativity And Its Role In The Processing Of Linear Recursion	1989	VLDB	6.2858126e-05
5,180	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS	5.6422249e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,433	Non-Linear Prefixes in Query Languages	2007	PODS	4.1945683e-05
10,914	Query Optimization by Quantifier Elimination	2024	PODS	4.1945683e-05
12,031	The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity	2013	PODS	4.1945683e-05
12,921	Semigroup techniques in recursive query optimization	1990	PODS	4.1945683e-05
3,585	Right-, left- and multi-linear rule transformations that maintain context information	1990	VLDB	6.9454028e-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
7,598	Polynomial-time program transformations in deductive databases	1990	PODS	4.7004867e-05
5,180	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS	5.6422249e-05
4,329	Commutativity And Its Role In The Processing Of Linear Recursion	1989	VLDB	6.2858126e-05