  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 the
parameter is the size of the OMQ. We establish exact criteria for
fixed-parameter tractability (fpt) evaluation of recursively enumerable classes
of such OMQs (under the widely held Exponential Time Hypothesis). One of the
main technical tools introduced in the paper is an fpt-reduction from deciding
parameterized uniform CSPs to parameterized OMQ evaluation. The reduction
preserves measures which are known to be essential for classifying recursively
enumerable classes of parameterized uniform CSPs: submodular width (according
to the well known result of Marx for unrestricted-arity schemas) and treewidth
(according to the well known result of Grohe for bounded-arity schemas). As
such, it can be employed to obtain hardness results for evaluation of
recursively enumerable classes of parameterized OMQs both in the unrestricted
and in the bounded arity case. Previously, in the case of bounded arity
schemas, this has been tackled using a technique requiring full introspection
into the construction employed by Grohe.

Logic in Computer Science;Artificial Intelligence;Computational Complexity;Databases;Formal Languages and Automata Theory