Overbound and Right-Linear Queries

Summary: Proposes partial-SIPS optimizations for a subclass of linear recursive Datalog queries, giving an algorithm that outperforms full-SIPS techniques (magic-sets/right-linear) and syntactically characterizes when partial SIPS are strictly preferable. Also compares context right-linear vs. magic-sets for optimizer choice and shows right- and left-linear programs are syntactic duals. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 931
Venue: PODS
Year: 1991
Pagerank: 7.116211e-05
Overall Rank: 3,417 | 76.26%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Inderpal Singh Mumick
2. Hamid Pirahesh

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
907	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00015417107
2,679	A Performance Study Of Transitive Closure Algorithms	1994	SIGMOD	8.3223476e-05
3,414	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS	7.1172834e-05
6,881	Modular Acyclicity and Tail Recursion in Logic Programs	1991	PODS	4.8929836e-05
7,289	On Tree-Based Techniques for Query Evaluation	1992	PODS	4.7692311e-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
1,423	Magic is Relevant	1990	SIGMOD	0.00012047765
2,048	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.689916e-05
2,473	Graph-Theoretic Methods In Database Theory	1990	PODS	8.7048914e-05
3,589	Right-, left- and multi-linear rule transformations that maintain context information	1990	VLDB	6.9387274e-05
5,504	Mixed-Approach Algorithms for Transitive Closure	1991	PODS	5.4716648e-05
6,881	Modular Acyclicity and Tail Recursion in Logic Programs	1991	PODS	4.8929836e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,550	Rule-Based Translation of Relational Queries into Iterative Programs	1986	SIGMOD	5.0113524e-05
12,992	A Necessary Condition For A Doubly Recursive Rule To Be Equivalent To A Linear Recursive Rule	1987	SIGMOD	4.1905499e-05
3,990	EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract)	1987	PODS	6.5536618e-05
12,931	Semigroup techniques in recursive query optimization	1990	PODS	4.1905499e-05
7,603	Polynomial-time program transformations in deductive databases	1990	PODS	4.6959912e-05
3,589	Right-, left- and multi-linear rule transformations that maintain context information	1990	VLDB	6.9387274e-05
16	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00099936325
5,183	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS	5.6368566e-05
7,069	Magic-sets Transformation in Nonrecursive Systems	1992	PODS	4.8380576e-05
2,048	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.689916e-05