{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T07:46:25Z","timestamp":1759131985474,"version":"3.41.0"},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[1983,9,1]],"date-time":"1983-09-01T00:00:00Z","timestamp":431222400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[1983,9]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/319989.319991","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:31:44Z","timestamp":1027769504000},"page":"324-353","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":156,"title":["Parallel algorithms for the execution of relational database operations"],"prefix":"10.1145","volume":"8","author":[{"given":"Dina","family":"Bitton","sequence":"first","affiliation":[{"name":"Univ. of Wisconsin, Madison"}]},{"given":"Haran","family":"Boral","sequence":"additional","affiliation":[{"name":"Univ. of Wisconsin, Madison"}]},{"given":"David J.","family":"DeWitt","sequence":"additional","affiliation":[{"name":"Univ. of Wisconsin, Madison"}]},{"given":"W. Kevin","family":"Wilkinson","sequence":"additional","affiliation":[{"name":"Univ. of Wisconsin, Madison"}]}],"member":"320","published-online":{"date-parts":[[1983,9]]},"reference":[{"key":"e_1_2_1_1_2","doi-asserted-by":"publisher","DOI":"10.1145\/320064.320065"},{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/320289.320292"},{"key":"e_1_2_1_3_2","volume-title":"Proc. AFIPS 1968 Spring Jt. Computer Conf.","volume":"32","author":"BATCHER K.E.","unstructured":"BATCHER , K.E. Sorting networks and their applications . In Proc. AFIPS 1968 Spring Jt. Computer Conf. , vol. 32 , AFIPS Press, Arlington, Va. BATCHER, K.E. Sorting networks and their applications. In Proc. AFIPS 1968 Spring Jt. Computer Conf., vol. 32, AFIPS Press, Arlington, Va."},{"key":"e_1_2_1_4_2","volume":"1","author":"BAUDET G.","year":"1978","unstructured":"BAUDET , G. , AND STEVENSON , D. Optimal sorting algorithms for parallel computers. IEEE Trans. Comput. C-27 , 1 ( Jan 1978 ). BAUDET, G., AND STEVENSON, D. Optimal sorting algorithms for parallel computers. IEEE Trans. Comput. C-27, 1 (Jan 1978).","journal-title":"IEEE Trans. Comput. C-27"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/582250.582266"},{"key":"e_1_2_1_6_2","volume":"6","author":"DEWITT D.J.","year":"1979","unstructured":"DEWITT , D.J. DIRECT --A multiprocessor organization for supporting relational database management systems. IEEE Trans. Comput. C-28 , 6 ( June 1979 ). DEWITT, D.J. DIRECT--A multiprocessor organization for supporting relational database management systems. IEEE Trans. Comput. C-28, 6 (June 1979).","journal-title":"IEEE Trans. Comput. C-28"},{"key":"e_1_2_1_7_2","volume-title":"Proc. 7th Conf. Very Large Data Bases (Sept.","author":"DEWITT D.J.","year":"1981","unstructured":"DEWITT , D.J. AND HAWTHORN , F. A performance evaluation of database machine architectures . In Proc. 7th Conf. Very Large Data Bases (Sept. 1981 ). DEWITT, D.J. AND HAWTHORN, F. A performance evaluation of database machine architectures. In Proc. 7th Conf. Very Large Data Bases (Sept. 1981)."},{"key":"e_1_2_1_8_2","volume-title":"Electronics Research Lab.","author":"EPSTEXN R.","year":"1979","unstructured":"EPSTEXN , R. Techniques for processing of aggregates in relational database systems. Memo. UCB\/ERL M79\/8 , Electronics Research Lab. , College of Engineering , Univ . California, Berkeley, Feb. 1979 . EPSTEXN, R. Techniques for processing of aggregates in relational database systems. Memo. UCB\/ERL M79\/8, Electronics Research Lab., College of Engineering, Univ. California, Berkeley, Feb. 1979."},{"key":"e_1_2_1_10_2","unstructured":"GOODMAN J.R. Personal communication.  GOODMAN J.R. Personal communication."},{"key":"e_1_2_1_11_2","volume-title":"The Art of Computer Programming--Sorting and Searching","author":"KNUTH D.E.","year":"1975","unstructured":"KNUTH , D.E. The Art of Computer Programming--Sorting and Searching . Addison-Wesley , Reading, Mass ., 1975 , p. 160. KNUTH, D.E. The Art of Computer Programming--Sorting and Searching. Addison-Wesley, Reading, Mass., 1975, p. 160."},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/320434.320447"},{"key":"e_1_2_1_13_2","volume-title":"Proc. AFIPS 1975 Nat. Computer Conf.","volume":"45","author":"OZKARAHAN E.A.","unstructured":"OZKARAHAN , E.A. , SCHUSTER , S.A. , AND SMITH K.C. RAP--An associative processor for database management . In Proc. AFIPS 1975 Nat. Computer Conf. , vol. 45 , AFIPS Press, Arlington, Va. OZKARAHAN, E.A., SCHUSTER, S.A., AND SMITH K.C. RAP--An associative processor for database management. In Proc. AFIPS 1975 Nat. Computer Conf., vol. 45, AFIPS Press, Arlington, Va."},{"key":"e_1_2_1_14_2","volume-title":"Advances in Computers","author":"SLOTNICK D.L.","year":"1970","unstructured":"SLOTNICK , D.L. Logic per track device . In Advances in Computers , J. Tou (Ed.), vol. 10 , Academic Press , New York , 1970 . SLOTNICK, D.L. Logic per track device. In Advances in Computers, J. Tou (Ed.), vol. 10, Academic Press, New York, 1970."},{"key":"e_1_2_1_15_2","volume":"2","author":"STONE H.S.","year":"1971","unstructured":"STONE , H.S. Parallel processing with the perfect shuffle. IEEE Trans. Comput., C-20 , 2 ( Feb. 1971 ). STONE, H.S. Parallel processing with the perfect shuffle. IEEE Trans. Comput., C-20, 2 (Feb. 1971).","journal-title":"IEEE Trans. Comput., C-20"},{"key":"e_1_2_1_16_2","first-page":"456","volume-title":"Proc. Int. Conf. Very Large Data Bases, (September 22-24","author":"LIPOVSKI G.J.","year":"1975","unstructured":"Su, S.Y.W., AND LIPOVSKI , G.J. CASSM : A cellular system for very large databases . In Proc. Int. Conf. Very Large Data Bases, (September 22-24 , Framingham, Mass.) ACM, New York , 1975 , pp. 456 - 472 . Su, S.Y.W., AND LIPOVSKI, G.J. CASSM: A cellular system for very large databases. In Proc. Int. Conf. Very Large Data Bases, (September 22-24, Framingham, Mass.) ACM, New York, 1975, pp. 456-472."},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/359461.359481"},{"key":"e_1_2_1_18_2","unstructured":"YOUSSEFI K. ET AL. INGRES version 6.0 reference manual.  YOUSSEFI K. ET AL. INGRES version 6.0 reference manual."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/319989.319991","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/319989.319991","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:07:18Z","timestamp":1750273638000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/319989.319991"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983,9]]},"references-count":17,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1983,9]]}},"alternative-id":["10.1145\/319989.319991"],"URL":"https:\/\/doi.org\/10.1145\/319989.319991","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[1983,9]]},"assertion":[{"value":"1983-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}