analiza aiqbench
This paper advances theoretical foundations in knowledge representation by analyzing the computational complexity of answering navigational queries over guarded existential rules. It establishes that for linear rule subclasses, query answering matches the efficiency found in plain graph databases, while providing reductions to understand broader classes within ontology-mediated reasoning frameworks. These findings are significant primarily for researchers focusing on logic-based AI and database theory rather than immediate product applications or quantum advancements.
Answering Path Queries under Linear and Guarded Existential Rules
arXiv:2607.22636v1 Announce Type: new 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 have gained increasing attention. In this paper, we investigate the complexity of answering two-way (conjunctive) regular path queries ((C)RPQs) 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 (C)RPQ answering is NL-complete in data complexity, which matches the data complexity of answering RPQs over plain graph databases (i.e., without an ontology). In combined complexity, both tasks are ExpTime-complete in the general case, but 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, which allows us to show that the complexity of (C)RPQ answering is the same as for CQs, namely 2ExpTime-complete in combined complexity (ExpTime-complete in the bounded-arity case) and PTime-complete in data complexity.
Authors:Jean-François Baget (LIRMM, Inria, University of Montpellier, CNRS, France), Meghyn Bienvenu (Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, France), Marie-Laure Mugnier (LIRMM, Inria, University of Montpellier, CNRS, France), Michaël Thomazo (Inria, DIENS, ENS, PSL University, CNRS, France)
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 have gained increasing attention. In this paper, we investigate the complexity of answering two-way (conjunctive) regular path queries ((C)RPQs) 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 (C)RPQ answering is NL-complete in data complexity, which matches the data complexity of answering RPQs over plain graph databases (i.e., without an ontology). In combined complexity, both tasks are ExpTime-complete in the general case, but 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, which allows us to show that the complexity of (C)RPQ answering is the same as for CQs, namely 2ExpTime-complete in combined complexity (ExpTime-complete in the bounded-arity case) and PTime-complete in data complexity.
Artificial Intelligence (cs.AI)
arXiv:2607.22636 [cs.AI]
(or arXiv:2607.22636v1 [cs.AI] for this version)
Text integral sub licența deschisă a publicației · 224 cuvinte
Subiecte conexe
Building trust in AI agents: A production-ready evaluation framework with Amazon Bedrock AgentCore
AWS · 16 oct. 2026
Run agent-driven Amazon SageMaker HyperPod operations with InstantStart
AWS · 4 sept. 2026
STAIR: Semantic-Temporal Automaton for Interpretable Reasoning in Temporal Question Answering
arXiv · 18 aug. 2026
Brief independent investigation of agents’ behavior, reasoning and collaboration in the OpenAI / Hugging Face hacking incident
METR · 26 aug. 2026