ACM SIGMOD Anthology VLDB dblp.uni-trier.de

A Non-Uniform Data Fragmentation Strategy for Parallel Main-Menory Database Systems.

Nick Bassiliades, Ioannis P. Vlahavas: A Non-Uniform Data Fragmentation Strategy for Parallel Main-Menory Database Systems. VLDB 1995: 370-381
@inproceedings{DBLP:conf/vldb/BassiliadesV95,
  author    = {Nick Bassiliades and
               Ioannis P. Vlahavas},
  editor    = {Umeshwar Dayal and
               Peter M. D. Gray and
               Shojiro Nishio},
  title     = {A Non-Uniform Data Fragmentation Strategy for Parallel Main-Menory
               Database Systems},
  booktitle = {VLDB'95, Proceedings of 21th International Conference on Very
               Large Data Bases, September 11-15, 1995, Zurich, Switzerland},
  publisher = {Morgan Kaufmann},
  year      = {1995},
  isbn      = {1-55860-379-4},
  pages     = {370-381},
  ee        = {db/conf/vldb/BassiliadesV95.html},
  crossref  = {DBLP:conf/vldb/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In multi-processor database systems there are processor initialization andinter-communication overheads that diverge real systems from the ideal linear behaviour as the number of processors increases. Main-memory database systems suffer more since the database processing cost is small compared to disk-based database systems and thus comparable to the processor initialization cost. The usual uniform data fragmentation strategy divides a relation into equal data partitions, leading to idleness of single processors after local query execution termination and before global termination. In this paper, we propose a new, non-uniform data fragmentation strategy that results in concurrent termination of query processing among all the processors. The proposed fragmentation strategy is analytically modeled, simulated andcompared to the uniform strategy. It is proven that the non-uniform fragmentation strategy offers inherentlybetter performance for a parallel database system than the uniform strategy. Furthermore, the non-uniform strategy scales-up perfectly till an upper limit, after which a system reconfiguration is needed.

Copyright © 1995 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 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Umeshwar Dayal, Peter M. D. Gray, Shojiro Nishio (Eds.): VLDB'95, Proceedings of 21th International Conference on Very Large Data Bases, September 11-15, 1995, Zurich, Switzerland. Morgan Kaufmann 1995, ISBN 1-55860-379-4
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[1]
Peter M. G. Apers, Carel A. van den Berg, Jan Flokstra, Paul W. P. J. Grefen, Martin L. Kersten, Annita N. Wilschut: PRISMA/DB: A Parallel Main Memory Relational DBMS. IEEE Trans. Knowl. Data Eng. 4(6): 541-554(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
...
[3]
...
[4]
Björn Bergsten, Michel Couprie, Patrick Valduriez: Overview of Parallel Architectures for Databases. Comput. J. 36(8): 734-740(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
Haran Boral, William Alexander, Larry Clay, George P. Copeland, Scott Danforth, Michael J. Franklin, Brian E. Hart, Marc G. Smith, Patrick Valduriez: Prototyping Bubba, A Highly Parallel Database System. IEEE Trans. Knowl. Data Eng. 2(1): 4-24(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
László Böszörményi, Johann Eder, Carsten Weich: PPOST: A Parallel Database in Main Memory. DEXA 1994: 754-758 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
George P. Copeland, William Alexander, Ellen E. Boughter, Tom W. Keller: Data Placement In Bubba. SIGMOD Conference 1988: 99-108 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
Zarka Cvetanovic: The Effects of Problem Partitioning, Allocation, and Granularity on the Performance of Multiple-Processor Systems. IEEE Trans. Computers 36(4): 421-432(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
David J. DeWitt, Shahram Ghandeharizadeh, Donovan A. Schneider, Allan Bricker, Hui-I Hsiao, Rick Rasmussen: The Gamma Database Machine Project. IEEE Trans. Knowl. Data Eng. 2(1): 44-62(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
David J. DeWitt, Jim Gray: Parallel Database Systems: The Future of High Performance Database Systems. Commun. ACM 35(6): 85-98(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
David Hung-Chang Du, J. S. Sobolewski: Disk Allocation for Cartesian Product Files on Multiple-Disk Systems. ACM Trans. Database Syst. 7(1): 82-101(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
...
[13]
Hector Garcia-Molina, Kenneth Salem: Main Memory Database Systems: An Overview. IEEE Trans. Knowl. Data Eng. 4(6): 509-516(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
Shahram Ghandeharizadeh, David J. DeWitt: A Multiuser Performance Analysis of Alternative Declustering Strategies. ICDE 1990: 466-475 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[15]
Shahram Ghandeharizadeh, David J. DeWitt, Waheed Qureshi: A Performance Analysis of Alternative Multi-Attribute Declustering Strategies. SIGMOD Conference 1992: 29-38 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[16]
Goetz Graefe: Volcano - An Extensible and Parallel Query Evaluation System. IEEE Trans. Knowl. Data Eng. 6(1): 120-135(1994) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[17]
...
[18]
...
[19]
Kyung-Chang Kim: Parallelism in Object-Oriented Query Processing. ICDE 1990: 209-217 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[20]
Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[21]
Jaideep Srivastava, Thomas M. Niccum, Bhaskar Himatsingka: Data Declustering in PADMA: A PArallel Database MAnager. IEEE Data Eng. Bull. 17(3): 3-13(1994) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[22]
Michael Stonebraker: Introduction to the Special Issue on Database Prototype Systems. IEEE Trans. Knowl. Data Eng. 2(1): 1-3(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[23]
Michael Stonebraker, Randy H. Katz, David A. Patterson, John K. Ousterhout: The Design of XPRS. VLDB 1988: 318-330 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[24]
The Tandem Performance Group: A Benchmark of NonStop SQL on the Debit Credit Transaction (Invited Paper). SIGMOD Conference 1988: 337-341 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[25]
...
[26]
Arun K. Thakore, Stanley Y. W. Su: Performance Analysis of Parallel Object-Oriented Query Processing Algorithms. Distributed and Parallel Databases 2(1): 59-100(1994) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[27]
Patrick Valduriez: Parallel Database Systems: Open Problems and New Issues. Distributed and Parallel Databases 1(2): 137-165(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[28]
Annita N. Wilschut, Jan Flokstra, Peter M. G. Apers: Parallelism in a Main-Memory DBMS: The Performance of PRISMA/DB. VLDB 1992: 521-532 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

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