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: hdca3b8e1991e549f
Venue: PODS
Year: 1991
Pagerank: 7.081251e-05
Overall Rank: 3,685 | 75.31%
DOI: 10.1145/113413.113425

Incoming Non-self Citations Over Time

Authors

1. Inderpal Singh Mumick (Stanford University)
2. Hamid Pirahesh (IBM)

BibTeX Citation

@inproceedings{mumick_pods91,
        address = {New York, NY, USA},
        series = {{PODS} '91},
        title = {{Overbound and Right-Linear Queries}},
        url = {https://dl.acm.org/doi/10.1145/113413.113425},
        doi = {10.1145/113413.113425},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Mumick, Inderpal Singh and Pirahesh, Hamid},
        year = {1991}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
981	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00012688969
3,326	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS	7.4103766e-05
3,567	A Performance Study Of Transitive Closure Algorithms	1994	SIGMOD	7.1826291e-05
7,622	Modular Acyclicity and Tail Recursion in Logic Programs	1991	PODS	5.4663379e-05
8,218	On Tree-Based Techniques for Query Evaluation	1992	PODS	5.3595692e-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,443	Magic is Relevant	1990	SIGMOD	0.00010618161
1,986	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.2371562e-05
3,030	Graph-Theoretic Methods In Database Theory	1990	PODS	7.7156987e-05
3,856	Right-, left- and multi-linear rule transformations that maintain context information	1990	VLDB	6.9565167e-05
6,117	Mixed-Approach Algorithms for Transitive Closure	1991	PODS	5.8653729e-05
7,622	Modular Acyclicity and Tail Recursion in Logic Programs	1991	PODS	5.4663379e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,282	Rule-Based Translation of Relational Queries into Iterative Programs	1986	SIGMOD
2	13,516	A Necessary Condition For A Doubly Recursive Rule To Be Equivalent To A Linear Recursive Rule	1987	SIGMOD
3	4,501	EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract)	1987	PODS
4	13,453	Semigroup techniques in recursive query optimization	1990	PODS
5	8,076	Polynomial-time program transformations in deductive databases	1990	PODS
6	3,856	Right-, left- and multi-linear rule transformations that maintain context information	1990	VLDB
7	18	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS
8	5,434	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS
9	7,300	Magic-sets Transformation in Nonrecursive Systems	1992	PODS
10	1,986	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD