  The paper analyzes the parameterized complexity of evaluating Ontology
Mediated Queries (OMQs) based on Guarded TGDs (GTGDs) and Unions of Conjunctive
Queries (UCQs), in the setting where relational symbols might have unbounded
arity and where the parameter is the size of the OMQ. It establishes 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. A fundamental feature of the reduction is preservation of measures
which are known to be essential for classifying classes of parameterized
uniform CSPs: submodular width (according to the well known result of Marx for
unbounded-arity schemas) and treewidth (according to the well known result of
Grohe for bounded-arity schemas). As such, the reduction can be employed to
obtain hardness results for evaluation of classes of parameterized OMQs both in
the unbounded 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.
