Evaluating Datalog via Tree Automata and Cycluits

Amarilli, Antoine; Bourhis, Pierre; Monet, Mikaël; Senellart, Pierre

Type de document :

Article dans une revue scientifique: Article original

DOI :

10.1007/s00224-018-9901-2

Titre :

Evaluating Datalog via Tree Automata and Cycluits

Auteur(s) :

Amarilli, Antoine [Auteur]
Département Informatique et Réseaux [INFRES]
Data, Intelligence and Graphs [DIG]
Bourhis, Pierre [Auteur]

Self-adaptation for distributed services and large software systems [SPIRALS]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Monet, Mikaël [Auteur]
Value from Data [VALDA]
Département Informatique et Réseaux [INFRES]
Data, Intelligence and Graphs [DIG]
Senellart, Pierre [Auteur]
Département Informatique et Réseaux [INFRES]
Data, Intelligence and Graphs [DIG]
Value from Data [VALDA]

Titre de la revue :

Theory of Computing Systems

Pagination :

1620-1678

Éditeur :

Springer Verlag

Date de publication :

2019-11-15

ISSN :

1432-4350

Mot(s)-clé(s) en anglais :

Database theory
Datalog
Automata
Provenance
Circuits

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 show that clique-frontier-guarded Datalog 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 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.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Projet ANR :

DÉfis pour la Logique, les Transducteurs et les Automates

Collections :