Combined tractability of query evaluation via tree automata and cycluits

DOI10.4230/LIPICS.ICDT.2017.6MaRDI QIDQ3174894zbMATH OpenOpenAlexFDO

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

Publication date 18 July 2018

Full work available at URL https://arxiv.org/abs/1612.04203

zbMATH Keywords

provenancetreewidthtree automatacircuitsquery evaluation

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Database theory (68P15)

Abstract: 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.

Recommendations

• Evaluating Datalog via tree automata and cycluits
• When is the evaluation of conjunctive queries tractable?
• Hypertree decompositions and tractable queries
• Semantically Acyclic Conjunctive Queries under Functional Dependencies
• scientific article; zbMATH DE number 2080462

Cited in

(5)

• The fine classification of conjunctive queries and parameterized logarithmic space
• Connecting knowledge compilation classes and width parameters
• An epistemic approach to model uncertainty in data-graphs
• Evaluating Datalog via tree automata and cycluits
• When is the evaluation of conjunctive queries tractable?

This page was built for publication: Combined tractability of query evaluation via tree automata and cycluits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3174894)