Combined Tractability of Query Evaluation via Tree Automata and Cycluits (Extended Version)

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
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 proceeds via compilation 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.
Type de document :
Pré-publication, Document de travail
69 pages, accepted at ICDT'17. Appendix F contains results from an independent upcoming journal p.. 2016
Liste complète des métadonnées

Littérature citée [70 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01439309
Contributeur : Pierre Senellart <>
Soumis le : mercredi 18 janvier 2017 - 14:56:30
Dernière modification le : jeudi 11 janvier 2018 - 06:27:32
Document(s) archivé(s) le : mercredi 19 avril 2017 - 14:45:17

Fichier

amarilli2017combined_long.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01439309, version 1
  • ARXIV : 1612.04203

Citation

Antoine Amarilli, Pierre Bourhis, Mikaël Monet, Pierre Senellart. Combined Tractability of Query Evaluation via Tree Automata and Cycluits (Extended Version). 69 pages, accepted at ICDT'17. Appendix F contains results from an independent upcoming journal p.. 2016. 〈hal-01439309〉

Partager

Métriques

Consultations de la notice

296

Téléchargements de fichiers

30