ACM SIGMOD Anthology TODS dblp.uni-trier.de

Parallel Algorithms for the Execution of Relational Database Operations.

Dina Bitton, Haran Boral, David J. DeWitt, W. Kevin Wilkinson: Parallel Algorithms for the Execution of Relational Database Operations. ACM Trans. Database Syst. 8(3): 324-353(1983)
@article{DBLP:journals/tods/BittonBDW83,
  author    = {Dina Bitton and
               Haran Boral and
               David J. DeWitt and
               W. Kevin Wilkinson},
  title     = {Parallel Algorithms for the Execution of Relational Database
               Operations},
  journal   = {ACM Trans. Database Syst.},
  volume    = {8},
  number    = {3},
  year      = {1983},
  pages     = {324-353},
  ee        = {http://doi.acm.org/10.1145/319989.319991, db/journals/tods/BittonBDW83.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

This paper presents and analyzes algorithms for parallel processing of relational database operations in a general multiprocessor framework. To analyze alternative algorithms, we introduce an analysis methodology which incorporates I/O, CPU, and message costs and which can be adjusted to fit different multiprocessor architectures. Algorithms are presented and analyzed for sorting, projection, and join operations. While some of these algorithms have been presented and analyzed previously, we have generalized each in order to handle the case where the number of pages is significantly larger than the number of processors. In addition, we present and analyze algorithms for the parallel execution of update and aggregate operations.

Copyright © 1983 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 ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... 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]
Jayanta Banerjee, David K. Hsiao, Richard I. Baum: Concepts and Capabilities of a Database Computer. ACM Trans. Database Syst. 3(4): 347-384(1978) BibTeX
[3]
Kenneth E. Batcher: Sorting Networks and Their Applications. AFIPS Spring Joint Computing Conference 1968: 307-314 BibTeX
[4]
Gérard M. Baudet, David Stevenson: Optimal Sorting Algorithms for Parallel Computers. IEEE Trans. Computers 27(1): 84-87(1978) BibTeX
[5]
Haran Boral, David J. DeWitt: Design Considerations for Data-flow Database Machines. SIGMOD Conference 1980: 94-104 BibTeX
[6]
David J. DeWitt: DIRECT - A Multiprocessor Organization for Supporting Relational Database Management Systems. IEEE Trans. Computers 28(6): 395-406(1979) BibTeX
[7]
David J. DeWitt, Paula B. Hawthorn: A Performance Evaluation of Data Base Machine Architectures (Invited Paper). VLDB 1981: 199-214 BibTeX
[8]
...
[9]
...
[10]
...
[11]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[12]
Chyuan Shiun Lin, Diane C. P. Smith, John Miles Smith: The Design of a Rotating Associative Array Memory for a Relational Database Management Application. ACM Trans. Database Syst. 1(1): 53-65(1976) BibTeX
[13]
...
[14]
D. L. Slotnick: Logic per Track Devices. Advances in Computers 10: 291-296(1970) BibTeX
[15]
...
[16]
Stanley Y. W. Su, G. Jack Lipovski: CASSM: A Cellular System for Very Large Data Bases. VLDB 1975: 456-472 BibTeX
[17]
Clark D. Thompson, H. T. Kung: Sorting on a Mesh-Connected Parallel Computer. Commun. ACM 20(4): 263-271(1977) BibTeX
[18]
...

Referenced by

  1. Jose Alvin G. Gendrano, Bruce C. Huang, Jim M. Rodrigue, Bongki Moon, Richard T. Snodgrass: Parallel Algorithms for Computing Temporal Aggregates. ICDE 1999: 418-427
  2. Takeshi Fukuda, Hirofumi Matsuzawa: Parallel Processing of Multiple Aggregate Queries on Shared-Nothing Multiprocessors. EDBT 1998: 278-292
  3. Silvio Salza, Massimiliano Renzetti: A Modeling Tool for Workload Analysis and Performance Tuning of Parallel Database Applications. ADBIS 1997: 152-161
  4. Nadejda Biscondi, André Flory, Lionel Brunie: Parallel Databases: Structured Query Optimization. ADBIS 1996: 146-152
  5. 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)
  6. Kun-Lung Wu, Philip S. Yu, Jen-Yao Chung, James Z. Teng: A Performance Study of Workfile Disk Management for Concurrent Mergesorts in a Multiprocessor Database System. VLDB 1995: 100-109
  7. Ambuj Shatdal, Jeffrey F. Naughton: Adaptive Parallel Aggregation Algorithms. SIGMOD Conference 1995: 104-114
  8. Nick Kline, Richard T. Snodgrass: Computing Temporal Aggregates. ICDE 1995: 222-231
  9. Gabriel Matsliach, Oded Shmueli: A Combined Method for Maintaining Large Indices in Multiprocessor Multidisk Environments. IEEE Trans. Knowl. Data Eng. 6(3): 479-496(1994)
  10. Patrick Martin, Per-Åke Larson, Vinay Deshpande: Parallel Hash-Based Join Algorithms for a Shared-Everything. IEEE Trans. Knowl. Data Eng. 6(5): 750-763(1994)
  11. Eileen Tien Lin, Edward Omiecinski, Sudhakar Yalamanchili: Large Join Optimization on a Hypercube Multiprocessor. IEEE Trans. Knowl. Data Eng. 6(2): 304-315(1994)
  12. Won S. Lee, Phillip C.-Y. Sheu: An Object-Oriented Query Evaluation Scheme for Logical Databases in Massively Parallel Environment. IEEE Trans. Knowl. Data Eng. 6(1): 181-187(1994)
  13. Goetz Graefe: Volcano - An Extensible and Parallel Query Evaluation System. IEEE Trans. Knowl. Data Eng. 6(1): 120-135(1994)
  14. Kun-Lung Wu, Philip S. Yu, James Z. Teng: Data Placement and Buffer Management for Concurrent Mergesorts with Parallel Prefetching. ICDE 1994: 418-427
  15. Richard L. Cole, Mark J. Anderson, Robert J. Bestgen: Query Processing in the IBM Application System/400. IEEE Data Eng. Bull. 16(4): 19-28(1993)
  16. Ambuj Shatdal, Jeffrey F. Naughton: Using Shared Virtual Memory for Parallel Join Processing. SIGMOD Conference 1993: 119-128
  17. Chiang Lee, Zue-An Chang: Workload Balance and Page Access Scheduling For Parallel Joins In Shared-Nothing Systems. ICDE 1993: 411-418
  18. Priti Mishra, Margaret H. Eich: Join Processing in Relational Databases. ACM Comput. Surv. 24(1): 63-113(1992)
  19. Douglas Stott Parker Jr., Eric Simon, Patrick Valduriez: SVP: A Model Capturing Sets, Lists, Streams, and Parallelism. VLDB 1992: 115-126
  20. Vinay S. Pai, Peter J. Varman: Prefetching with Multiple Disks for External Mergesort: Simulation and Analysis. ICDE 1992: 273-282
  21. Ing-Miin Hsu, Mukesh Singhal, Ming T. Liu: Distributed Rule Processing in Active Databases. ICDE 1992: 106-113
  22. Dennis Shasha, Jason Tsong-Li Wang: Optimizing Equijoin Queries In Distributed Databases Where Relations Are Hash Partitioned. ACM Trans. Database Syst. 16(2): 279-308(1991)
  23. Frédéric Andrès, Michel Couprie, Yann Viémont: A Multi-Environment Cost Evaluator for Parallel Database Systems. DASFAA 1991: 126-135
  24. Edward Omiecinski, Peter Scheuermann: A Parallel Algorithm for Record Clustering. ACM Trans. Database Syst. 15(4): 599-624(1990)
  25. Charles Severance, Sakti Pramanik, P. Wolberg: Distributed Linear Hashing and Parallel Projection in Main Memory Databases. VLDB 1990: 674-682
  26. Hongjun Lu, Kian-Lee Tan, Ming-Chien Shan: Hash-Based Join Algorithms for Multiprocessor Computers. VLDB 1990: 198-209
  27. Ouri Wolfson, Aya Ozeri: A New Paradigm for Parallel and Distributed Rule-Processing. SIGMOD Conference 1990: 133-142
  28. Goetz Graefe: Encapsulation of Parallelism in the Volcano Query Processing System. SIGMOD Conference 1990: 102-111
  29. Balakrishna R. Iyer, Daniel M. Dias: System Issues in Parallel Sorting for Database Systems. ICDE 1990: 246-255
  30. Balakrishna R. Iyer, Gary R. Ricard, Peter J. Varman: Percentile Finding Algorithm for Multiple Sorted Runs. VLDB 1989: 135-144
  31. Simona Rabinovici-Cohen, Ouri Wolfson: Why a Single Parallelization Strategy in not Enough in Knowledge Bases. PODS 1989: 200-216
  32. Elisabetta Grazzini, Fabio Pippolini: A Strategy for Executing Complex Queries. MFDBS 1989: 207-221
  33. Marguerite C. Murphy, Doron Rotem: Processor Scheduling for Multiprocessor Joins. ICDE 1989: 140-148
  34. Won S. Lee, Phillip C.-Y. Sheu: An Object-based Query Evaluation Scheme for Deductive Databases in Massively Parallel Computing Environment. ICDE 1989: 497-504
  35. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  36. Ghassan Z. Qadah: Filter-Based Join Algorithms on Uniprocessor and Distributed-Memory Multiprocessor Database Machines. EDBT 1988: 388-413
  37. Patrick Valduriez: Join Indices. ACM Trans. Database Syst. 12(2): 218-246(1987)
  38. James P. Richardson, Hongjun Lu, Krishna P. Mikkilineni: Design and Evaluation of Parallel Pipelined Join Algorithms. SIGMOD Conference 1987: 399-409
  39. Roger Shultz, Ila Miller: Tree Structured Multiple Processor Join Methods. ICDE 1987: 190-199
  40. Setrag Khoshafian, George P. Copeland, Thomas Jagodis, Haran Boral, Patrick Valduriez: A Query Processing Strategy for the Decomposed Storage Model. ICDE 1987: 636-643
  41. Leonard D. Shapiro: Join Processing in Database Systems with Large Main Memories. ACM Trans. Database Syst. 11(3): 239-264(1986)
  42. Jai Menon: A Study of Sort Algorithms for Multiprocessor Database Machines. VLDB 1986: 197-206
  43. Tobin J. Lehman, Michael J. Carey: Query Processing in Main Memory Database Management Systems. SIGMOD Conference 1986: 239-250
  44. George P. Copeland, Setrag Khoshafian: A Decomposition Storage Model. SIGMOD Conference 1985: 268-279
  45. Rakesh Agrawal, David J. DeWitt: Recovery Architectures for Multiprocessor Database Machines. SIGMOD Conference 1985: 131-145
  46. Patrick Valduriez, Georges Gardarin: Join and Semijoin Algorithms for a Multiprocessor Database Machine. ACM Trans. Database Syst. 9(1): 133-161(1984)
  47. Roger K. Shultz, Roy J. Zingg: Response Time Analysis of Multiprocessor Computers for Database Support. ACM Trans. Database Syst. 9(1): 100-132(1984)
  48. Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984)
  49. Kjell Bratbergsengen: Hashing Methods and Relational Algebra Operations. VLDB 1984: 323-333
  50. Stanley Y. W. Su, Krishna P. Mikkilineni: Parallel Algorithms and Their Implementation in MICRONET. VLDB 1982: 310-324
  51. David J. DeWitt, Paula B. Hawthorn: A Performance Evaluation of Data Base Machine Architectures (Invited Paper). VLDB 1981: 199-214
  52. Paula B. Hawthorn: The Effect of Target Applications on the Design of Database Machines. SIGMOD Conference 1981: 188-197
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:38:52 2008