DBScholar

Back to papers

Optimization of Nonrecursive Queries

Summary: Formalizes nonrecursive-query optimization and exposes the assumptions behind traditional join-ordering methods. Delivers a quadratic-time algorithm for optimal join ordering in acyclic queries, remaining effective heuristically for cyclic queries and large deductive workloads. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
h2bf6d019bd51852d
Venue
VLDB
Year
1986
Pagerank
0.00029179719
Overall Rank
143 | 99.05%
DOI
-

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{krishnamurthy_vldb86,
        title = {{Optimization of Nonrecursive Queries}},
        author = {Krishnamurthy, Ravi and Boral, Haran and Zaniolo, Carlo},
        journal = {PVLDB},
        series = {{VLDB} '86},
        year = {1986}
}

Incoming Citations (Sorted by Pagerank)

Showing 49 of 49 citing papers.

Rank Citing Paper Year Venue Pagerank
53 Eddies: Continuously Adaptive Query Processing 2000 SIGMOD 0.00040860054
125 Predicate Migration: Optimizing Queries with Expensive Predicates 1993 SIGMOD 0.00030470848
321 Measuring the Complexity of Join Enumeration in Query Optimization 1990 VLDB 0.00021088704
386 Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors 2009 VLDB 0.00019444411
470 Optimization of Large Join Queries 1988 SIGMOD 0.00017755852
487 Randomized Algorithms For Optimizing Large Join Queries 1990 SIGMOD 0.00017462723
686 Optimizing Queries over Multimedia Repositories 1996 SIGMOD 0.00014775707
708 Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques 1989 SIGMOD 0.00014629998
725 Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization 1991 SIGMOD 0.00014465736
827 Adaptive Ordering of Pipelined Stream Filters 2004 SIGMOD 0.00013632674
850 The Design of an Acquisitional Query Processor For Sensor Networks 2003 SIGMOD 0.00013488409
859 Query Optimization by Simulated Annealing 1987 SIGMOD 0.00013418999
1,032 Cost-Based Optimization for Magic: Algebra and Implementation 1996 SIGMOD 0.00012401489
1,075 Towards an Open Architecture for LDL 1989 VLDB 0.0001215903
1,186 Adaptive Optimization of Very Large Join Queries 2018 SIGMOD 0.0001160797
1,416 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00010734049
1,465 Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities 2019 SIGMOD 0.00010576304
1,603 SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning 2019 SIGMOD 0.00010097649
1,623 Query Optimization in Heterogeneous DBMS 1992 VLDB 0.00010045919
2,008 PIQL: Success-Tolerant Query Processing in the Cloud 2012 VLDB 9.1988831e-05
2,032 Practical Predicate Placement 1994 SIGMOD 9.1561026e-05
2,136 Optimization of Multi-Way Join Queries for Parallel Execution 1991 VLDB 8.9789503e-05
2,266 Parallel evaluation of multi-join queries 1995 SIGMOD 8.7229053e-05
2,339 Extending the Search Strategy in a Query Optimizer 1991 VLDB 8.6118503e-05
2,516 Optimization of Queries with User-defined Predicates 1996 VLDB 8.3610198e-05
2,626 On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces 1993 VLDB 8.2068909e-05
3,005 Multiple Join Size Estimation by Virtual Domains (extended abstract) 1993 PODS 7.7621043e-05
3,720 Bypassing Joins in Disjunctive Queries 1995 VLDB 7.0715239e-05
3,797 Query Simplification: Graceful Degradation for Join-Order Optimization 2009 SIGMOD 7.0163619e-05
4,001 Partial Join Order Optimization in the ParAccel Analytic Database 2009 SIGMOD 6.8607903e-05
4,192 Cost-based Selection of Path Expression Processing Algorithms in Object-Oriented Databases 1996 VLDB 6.7446783e-05
4,366 Lifting the Burden of History from Adaptive Query Processing 2004 VLDB 6.6333069e-05
4,472 Flow Algorithms for Two Pipelined Filter Ordering Problems 2006 PODS 6.5844e-05
4,621 Join Query Optimization Techniques for Complex Event Processing Applications 2018 VLDB 6.4987856e-05
4,786 Applying Hash Filters to Improving the Execution of Bushy Trees 1993 VLDB 6.4143659e-05
5,425 Efficient Massively Parallel Join Optimization for Large Queries* 2022 SIGMOD 6.1349269e-05
5,908 Quantum-Inspired Digital Annealing for Join Ordering 2024 VLDB 5.9506986e-05
6,106 Optimization of Conjunctive Predicates for Main Memory Column Stores 2016 VLDB 5.8859291e-05
6,110 On the Complexity of Generating Optimal Plans with Cross Products (extended abstract) 1997 PODS 5.8843027e-05
7,225 Adding Magic to an Optimising Datalog Compiler 2008 SIGMOD 5.5810777e-05
8,014 AJoin: Ad-hoc Stream Joins at Scale 2020 VLDB 5.4070928e-05
8,039 Efficiently Computing Join Orders with Heuristic Search 2023 SIGMOD 5.4017809e-05
8,130 Client-Site Query Extensions 1999 SIGMOD 5.3937641e-05
8,462 On the Optimality of Strategies for Multiple Joins 1990 PODS 5.3350162e-05
8,599 A Generic Flow Algorithm for Shared Filter Ordering Problems 2008 PODS 5.3055205e-05
8,651 Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation 2026 VLDB 5.2945994e-05
9,124 Sharing-Aware Horizontal Partitioning for Exploiting Correlations During Query Processing 2010 VLDB 5.2253914e-05
9,211 DPconv: Super-Polynomially Faster Join Ordering 2024 SIGMOD 5.206112e-05
11,546 Towards a Converged Relational-Graph Optimization Framework 2024 SIGMOD 4.9793485e-05
Previous Page 1 / 1 Next

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.0023947656
635 LDL: A Logic-Based Data-Language 1986 VLDB 0.00015368492
863 The Representation and Deductive Retrieval of Complex Objects 1985 VLDB 0.00013392127
1,867 Optimizing the Rule-Data Interface in a KMS 1986 VLDB 9.4806184e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 8,015 Optimization of Multiple-Relation Multiple-Disjunct Queries 1988 PODS
2 10,508 Succinct Structure Representations for Efficient Query Optimization 2026 SIGMOD
3 2,136 Optimization of Multi-Way Join Queries for Parallel Execution 1991 VLDB
4 8,148 Optimization of Object-Oriented Recursive Queries using Cost-Controlled Strategies 1992 SIGMOD
5 2,154 A Recursive Algebra and Query Optimization for Nested Relations 1989 SIGMOD
6 9,347 Optimizing Recursive Queries in SQL 2005 SIGMOD
7 2,516 Optimization of Queries with User-defined Predicates 1996 VLDB
8 1,098 A General Framework for the Optimization of Object-Oriented Queries 1992 SIGMOD
9 1,186 Adaptive Optimization of Very Large Join Queries 2018 SIGMOD
10 272 An Overview of Query Optimization in Relational Systems 1998 PODS