Characterising Fixed Parameter Tractability of Query Evaluation over Guarded TGDs

We study the parameterized complexity of evaluating Ontology Mediated Queries(OMQs) based on Guarded TGDs (GTGDs) and Unions of Conjunctive Queries (UCQs),in the case where relational symbols have unrestricted arity and where theparameter is the size of the OMQ. We establish exact criteria forfixed-parameter tractability (fpt) evaluation of recursively enumerable classesof such OMQs (under the widely held Exponential Time Hypothesis). One of themain technical tools introduced in the paper is an fpt-reduction from decidingparameterized uniform CSPs to parameterized OMQ evaluation. The reductionpreserves measures which are known to be essential for classifying recursivelyenumerable classes of parameterized uniform CSPs: submodular width (accordingto the well known result of Marx for unrestricted-arity schemas) and treewidth(according to the well known result of Grohe for bounded-arity schemas). Assuch, it can be employed to obtain hardness results for evaluation ofrecursively enumerable classes of parameterized OMQs both in the unrestrictedand in the bounded arity case. Previously, in the case of bounded arityschemas, this has been tackled using a technique requiring full introspectioninto the construction employed by Grohe.