Abstract
Ontology-mediated query answering is concerned
with the problem of answering queries over knowledge bases consisting of a database instance and
an ontology. While most work in the area focuses on conjunctive queries (CQs), navigational
queries are gaining increasing attention. In this
paper, we investigate the complexity of answering
two-way conjunctive regular path queries (CRPQs)
over knowledge bases whose ontology is given by
a set of guarded existential rules. We first consider
the subclass of linear existential rules and show that
CRPQ answering is EXPTIME-complete in combined complexity and NL-complete in data complexity, matching the recently established bounds
for answering non-conjunctive RPQs. For guarded
rules, we provide a non-trivial reduction to the linear case, which allows us to show that the complexity of CRPQ answering is the same as for CQs,
namely 2EXPTIME-complete in combined complexity and PTIME-complete in data complexity