Evaluating Datalog via Tree Automata and Cycluits - Equipe Data, Intelligence and Graphs Accéder directement au contenu
Article Dans Une Revue Theory of Computing Systems Année : 2019

Evaluating Datalog via Tree Automata and Cycluits

Résumé

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.

Dates et versions

hal-01891811 , version 1 (10-10-2018)

Identifiants

Citer

Antoine Amarilli, Pierre Bourhis, Mikaël Monet, Pierre Senellart. Evaluating Datalog via Tree Automata and Cycluits. Theory of Computing Systems, 2019, 63 (7), pp.1620-1678. ⟨10.1007/s00224-018-9901-2⟩. ⟨hal-01891811⟩
157 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More