Optimization of Nonrecursive Queries

Summary: Formal model and optimization problem for join ordering in nonrecursive queries; limits of exponential algorithms in deductive databases with hundreds of joins. Quadratic-time algorithm finds optimal join order for acyclic queries; robust to cyclic cases. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 7741
Venue: VLDB
Year: 1986
Pagerank: 0.00041430126
Overall Rank: 144 | 99.01%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 49 of 49 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
116	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.00046191288
140	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00042289025
195	Optimizing Queries over Multimedia Repositories	1996	SIGMOD	0.00035317524
388	Optimization of Large Join Queries	1988	SIGMOD	0.00024654816
400	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD	0.00024308369
422	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00023654556
569	Query Optimization by Simulated Annealing	1987	SIGMOD	0.00019912758
627	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00018959896
782	Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques	1989	SIGMOD	0.00016665859
811	Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization	1991	SIGMOD	0.00016385568
891	Towards an Open Architecture for LDL	1989	VLDB	0.00015531595
897	Estimating the Size of Generalized Transitive Closures	1989	VLDB	0.00015484372
903	The Design of an Acquisitional Query Processor For Sensor Networks	2003	SIGMOD	0.00015449454
1,041	Adaptive Ordering of Pipelined Stream Filters	2004	SIGMOD	0.00014470785
1,313	Cost-Based Optimization for Magic: Algebra and Implementation	1996	SIGMOD	0.00012629432
1,621	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011105663
1,846	Query Optimization in Heterogeneous DBMS	1992	VLDB	0.00010338936
2,051	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB	9.6871984e-05
2,062	PIQL: Success-Tolerant Query Processing in the Cloud	2012	VLDB	9.654149e-05
2,089	Practical Predicate Placement	1994	SIGMOD	9.5689208e-05
2,143	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	9.4437798e-05
2,222	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2019	SIGMOD	9.2598438e-05
2,268	Extending the Search Strategy in a Query Optimizer	1991	VLDB	9.1524415e-05
2,311	Parallel evaluation of multi-join queries	1995	SIGMOD	9.0610521e-05
2,771	On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces	1993	VLDB	8.149365e-05
2,867	Optimization of Queries with User-defined Predicates	1996	VLDB	7.9931252e-05
3,056	Multiple Join Size Estimation by Virtual Domains (extended abstract)	1993	PODS	7.6459653e-05
3,667	Bypassing Joins in Disjunctive Queries	1995	VLDB	6.8587775e-05
3,904	Cost-based Selection of Path Expression Processing Algorithms in Object-Oriented Databases	1996	VLDB	6.6437893e-05
4,001	Partial Join Order Optimization in the ParAccel Analytic Database	2009	SIGMOD	6.540692e-05
4,267	Flow Algorithms for Two Pipelined Filter Ordering Problems	2006	PODS	6.2995545e-05
4,734	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	5.9553181e-05
4,945	Lifting the Burden of History from Adaptive Query Processing	2004	VLDB	5.8115261e-05
5,091	Join Query Optimization Techniques for Complex Event Processing Applications	2018	VLDB	5.7010894e-05
5,303	Applying Hash Filters To Improving The Execution Of Bushy Trees	1993	VLDB	5.5740327e-05
6,060	Efficient Massively Parallel Join Optimization for Large Queries*	2022	SIGMOD	5.2271244e-05
6,372	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB	5.0878306e-05
6,541	On the Complexity of Generating Optimal Plans with Cross Products (extended abstract)	1997	PODS	5.0160682e-05
6,955	Adding Magic to an Optimising Datalog Compiler	2008	SIGMOD	4.8812945e-05
7,486	Quantum-Inspired Digital Annealing for Join Ordering	2024	VLDB	4.7135369e-05
7,563	Client-Site Query Extensions	1999	SIGMOD	4.7053932e-05
7,979	On the Optimality of Strategies for Multiple Joins	1990	PODS	4.6089395e-05
8,078	AJoin: Ad-hoc Stream Joins at Scale	2020	VLDB	4.5873626e-05
8,149	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD	4.5715614e-05
8,247	A Generic Flow Algorithm for Shared Filter Ordering Problems	2008	PODS	4.5454359e-05
8,869	Sharing-Aware Horizontal Partitioning for Exploiting Correlations During Query Processing	2010	VLDB	4.4277859e-05
10,295	Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation	2026	VLDB	4.1905499e-05
10,990	DPconv: Super-Polynomially Faster Join Ordering	2024	SIGMOD	4.1905499e-05
10,997	Towards a Converged Relational-Graph Optimization Framework	2024	SIGMOD	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 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	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0040465394
520	LDL: A Logic-Based Data-Language	1986	VLDB	0.00021145923
637	The Representation and Deductive Retrieval of Complex Objects	1985	VLDB	0.00018812264
850	Optimizing the Rule-Data Interface in a KMS	1986	VLDB	0.00015911875

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
418	Query Optimization in the Presence of Foreign Functions	1993	VLDB	0.0002372277
7,829	Optimization of Multiple-Relation Multiple-Disjunct Queries	1988	PODS	4.6373918e-05
7,794	Optimization of Object-Oriented Recursive Queries using Cost-Controlled Strategies	1992	SIGMOD	4.6446441e-05
2,109	A Recursive Algebra and Query Optimization for Nested Relations	1989	SIGMOD	9.5283567e-05
2,051	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB	9.6871984e-05
9,110	Optimizing Recursive Queries in SQL	2005	SIGMOD	4.3900304e-05
2,867	Optimization of Queries with User-defined Predicates	1996	VLDB	7.9931252e-05
1,201	A General Framework for the Optimization of Object-Oriented Queries	1992	SIGMOD	0.00013341955
1,621	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011105663
454	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00022796106