Evaluating Datalog via Tree Automata and Cycluits

Antoine Amarilli 1, 2 Pierre Bourhis 3 Mikaël Monet 4, 1, 2 Pierre Senellart 4, 1, 2
1 DIG - Data, Intelligence and Graphs
LTCI - Laboratoire Traitement et Communication de l'Information
3 SPIRALS - Self-adaptation for distributed services and large software systems
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
4 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 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.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Contributor : Pierre Senellart <>
Submitted on : Wednesday, October 10, 2018 - 8:30:48 AM
Last modification on : Friday, June 7, 2019 - 11:18:38 AM

Links full text


  • HAL Id : hal-01891814, version 1
  • ARXIV : 1808.04663


Antoine Amarilli, Pierre Bourhis, Mikaël Monet, Pierre Senellart. Evaluating Datalog via Tree Automata and Cycluits. 2018. ⟨hal-01891814⟩



Record views