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.00029092688
Overall Rank
144 | 99.04%
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.00040739114
125 Predicate Migration: Optimizing Queries with Expensive Predicates 1993 SIGMOD 0.00030398363
322 Measuring the Complexity of Join Enumeration in Query Optimization 1990 VLDB 0.00021032289
381 Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors 2009 VLDB 0.00019497061
470 Optimization of Large Join Queries 1988 SIGMOD 0.00017699145
489 Randomized Algorithms For Optimizing Large Join Queries 1990 SIGMOD 0.00017402488
687 Optimizing Queries over Multimedia Repositories 1996 SIGMOD 0.00014736766
714 Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques 1989 SIGMOD 0.00014578551
728 Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization 1991 SIGMOD 0.0001441771
824 Adaptive Ordering of Pipelined Stream Filters 2004 SIGMOD 0.0001360282
852 The Design of an Acquisitional Query Processor For Sensor Networks 2003 SIGMOD 0.00013447072
862 Query Optimization by Simulated Annealing 1987 SIGMOD 0.00013372073
1,032 Cost-Based Optimization for Magic: Algebra and Implementation 1996 SIGMOD 0.00012376627
1,076 Towards an Open Architecture for LDL 1989 VLDB 0.00012128405
1,185 Adaptive Optimization of Very Large Join Queries 2018 SIGMOD 0.00011586181
1,423 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00010696781
1,444 Pessimistic Cardinality Estimation: Tighter Upper Bounds for Intermediate Join Cardinalities 2019 SIGMOD 0.00010616242
1,609 SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning 2019 SIGMOD 0.0001007196
1,630 Query Optimization in Heterogeneous DBMS 1992 VLDB 0.00010013052
2,018 PIQL: Success-Tolerant Query Processing in the Cloud 2012 VLDB 9.1687512e-05
2,033 Practical Predicate Placement 1994 SIGMOD 9.1389597e-05
2,151 Optimization of Multi-Way Join Queries for Parallel Execution 1991 VLDB 8.9483042e-05
2,280 Parallel evaluation of multi-join queries 1995 SIGMOD 8.6972041e-05
2,351 Extending the Search Strategy in a Query Optimizer 1991 VLDB 8.5799847e-05
2,521 Optimization of Queries with User-defined Predicates 1996 VLDB 8.3339593e-05
2,630 On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces 1993 VLDB 8.1828876e-05
3,009 Multiple Join Size Estimation by Virtual Domains (extended abstract) 1993 PODS 7.7439468e-05
3,725 Bypassing Joins in Disjunctive Queries 1995 VLDB 7.0458585e-05
3,807 Query Simplification: Graceful Degradation for Join-Order Optimization 2009 SIGMOD 6.9902343e-05
4,018 Partial Join Order Optimization in the ParAccel Analytic Database 2009 SIGMOD 6.8358751e-05
4,213 Cost-based Selection of Path Expression Processing Algorithms in Object-Oriented Databases 1996 VLDB 6.7198499e-05
4,394 Lifting the Burden of History from Adaptive Query Processing 2004 VLDB 6.6084598e-05
4,478 Flow Algorithms for Two Pipelined Filter Ordering Problems 2006 PODS 6.5682405e-05
4,640 Join Query Optimization Techniques for Complex Event Processing Applications 2018 VLDB 6.4742349e-05
4,809 Applying Hash Filters to Improving the Execution of Bushy Trees 1993 VLDB 6.3910269e-05
5,446 Efficient Massively Parallel Join Optimization for Large Queries* 2022 SIGMOD 6.1117489e-05
5,926 Quantum-Inspired Digital Annealing for Join Ordering 2024 VLDB 5.9282142e-05
6,122 Optimization of Conjunctive Predicates for Main Memory Column Stores 2016 VLDB 5.8638562e-05
6,125 On the Complexity of Generating Optimal Plans with Cross Products (extended abstract) 1997 PODS 5.862077e-05
7,246 Adding Magic to an Optimising Datalog Compiler 2008 SIGMOD 5.5599899e-05
8,035 AJoin: Ad-hoc Stream Joins at Scale 2020 VLDB 5.3866645e-05
8,064 Efficiently Computing Join Orders with Heuristic Search 2023 SIGMOD 5.3813708e-05
8,153 Client-Site Query Extensions 1999 SIGMOD 5.373387e-05
8,486 On the Optimality of Strategies for Multiple Joins 1990 PODS 5.3148581e-05
8,621 A Generic Flow Algorithm for Shared Filter Ordering Problems 2008 PODS 5.2863457e-05
8,677 Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation 2026 VLDB 5.2745941e-05
9,153 Sharing-Aware Horizontal Partitioning for Exploiting Correlations During Query Processing 2010 VLDB 5.2056492e-05
9,244 DPconv: Super-Polynomially Faster Join Ordering 2024 SIGMOD 5.1864409e-05
11,601 Towards a Converged Relational-Graph Optimization Framework 2024 SIGMOD 4.9605343e-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.0023948467
638 LDL: A Logic-Based Data-Language 1986 VLDB 0.0001531355
866 The Representation and Deductive Retrieval of Complex Objects 1985 VLDB 0.00013342501
1,871 Optimizing the Rule-Data Interface in a KMS 1986 VLDB 9.4478731e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 8,036 Optimization of Multiple-Relation Multiple-Disjunct Queries 1988 PODS
2 10,585 Succinct Structure Representations for Efficient Query Optimization 2026 SIGMOD
3 8,167 Optimization of Object-Oriented Recursive Queries using Cost-Controlled Strategies 1992 SIGMOD
4 2,163 A Recursive Algebra and Query Optimization for Nested Relations 1989 SIGMOD
5 2,151 Optimization of Multi-Way Join Queries for Parallel Execution 1991 VLDB
6 9,382 Optimizing Recursive Queries in SQL 2005 SIGMOD
7 2,521 Optimization of Queries with User-defined Predicates 1996 VLDB
8 1,102 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 259 An Overview of Query Optimization in Relational Systems 1998 PODS