Optimization of Nonrecursive Queries.
Ravi Krishnamurthy, Haran Boral, Carlo Zaniolo:
Optimization of Nonrecursive Queries.
VLDB 1986: 128-137@inproceedings{DBLP:conf/vldb/KrishnamurthyBZ86,
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, http://dblp.uni-trier.de}
}
BibTeX
Abstract
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
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
References
- [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]
- ...
- [Krishnamur.]
- ...
- [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
- Wolfgang Scheufele:
Review - On the Optimal Nesting Order for Computing N-Relational Joins.
ACM SIGMOD Digital Review 2: (2000)
- Ron Avnur, Joseph M. Hellerstein:
Eddies: Continuously Adaptive Query Processing.
SIGMOD Conference 2000: 261-272
- Navin Kabra, David J. DeWitt:
OPT++: An Object-Oriented Implementation for Extensible Database Query Optimization.
VLDB J. 8(1): 55-78(1999)
- Surajit Chaudhuri, Kyuseok Shim:
Optimization of Queries with User-Defined Predicates.
ACM Trans. Database Syst. 24(2): 177-228(1999)
- Tobias Mayr, Praveen Seshadri:
Client-Site Query Extensions.
SIGMOD Conference 1999: 347-358
- Ramana Yerneni, Chen Li, Jeffrey D. Ullman, Hector Garcia-Molina:
Optimizing Large Join Queries in Mediation Systems.
ICDT 1999: 348-364
- Joseph M. Hellerstein:
Optimization Techniques for Queries with Expensive Methods.
ACM Trans. Database Syst. 23(2): 113-157(1998)
- Michael Steinbrunn, Guido Moerkotte, Alfons Kemper:
Heuristic and Randomized Optimization for the Join Ordering Problem.
VLDB J. 6(3): 191-208(1997)
- 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)
- 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)
- Wolfgang Scheufele, Guido Moerkotte:
On the Complexity of Generating Optimal Plans with Cross Products.
PODS 1997: 238-248
- Sha Guo, Wei Sun, Mark Allen Weiss:
Solving Satisfiability and Implication Problems in Database Systems.
ACM Trans. Database Syst. 21(2): 270-293(1996)
- 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)
- Georges Gardarin, Jean-Robert Gruser, Zhao-Hui Tang:
Cost-based Selection of Path Expression Processing Algorithms in Object-Oriented Databases.
VLDB 1996: 390-401
- Surajit Chaudhuri, Kyuseok Shim:
Optimization of Queries with User-defined Predicates.
VLDB 1996: 87-98
- 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
- Surajit Chaudhuri, Luis Gravano:
Optimizing Queries over Multimedia Repositories.
SIGMOD Conference 1996: 91-102
- Ram D. Gopal, Ram Ramesh:
The Query Clustering Problem: A Set Partitioning Approach.
IEEE Trans. Knowl. Data Eng. 7(6): 885-899(1995)
- Michael Steinbrunn, Klaus Peithner, Guido Moerkotte, Alfons Kemper:
Bypassing Joins in Disjunctive Queries.
VLDB 1995: 228-238
- Annita N. Wilschut, Jan Flokstra, Peter M. G. Apers:
Parallel Evaluation of Multi-Join Queries.
SIGMOD Conference 1995: 115-126
- Sophie Cluet, Guido Moerkotte:
On the Complexity of Generating Optimal Left-Deep Processing Trees with Cross Products.
ICDT 1995: 54-67
- Suk-Chung Yoon, Il-Yeol Song, E. K. Park:
Semantic Query Processing in Object-Oriented Databases Using Deductive Approach.
CIKM 1995: 150-157
- M. Tamer Özsu, Adriana Muñoz, Duane Szafron:
An Extensible Query Optimizer for an Objectbase Management System.
CIKM 1995: 188-196
- Eileen Tien Lin, Edward Omiecinski, Sudhakar Yalamanchili:
Large Join Optimization on a Hypercube Multiprocessor.
IEEE Trans. Knowl. Data Eng. 6(2): 304-315(1994)
- Joseph M. Hellerstein:
Practical Predicate Placement.
SIGMOD Conference 1994: 325-335
- Tadeusz Morzy, Maciej Matysiak, Silvio Salza:
Tabu Search Optimization of Large Join Queries.
EDBT 1994: 309-322
- Goetz Graefe:
Query Evaluation Techniques for Large Databases.
ACM Comput. Surv. 25(2): 73-170(1993)
- Ming-Syan Chen, Hui-I Hsiao, Philip S. Yu:
Applying Hash Filters to Improving the Execution of Bushy Trees.
VLDB 1993: 505-516
- Rosana S. G. Lanzelotte, Patrick Valduriez, Mohamed Zaït:
On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces.
VLDB 1993: 493-504
- Joseph M. Hellerstein, Michael Stonebraker:
Predicate Migration: Optimizing Queries with Expensive Predicates.
SIGMOD Conference 1993: 267-276
- Allen Van Gelder:
Multiple Join Size Estimation by Virtual Domains.
PODS 1993: 180-189
- Arun N. Swami, Balakrishna R. Iyer:
A Polynomial Time Algorithm for Optimizing Join Queries.
ICDE 1993: 345-354
- Anne H. H. Ngu, Ling-Ling Yan, Limsoon Wong:
Heterogeneous Query Optimization Using Maximal Sub-Queries.
DASFAA 1993: 413-420
- 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)
- Weimin Du, Ravi Krishnamurthy, Ming-Chien Shan:
Query Optimization in a Heterogeneous DBMS.
VLDB 1992: 277-291
- Jean-Pierre Cheiney, Rosana S. G. Lanzelotte:
A Model for Optimizing Deductive and Object-Oriented DB Requests.
ICDE 1992: 385-392
- Hongjun Lu, Ming-Chien Shan, Kian-Lee Tan:
Optimization of Multi-Way Join Queries for Parallel Execution.
VLDB 1991: 549-560
- Rosana S. G. Lanzelotte, Patrick Valduriez:
Extending the Search Strategy in a Query Optimizer.
VLDB 1991: 363-373
- 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
- Himawan Gunadhi, Arie Segev:
Query Processing Algorithms for Temporal Intersection Joins.
ICDE 1991: 336-344
- Rosana S. G. Lanzelotte, Jean-Pierre Cheiney:
Adapting Relational Optimization Technology to Deductive and Object-Oriented Declarative Database Languages.
DBPL 1991: 322-336
- Kenichi Yajima, Hiroyuki Kitagawa, Kazunori Yamaguchi, Nobuo Ohbo, Yuzuru Fujiwara:
Optimization of Queries Including ADT Functions.
DASFAA 1991: 366-373
- Frédéric Andrès, Michel Couprie, Yann Viémont:
A Multi-Environment Cost Evaluator for Parallel Database Systems.
DASFAA 1991: 126-135
- 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)
- 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)
- Kiyoshi Ono, Guy M. Lohman:
Measuring the Complexity of Join Enumeration in Query Optimization.
VLDB 1990: 314-325
- Yannis E. Ioannidis, Younkyung Cha Kang:
Randomized Algorithms for Optimizing Large Join Queries.
SIGMOD Conference 1990: 312-321
- Y. C. Tay:
On the Optimality of Strategies for Multiple Joins.
PODS 1990: 124-131
- Sreekumar T. Shenoy, Z. Meral Özsoyoglu:
Design and Implementation of a Semantic Query Optimizer.
IEEE Trans. Knowl. Data Eng. 1(3): 344-361(1989)
- Richard J. Lipton, Jeffrey F. Naughton:
Estimating the Size of Generalized Transitive Closures.
VLDB 1989: 165-171
- Danette Chimenti, Ruben Gamboa, Ravi Krishnamurthy:
Towards on Open Architecture for LDL.
VLDB 1989: 195-203
- Arun N. Swami:
Optimization of Large Join Queries: Combining Heuristic and Combinatorial Techniques.
SIGMOD Conference 1989: 367-376
- Jeffrey D. Ullman:
Principles of Database and Knowledge-Base Systems, Volume II.
Computer Science Press 1989, ISBN 0-7167-8162-X
Contents - Arun N. Swami, Anoop Gupta:
Optimization of Large Join Queries.
SIGMOD Conference 1988: 8-17
- Ravi Krishnamurthy, Carlo Zaniolo:
Optimization in a Logic Based Language for Knowledge and Data Intensive Applications.
EDBT 1988: 16-33
- Yannis E. Ioannidis, Eugene Wong:
Query Optimization by Simulated Annealing.
SIGMOD Conference 1987: 9-22
- Setrag Khoshafian, George P. Copeland, Thomas Jagodis, Haran Boral, Patrick Valduriez:
A Query Processing Strategy for the Decomposed Storage Model.
ICDE 1987: 636-643
- Ravi Krishnamurthy, Carlo Zaniolo:
Control and Optimization Strategies in the Implementation of LDL.
DBPL 1987: 329-345
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:45:28 2009