Commutativity and Its Role in the Processing of Linear Recursion

Summary: Characterizes when pairs of linear, function-free recursive rules commute, giving a syntactic sufficient condition and, for a restricted class, a polynomial-time decidable necessary-and-sufficient test. Relates commutativity algebraically to separable recursion and recursively redundant predicates. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: he7aa2ec15dfa1151
Venue: VLDB
Year: 1989
Pagerank: 6.7134031e-05
Overall Rank: 4,228 | 71.59%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Yannis E. Ioannidis (University of Wisconsin)

BibTeX Citation

@article{ioannidis_vldb89,
        title = {{Commutativity and Its Role in the Processing of Linear Recursion}},
        author = {Ioannidis, Yannis E.},
        journal = {PVLDB},
        series = {{VLDB} '89},
        pages = {155--165},
        year = {1989}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,026	Proof-Tree Transformation Theorems and Their Applications	1989	PODS	9.1626332e-05
7,702	Hard problems for simple logic programs	1990	SIGMOD	5.4729121e-05
8,059	Polynomial-time program transformations in deductive databases	1990	PODS	5.3961311e-05
13,412	Semigroup techniques in recursive query optimization	1990	PODS	4.9769913e-05
13,420	Factoring Augmented Regular Chain Programs	1990	VLDB	4.9769913e-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
353	On the Power of Magic	1987	PODS	0.00020213935
859	Query Optimization by Simulated Annealing	1987	SIGMOD	0.0001341356
946	A Time Bound on the Materialization of Some Recursively Defined Views	1985	VLDB	0.00012930818
1,287	On the Computation of the Transitive Closure of Relational Operators	1986	VLDB	0.00011179513
2,026	Proof-Tree Transformation Theorems and Their Applications	1989	PODS	9.1626332e-05
3,715	Compiling Separable Recursions	1988	SIGMOD	7.0736815e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,715	Compiling Separable Recursions	1988	SIGMOD
2	1,830	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS
3	3,849	Right-, left- and multi-linear rule transformations that maintain context information	1990	VLDB
4	2,110	A Study of Transitive Closure As a Recursion Mechanism	1987	SIGMOD
5	13,412	Semigroup techniques in recursive query optimization	1990	PODS
6	1,981	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD
7	13,475	A Necessary Condition For A Doubly Recursive Rule To Be Equivalent To A Linear Recursive Rule	1987	SIGMOD
8	6,746	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS
9	5,417	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS
10	2,026	Proof-Tree Transformation Theorems and Their Applications	1989	PODS