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.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/vldb7588 or /cdrom

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

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

Very Large Data Bases, 7th International Conference, September 9-11, 1981, Cannes, France, Proceedings. IEEE Computer Society 1981
Contents

References

[1]: Won Kim: A New Way to Compute the Product and Join of Relations. SIGMOD Conference 1980: 179-187
[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)
[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
[5]: T. H. Merrett, Yahiko Kambayashi: Join Scheduling in a Paging Environment Using the Consecutive Retrieval Property. FODO 1981: 323-347