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.1232056e-05
Overall Rank: 3,414 | 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
909	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00015428222
2,675	A Performance Study Of Transitive Closure Algorithms	1994	SIGMOD	8.3315228e-05
3,413	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS	7.1240395e-05
6,876	Modular Acyclicity and Tail Recursion in Logic Programs	1991	PODS	4.8977465e-05
7,293	On Tree-Based Techniques for Query Evaluation	1992	PODS	4.7740089e-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.00012054867
2,042	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.699257e-05
2,474	Graph-Theoretic Methods In Database Theory	1990	PODS	8.7135761e-05
3,585	Right-, left- and multi-linear rule transformations that maintain context information	1990	VLDB	6.9454028e-05
5,492	Mixed-Approach Algorithms for Transitive Closure	1991	PODS	5.4771871e-05
6,876	Modular Acyclicity and Tail Recursion in Logic Programs	1991	PODS	4.8977465e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,554	Rule-Based Translation of Relational Queries into Iterative Programs	1986	SIGMOD	5.0155947e-05
12,981	A Necessary Condition For A Doubly Recursive Rule To Be Equivalent To A Linear Recursive Rule	1987	SIGMOD	4.1945683e-05
3,999	EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract)	1987	PODS	6.5469939e-05
12,921	Semigroup techniques in recursive query optimization	1990	PODS	4.1945683e-05
7,598	Polynomial-time program transformations in deductive databases	1990	PODS	4.7004867e-05
3,585	Right-, left- and multi-linear rule transformations that maintain context information	1990	VLDB	6.9454028e-05
16	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.0010066783
5,180	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS	5.6422249e-05
7,075	Magic-sets Transformation in Nonrecursive Systems	1992	PODS	4.842703e-05
2,042	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.699257e-05