2026-08-16T13:06:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8606 2024-03-06T10:42:26Z ddc:004 open_access

Enumeration on Trees under Relabelings Amarilli, Antoine Bourhis, Pierre Mengel, Stefan enumeration trees updates MSO circuits knowledge compilation 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Antoine Amarilli and Pierre Bourhis and Stefan Mengel 2018 Is Part Of LIPIcs, Volume 98, 21st International Conference on Database Theory (ICDT 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2018.5 urn:nbn:de:0030-drops-86060 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2018.5 eng https://creativecommons.org/licenses/by/3.0/legalcode