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.00029168671
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.000408505
125 Predicate Migration: Optimizing Queries with Expensive Predicates 1993 SIGMOD 0.00030462671
321 Measuring the Complexity of Join Enumeration in Query Optimization 1990 VLDB 0.00021082176
386 Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors 2009 VLDB 0.00019446558
469 Optimization of Large Join Queries 1988 SIGMOD 0.00017749337
487 Randomized Algorithms For Optimizing Large Join Queries 1990 SIGMOD 0.00017455404
686 Optimizing Queries over Multimedia Repositories 1996 SIGMOD 0.00014769852
708 Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques 1989 SIGMOD 0.00014623779
726 Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization 1991 SIGMOD 0.00014459508
827 Adaptive Ordering of Pipelined Stream Filters 2004 SIGMOD 0.00013629035
850 The Design of an Acquisitional Query Processor For Sensor Networks 2003 SIGMOD 0.00013482116
859 Query Optimization by Simulated Annealing 1987 SIGMOD 0.0001341356
1,032 Cost-Based Optimization for Magic: Algebra and Implementation 1996 SIGMOD 0.00012396854
1,076 Towards an Open Architecture for LDL 1989 VLDB 0.00012154177
1,185 Adaptive Optimization of Very Large Join Queries 2018 SIGMOD 0.00011607329
1,416 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00010729775
1,465 Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities 2019 SIGMOD 0.00010572023
1,605 SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning 2019 SIGMOD 0.00010095581
1,624 Query Optimization in Heterogeneous DBMS 1992 VLDB 0.00010041204
2,009 PIQL: Success-Tolerant Query Processing in the Cloud 2012 VLDB 9.1949132e-05
2,035 Practical Predicate Placement 1994 SIGMOD 9.1519324e-05
2,138 Optimization of Multi-Way Join Queries for Parallel Execution 1991 VLDB 8.9747973e-05
2,267 Parallel evaluation of multi-join queries 1995 SIGMOD 8.7192424e-05
2,341 Extending the Search Strategy in a Query Optimizer 1991 VLDB 8.6079269e-05
2,516 Optimization of Queries with User-defined Predicates 1996 VLDB 8.3572065e-05
2,627 On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces 1993 VLDB 8.2030431e-05
3,000 Multiple Join Size Estimation by Virtual Domains (extended abstract) 1993 PODS 7.7657164e-05
3,722 Bypassing Joins in Disjunctive Queries 1995 VLDB 7.0684532e-05
3,800 Query Simplification: Graceful Degradation for Join-Order Optimization 2009 SIGMOD 7.0130412e-05
4,002 Partial Join Order Optimization in the ParAccel Analytic Database 2009 SIGMOD 6.8577586e-05
4,193 Cost-based Selection of Path Expression Processing Algorithms in Object-Oriented Databases 1996 VLDB 6.7415036e-05
4,369 Lifting the Burden of History from Adaptive Query Processing 2004 VLDB 6.6302169e-05
4,474 Flow Algorithms for Two Pipelined Filter Ordering Problems 2006 PODS 6.5813764e-05
4,623 Join Query Optimization Techniques for Complex Event Processing Applications 2018 VLDB 6.4957114e-05
4,790 Applying Hash Filters to Improving the Execution of Bushy Trees 1993 VLDB 6.4114271e-05
5,429 Efficient Massively Parallel Join Optimization for Large Queries* 2022 SIGMOD 6.1320252e-05
5,911 Quantum-Inspired Digital Annealing for Join Ordering 2024 VLDB 5.9478816e-05
6,108 Optimization of Conjunctive Predicates for Main Memory Column Stores 2016 VLDB 5.8831615e-05
6,111 On the Complexity of Generating Optimal Plans with Cross Products (extended abstract) 1997 PODS 5.8815204e-05
7,227 Adding Magic to an Optimising Datalog Compiler 2008 SIGMOD 5.5784356e-05
8,019 AJoin: Ad-hoc Stream Joins at Scale 2020 VLDB 5.4045347e-05
8,046 Efficiently Computing Join Orders with Heuristic Search 2023 SIGMOD 5.3992239e-05
8,136 Client-Site Query Extensions 1999 SIGMOD 5.3912113e-05
8,471 On the Optimality of Strategies for Multiple Joins 1990 PODS 5.3324907e-05
8,606 A Generic Flow Algorithm for Shared Filter Ordering Problems 2008 PODS 5.303032e-05
8,659 Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation 2026 VLDB 5.292093e-05
9,133 Sharing-Aware Horizontal Partitioning for Exploiting Correlations During Query Processing 2010 VLDB 5.2229181e-05
9,221 DPconv: Super-Polynomially Faster Join Ordering 2024 SIGMOD 5.2036474e-05
11,552 Towards a Converged Relational-Graph Optimization Framework 2024 SIGMOD 4.9769913e-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.0023943337
636 LDL: A Logic-Based Data-Language 1986 VLDB 0.00015361511
865 The Representation and Deductive Retrieval of Complex Objects 1985 VLDB 0.00013385895
1,868 Optimizing the Rule-Data Interface in a KMS 1986 VLDB 9.4764925e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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