  Ontology-mediated querying and querying in the presence of constraints are
two key database problems where tuple-generating dependencies (TGDs) play a
central role. In ontology-mediated querying, TGDs can formalize the ontology
and thus derive additional facts from the given data, while in querying in the
presence of constraints, they restrict the set of admissible databases. In this
work, we study the limits of efficient query evaluation in the context of the
above two problems, focussing on guarded and frontier-guarded TGDs and on UCQs
as the actual queries. We show that a class of ontology-mediated queries (OMQs)
based on guarded TGDs can be evaluated in FPT iff the OMQs in the class are
equivalent to OMQs in which the actual query has bounded treewidth, up to some
reasonable assumptions. For querying in the presence of constraints, we
consider classes of constraint-query specifications (CQSs) that bundle a set of
constraints with an actual query. We show a dichotomy result for CQSs based on
guarded TGDs that parallels the one for OMQs except that, additionally, FPT
coincides with PTime combined complexity. The proof is based on a novel
connection between OMQ and CQS evaluation. Using a direct proof, we also show a
similar dichotomy result, again up to some reasonable assumptions, for CQSs
based on frontier-guarded TGDs with a bounded number of atoms in TGD heads. Our
results on CQSs can be viewed as extensions of Grohe's well-known
characterization of the tractable classes of CQs (without constraints). Like
Grohe's characterization, all the above results assume that the arity of
relation symbols is bounded by a constant. We also study the associated meta
problems, i.e., whether a given OMQ or CQS is equivalent to one in which the
actual query has bounded treewidth.
