Optimization of Nonrecursive Queries.

Ravi Krishnamurthy, Haran Boral, Carlo Zaniolo: Optimization of Nonrecursive Queries. VLDB 1986: 128-137
  author    = {Ravi Krishnamurthy and
               Haran Boral and
               Carlo Zaniolo},
  editor    = {Wesley W. Chu and
               Georges Gardarin and
               Setsuo Ohsuga and
               Yahiko Kambayashi},
  title     = {Optimization of Nonrecursive Queries},
  booktitle = {VLDB'86 Twelfth International Conference on Very Large Data Bases,
               August 25-28, 1986, Kyoto, Japan, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1986},
  isbn      = {0-934613-18-4},
  pages     = {128-137},
  ee        = {db/conf/vldb/KrishnamurthyBZ86.html},
  crossref  = {DBLP:conf/vldb/86},
  bibsource = {DBLP,}


State-of-the-art optimization approaches for relational database systems, e.g., those used in systems such as OBE, SQL/DS, and commercial INGRES. when used for queries in non-traditional database applications, suffer from two problems. First, the time complexity of their optimization algorithms, being combinatoric, is exponential in the number of relations to be joined in the query. Their cost is therefore prohibitive in situations such as deductive databases and logic oriented languages for knowledge bases, where hundreds of joins may be required. The second problem with the traditional approaches is that, albeit effective in their specific domain, it is not clear whether they can be generalized to different scenarios (e.g. parallel evaluation) since they lack a formal model to define the assumptions and critical factors on which their valiclity depends. This paper proposes a solution to these problems by presenting (i) a formal model and a precise statement of the optimization problem that delineates the assumptions and limitations of the previous approaches, and (ii) a quadratic-time algorithm that determines the optimum join order for acyclic queries. The approach proposed is robust; in particular, it is shown that it remains heuristically effective for cyclic queries as well.

Copyright © 1986 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Wesley W. Chu, Georges Gardarin, Setsuo Ohsuga, Yahiko Kambayashi (Eds.): VLDB'86 Twelfth International Conference on Very Large Data Bases, August 25-28, 1986, Kyoto, Japan, Proceedings. Morgan Kaufmann 1986, ISBN 0-934613-18-4
Contents BibTeX


[Abdel-W. 80]
[Blasgen 76]
[Gallaire 84]
Hervé Gallaire, Jack Minker, Jean-Marie Nicolas: Logic and Databases: A Deductive Approach. ACM Comput. Surv. 16(2): 153-185(1984) BibTeX
[Ibaraki 84]
Toshihide Ibaraki, Tiko Kameda: On the Optimal Nesting Order for Computing N-Relational Joins. ACM Trans. Database Syst. 9(3): 482-502(1984) BibTeX
[Lawler 78]
[Kellog 81]
Charles Kellogg, Larry Travis: Reasoning with Data in a Deductively Augmented Data Management System. Advances in Data Base Theory 1979: 261-295 BibTeX
[Kellog 85]
[Monma 79]
[Sellinger 79]
Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34 BibTeX
[Tsur 85]
[Ullman 85]
Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) BibTeX
[Whang 85]
[Zaniolo 85]
Carlo Zaniolo: The Representation and Deductive Retrieval of Complex Objects. VLDB 1985: 458-469 BibTeX

