Complexity of Answering Path Queries under Guarded Existential Rules

A new arXiv paper investigates the complexity of answering two-way regular path queries (RPQs) and conjunctive regular path queries (CRPQs) over knowledge bases with ontologies expressed as guarded existential rules. The study first examines linear existential rules, finding that RPQ and CRPQ answering is NL-complete in data complexity, matching the complexity for plain graph databases. In combined complexity, both tasks are ExpTime-complete generally, but RPQ drops to PTime-complete and CRPQ to PSpace-complete when predicate arity is bounded. For guarded rules, the authors provide a non-trivial reduction showing that RPQ answering is 2ExpTime-complete in combined complexity, with a tight lower bound via a reduction from alternating Turing machines with exponential space. The paper contributes to ontology-mediated query answering, extending prior work on conjunctive queries to navigational queries.