Answering Path Queries under Linear and Guarded Existential Rules

Jean-François Baget; Meghyn Bienvenu; Marie-Laure Mugnier; Michaël Thomazo

cs.AIJun 22, 2026

Answering Path Queries under Linear and Guarded Existential Rules

Authors: Jean-François Baget, Meghyn Bienvenu, Marie-Laure Mugnier, Michaël Thomazo

Organizations: LIRMM, Inria, University of Montpellier, CNRS, France · LIRMM, Inria, University of Montpellier, CNRS, Montpellier, France · Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, France · Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, Talence, France · Inria, DIENS, ENS, PSL University, CNRS, France · Inria, DIENS, ENS, PSL University, CNRS, Paris, 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.

Figures & tables

	RPQ	CQ	CRPQ
Data	NL -c	AC 0	NL -c
Combined, bounded arity	PTime -c	NP -c	PSpace -c
Combined, unbounded arity	ExpTime -c	PSpace -c	ExpTime -c

Table 1. Landscape of (C)(RP)Q Answering Complexity under Linear Rules

	RPQ	CQ	CRPQ
Data	PTime -c	PTime -c	PTime -c
Combined, bounded arity	ExpTime -c	ExpTime -c	ExpTime -c
Combined, unbounded arity	2ExpTime -c	2ExpTime -c	2ExpTime -c

Table 2. Landscape of (C)(RP)Q Answering Complexity under Guarded Rules

Panel of Figure 1 — Figure 1. The existential gadget

Panel of Figure 2 — Figure 2. The universal gadget

Panel of Figure 3 — Figure 3. Valid proof scheme $(\mathcal{F},\mathcal{T})$ , with $\mathcal{T}=\{((2,s_{0},1,s_{f}),(\alpha_{1},\alpha_{1}))\}$ (Example 6 )

Panel of Figure 4 — Figure 4. Chase graph $\mathcal{CG}_{D}$ on the left and a backbone of $\pi$ on the right (Example 9 )

	RPQ answering		CRPQ answering
Fragment	Data	Combined (b)	Data	Combined (b)
DL-Lite R	NL-c	PTime-c	NL-c	PSpace-c
Linear	NL-c	PTime-c	NL-c	PSpace-c
$\mathcal{ELH}$	PTime-c	PTime-c	PTime-c	PSpace-c
$\mathcal{ELHI}$	PTime-c	ExpTime-c	PTime-c	ExpTime-c
Guarded	PTime-c	ExpTime-c	PTime-c	ExpTime-c

Table 3. Data and arity-bounded combined complexities of (C)-RPQ-answering under lightweight DL ontologies

Explore similar work

How Hard is it to Decide if a Fact is Relevant to a Query?
Apr 24, 2026Meghyn Bienvenu, Diego Figueira, Pierre LafourcadeRelevance Queries
Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, F-33400, Talence, France
Recovering Explanations from Transformed Rule-Based Ontologies
Jul 31, 2026Alex Ivliev, Markus Krötzsch, Maximilian MarxOntology Recursive Reasoner
Knowledge-Based Systems Group, TU Dresden, Dresden, Germany
Ontology-Guided Evidence Path Inference for Multi-hop Knowledge Graph Question Answering
Jun 26, 2026Yongxue Shan, Meihan Wu, Cundi Fang +2Knowledge Graphs Multi-Hop Reasoning
National University of Defense Technology · Changsha, China · Pengcheng Laboratory +1

Apr 24, 2026, cs.DBJ/K move · Enter open · S save

How Hard is it to Decide if a Fact is Relevant to a Query?

Meghyn Bienvenu, Diego Figueira, Pierre Lafourcade

Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, F-33400, Talence, France

Relevance Queries Entailment Ontology Multi-Hop Reasoning Associations+1

Open paper AskPDF arXiv

We consider the following fundamental problem: given a database D, Boolean conjunctive query (CQ) q, and fact f in D, decide whether f is relevant to q wrt. D, i.e., does f belong to a minimal subset S of D such that S |= q. Despite being of central importance to query answer explanation, the combined complexity of deciding query relevance has not been studied in detail, leaving open what makes this problem hard, and which restrictions can yield lower complexity. Relevance has already been shown to be harder than query evaluation: namely,

Σ^p_2

-complete for CQs, even over a binary signature. We further observe that NP-hardness applies already to (acyclic) chain CQs. Our work identifies self-joins (multiple atoms with the same relation) as the culprit. Indeed, we prove that if we forbid or bound the occurrence of self-joins, then relevance has the same complexity as query evaluation, namely, NP (without structural restrictions) and LogCFL (for bounded hypertreewidth classes). In the ontology setting, we establish an analogous result for ontology-mediated queries consisting of a CQ and DL-Lite_R ontology, namely that relevance is no harder than query answering provided that we bound the interaction width (which generalizes both self-join width and a recently introduced 'interaction-free' condition). Our results thus pinpoint what makes relevance harder than query evaluation and identify natural classes of queries which admit efficient relevance computation.

Abstract

Explore similar work

How Hard is it to Decide if a Fact is Relevant to a Query?

Recovering Explanations from Transformed Rule-Based Ontologies

Ontology-Guided Evidence Path Inference for Multi-hop Knowledge Graph Question Answering