License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2015.324
URN: urn:nbn:de:0030-drops-49939
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4993/
Go to the corresponding LIPIcs Volume Portal

Neven, Frank ; Schweikardt, Nicole ; Servais, Frédéric ; Tan, Tony

Distributed Streaming with Finite Memory

pdf-format:
20.pdf (0.6 MB)

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 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 proceeds 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 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.

BibTeX - Entry

@InProceedings{neven_et_al:LIPIcs:2015:4993,
  author =	{Frank Neven and Nicole Schweikardt and Fr{\'e}d{\'e}ric Servais and Tony Tan},
  title =	{{Distributed Streaming with Finite Memory}},
  booktitle =	{18th International Conference on Database Theory (ICDT 2015)},
  pages =	{324--341},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-79-8},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{31},
  editor =	{Marcelo Arenas and Mart{\'i}n Ugarte},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/4993},
  URN =		{urn:nbn:de:0030-drops-49939},
  doi =		{10.4230/LIPIcs.ICDT.2015.324},
  annote =	{Keywords: distributed systems, relational algebra, semijoin algebra, register automata, register transducers.}
}

Keywords: distributed systems, relational algebra, semijoin algebra, register automata, register transducers.
Collection: 18th International Conference on Database Theory (ICDT 2015)
Issue Date: 2015
Date of publication: 19.03.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI