This study investigates the path query problem based on knowledge bases, particularly under guarded existential rules. While most related research focuses on conjunctive queries (CQs), navigational queries are gaining increasing attention. We primarily examine how to answer two-way (conjunctive) regular path queries ((C)RPQs) given an ontology defined by guarded existential rules.
First, we consider the subclass of linear existential rules and demonstrate that answering (C)RPQs is NL-complete in data complexity, matching the data complexity of answering RPQs over plain graph databases without an ontology. In terms of combined complexity, although the general case is ExpTime-complete, RPQ and CRPQ answering drop to PTime-complete and PSpace-complete respectively if there is a bound on predicate arity.
For guarded rules, we provide a non-trivial reduction to the linear case, allowing us to show that the complexity of answering (C)RPQs matches that of CQs, namely 2ExpTime-complete in combined complexity (ExpTime-complete in the bounded-arity case) and PTime-complete in data complexity.
Blogger's Review: This paper offers a fresh perspective on the complexity of path queries, particularly insightful analysis when dealing with guarded existential rules, which has significant theoretical value and practical application potential.