Referenced by

  1. Wolfgang Scheufele: Review - On the Optimal Nesting Order for Computing N-Relational Joins. ACM SIGMOD Digital Review 2: (2000)
  2. Ron Avnur, Joseph M. Hellerstein: Eddies: Continuously Adaptive Query Processing. SIGMOD Conference 2000: 261-272
  3. Navin Kabra, David J. DeWitt: OPT++: An Object-Oriented Implementation for Extensible Database Query Optimization. VLDB J. 8(1): 55-78(1999)
  4. Surajit Chaudhuri, Kyuseok Shim: Optimization of Queries with User-Defined Predicates. ACM Trans. Database Syst. 24(2): 177-228(1999)
  5. Tobias Mayr, Praveen Seshadri: Client-Site Query Extensions. SIGMOD Conference 1999: 347-358
  6. Ramana Yerneni, Chen Li, Jeffrey D. Ullman, Hector Garcia-Molina: Optimizing Large Join Queries in Mediation Systems. ICDT 1999: 348-364
  7. Joseph M. Hellerstein: Optimization Techniques for Queries with Expensive Methods. ACM Trans. Database Syst. 23(2): 113-157(1998)
  8. Michael Steinbrunn, Guido Moerkotte, Alfons Kemper: Heuristic and Randomized Optimization for the Join Ordering Problem. VLDB J. 6(3): 191-208(1997)
  9. Ming-Syan Chen, Hui-I Hsiao, Philip S. Yu: On Applying Hash Filters to Improving the Execution of Multi-Join Queries. VLDB J. 6(2): 121-131(1997)
  10. Nicola Leone, Pasquale Rullo, Antonella Mecchia, Giuseppe Rossi: A Deductive Environment for Dealing with Objects and Nonmonotonic Reasoning. IEEE Trans. Knowl. Data Eng. 9(4): 539-558(1997)
  11. Wolfgang Scheufele, Guido Moerkotte: On the Complexity of Generating Optimal Plans with Cross Products. PODS 1997: 238-248
  12. Sha Guo, Wei Sun, Mark Allen Weiss: Solving Satisfiability and Implication Problems in Database Systems. ACM Trans. Database Syst. 21(2): 270-293(1996)
  13. Myra Spiliopoulou, Michael Hatzopoulos, Yannis Cotronis: Parallel Optimization of Large Join Queries with Set Operators and Aggregates in a Parallel Environment Supporting Pipeline. IEEE Trans. Knowl. Data Eng. 8(3): 429-445(1996)
  14. Georges Gardarin, Jean-Robert Gruser, Zhao-Hui Tang: Cost-based Selection of Path Expression Processing Algorithms in Object-Oriented Databases. VLDB 1996: 390-401
  15. Surajit Chaudhuri, Kyuseok Shim: Optimization of Queries with User-defined Predicates. VLDB 1996: 87-98
  16. Praveen Seshadri, Joseph M. Hellerstein, Hamid Pirahesh, T. Y. Cliff Leung, Raghu Ramakrishnan, Divesh Srivastava, Peter J. Stuckey, S. Sudarshan: Cost-Based Optimization for Magic: Algebra and Implementation. SIGMOD Conference 1996: 435-446
  17. Surajit Chaudhuri, Luis Gravano: Optimizing Queries over Multimedia Repositories. SIGMOD Conference 1996: 91-102
  18. Ram D. Gopal, Ram Ramesh: The Query Clustering Problem: A Set Partitioning Approach. IEEE Trans. Knowl. Data Eng. 7(6): 885-899(1995)
  19. Michael Steinbrunn, Klaus Peithner, Guido Moerkotte, Alfons Kemper: Bypassing Joins in Disjunctive Queries. VLDB 1995: 228-238
  20. Annita N. Wilschut, Jan Flokstra, Peter M. G. Apers: Parallel Evaluation of Multi-Join Queries. SIGMOD Conference 1995: 115-126
  21. Sophie Cluet, Guido Moerkotte: On the Complexity of Generating Optimal Left-Deep Processing Trees with Cross Products. ICDT 1995: 54-67
  22. Suk-Chung Yoon, Il-Yeol Song, E. K. Park: Semantic Query Processing in Object-Oriented Databases Using Deductive Approach. CIKM 1995: 150-157
  23. M. Tamer Özsu, Adriana Muñoz, Duane Szafron: An Extensible Query Optimizer for an Objectbase Management System. CIKM 1995: 188-196
  24. Eileen Tien Lin, Edward Omiecinski, Sudhakar Yalamanchili: Large Join Optimization on a Hypercube Multiprocessor. IEEE Trans. Knowl. Data Eng. 6(2): 304-315(1994)
  25. Joseph M. Hellerstein: Practical Predicate Placement. SIGMOD Conference 1994: 325-335
  26. Tadeusz Morzy, Maciej Matysiak, Silvio Salza: Tabu Search Optimization of Large Join Queries. EDBT 1994: 309-322
  27. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
  28. Ming-Syan Chen, Hui-I Hsiao, Philip S. Yu: Applying Hash Filters to Improving the Execution of Bushy Trees. VLDB 1993: 505-516
  29. Rosana S. G. Lanzelotte, Patrick Valduriez, Mohamed Zaït: On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces. VLDB 1993: 493-504
  30. Joseph M. Hellerstein, Michael Stonebraker: Predicate Migration: Optimizing Queries with Expensive Predicates. SIGMOD Conference 1993: 267-276
  31. Allen Van Gelder: Multiple Join Size Estimation by Virtual Domains. PODS 1993: 180-189
  32. Arun N. Swami, Balakrishna R. Iyer: A Polynomial Time Algorithm for Optimizing Join Queries. ICDE 1993: 345-354
  33. Anne H. H. Ngu, Ling-Ling Yan, Limsoon Wong: Heterogeneous Query Optimization Using Maximal Sub-Queries. DASFAA 1993: 413-420
  34. Witold Litwin, Tore Risch: Main Memory Oriented Optimization of OO Queries Using Typed Datalog with Foreign Predicates. IEEE Trans. Knowl. Data Eng. 4(6): 517-528(1992)
  35. Weimin Du, Ravi Krishnamurthy, Ming-Chien Shan: Query Optimization in a Heterogeneous DBMS. VLDB 1992: 277-291
  36. Jean-Pierre Cheiney, Rosana S. G. Lanzelotte: A Model for Optimizing Deductive and Object-Oriented DB Requests. ICDE 1992: 385-392
  37. Hongjun Lu, Ming-Chien Shan, Kian-Lee Tan: Optimization of Multi-Way Join Queries for Parallel Execution. VLDB 1991: 549-560
  38. Rosana S. G. Lanzelotte, Patrick Valduriez: Extending the Search Strategy in a Query Optimizer. VLDB 1991: 363-373
  39. Yannis E. Ioannidis, Younkyung Cha Kang: Left-Deep vs. Bushy Trees: An Analysis of Strategy Spaces and its Implications for Query Optimization. SIGMOD Conference 1991: 168-177
  40. Himawan Gunadhi, Arie Segev: Query Processing Algorithms for Temporal Intersection Joins. ICDE 1991: 336-344
  41. Rosana S. G. Lanzelotte, Jean-Pierre Cheiney: Adapting Relational Optimization Technology to Deductive and Object-Oriented Declarative Database Languages. DBPL 1991: 322-336
  42. Kenichi Yajima, Hiroyuki Kitagawa, Kazunori Yamaguchi, Nobuo Ohbo, Yuzuru Fujiwara: Optimization of Queries Including ADT Functions. DASFAA 1991: 366-373
  43. Frédéric Andrès, Michel Couprie, Yann Viémont: A Multi-Environment Cost Evaluator for Parallel Database Systems. DASFAA 1991: 126-135
  44. Kyu-Young Whang, Ravi Krishnamurthy: Query Optimization in a Memory-Resident Domain Relational Calculus Database System. ACM Trans. Database Syst. 15(1): 67-95(1990)
  45. Danette Chimenti, Ruben Gamboa, Ravi Krishnamurthy, Shamim A. Naqvi, Shalom Tsur, Carlo Zaniolo: The LDL System Prototype. IEEE Trans. Knowl. Data Eng. 2(1): 76-90(1990)
  46. Kiyoshi Ono, Guy M. Lohman: Measuring the Complexity of Join Enumeration in Query Optimization. VLDB 1990: 314-325
  47. Yannis E. Ioannidis, Younkyung Cha Kang: Randomized Algorithms for Optimizing Large Join Queries. SIGMOD Conference 1990: 312-321
  48. Y. C. Tay: On the Optimality of Strategies for Multiple Joins. PODS 1990: 124-131
  49. Sreekumar T. Shenoy, Z. Meral Özsoyoglu: Design and Implementation of a Semantic Query Optimizer. IEEE Trans. Knowl. Data Eng. 1(3): 344-361(1989)
  50. Richard J. Lipton, Jeffrey F. Naughton: Estimating the Size of Generalized Transitive Closures. VLDB 1989: 165-171
  51. Danette Chimenti, Ruben Gamboa, Ravi Krishnamurthy: Towards on Open Architecture for LDL. VLDB 1989: 195-203
  52. Arun N. Swami: Optimization of Large Join Queries: Combining Heuristic and Combinatorial Techniques. SIGMOD Conference 1989: 367-376
  53. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
  54. Arun N. Swami, Anoop Gupta: Optimization of Large Join Queries. SIGMOD Conference 1988: 8-17
  55. Ravi Krishnamurthy, Carlo Zaniolo: Optimization in a Logic Based Language for Knowledge and Data Intensive Applications. EDBT 1988: 16-33
  56. Yannis E. Ioannidis, Eugene Wong: Query Optimization by Simulated Annealing. SIGMOD Conference 1987: 9-22
  57. Setrag Khoshafian, George P. Copeland, Thomas Jagodis, Haran Boral, Patrick Valduriez: A Query Processing Strategy for the Decomposed Storage Model. ICDE 1987: 636-643
  58. Ravi Krishnamurthy, Carlo Zaniolo: Control and Optimization Strategies in the Implementation of LDL. DBPL 1987: 329-345
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:45:28 2009