Evaluating Datalog via Tree Automata and Cycluits
Document type :
Compte-rendu et recension critique d'ouvrage
Title :
Evaluating Datalog via Tree Automata and Cycluits
Author(s) :
Amarilli, Antoine [Auteur]
Data, Intelligence and Graphs [DIG]
Département Informatique et Réseaux [INFRES]
Bourhis, Pierre [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Self-adaptation for distributed services and large software systems [SPIRALS]
Monet, Mikaël [Auteur]
Data, Intelligence and Graphs [DIG]
Département Informatique et Réseaux [INFRES]
Value from Data [VALDA]
Senellart, Pierre [Auteur]
Value from Data [VALDA]
Data, Intelligence and Graphs [DIG]
Département Informatique et Réseaux [INFRES]
Data, Intelligence and Graphs [DIG]
Département Informatique et Réseaux [INFRES]
Bourhis, Pierre [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Self-adaptation for distributed services and large software systems [SPIRALS]
Monet, Mikaël [Auteur]
Data, Intelligence and Graphs [DIG]
Département Informatique et Réseaux [INFRES]
Value from Data [VALDA]
Senellart, Pierre [Auteur]
Value from Data [VALDA]
Data, Intelligence and Graphs [DIG]
Département Informatique et Réseaux [INFRES]
Journal title :
Theory of Computing Systems
Pages :
1620-1678
Publisher :
Springer Verlag
Publication date :
2019-11-15
ISSN :
1432-4350
English keyword(s) :
Database theory
Datalog
Automata
Provenance
Circuits
Datalog
Automata
Provenance
Circuits
HAL domain(s) :
Informatique [cs]/Base de données [cs.DB]
English abstract : [en]
We investigate parameterizations of both database instances and queries that make query evaluation fixed-parameter tractable in combined complexity. We show that clique-frontier-guarded Datalog with stratified negation ...
Show more >We investigate parameterizations of both database instances and queries that make query evaluation fixed-parameter tractable in combined complexity. We show that clique-frontier-guarded Datalog with stratified negation (CFG-Datalog) enjoys bilinear-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 translating to alternating two-way automata, whose semantics is defined via cyclic provenance circuits (cycluits) that can be tractably evaluated.Show less >
Show more >We investigate parameterizations of both database instances and queries that make query evaluation fixed-parameter tractable in combined complexity. We show that clique-frontier-guarded Datalog with stratified negation (CFG-Datalog) enjoys bilinear-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 translating to alternating two-way automata, whose semantics is defined via cyclic provenance circuits (cycluits) that can be tractably evaluated.Show less >
Language :
Anglais
Popular science :
Non
Collections :
Source :
Files
- http://arxiv.org/pdf/1808.04663
- Open access
- Access the document
- 1808.04663
- Open access
- Access the document
- document
- Open access
- Access the document
- 1808.04663v2.pdf
- Open access
- Access the document