Combined Tractability of Query Evaluation via Tree Automata and Cycluits

Antoine Amarilli 1 Pierre Bourhis 2 Mikaël Monet 1, 3 Pierre Senellart 3, 4
2 LINKS - Linking Dynamic Data
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
3 VALDA - Value from Data
DI-ENS - Département d'informatique de l'École normale supérieure, Inria de Paris
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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [53 references]  Display  Hide  Download

https://hal.inria.fr/hal-01439294
Contributor : Pierre Senellart <>
Submitted on : Wednesday, January 18, 2017 - 2:48:28 PM
Last modification on : Friday, June 7, 2019 - 11:18:40 AM
Long-term archiving on : Wednesday, April 19, 2017 - 2:37:52 PM

File

amarilli2017combined.pdf
Files produced by the author(s)

Identifiers

Citation

Antoine Amarilli, Pierre Bourhis, Mikaël Monet, Pierre Senellart. Combined Tractability of Query Evaluation via Tree Automata and Cycluits. ICDT 2017 - International Conference on Database Theory, Mar 2017, Venice, Italy. ⟨10.4230/LIPIcs.ICDT.2017.6⟩. ⟨hal-01439294⟩

Share

Metrics

Record views

599

Files downloads

131