ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Scheduling of Page-Fetches in Join Operations.

T. H. Merrett, Yahiko Kambayashi, H. Yasuura: Scheduling of Page-Fetches in Join Operations. VLDB 1981: 488-498
@inproceedings{DBLP:conf/vldb/MerrettKY81,
  author    = {T. H. Merrett and
               Yahiko Kambayashi and
               H. Yasuura},
  title     = {Scheduling of Page-Fetches in Join Operations},
  booktitle = {Very Large Data Bases, 7th International Conference, September
               9-11, 1981, Cannes, France, Proceedings},
  publisher = {IEEE Computer Society},
  year      = {1981},
  pages     = {488-498},
  ee        = {db/conf/vldb/MerrettKY81.html},
  crossref  = {DBLP:conf/vldb/81},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

One of the major problems of relational database systems is to find efficient procedures for database operations. This paper discusses procedures to schedule join operations in a paging environment. We assume that the two relations required to be joined are divided into pages and that only a subset of all page-pairs (one page from each relation) are required to be processed. The number of page swappings varies depending on the sequence of the page-pair processing. Our problem is to find the schedules which require the least page-swapping counts. The problem, however, can be represented as a special case of the Hamiltonian path problem and thus it is shown to be NP-complete. Two sufficient conditions for the existence of the minimum solutions are shown, which are based on the Hamiltonian path condition and the Eular path condition. Using these conditions, heuristic procedures for near optimum solutions are obtained.

Copyright © 1981 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.


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

Very Large Data Bases, 7th International Conference, September 9-11, 1981, Cannes, France, Proceedings. IEEE Computer Society 1981
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[1]
Won Kim: A New Way to Compute the Product and Join of Relations. SIGMOD Conference 1980: 179-187 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
M. R. Garey, David S. Johnson, Robert Endre Tarjan: The Planar Hamiltonian Circuit Problem is NP-Complete. SIAM J. Comput. 5(4): 704-714(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
...
[4]
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
T. H. Merrett, Yahiko Kambayashi: Join Scheduling in a Paging Environment Using the Consecutive Retrieval Property. FODO 1981: 323-347 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

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