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: 930
Venue: PODS
Year: 1991
Pagerank: 7.2683975e-05
Overall Rank: 3,603 | 75.29%
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
953	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00012997935
3,245	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS	7.60327e-05
3,491	A Performance Study Of Transitive Closure Algorithms	1994	SIGMOD	7.3658999e-05
7,454	Modular Acyclicity and Tail Recursion in Logic Programs	1991	PODS	5.6128072e-05
8,035	On Tree-Based Techniques for Query Evaluation	1992	PODS	5.5028526e-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,410	Magic is Relevant	1990	SIGMOD	0.00010853223
1,921	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.4809066e-05
2,957	Graph-Theoretic Methods In Database Theory	1990	PODS	7.9200375e-05
3,767	Right-, left- and multi-linear rule transformations that maintain context information	1990	VLDB	7.1421254e-05
5,975	Mixed-Approach Algorithms for Transitive Closure	1991	PODS	6.0220239e-05
7,454	Modular Acyclicity and Tail Recursion in Logic Programs	1991	PODS	5.6128072e-05

Semantically Similar Papers

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