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: 862
Venue: PODS
Year: 1989
Pagerank: 9.3746238e-05
Overall Rank: 1,970 | 86.49%
DOI: 10.1145/73721.73739

Incoming Non-self Citations Over Time

Authors

1. Raghu Ramakrishnan (University of Wisconsin)
2. Yehoshua Sagiv (Hebrew University)
3. Jeffrey D. Ullman (Stanford University)
4. Moshe Y. Vardi (IBM)

BibTeX Citation

@inproceedings{ramakrishnan_pods89,
        address = {New York, NY, USA},
        series = {{PODS} '89},
        title = {{Proof-Tree Transformation Theorems and Their Applications}},
        url = {https://dl.acm.org/doi/10.1145/73721.73739},
        doi = {10.1145/73721.73739},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Ramakrishnan, Raghu and Sagiv, Yehoshua and Ullman, Jeffrey D. and Vardi, Moshe Y.},
        year = {1989}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
515	Answering Recursive Queries Using Views	1997	PODS	0.00017177428
953	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00012997935
3,563	Describing and Using Query Capabilities of Heterogeneous Sources	1997	VLDB	7.3076984e-05
4,150	Commutativity and Its Role in the Processing of Linear Recursion	1989	VLDB	6.8705682e-05
4,190	QuickFOIL: Scalable Inductive Logic Programming	2015	VLDB	6.8431849e-05
5,288	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS	6.280882e-05
7,549	Hard problems for simple logic programs	1990	SIGMOD	5.6011655e-05
7,886	Polynomial-time program transformations in deductive databases	1990	PODS	5.5225498e-05
13,099	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS	5.093636e-05
13,100	Detecting Redundant Tuples During Query Evaluation	1991	PODS	5.093636e-05
13,116	Semigroup techniques in recursive query optimization	1990	PODS	5.093636e-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.00060089598
174	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00027231487
313	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.0002168869
429	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS	0.00018607152
616	Parallel Evaluation of Recursive Rule Queries	1986	PODS	0.00015712636
3,629	Compiling Separable Recursions	1988	SIGMOD	7.2392728e-05
4,150	Commutativity and Its Role in the Processing of Linear Recursion	1989	VLDB	6.8705682e-05
5,288	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS	6.280882e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,627	Non-Linear Prefixes in Query Languages	2007	PODS
2	11,135	Query Optimization by Quantifier Elimination	2024	PODS
3	12,229	The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity	2013	PODS
4	13,116	Semigroup techniques in recursive query optimization	1990	PODS
5	3,767	Right-, left- and multi-linear rule transformations that maintain context information	1990	VLDB
6	1,921	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD
7	6,613	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS
8	7,886	Polynomial-time program transformations in deductive databases	1990	PODS
9	5,288	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS
10	4,150	Commutativity and Its Role in the Processing of Linear Recursion	1989	VLDB