Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/18317
Title: | Distributed streaming with finite memory | Authors: | NEVEN, Frank Schweikardt, Nicole SERVAIS, Frederic TAN, Tony |
Issue Date: | 2015 | Source: | International Conference on Database Theory, Brussels, 23-27 March 2015 | Abstract: | We introduce three formal models of distributed systems for query evaluations on massive databases: Distributed Streaming with Register Automata (DSA), Distributed Streaming with Register Transducer (DST), and Distributed Streaming with Register Transducer and Join (DSTJ). These models are based on the key-value 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 proceed in a constant number of rounds, where the result of the last round is the input to the next round, and transformation to key-value pairs is required to be generic. The difference between the three models is in the local computation part. In DSA it is limited to making one pass over its input using a register automaton, while in DST 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 DSTJ is an extension of DST, where in the local computation a Cartesian product between two sets is allowed. We obtain the following results: (1) DSAs can evaluate the first-order queries over bounded degree databases; (2) DSTs can evaluate the semijoin algebra; (3) DSTJs can evaluate the whole relational algebra; (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. | Keywords: | distributed systems; relational algebra; semijoin algebra; register automata; register transducers | Document URI: | http://hdl.handle.net/1942/18317 | DOI: | 10.4230/LIPIcs.ICDT.2015.1 | Rights: | © Frank Neven, Nicole Schweikardt, Frederic Servais, Tony Tan; licensed under Creative Commons License CC-BY | Category: | C2 | Type: | Conference Material |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
icdt2015-final-version.pdf | Conference material | 577.64 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
1
checked on Sep 3, 2020
Page view(s)
24
checked on Sep 7, 2022
Download(s)
4
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.