ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Query Processing on Personal Computers: A Pragmatic Approach (Extended Abstract).

Ravi Krishnamurthy, Stephen P. Morgan: Query Processing on Personal Computers: A Pragmatic Approach (Extended Abstract). VLDB 1984: 26-29
@inproceedings{DBLP:conf/vldb/KrishnamurthyM84,
  author    = {Ravi Krishnamurthy and
               Stephen P. Morgan},
  editor    = {Umeshwar Dayal and
               Gunter Schlageter and
               Lim Huat Seng},
  title     = {Query Processing on Personal Computers: A Pragmatic Approach
               (Extended Abstract)},
  booktitle = {Tenth International Conference on Very Large Data Bases, August
               27-31, 1984, Singapore, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1984},
  isbn      = {0-934613-16-8},
  pages     = {26-29},
  ee        = {db/conf/vldb/KrishnamurthyM84.html},
  crossref  = {DBLP:conf/vldb/84},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We present a query processing strategy for personal computers that requires at most a single sequential scan of the database for nearly all queries. On personal computers, most queries are ad-hoc, produce little output, and operate on small databases limited by secondary storage. For these queries we can use the relatively large amount of main memory to offset the slow secondary storage accesses. This is our intuitive motivation for the two-step query processing strategy which we present in this paper. In the first step we use a reduction scheme to find, for a query, a subset of the database which can fit into main memory. This step requires at most a single sequential scan of the database. In the second step we compute the answer to the query without further access to secondary storage. Since traditional query processing strategies are nonlinear in secondary storage access, we contend that our strategy is superior for nearly all queries; for the remainder, our strategy degrades gracefully. Even though we use the example of query processing on personal computers throughout this paper, the strategy we present is general, and applicable to any database management system which has a large amount of available main memory.

Copyright © 1984 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

Umeshwar Dayal, Gunter Schlageter, Lim Huat Seng (Eds.): Tenth International Conference on Very Large Data Bases, August 27-31, 1984, Singapore, Proceedings. Morgan Kaufmann 1984, ISBN 0-934613-16-8
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[BC81]
Philip A. Bernstein, Dah-Ming W. Chiu: Using Semi-Joins to Solve Relational Queries. J. ACM 28(1): 25-40(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ber81]
Philip A. Bernstein, Nathan Goodman, Eugene Wong, Christopher L. Reeve, James B. Rothnie Jr.: Query Processing in a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 6(4): 602-625(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BG79]
Philip A. Bernstein, Nathan Goodman: The power of inequality semijoins. Inf. Syst. 6(4): 255-265(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GJ79]
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
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KM84]
Ravi Krishnamurthy, Stephen P. Morgan: Distributed Query Optimization: An Engineering Approach. ICDE 1984: 220-227 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KM84a]
...
[KN84]
...
[Lit81]
Witold Litwin: Trie Hashing. SIGMOD Conference 1981: 19-29 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Referenced by

  1. Kyu-Young Whang, Ravi Krishnamurthy: The Multilevel Grid File - A Dynamic Hierarchical Multidimensional File Structure. DASFAA 1991: 449-459
  2. Elisabetta Grazzini, Fabio Pippolini: A Strategy for Executing Complex Queries. MFDBS 1989: 207-221
  3. Witold Litwin, Djamel Eddine Zegour, Gérard Lévy: Multilevel Trie Hashing. EDBT 1988: 309-335

Copyright © Mon Nov 2 21:18:01 2009 by Michael Ley (ley@uni-trier.de)