Commutativity And Its Role In The Processing Of Linear Recursion

Summary: Analyzes commutativity in linear recursion for query processing; gives a polynomial-time test and a sufficient condition for two linear, restricted rules to commute. Centers commutativity in separable recursion and redundant predicates via algebraic structure. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 7895
Venue: VLDB
Year: 1989
Pagerank: 6.279813e-05
Overall Rank: 4,324 | 69.95%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Yannis E. Ioannidis

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,038	Proof-Tree Transformation Theorems and Their Applications	1989	PODS	9.7062591e-05
7,018	Hard problems for simple logic programs	1990	SIGMOD	4.8555836e-05
7,603	Polynomial-time program transformations in deductive databases	1990	PODS	4.6959912e-05
12,931	Semigroup techniques in recursive query optimization	1990	PODS	4.1905499e-05
12,939	Factoring Augmented Regular Chain Programs	1990	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
359	On the Power of Magic	1987	PODS	0.00025830228
569	Query Optimization by Simulated Annealing	1987	SIGMOD	0.00019912758
612	A Time Bound on the Materialization of Some Recursively Defined Views	1985	VLDB	0.0001915957
1,078	On The Computation Of The Transitive Closure Of Relational Operators	1986	VLDB	0.00014223265
2,038	Proof-Tree Transformation Theorems and Their Applications	1989	PODS	9.7062591e-05
3,556	Compiling Separable Recursions	1988	SIGMOD	6.9712392e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,556	Compiling Separable Recursions	1988	SIGMOD	6.9712392e-05
1,997	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.837483e-05
3,589	Right-, left- and multi-linear rule transformations that maintain context information	1990	VLDB	6.9387274e-05
1,905	A Study of Transitive Closure As a Recursion Mechanism	1987	SIGMOD	0.00010142772
12,931	Semigroup techniques in recursive query optimization	1990	PODS	4.1905499e-05
2,048	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.689916e-05
12,992	A Necessary Condition For A Doubly Recursive Rule To Be Equivalent To A Linear Recursive Rule	1987	SIGMOD	4.1905499e-05
6,234	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS	5.1387584e-05
5,183	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS	5.6368566e-05
2,038	Proof-Tree Transformation Theorems and Their Applications	1989	PODS	9.7062591e-05