@inproceedings{0147bfaa56514ac8825cbcc58190c31d,
title = "Combined tractability of query evaluation via tree automata and cycluits",
abstract = "We investigate parameterizations of both database instances and queries that make query evaluation fixed-parameter tractable in combined complexity. We introduce a new Datalog fragment with stratified negation, intensional-clique-guarded Datalog (ICG-Datalog), with linear-time evaluation on structures of bounded treewidth for programs of bounded rule size. Such programs capture in particular conjunctive queries with simplicial decompositions of bounded width, guarded negation fragment queries of bounded CQ-rank, or two-way regular path queries. Our result is shown by compiling to alternating two-way automata, whose semantics is defined via cyclic provenance circuits (cycluits) that can be tractably evaluated. Last, we prove that probabilistic query evaluation remains intractable in combined complexity under this parameterization.",
keywords = "Circuits, Provenance, Query evaluation, Tree automata, Treewidth",
author = "Antoine Amarilli and Pierre Bourhis and Mika{\"e}l Monet and Pierre Senellart",
note = "Publisher Copyright: {\textcopyright} Antoine Amarilli, Pierre Bourhis, Mika{\"e}l Monet, and Pierre Senellart; licensed under Creative Commons License CC-BY 20th International Conference on Database Theory (ICDT 2017).; 20th International Conference on Database Theory, ICDT 2017 ; Conference date: 21-03-2017 Through 24-03-2017",
year = "2017",
month = mar,
day = "1",
doi = "10.4230/LIPIcs.ICDT.2017.6",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Giorgio Orsi and Michael Benedikt",
booktitle = "20th International Conference on Database Theory, ICDT 2017",
}