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
7931
Venue
VLDB
Year
1986
Pagerank
0.0002959213
Overall Rank
143 | 99.03%
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.00041071971
132 Predicate Migration: Optimizing Queries with Expensive Predicates 1993 SIGMOD 0.00030378624
316 Measuring the Complexity of Join Enumeration in Query Optimization 1990 VLDB 0.0002141607
388 Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors 2009 VLDB 0.00019410042
463 Optimization of Large Join Queries 1988 SIGMOD 0.00018064961
479 Randomized Algorithms For Optimizing Large Join Queries 1990 SIGMOD 0.00017789732
675 Optimizing Queries over Multimedia Repositories 1996 SIGMOD 0.00015080025
698 Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques 1989 SIGMOD 0.00014879675
708 Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization 1991 SIGMOD 0.00014727576
813 Adaptive Ordering of Pipelined Stream Filters 2004 SIGMOD 0.00013846487
828 The Design of an Acquisitional Query Processor For Sensor Networks 2003 SIGMOD 0.00013769869
839 Query Optimization by Simulated Annealing 1987 SIGMOD 0.00013692785
1,037 Cost-Based Optimization for Magic: Algebra and Implementation 1996 SIGMOD 0.00012494928
1,062 Towards an Open Architecture for LDL 1989 VLDB 0.000123618
1,286 Adaptive Optimization of Very Large Join Queries 2018 SIGMOD 0.00011320736
1,382 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00010965236
1,499 Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities 2019 SIGMOD 0.00010564536
1,595 Query Optimization in Heterogeneous DBMS 1992 VLDB 0.00010249433
1,712 SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning 2019 SIGMOD 9.9492299e-05
1,969 PIQL: Success-Tolerant Query Processing in the Cloud 2012 VLDB 9.3749819e-05
2,005 Practical Predicate Placement 1994 SIGMOD 9.3203144e-05
2,104 Optimization of Multi-Way Join Queries for Parallel Execution 1991 VLDB 9.1594086e-05
2,272 Parallel evaluation of multi-join queries 1995 SIGMOD 8.8242407e-05
2,286 Extending the Search Strategy in a Query Optimizer 1991 VLDB 8.8044994e-05
2,465 Optimization of Queries with User-defined Predicates 1996 VLDB 8.5428786e-05
2,582 On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces 1993 VLDB 8.3875949e-05
2,984 Multiple Join Size Estimation by Virtual Domains (extended abstract) 1993 PODS 7.8920597e-05
3,656 Bypassing Joins in Disjunctive Queries 1995 VLDB 7.2224287e-05
3,813 Query Simplification: Graceful Degradation for Join-Order Optimization 2009 SIGMOD 7.1051056e-05
4,044 Partial Join Order Optimization in the ParAccel Analytic Database 2009 SIGMOD 6.9400535e-05
4,109 Cost-based Selection of Path Expression Processing Algorithms in Object-Oriented Databases 1996 VLDB 6.8953193e-05
4,283 Lifting the Burden of History from Adaptive Query Processing 2004 VLDB 6.7836167e-05
4,421 Flow Algorithms for Two Pipelined Filter Ordering Problems 2006 PODS 6.713113e-05
4,588 Join Query Optimization Techniques for Complex Event Processing Applications 2018 VLDB 6.6167545e-05
5,014 Applying Hash Filters to Improving the Execution of Bushy Trees 1993 VLDB 6.4002123e-05
5,399 Efficient Massively Parallel Join Optimization for Large Queries* 2022 SIGMOD 6.2319315e-05
6,009 Optimization of Conjunctive Predicates for Main Memory Column Stores 2016 VLDB 6.0113733e-05
6,164 On the Complexity of Generating Optimal Plans with Cross Products (extended abstract) 1997 PODS 5.9532278e-05
7,079 Adding Magic to an Optimising Datalog Compiler 2008 SIGMOD 5.7090732e-05
7,856 AJoin: Ad-hoc Stream Joins at Scale 2020 VLDB 5.5306709e-05
7,882 Efficiently Computing Join Orders with Heuristic Search 2023 SIGMOD 5.5237338e-05
7,910 Quantum-Inspired Digital Annealing for Join Ordering 2024 VLDB 5.5181056e-05
7,966 Client-Site Query Extensions 1999 SIGMOD 5.5173328e-05
8,294 On the Optimality of Strategies for Multiple Joins 1990 PODS 5.4574671e-05
8,437 A Generic Flow Algorithm for Shared Filter Ordering Problems 2008 PODS 5.4252897e-05
8,965 Sharing-Aware Horizontal Partitioning for Exploiting Correlations During Query Processing 2010 VLDB 5.3432371e-05
9,042 DPconv: Super-Polynomially Faster Join Ordering 2024 SIGMOD 5.3256042e-05
9,969 Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation 2026 VLDB 5.1845938e-05
11,205 Towards a Converged Relational-Graph Optimization Framework 2024 SIGMOD 5.093636e-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.0024089429
622 LDL: A Logic-Based Data-Language 1986 VLDB 0.00015686753
848 The Representation and Deductive Retrieval of Complex Objects 1985 VLDB 0.00013651467
1,830 Optimizing the Rule-Data Interface in a KMS 1986 VLDB 9.6641384e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 7,858 Optimization of Multiple-Relation Multiple-Disjunct Queries 1988 PODS
2 10,296 Succinct Structure Representations for Efficient Query Optimization 2026 SIGMOD
3 2,198 A Recursive Algebra and Query Optimization for Nested Relations 1989 SIGMOD
4 7,986 Optimization of Object-Oriented Recursive Queries using Cost-Controlled Strategies 1992 SIGMOD
5 2,104 Optimization of Multi-Way Join Queries for Parallel Execution 1991 VLDB
6 9,173 Optimizing Recursive Queries in SQL 2005 SIGMOD
7 2,465 Optimization of Queries with User-defined Predicates 1996 VLDB
8 1,073 A General Framework for the Optimization of Object-Oriented Queries 1992 SIGMOD
9 1,286 Adaptive Optimization of Very Large Join Queries 2018 SIGMOD
10 290 An Overview of Query Optimization in Relational Systems 1998 PODS