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}
}
BibTeX

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 ... BibTeX

Printed Edition

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

References

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

Referenced by

  1. Chee Yong Chan, Beng Chin Ooi: Efficient Scheduling of Page Access in Index-Based Join Processing. IEEE Trans. Knowl. Data Eng. 9(6): 1005-1011(1997)
  2. Sunita Sarawagi, Michael Stonebraker: Reordering Query Execution in Tertiary Memory Databases. VLDB 1996: 156-167
  3. Chiang Lee, Zue-An Chang: Utilizing Page-Level Join Index for Optimization in Parallel Join Execution. IEEE Trans. Knowl. Data Eng. 7(6): 900-914(1995)
  4. Sunita Sarawagi: Query Processing in Tertiary Memory Databases. VLDB 1995: 585-596
  5. Marguerite C. Murphy, Doron Rotem: Multiprocessor Join Scheduling. IEEE Trans. Knowl. Data Eng. 5(2): 322-338(1993)
  6. Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger: Efficient Processing of Spatial Joins Using R-Trees. SIGMOD Conference 1993: 237-246
  7. Priti Mishra, Margaret H. Eich: Join Processing in Relational Databases. ACM Comput. Surv. 24(1): 63-113(1992)
  8. Farshad Fotouhi, Sakti Pramanik: Optimal Secondary Storage Access Sequence for Performing Relational Join. IEEE Trans. Knowl. Data Eng. 1(3): 318-328(1989)
  9. Marguerite C. Murphy, Doron Rotem: Effective Resource Utilization for Multiprocessor Join Execution. VLDB 1989: 67-75
  10. Marguerite C. Murphy, Doron Rotem: Processor Scheduling for Multiprocessor Joins. ICDE 1989: 140-148
  11. Pankaj Goyal, H. F. Li, E. Regener, Fereidoon Sadri: Scheduling of Page Fetches in Join Operations Using Bc-Trees. ICDE 1988: 304-310
  12. Sakti Pramanik, David Ittner: Use of Graph-Theoretic Models for Optimal Relational Database Accesses to Perform Join. ACM Trans. Database Syst. 10(1): 57-74(1985)
  13. Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984)
  14. Yahiko Kambayashi, Masatoshi Yoshikawa, Shuzo Yajima: Query Processing for Distributed Databases Using Generalized Semi-Joins. SIGMOD Conference 1982: 151-160
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings (1977-1981): Copyright © by IEEE,
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:45:14 2009