This is an abstract of a paper with the same title and authors accepted at IJCAI 2017. Acknowledgements. This work was supported by the French ANR projects ASPIQ (ANR-12BS02-0003) and PAGODA (ANR-12-JS02-0007).
In ontology-mediated query answering (OMQA), a database is enriched with an ontological layer and queries are answered by taking into account the information from both the data and ontology. Although most work on OMQA to date has focused on the fundamental conjunctive queries (CQs), navigational queries are gaining increasing attention. The simplest such queries are regular path queries (RPQs), which ask for paths conforming to a given regular language, but many extensions of RPQs have been considered, including conjunctive (two-way) regular path queries (CRPQs) which generalize both RPQs and CQs. In recent years, such queries have been investigated for a whole range of description logics, from highly expressive DLs of the Z family to Horn DLs like Horn-SROIQ and lightweight DLs of the DL-Lite and E L families.
In this paper, we consider the ontological language of existential rules, and specially the central fragment of guarded existential rules. Of particular interest is the subclass of linear existential rules, a natural generalization of DL-LiteR. While the complexity landscape for answering navigational queries in the presence of DL ontologies is now quite clear, the combination of navigational queries and existential rules has only begun to be explored. Recently, the complexity of RPQ answering over linear existential rules was studied. It was shown to be the same as for DL-LiteR in data complexity (NL-complete) and in combined complexity with bounded arity (PTIME-complete). However, in the unbounded arity case, the combined complexity rises to EXPTIME-complete.
We make a step towards a better understanding of the complexity of answering CRPQs over linear and guarded existential rule bases and provide the following tight complexity results. In the linear case, CRPQ answering is EXPTIME-complete in combined complexity, PSPACEcomplete in combined complexity with bounded predicate arity and NL-complete in data complexity; hence, it is not more difficult than RPQ answering, except for combined complexity with bounded predicate arity. In the guarded case, CRPQ answering is 2EXPTIME-complete in combined complexity, EXPTIME-complete in combined complexity with bounded predicate arity, and PTIME-complete in data complexity; hence, it is not more difficult than plain CQ answering.
To achieve these results, we first investigate the case of linear rules and provide a CRPQ answering algorithm that uses RPQ answering as an oracle and runs within the mentioned complexity classes. The matching lower bounds come from earlier results on RPQ and CQ answering. We next provide a non-trivial reduction of the guarded case to the linear case. This translation involves a double exponential blow-up of the rule base (while the instance only grows exponentially in the predicate arity). However, a careful analysis of the algorithm provided for linear rules shows that it actually runs in 2EXPTIME with respect to the original guarded knowledge base (and in EXPTIME in the case of bounded-arity rules).