ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Global Query Optimization.

Timos K. Sellis: Global Query Optimization. SIGMOD Conference 1986: 191-205
@inproceedings{DBLP:conf/sigmod/Sellis86,
  author    = {Timos K. Sellis},
  editor    = {Carlo Zaniolo},
  title     = {Global Query Optimization},
  booktitle = {Proceedings of the 1986 ACM SIGMOD International Conference on
               Management of Data, Washington, D.C., May 28-30, 1986},
  publisher = {ACM Press},
  year      = {1986},
  pages     = {191-205},
  ee        = {http://doi.acm.org/10.1145/16894.16874, db/conf/sigmod/Sellis86.html},
  crossref  = {DBLP:conf/sigmod/86},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

In some recently proposed extensions to relational database systems as well as in deductive databases, a database system is presented with a collection of queries to process instead of just one. It is an interesting problem then, to come up with algorithms that process these queries together instead of one query at a time. We examine the problem of multiple (global) query optimization in this paper. A hierarchy of algorithms that can be used for global query optimization is exhibited and analyzed. These algorithms range from an arbitrary serial execution without any sharing of common results among the queries to an exhaustive search of all possible ways to process all queries.

Copyright © 1986 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Carlo Zaniolo (Ed.): Proceedings of the 1986 ACM SIGMOD International Conference on Management of Data, Washington, D.C., May 28-30, 1986. ACM Press 1986 BibTeX , SIGMOD Record 15(2)
Contents

Online Edition: ACM Digital Library


References

[ASTR76]
Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson: System R: Relational Approach to Database Management. ACM Trans. Database Syst. 1(2): 97-137(1976) BibTeX
[CHAK82]
Upen S. Chakravarthy, Jack Minker: Processing Multiple Queries in Database Systems. IEEE Database Eng. Bull. 5(3): 38-43(1982) BibTeX
[CHAK84]
Upen S. Chakravarthy, Daniel H. Fishman, Jack Minker: Semantic Query Optimization in Expert Systems and Database Systems. Expert Database Workshop 1984: 659-674 BibTeX
[CHAK85]
...
[FINK82]
Sheldon J. Finkelstein: Common Subexpression Analysis in Database Applications. SIGMOD Conference 1982: 235-245 BibTeX
[GALL78]
...
[GARE79]
M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
BibTeX
[GRAN80]
...
[GRAN81]
John Grant, Jack Minker: Optimization in Deductive and Conventional Relational Database Systems. Advances in Data Base Theory 1979: 195-234 BibTeX
[GUTT84]
Antonin Guttman: New Features for Relational Database Systems to Support CAD Applications. Ph.D. thesis, University of California, Berkeley 1984
BibTeX
[HALL74]
Patrick A. V. Hall: Common Subexpression Identification in General Algebraic Systems. Technical Rep. UKSC 0060, IBM United Kingdom Scientific Centre : (1974) BibTeX
[HALL76]
Patrick A. V. Hall: Optimization of a Single Relation Expression in a Relational Data Base System. IBM J. Res. Dev. 20(3): 244-257(1976) BibTeX
[IOAN86]
...
[JARK84a]
Matthias Jarke, James Clifford, Yannis Vassiliou: An Optimizing Prolog Front-End to a Relational Query System. SIGMOD Conference 1984: 296-306 BibTeX
[JARK84b]
...
[KIM84]
...
[KUNG84]
Ru-Mei Kung, Eric N. Hanson, Yannis E. Ioannidis, Timos K. Sellis, Leonard D. Shapiro, Michael Stonebraker: Heuristic Search in Data Base Systems. Expert Database Workshop 1984: 537-548 BibTeX
[LARS85]
Per-Åke Larson, H. Z. Yang: Computing Queries from Derived Relations. VLDB 1985: 259-269 BibTeX
[RICH83]
...
[ROUS82a]
Nick Roussopoulos: View Indexing in Relational Databases. ACM Trans. Database Syst. 7(2): 258-290(1982) BibTeX
[ROUS82b]
...
[RTI84]
...
[SELI79]
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
[SELL85a]
Timos K. Sellis, Leonard D. Shapiro: Optimization of Extended Database Query Languages. SIGMOD Conference 1985: 424-436 BibTeX
[SELL85b]
...
[SELL86]
...
[STON76]
Michael Stonebraker, Eugene Wong, Peter Kreps, Gerald Held: The Design and Implementation of INGRES. ACM Trans. Database Syst. 1(3): 189-222(1976) BibTeX
[STON85]
Michael Stonebraker, Lawrence A. Rowe: The Design of Postgres. SIGMOD Conference 1986: 340-355 BibTeX
[ULLM85]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX
[WONG76]
Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) BibTeX
[ZANI83]
Carlo Zaniolo: The Database Language GEM. SIGMOD Conference 1983: 207-218 BibTeX

Referenced by

  1. Odysseas G. Tsatalos, Marvin H. Solomon, Yannis E. Ioannidis: The GMAP: A Versatile Tool for Physical Data Independence. VLDB J. 5(2): 101-118(1996)
  2. Sha Guo, Wei Sun, Mark Allen Weiss: Solving Satisfiability and Implication Problems in Database Systems. ACM Trans. Database Syst. 21(2): 270-293(1996)
  3. Sha Guo, Wei Sun, Mark Allen Weiss: On Satisfiability, Equivalence, and Impication Problems Involving Conjunctive Queries in Database Systems. IEEE Trans. Knowl. Data Eng. 8(4): 604-616(1996)
  4. Yannis E. Ioannidis, Raghu Ramakrishnan: Containment of Conjunctive Queries: Beyond Relations as Sets. ACM Trans. Database Syst. 20(3): 288-324(1995)
  5. Lars Bækgaard, Leo Mark: Incremental Computation of Nested Relational Query Expressions. ACM Trans. Database Syst. 20(2): 111-148(1995)
  6. Gultekin Özsoyoglu, Richard T. Snodgrass: Temporal and Real-Time Databases: A Survey. IEEE Trans. Knowl. Data Eng. 7(4): 513-532(1995)
  7. Sharma Chakravarthy: Early Active Database Efforts: A Capsule Summary. IEEE Trans. Knowl. Data Eng. 7(6): 1008-1010(1995)
  8. Odysseas G. Tsatalos, Marvin H. Solomon, Yannis E. Ioannidis: The GMAP: A Versatile Tool for Physical Data Independence. VLDB 1994: 367-378
  9. Alfons Kemper, Guido Moerkotte, Klaus Peithner, Michael Steinbrunn: Optimizing Disjunctive Queries with Expensive Predicates. SIGMOD Conference 1994: 336-347
  10. Christian S. Jensen, Leo Mark, Nick Roussopoulos, Timos K. Sellis: Using Differential Techniques to Efficiently Support Transaction Time. VLDB J. 2(1): 75-111(1993)
  11. Michael Siegel, Edward Sciore, Sharon C. Salveter: A Method for Automatic Rule Derivation to Support Semantic Query Optimization. ACM Trans. Database Syst. 17(4): 563-600(1992)
  12. Nabil Kamel, Roger King: Intelligent Database Caching Through the Use of Page-Answers and Page-Traces. ACM Trans. Database Syst. 17(4): 601-646(1992)
  13. Michael Stonebraker: Managing Persistent Objects in a Multi-Level Store. SIGMOD Conference 1991: 2-11
  14. 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
  15. A. Y. Lu, Phillip C.-Y. Sheu: Processing of Multiple Queries in Distributed Databases. ICDE 1991: 42-49
  16. Ken-Chih Liu, Lu Zhang: Natural Joins in Relational Databases with Indefinite and Maybe Information. ICDE 1991: 132-139
  17. Michael Stonebraker, Lawrence A. Rowe, Michael Hirohama: The Implementation of Postgres. IEEE Trans. Knowl. Data Eng. 2(1): 125-142(1990)
  18. Sreekumar T. Shenoy, Z. Meral Özsoyoglu: Design and Implementation of a Semantic Query Optimizer. IEEE Trans. Knowl. Data Eng. 1(3): 344-361(1989)
  19. Xian-He Sun, Nabil Kamel, Lionel M. Ni: Solving Implication Problems in Database Applications. SIGMOD Conference 1989: 185-192
  20. François Bry: Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited. SIGMOD Conference 1989: 193-204
  21. Umeshwar Dayal: Queries and Views in an Object-Oriented Data Model. DBPL 1989: 80-102
  22. J. T. Park, Toby J. Teorey: A Knowledge/Based Approach to Multiple Query Processing. DASFAA 1989: 133-140
  23. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  24. Michael Stonebraker, Randy H. Katz, David A. Patterson, John K. Ousterhout: The Design of XPRS. VLDB 1988: 318-330
  25. 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
  26. Arnon Rosenthal, Upen S. Chakravarthy: Anatomy of a Mudular Multiple Query Optimizer. VLDB 1988: 230-239
  27. Jaideep Srivastava, C. V. Ramamoorthy: Efficient Algorithms for Maintenance of Large Database. ICDE 1988: 402-408
  28. Jooseok Park, Arie Segev: Using Common Subexpressions to Optimize Multiple Queries. ICDE 1988: 311-319
  29. H. Z. Yang, Per-Åke Larson: Query Transformation for PSJ-Queries. VLDB 1987: 245-254
  30. Timos K. Sellis: Efficiently Supporting Procedures in Relational Database Systems. SIGMOD Conference 1987: 278-291
  31. Yannis E. Ioannidis, Eugene Wong: Query Optimization by Simulated Annealing. SIGMOD Conference 1987: 9-22
  32. Eric N. Hanson: A Performance Analysis of View Materialization Strategies. SIGMOD Conference 1987: 440-453
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
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:39:45 2009