Use of Graph-Theoretic Models for Optimal Relational Database Accesses to Perform Join.

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)

@article{DBLP:journals/tods/PramanikI85,
  author    = {Sakti Pramanik and
               David Ittner},
  title     = {Use of Graph-Theoretic Models for Optimal Relational Database
               Accesses to Perform Join},
  journal   = {ACM Trans. Database Syst.},
  volume    = {10},
  number    = {1},
  year      = {1985},
  pages     = {57-74},
  ee        = {http://doi.acm.org/10.1145/3148.3325, db/journals/tods/PramanikI85.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

A graph model is presented to analyze the performance of a relational join. The amount of page reaccesses, the page access sequence, and the amount of buffer needed are represented in terms of graph parameters. By using the graph model formed from the index on the join attributes, we determine the relationships between these parameters. Two types of buffer allocation strategies are studied, and the upper bound on the buffer size with no page reaccess is given. This bound is shown to be the maximum cut value of a graph. Hence, the problem of computing this upper bound is NP-hard. We also give algorithms to determine a page access sequence requiring a near optimal buffer size with no page reaccess. The optimal page access sequence for a fixed buffer size has also been considered.

Copyright © 1985 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.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" 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/An3-1 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 2" 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/aDVD2 or /dvd

BibTeX

References

[1]: Edward Babb: Implementing a Relational Database by Means of Specialized Hardware. ACM Trans. Database Syst. 4(1): 1-29(1979) BibTeX
[2]: Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX
[3]: Mike W. Blasgen, Kapali P. Eswaran: Storage and Access in Relational Data Bases. IBM Systems Journal 16(4): 362-377(1977) BibTeX
[4]: ...
[5]: Leo R. Gotlieb: Computing Joins of Relations. SIGMOD Conference 1975: 55-63 BibTeX
[6]: ...
[7]: H. T. Kung, Philip L. Lehman: Systolic (VLSI) Arrays for Relational Database Operations. SIGMOD Conference 1980: 105-116 BibTeX
[8]: M. J. Menon, David K. Hsiao: Design and Analysis of a Relational Join Operation for VLSI. VLDB 1981: 44-55 BibTeX
[9]: T. H. Merrett, Yahiko Kambayashi, H. Yasuura: Scheduling of Page-Fetches in Join Operations. VLDB 1981: 488-498 BibTeX
[10]: ...
[11]: ...
[12]: ...
[13]: ...
[14]: Stanley Y. W. Su, G. Jack Lipovski: CASSM: A Cellular System for Very Large Data Bases. VLDB 1975: 456-472 BibTeX
[15]: ...

Referenced by

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)
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)
Chiang Lee, Zue-An Chang: Workload Balance and Page Access Scheduling For Parallel Joins In Shared-Nothing Systems. ICDE 1993: 411-418
Priti Mishra, Margaret H. Eich: Join Processing in Relational Databases. ACM Comput. Surv. 24(1): 63-113(1992)
Farshad Fotouhi, Sakti Pramanik: Optimal Secondary Storage Access Sequence for Performing Relational Join. IEEE Trans. Knowl. Data Eng. 1(3): 318-328(1989)
Marguerite C. Murphy, Doron Rotem: Processor Scheduling for Multiprocessor Joins. ICDE 1989: 140-148
Giovanni Maria Sacco: Fragmentation: A Technique for Efficient Query Processing. ACM Trans. Database Syst. 11(2): 113-133(1986)

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]