Document Open Access Logo

Enumeration on Trees under Relabelings

Authors Antoine Amarilli, Pierre Bourhis, Stefan Mengel

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2018.5.pdf
  • Filesize: 469 kB
  • 18 pages

Document Identifiers

Author Details

Antoine Amarilli
Pierre Bourhis
Stefan Mengel

Cite As Get BibTex

Antoine Amarilli, Pierre Bourhis, and Stefan Mengel. Enumeration on Trees under Relabelings. In 21st International Conference on Database Theory (ICDT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 98, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICDT.2018.5

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.

Subject Classification

Keywords
  • enumeration
  • trees
  • updates
  • MSO
  • circuits
  • knowledge compilation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The design and analysis of computer algorithms. Addison-Wesley, 1974. Google Scholar
  2. Antoine Amarilli. Leveraging the structure of uncertain data. PhD thesis, Télécom ParisTech, 2016. URL: https://tel.archives-ouvertes.fr/tel-01345836.
  3. Antoine Amarilli, Pierre Bourhis, Louis Jachiet, and Stefan Mengel. A circuit-based approach to efficient enumeration. CoRR, abs/1702.05589, 2017. URL: http://arxiv.org/abs/1702.05589.
  4. Antoine Amarilli, Pierre Bourhis, Louis Jachiet, and Stefan Mengel. A circuit-based approach to efficient enumeration. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 111:1-111:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.111.
  5. Antoine Amarilli, Pierre Bourhis, and Stefan Mengel. Enumeration on trees under relabelings. CoRR, abs/1709.06185, 2017. URL: http://arxiv.org/abs/1709.06185.
  6. Antoine Amarilli, Pierre Bourhis, and Pierre Senellart. Provenance circuits for trees and treelike instances (extended version). CoRR, abs/1511.08723, 2015. URL: http://arxiv.org/abs/1511.08723.
  7. Stefan Arnborg, Jens Lagergren, and Detlef Seese. Easy problems for tree-decomposable graphs. J. Algorithms, 12(2), 1991. Google Scholar
  8. Guillaume Bagan. MSO queries on tree decomposable structures are computable with linear delay. In CSL, 2006. Google Scholar
  9. Guillaume Bagan, Arnaud Durand, and Etienne Grandjean. On acyclic conjunctive queries and constant delay enumeration. In Jacques Duparc and Thomas A. Henzinger, editors, Computer Science Logic, 21st International Workshop, CSL 2007, 16th Annual Conference of the EACSL, Lausanne, Switzerland, September 11-15, 2007, Proceedings, volume 4646 of Lecture Notes in Computer Science, pages 208-222. Springer, 2007. URL: http://dx.doi.org/10.1007/978-3-540-74915-8_18.
  10. Andrey Balmin, Yannis Papakonstantinou, and Victor Vianu. Incremental validation of XML documents. ACM Trans. Database Syst., 29(4):710-751, 2004. URL: http://dx.doi.org/10.1145/1042046.1042050.
  11. Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. Answering conjunctive queries under updates. In Emanuel Sallinger, Jan Van den Bussche, and Floris Geerts, editors, Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017, Chicago, IL, USA, May 14-19, 2017, pages 303-318. ACM, 2017. URL: http://dx.doi.org/10.1145/3034786.3034789.
  12. Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. Answering FO+MOD queries under updates on bounded degree databases. In Michael Benedikt and Giorgio Orsi, editors, 20th International Conference on Database Theory, ICDT 2017, March 21-24, 2017, Venice, Italy, volume 68 of LIPIcs, pages 8:1-8:18. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ICDT.2017.8.
  13. Hans L. Bodlaender and Torben Hagerup. Parallel algorithms with optimal speedup for bounded treewidth. SIAM J. Comput., 27(6):1725-1746, 1998. URL: http://dx.doi.org/10.1137/S0097539795289859.
  14. Thomas Colcombet. A combinatorial theorem for trees. In Lars Arge, Christian Cachin, Tomasz Jurdzinski, and Andrzej Tarlecki, editors, Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, Wroclaw, Poland, July 9-13, 2007, Proceedings, volume 4596 of Lecture Notes in Computer Science, pages 901-912. Springer, 2007. URL: http://dx.doi.org/10.1007/978-3-540-73420-8_77.
  15. Bruno Courcelle. The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Inf. Comput., 85(1):12-75, 1990. URL: http://dx.doi.org/10.1016/0890-5401(90)90043-H.
  16. Adnan Darwiche. On the tractable counting of theory models and its application to truth maintenance and belief revision. Journal of Applied Non-Classical Logics, 11(1-2):11-34, 2001. URL: http://dx.doi.org/10.3166/jancl.11.11-34.
  17. Daniel Deutch, Tova Milo, Sudeepa Roy, and Val Tannen. Circuits for datalog provenance. In Nicole Schweikardt, Vassilis Christophides, and Vincent Leroy, editors, Proc. 17th International Conference on Database Theory (ICDT), Athens, Greece, March 24-28, 2014., pages 201-212. OpenProceedings.org, 2014. URL: http://dx.doi.org/10.5441/002/icdt.2014.22.
  18. Arnaud Durand and Etienne Grandjean. First-order queries on structures of bounded degree are computable with constant delay. ACM Trans. Comput. Log., 8(4):21, 2007. URL: http://dx.doi.org/10.1145/1276920.1276923.
  19. David Eppstein and Denis Kurz. K-best solutions of MSO problems on tree-decomposable graphs. CoRR, abs/1703.02784, 2017. URL: http://arxiv.org/abs/1703.02784.
  20. J. Nathan Foster, Todd J. Green, and Val Tannen. Annotated XML: queries and provenance. In Maurizio Lenzerini and Domenico Lembo, editors, Proceedings of the Twenty-Seventh ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2008, June 9-11, 2008, Vancouver, BC, Canada, pages 271-280. ACM, 2008. URL: http://dx.doi.org/10.1145/1376916.1376954.
  21. Todd J. Green, Gregory Karvounarakis, and Val Tannen. Provenance semirings. In Leonid Libkin, editor, Proceedings of the Twenty-Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 11-13, 2007, Beijing, China, pages 31-40. ACM, 2007. URL: http://dx.doi.org/10.1145/1265530.1265535.
  22. Wojciech Kazana and Luc Segoufin. First-order query evaluation on structures of bounded degree. Logical Methods in Computer Science, 7(2), 2011. URL: http://dx.doi.org/10.2168/LMCS-7(2:20)2011.
  23. Wojciech Kazana and Luc Segoufin. Enumeration of monadic second-order queries on trees. ACM Trans. Comput. Log., 14(4):25:1-25:12, 2013. URL: http://dx.doi.org/10.1145/2528928.
  24. Katja Losemann and Wim Martens. MSO queries on trees: enumerating answers under updates. In Thomas A. Henzinger and Dale Miller, editors, Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS '14, Vienna, Austria, July 14 - 18, 2014, pages 67:1-67:10. ACM, 2014. URL: http://dx.doi.org/10.1145/2603088.2603137.
  25. Matthias Niewerth and Luc Segoufin. Enumeration of MSO queries on strings with constant delay and logarithmic updates. In PODS, 2018. To appear. Google Scholar
  26. Milos Nikolic and Dan Olteanu. Incremental maintenance of regression models over joins, 2017. URL: http://arxiv.org/abs/1703.07484.
  27. Dan Olteanu and Jakub Závodný. Size bounds for factorised representations of query results. ACM Trans. Database Syst., 40(1):2:1-2:44, 2015. URL: http://dx.doi.org/10.1145/2656335.
  28. Luc Segoufin. A glimpse on constant delay enumeration (invited talk). In Ernst W. Mayr and Natacha Portier, editors, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), STACS 2014, March 5-8, 2014, Lyon, France, volume 25 of LIPIcs, pages 13-27. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2014. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2014.13.
  29. Volker Strassen. Vermeidung von divisionen. Journal für die reine und angewandte Mathematik, 264, 1973. URL: https://eudml.org/doc/151394.
  30. Teruji Sugaya, Masaaki Nishino, Norihito Yasuda, and Shin-Ichi Minato. Fast compilation of s-t paths on a graph for counting and enumeration. In AMBN, volume 73 of PMLR, 2017. URL: http://proceedings.mlr.press/v73/teruji-sugaya17a.html.
  31. Kunihiro Wasa. Enumeration of enumeration algorithms. CoRR, abs/1605.05102, 2016. URL: http://arxiv.org/abs/1605.05102.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact