Titre :

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

Auteur(s) :

Amarilli, Antoine [Auteur]
Laboratoire Traitement et Communication de l'Information [LTCI]
Bourhis, Pierre [Auteur]
Linking Dynamic Data [LINKS]
Monet, Mikaël [Auteur]
Value from Data [VALDA]
Laboratoire Traitement et Communication de l'Information [LTCI]
Senellart, Pierre [Auteur]
Département d'informatique - ENS-PSL [DI-ENS]
Value from Data [VALDA]

Discipline(s) HAL :

Informatique [cs]/Base de données [cs.DB]

Résumé en anglais : [en]

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, ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Commentaire :

69 pages, accepted at ICDT'17. Appendix F contains results from an independent upcoming journal paper by Michael Benedikt, Pierre Bourhis, Georg Gottlob, and Pierre Senellart

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL