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: 7740
Venue: VLDB
Year: 1986
Pagerank: 0.00041510555
Overall Rank: 143 | 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
115	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.00046221215
139	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00042299329
195	Optimizing Queries over Multimedia Repositories	1996	SIGMOD	0.00035406558
387	Optimization of Large Join Queries	1988	SIGMOD	0.0002471967
399	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD	0.00024315433
423	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00023669348
566	Query Optimization by Simulated Annealing	1987	SIGMOD	0.00019970535
629	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00018942366
688	Estimating the Size of Generalized Transitive Closures	1989	VLDB	0.00018134733
784	Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques	1989	SIGMOD	0.00016675823
813	Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization	1991	SIGMOD	0.0001639584
896	Towards an Open Architecture for LDL	1989	VLDB	0.00015529255
905	The Design of an Acquisitional Query Processor For Sensor Networks	2003	SIGMOD	0.0001546195
1,043	Adaptive Ordering of Pipelined Stream Filters	2004	SIGMOD	0.00014476247
1,313	Cost-Based Optimization for Magic: Algebra and Implementation	1996	SIGMOD	0.0001263831
1,619	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011111678
1,839	Query Optimization in Heterogeneous DBMS	1992	VLDB	0.00010349298
2,044	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB	9.6953608e-05
2,056	PIQL: Success-Tolerant Query Processing in the Cloud	2012	VLDB	9.6645763e-05
2,086	Practical Predicate Placement	1994	SIGMOD	9.5779956e-05
2,142	Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities	2019	SIGMOD	9.4507296e-05
2,219	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2019	SIGMOD	9.2623533e-05
2,263	Extending the Search Strategy in a Query Optimizer	1991	VLDB	9.1612588e-05
2,303	Parallel evaluation of multi-join queries	1995	SIGMOD	9.066178e-05
2,765	On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces	1993	VLDB	8.1572726e-05
2,860	Optimization of Queries with User-defined Predicates	1996	VLDB	7.9934503e-05
3,053	Multiple Join Size Estimation by Virtual Domains (extended abstract)	1993	PODS	7.64969e-05
3,666	Bypassing Joins in Disjunctive Queries	1995	VLDB	6.8618006e-05
3,902	Cost-based Selection of Path Expression Processing Algorithms in Object-Oriented Databases	1996	VLDB	6.6499453e-05
4,001	Partial Join Order Optimization in the ParAccel Analytic Database	2009	SIGMOD	6.5463503e-05
4,272	Flow Algorithms for Two Pipelined Filter Ordering Problems	2006	PODS	6.3052723e-05
4,738	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	5.9600502e-05
4,943	Lifting the Burden of History from Adaptive Query Processing	2004	VLDB	5.8170713e-05
5,097	Join Query Optimization Techniques for Complex Event Processing Applications	2018	VLDB	5.7011496e-05
5,300	Applying Hash Filters To Improving The Execution Of Bushy Trees	1993	VLDB	5.5793265e-05
6,056	Efficient Massively Parallel Join Optimization for Large Queries*	2022	SIGMOD	5.2321475e-05
6,374	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB	5.0927058e-05
6,543	On the Complexity of Generating Optimal Plans with Cross Products (extended abstract)	1997	PODS	5.0208799e-05
6,957	Adding Magic to an Optimising Datalog Compiler	2008	SIGMOD	4.8859842e-05
7,486	Quantum-Inspired Digital Annealing for Join Ordering	2024	VLDB	4.7180617e-05
7,562	Client-Site Query Extensions	1999	SIGMOD	4.7099168e-05
7,976	On the Optimality of Strategies for Multiple Joins	1990	PODS	4.613363e-05
8,075	AJoin: Ad-hoc Stream Joins at Scale	2020	VLDB	4.5917655e-05
8,164	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD	4.5718104e-05
8,252	A Generic Flow Algorithm for Shared Filter Ordering Problems	2008	PODS	4.5497007e-05
8,869	Sharing-Aware Horizontal Partitioning for Exploiting Correlations During Query Processing	2010	VLDB	4.4320338e-05
10,283	Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation	2026	VLDB	4.1945683e-05
10,987	DPconv: Super-Polynomially Faster Join Ordering	2024	SIGMOD	4.1945683e-05
10,994	Towards a Converged Relational-Graph Optimization Framework	2024	SIGMOD	4.1945683e-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.0040449103
519	LDL: A Logic-Based Data-Language	1986	VLDB	0.00021154077
632	The Representation and Deductive Retrieval of Complex Objects	1985	VLDB	0.00018923134
854	Optimizing the Rule-Data Interface in a KMS	1986	VLDB	0.00015933596

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
421	Query Optimization in the Presence of Foreign Functions	1993	VLDB	0.00023711553
7,824	Optimization of Multiple-Relation Multiple-Disjunct Queries	1988	PODS	4.6418459e-05
2,110	A Recursive Algebra and Query Optimization for Nested Relations	1989	SIGMOD	9.5315487e-05
7,793	Optimization of Object-Oriented Recursive Queries using Cost-Controlled Strategies	1992	SIGMOD	4.6489537e-05
2,044	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB	9.6953608e-05
9,112	Optimizing Recursive Queries in SQL	2005	SIGMOD	4.3942347e-05
2,860	Optimization of Queries with User-defined Predicates	1996	VLDB	7.9934503e-05
1,199	A General Framework for the Optimization of Object-Oriented Queries	1992	SIGMOD	0.00013354204
1,619	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011111678
454	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00022734812