ACM SIGMOD Anthology VLDB dblp.uni-trier.de

A Formal Model of Trade-off between Optimization and Execution Costs in Semantic Query Optimization.

Shashi Shekhar, Jaideep Srivastava, Soumitra Dutta: A Formal Model of Trade-off between Optimization and Execution Costs in Semantic Query Optimization. VLDB 1988: 457-467
@inproceedings{DBLP:conf/vldb/ShekarSD88,
  author    = {Shashi Shekhar and
               Jaideep Srivastava and
               Soumitra Dutta},
  editor    = {Fran\c{c}ois Bancilhon and
               David J. DeWitt},
  title     = {A Formal Model of Trade-off between Optimization and Execution
               Costs in Semantic Query Optimization},
  booktitle = {Fourteenth International Conference on Very Large Data Bases,
               August 29 - September 1, 1988, Los Angeles, California, USA,
               Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1988},
  isbn      = {0-934613-75-3},
  pages     = {457-467},
  ee        = {db/conf/vldb/ShekarSD88.html},
  crossref  = {DBLP:conf/vldb/88},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Conventional query optimizers assume that the cost of optimization is negligible. This assumption does not hold for much larger search spaces (of possible execution plans) such as those encountered during semantic query optimization. In particular, the optimization cost can become comparable to the execution cost, and thus a significant fraction of the response time for interactive queries[l]. This paper discusses the tradeoff between the two costs in the context of semantic query optimization, and reports a heuristic search algorithm which minimizes a weighted sum of both the costs. A detailed analysis of an experiment is presented to strengthen the claim. The paper also contributes a practical model of semantic query optimization, and a discussion of its search ordering and termination problems.

Copyright © 1988 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 ...

Printed Edition

François Bancilhon, David J. DeWitt (Eds.): Fourteenth International Conference on Very Large Data Bases, August 29 - September 1, 1988, Los Angeles, California, USA, Proceedings. Morgan Kaufmann 1988, ISBN 0-934613-75-3
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[1]
...
[2]
John Miles Smith, Philip Yen-Tang Chang: Optimizing the Performance of a Relational Algebra Database Interface. Commun. ACM 18(10): 568-579(1975) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
Michael Hammer, Stanley B. Zdonik: Knowledge-Based Query Processing. VLDB 1980: 137-147 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
Jonathan J. King: QUIST: A System for Semantic Query Optimization in Relational Databases. VLDB 1981: 510-517 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
Sreekumar T. Shenoy, Z. Meral Özsoyoglu: A System for Semantic Query Optimization. SIGMOD Conference 1987: 181-195 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
Upen S. Chakravarthy, Daniel H. Fishman, Jack Minker: Semantic Query Optimization in Expert Systems and Database Systems. Expert Database Workshop 1984: 659-674 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
...
[10]
...
[11]
Richard E. Korf: Depth-First Iterative-Deepening: An Optimal Admissible Tree Search. Artif. Intell. 27(1): 97-109(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
...
[13]
Rina Dechter, Judea Pearl: Generalized Best-First Search Strategies and the Optimality of A*. J. ACM 32(3): 505-536(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
...
[15]
Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Local Queries. SIGMOD Conference 1986: 84-95 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[16]
Timos K. Sellis: Global Query Optimization. SIGMOD Conference 1986: 191-205 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[17]
...
[18]
Sheldon J. Finkelstein: Common Subexpression Analysis in Database Applications. SIGMOD Conference 1982: 235-245 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[19]
Yannis E. Ioannidis, Eugene Wong: Query Optimization by Simulated Annealing. SIGMOD Conference 1987: 9-22 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[20]
...
[21]
...

Copyright © Tue Mar 16 02:22:00 2010 by Michael Ley (ley@uni-trier.de)