www.uhasselt.be
DSpace

Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/27688

Title: Finite-State Map-Reduce Computation and Relational Algebra Queries
Authors: Neven, Frank
Schweikardt, Nicole
Servais, Frederic
Tan, Tony
Issue Date: 2018
Publisher: ASSOC COMPUTING MACHINERY
Citation: ACM TRANSACTIONS ON COMPUTATIONAL LOGIC, 19(2) (Art N° 14)
Abstract: 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.
Notes: [Even, Frank N.; Servais, Frederic] Hasselt Univ, Martelarenlaan 42, B-3500 Hasselt, Belgium. [Even, Frank N.; Servais, Frederic] Transnatl Univ Limburg, Maastricht, Netherlands. [Schweikardt, Nicole] Humboldt Univ, Inst Informat, Unter Linden 6, D-10099 Berlin, Germany. [Tan, Tony] Natinal Taiwan Univ, Roosevelt Rd,Sect 4,1, Taipei 10617, Taiwan.
URI: http://hdl.handle.net/1942/27688
DOI: 10.1145/3197384
ISI #: 000439733900008
ISSN: 1529-3785
Category: A1
Type: Journal Contribution
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
Published version1.16 MBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.