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.2018.5
URN: urn:nbn:de:0030-drops-86060
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8606/
Go to the corresponding LIPIcs Volume Portal

Amarilli, Antoine ; Bourhis, Pierre ; Mengel, Stefan

Enumeration on Trees under Relabelings

pdf-format:
LIPIcs-ICDT-2018-5.pdf (0.5 MB)

Abstract

We study how to evaluate MSO queries with free variables on trees, within the
framework of enumeration algorithms. Previous work has shown how to enumerate
answers with linear-time preprocessing and delay linear in the size of each
output, i.e., constant-delay for free first-order variables. We extend this
result to support relabelings, a restricted kind of update operations on
trees which allows us to change the node labels. Our main result shows that we
can enumerate the answers of MSO queries on trees with linear-time preprocessing
and delay linear in each answer, while supporting node relabelings in logarithmic time. To
prove this, we reuse the circuit-based enumeration structure from our earlier
work, and develop techniques to maintain its index under node relabelings. We
also show how enumeration under relabelings can be applied to evaluate practical
query languages, such as aggregate, group-by, and parameterized queries.

BibTeX - Entry

@InProceedings{amarilli_et_al:LIPIcs:2018:8606,
  author =	{Antoine Amarilli and Pierre Bourhis and Stefan Mengel},
  title =	{{Enumeration on Trees under Relabelings}},
  booktitle =	{21st International Conference on Database Theory (ICDT 2018)},
  pages =	{5:1--5:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-063-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{98},
  editor =	{Benny Kimelfeld and Yael Amsterdamer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8606},
  URN =		{urn:nbn:de:0030-drops-86060},
  doi =		{10.4230/LIPIcs.ICDT.2018.5},
  annote =	{Keywords: enumeration, trees, updates, MSO, circuits, knowledge compilation}
}

Keywords: enumeration, trees, updates, MSO, circuits, knowledge compilation
Collection: 21st International Conference on Database Theory (ICDT 2018)
Issue Date: 2018
Date of publication: 05.03.2018

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