License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2022.19
URN: urn:nbn:de:0030-drops-158935
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15893/
Go to the corresponding LIPIcs Volume Portal

Muñoz, Martín ; Riveros, Cristian

Streaming Enumeration on Nested Documents

pdf-format:
LIPIcs-ICDT-2022-19.pdf (0.9 MB)

Abstract

Some of the most relevant document schemas used online, such as XML and JSON, have a nested format. In the last decade, the task of extracting data from nested documents over streams has become especially relevant. We focus on the streaming evaluation of queries with outputs of varied sizes over nested documents. We model queries of this kind as Visibly Pushdown Transducers (VPT), a computational model that extends visibly pushdown automata with outputs and has the same expressive power as MSO over nested documents. Since processing a document through a VPT can generate a massive number of results, we are interested in reading the input in a streaming fashion and enumerating the outputs one after another as efficiently as possible, namely, with constant-delay. This paper presents an algorithm that enumerates these elements with constant-delay after processing the document stream in a single pass. Furthermore, we show that this algorithm is worst-case optimal in terms of update-time per symbol and memory usage.

BibTeX - Entry

@InProceedings{munoz_et_al:LIPIcs.ICDT.2022.19,
  author =	{Mu\~{n}oz, Mart{\'\i}n and Riveros, Cristian},
  title =	{{Streaming Enumeration on Nested Documents}},
  booktitle =	{25th International Conference on Database Theory (ICDT 2022)},
  pages =	{19:1--19:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-223-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{220},
  editor =	{Olteanu, Dan and Vortmeier, Nils},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15893},
  URN =		{urn:nbn:de:0030-drops-158935},
  doi =		{10.4230/LIPIcs.ICDT.2022.19},
  annote =	{Keywords: Streaming, nested documents, query evaluation, enumeration algorithms}
}

Keywords: Streaming, nested documents, query evaluation, enumeration algorithms
Collection: 25th International Conference on Database Theory (ICDT 2022)
Issue Date: 2022
Date of publication: 19.03.2022

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