DROPS

Document

DOI: 10.4230/LIPIcs.ICDT.2015.324

Distributed Streaming with Finite Memory

Authors: Frank Neven, Nicole Schweikardt, Frédéric Servais, and Tony Tan

Published in: LIPIcs, Volume 31, 18th International Conference on Database Theory (ICDT 2015)

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.

Cite as

Frank Neven, Nicole Schweikardt, Frédéric Servais, and Tony Tan. Distributed Streaming with Finite Memory. In 18th International Conference on Database Theory (ICDT 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 31, pp. 324-341, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{neven_et_al:LIPIcs.ICDT.2015.324,
  author =	{Neven, Frank and Schweikardt, Nicole and Servais, Fr\'{e}d\'{e}ric and Tan, Tony},
  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 =	{Arenas, Marcelo and Ugarte, Mart{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2015.324},
  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.}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2011.312

Streamability of Nested Word Transductions

Authors: Emmanuel Filiot, Olivier Gauwin, Pierre-Alain Reynier, and Frédéric Servais

Published in: LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)

Abstract

We consider the problem of evaluating in streaming (i.e. in a single left-to-right pass) a nested word transduction with a limited amount of memory. A transduction T is said to be height bounded memory (HBM) if it can be evaluated with a memory that depends only on the size of T and on the height of the input word. We show that it is decidable in coNPTime for a nested word transduction defined by a visibly pushdown transducer (VPT), if it is HBM. In this case, the required amount of memory may depend exponentially on the height of the word. We exhibit a sufficient, decidable condition for a VPT to be evaluated with a memory that depends quadratically on the height of the word. This condition defines a class of transductions that strictly contains all determinizable VPTs.

Cite as

Emmanuel Filiot, Olivier Gauwin, Pierre-Alain Reynier, and Frédéric Servais. Streamability of Nested Word Transductions. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 312-324, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{filiot_et_al:LIPIcs.FSTTCS.2011.312,
  author =	{Filiot, Emmanuel and Gauwin, Olivier and Reynier, Pierre-Alain and Servais, Fr\'{e}d\'{e}ric},
  title =	{{Streamability of Nested Word Transductions}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{312--324},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Chakraborty, Supratik and Kumar, Amit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.312},
  URN =		{urn:nbn:de:0030-drops-33523},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.312},
  annote =	{Keywords: nested word, visibly pushdown transducer, streaming, XML}
}

Search Results

Documents authored by Servais, Frédéric

Distributed Streaming with Finite Memory

Abstract

Cite as

Streamability of Nested Word Transductions

Abstract

Cite as

Thanks for your feedback!

Could not send message