  We study the complexity of ontology-mediated querying when ontologies are
formulated in the guarded fragment of first-order logic (GF). Our general aim
is to classify the data complexity on the level of ontologies where query
evaluation w.r.t. an ontology O is considered to be in PTime if all (unions of
conjunctive) queries can be evaluated in PTime w.r.t. O and coNP-hard if at
least one query is coNP-hard w.r.t. O. We identify several large and relevant
fragments of GF that enjoy a dichotomy between PTime and coNP, some of them
additionally admitting a form of counting. In fact, almost all ontologies in
the BioPortal repository fall into these fragments or can easily be rewritten
to do so. We then establish a variation of Ladner's Theorem on the existence of
NP-intermediate problems and use this result to show that for other fragments,
there is provably no such dichotomy. Again for other fragments (such as full
GF), establishing a dichotomy implies the Feder-Vardi conjecture on the
complexity of constraint satisfaction problems. We also link these results to
Datalog-rewritability and study the decidability of whether a given ontology
enjoys PTime query evaluation, presenting both positive and negative results.
