{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:33:56Z","timestamp":1750221236825,"version":"3.41.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2018,4,30]],"date-time":"2018-04-30T00:00:00Z","timestamp":1525046400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004663","name":"Taiwan Ministry of Science and Technology","doi-asserted-by":"crossref","award":["105-2221-E-002-145-MY2"],"award-info":[{"award-number":["105-2221-E-002-145-MY2"]}],"id":[{"id":"10.13039\/501100004663","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2018,4,30]]},"abstract":"<jats:p>We introduce three formal models of distributed systems for query evaluation on massive databases: Distributed Streaming with Register Automata (DSAs), Distributed Streaming with Register Transducers (DSTs), and Distributed Streaming with Register Transducers and Joins (DSTJs). These models are based on the map-reduce paradigm where the input is transformed into a dataset of key-value pairs, and on each key a local computation is performed on the values associated with that key resulting in another set of key-value pairs. Computation proceeds in a constant number of rounds, where the result of the last round is the input to the next round, and transformation of key-value pairs is required to be generic. The difference between the three models is in the local computation part. In DSAs it is limited to making one pass over its input using a register automaton, while in DSTs it can make two passes: in the first pass it uses a finite state automaton and in the second it uses a register transducer. The third model DSTJs is an extension of DSTs, where local computations are capable of constructing the Cartesian product of two sets. We obtain the following results: (1) DSAs can evaluate first-order queries over bounded degree databases; (2) DSTs can evaluate semijoin algebra queries over arbitrary databases; (3) DSTJs can evaluate the whole relational algebra over arbitrary databases; (4) DSTJs are strictly stronger than DSTs, which in turn are strictly stronger than DSAs; (5) within DSAs, DSTs, and DSTJs, there is a strict hierarchy w.r.t. the number of rounds.<\/jats:p>","DOI":"10.1145\/3197384","type":"journal-article","created":{"date-parts":[[2018,6,27]],"date-time":"2018-06-27T12:22:36Z","timestamp":1530102156000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Finite-State Map-Reduce Computation and Relational Algebra Queries"],"prefix":"10.1145","volume":"19","author":[{"given":"Frank","family":"Neven","sequence":"first","affiliation":[{"name":"Hasselt University 8 Transnational University of Limburg, Hasselt, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicole","family":"Schweikardt","sequence":"additional","affiliation":[{"name":"Humboldt-Universit\u00e4t zu Berlin, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frederic","family":"Servais","sequence":"additional","affiliation":[{"name":"Hasselt University 8 Transnational University of Limburg, Hasselt, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tony","family":"Tan","sequence":"additional","affiliation":[{"name":"National Taiwan University, Taipei, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,6,26]]},"reference":[{"unstructured":"S. Abiteboul R. Hull and V. Vianu. 1995. Foundations of Databases. Addison-Wesley.   S. Abiteboul R. Hull and V. Vianu. 1995. Foundations of Databases. Addison-Wesley.","key":"e_1_2_1_1_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1145\/1951365.1951367"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1109\/ICDE.2013.6544814"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1007\/s00224-015-9627-3"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.14778\/2535570.2488334"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1109\/TKDE.2011.47"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1145\/2247596.2247613"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1145\/2450142.2450151"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1145\/2463664.2465224"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1145\/2594538.2594558"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1145\/3125644"},{"volume-title":"Proceedings of the ACM\/IEEE Symposium on Logic in Computer Science (LICS\u201917)","author":"Chen Y.-F.","unstructured":"Y.-F. Chen , O. Leng\u00e1l , T. Tan , and Z. Wu . 2017. Register automata with linear arithmetic . In Proceedings of the ACM\/IEEE Symposium on Logic in Computer Science (LICS\u201917) . 1--12 Y.-F. Chen, O. Leng\u00e1l, T. Tan, and Z. Wu. 2017. Register automata with linear arithmetic. In Proceedings of the ACM\/IEEE Symposium on Logic in Computer Science (LICS\u201917). 1--12","key":"e_1_2_1_12_1"},{"volume-title":"Proceedings of the International Conference on World Wide Web (WWW\u201910)","author":"Chierichetti F.","unstructured":"F. Chierichetti , R. Kumar , and A. Tomkins . 2010. Max-cover in map-reduce . In Proceedings of the International Conference on World Wide Web (WWW\u201910) . F. Chierichetti, R. Kumar, and A. Tomkins. 2010. Max-cover in map-reduce. In Proceedings of the International Conference on World Wide Web (WWW\u201910).","key":"e_1_2_1_13_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1145\/362384.362685"},{"volume-title":"Proceedings of the Conference on Symposium on Operating Systems Design and Implementation (OSDI\u201904)","author":"Dean J.","unstructured":"J. Dean and S. Ghemawat . 2004. MapReduce: Simplified data processing on large clusters . In Proceedings of the Conference on Symposium on Operating Systems Design and Implementation (OSDI\u201904) . 137--150. J. Dean and S. Ghemawat. 2004. MapReduce: Simplified data processing on large clusters. In Proceedings of the Conference on Symposium on Operating Systems Design and Implementation (OSDI\u201904). 137--150.","key":"e_1_2_1_15_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1145\/1629175.1629198"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.14778\/1687553.1687568"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1007\/11604686_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1145\/382780.382783"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1145\/1860702.1860704"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1145\/1824777.1824786"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1016\/0304-3975(94)90242-9"},{"volume-title":"Proceedings of the Symposium on Discrete Algorithms (SODA\u201910)","author":"Karloff H.","unstructured":"H. Karloff , S. Suri , and S. Vassilvitskii . 2010. A model of computation for mapreduce . In Proceedings of the Symposium on Discrete Algorithms (SODA\u201910) . 938--948. H. Karloff, S. Suri, and S. Vassilvitskii. 2010. A model of computation for mapreduce. In Proceedings of the Symposium on Discrete Algorithms (SODA\u201910). 938--948.","key":"e_1_2_1_23_1"},{"volume-title":"Proceedings of the International Conference on Database Theory (ICDT\u201916)","author":"Koutris P.","unstructured":"P. Koutris , P. Beame , and D. Suciu . 2016. Worst-case optimal algorithms for parallel query processing . In Proceedings of the International Conference on Database Theory (ICDT\u201916) . 8:1--8:18. P. Koutris, P. Beame, and D. Suciu. 2016. Worst-case optimal algorithms for parallel query processing. In Proceedings of the International Conference on Database Theory (ICDT\u201916). 8:1--8:18.","key":"e_1_2_1_24_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1145\/1989284.1989310"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1145\/3092931.3092934"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.1145\/2809814"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1145\/1989493.1989505"},{"volume-title":"Elements of Finite Model Theory","author":"Libkin L.","unstructured":"L. Libkin . 2004. Elements of Finite Model Theory . Springer-Verlag . L. Libkin. 2004. Elements of Finite Model Theory. Springer-Verlag.","key":"e_1_2_1_29_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.1145\/1013560.1013562"},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.1006\/inco.1999.2842"},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.1145\/1376616.1376726"},{"unstructured":"Apache Pig. 2017. Home Page. Retrieved April 6 2018 from http:\/\/pig.apache.org\/.  Apache Pig. 2017. Home Page. Retrieved April 6 2018 from http:\/\/pig.apache.org\/.","key":"e_1_2_1_33_1"},{"unstructured":"Apache Spark. 2017. Bagel. Retrieved April 6 2018 from http:\/\/spark.apache.org\/docs\/0.7.3\/bagel-programming-guide.html.  Apache Spark. 2017. Bagel. Retrieved April 6 2018 from http:\/\/spark.apache.org\/docs\/0.7.3\/bagel-programming-guide.html.","key":"e_1_2_1_34_1"},{"unstructured":"Apache Spark. 2017. Home Page. Retrieved April 6 2018 from http:\/\/spark.apache.org.  Apache Spark. 2017. Home Page. Retrieved April 6 2018 from http:\/\/spark.apache.org.","key":"e_1_2_1_35_1"},{"unstructured":"Apache Spark. 2017. Spark Programming Guide. Retrieved from http:\/\/spark.apache.org\/docs\/latest\/programming-guide.html.  Apache Spark. 2017. Spark Programming Guide. Retrieved from http:\/\/spark.apache.org\/docs\/latest\/programming-guide.html.","key":"e_1_2_1_36_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_37_1","DOI":"10.1145\/1963405.1963491"},{"doi-asserted-by":"publisher","key":"e_1_2_1_38_1","DOI":"10.1145\/2463676.2463719"},{"volume-title":"Proceedings of the International Conference on Data Engineering (ICDE\u201910)","author":"Thusoo A.","unstructured":"A. Thusoo , J. Sen Sarma , N. Jain , Z. Shao , P. Chakka , N. Zhang , S. Anthony , H. Liu , and R. Murthy . 2010. Hive\u2014a petabyte scale data warehouse using Hadoop . In Proceedings of the International Conference on Data Engineering (ICDE\u201910) . 996--1005. A. Thusoo, J. Sen Sarma, N. Jain, Z. Shao, P. Chakka, N. Zhang, S. Anthony, H. Liu, and R. Murthy. 2010. Hive\u2014a petabyte scale data warehouse using Hadoop. In Proceedings of the International Conference on Data Engineering (ICDE\u201910). 996--1005.","key":"e_1_2_1_39_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_40_1","DOI":"10.1145\/79173.79181"},{"key":"e_1_2_1_41_1","volume-title":"Hadoop\u2014The Definitive Guide: Storage and Analysis at Internet Scale","author":"White T.","unstructured":"T. White . 2012. Hadoop\u2014The Definitive Guide: Storage and Analysis at Internet Scale ( 3 rd ed., revised and updated). O\u2019Reilly . T. White. 2012. Hadoop\u2014The Definitive Guide: Storage and Analysis at Internet Scale (3rd ed., revised and updated). O\u2019Reilly.","edition":"3"},{"doi-asserted-by":"publisher","key":"e_1_2_1_42_1","DOI":"10.1145\/2463676.2465288"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the 7th International Conference on Very Large Data Bases. 82--94","author":"Yannakakis Mihalis","year":"1981","unstructured":"Mihalis Yannakakis . 1981 . Algorithms for acyclic database schemes . In Proceedings of the 7th International Conference on Very Large Data Bases. 82--94 . Mihalis Yannakakis. 1981. Algorithms for acyclic database schemes. In Proceedings of the 7th International Conference on Very Large Data Bases. 82--94."},{"volume-title":"Proceedings of the Conference on Networked Systems Design and Implementation (NSDI\u201912)","author":"Zaharia M.","unstructured":"M. Zaharia , M. Chowdhury , T. Das , A. Dave , J. Ma , M. McCauley , M. Franklin , S. Shenker , and I. Stoica . 2012. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing . In Proceedings of the Conference on Networked Systems Design and Implementation (NSDI\u201912) . 15--28. M. Zaharia, M. Chowdhury, T. Das, A. Dave, J. Ma, M. McCauley, M. Franklin, S. Shenker, and I. Stoica. 2012. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing. In Proceedings of the Conference on Networked Systems Design and Implementation (NSDI\u201912). 15--28.","key":"e_1_2_1_44_1"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3197384","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3197384","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:18Z","timestamp":1750212438000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3197384"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,30]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,4,30]]}},"alternative-id":["10.1145\/3197384"],"URL":"https:\/\/doi.org\/10.1145\/3197384","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2018,4,30]]},"assertion":[{"value":"2017-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-06-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}