  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.

Databases