# Data Complexity of Querying Description Logic Knowledge Bases under Cost-Based Semantics

Meghyn Bienvenu, Quentin Maniere

<figure><img src="image_1.png" /></figure>

## To cite this version:

Meghyn Bienvenu, Quentin Maniere. Data Complexity of Querying Description Logic Knowledge Bases under Cost-Based Semantics. Proceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI-26), Jan 2026, Singapore, Singapore. hal-05360907

HAL Id: hal-05360907

https://hal.science/hal-05360907v1

Submitted on 22 Nov 2025

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Data Complexity of Querying Description Logic
## Knowledge Bases under Cost-Based Semantics

Meghyn Bienvenu¹, Quentin Manière²,³

¹Université de Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, Talence, France

²Department of Computer Science, Leipzig University, Germany

³Center for Scalable Data Analytics and Artificial Intelligence (ScaDS.AI), Dresden/Leipzig, Germany
meghyn.bienvenu@labri.fr, quentin.maniere@uni-leipzig.de

## Abstract

In this paper, we study the data complexity of querying inconsistent weighted description logic (DL) knowledge bases under recently-introduced cost-based semantics. In a nutshell, the idea is to assign each interpretation a cost based upon the weights of the violated axioms and assertions, and certain and possible query answers are determined by considering all (resp. some) interpretations having optimal or bounded cost. Whereas the initial study of cost-based semantics focused on DLs between $EL_⊥$ and $ALCO$, we consider DLs that may contain inverse roles and role inclusions, thus covering prominent DL-Lite dialects. Our data complexity analysis goes significantly beyond existing results by sharpening several lower bounds and pinpointing the precise complexity of optimal-cost certain answer semantics (no non-trivial upper bound was known). Moreover, while all existing results show the intractability of cost-based semantics, our most challenging and surprising result establishes that if we consider DL-Lite<sup>H</sup><sub>bool</sub> ontologies and a fixed cost bound, certain answers for instance queries and possible answers for conjunctive queries can be computed using first-order rewriting and thus enjoy the lowest possible data complexity (AC<sup>0</sup>).

**Extended version** — http://arxiv.org/abs/2511.07095

## 1 Introduction

Ontology-mediated query answering (OMQA) has been extensively studied within the KR and database communities as a means of improving data access by exploiting semantic information provided by an ontology (Poggi et al. 2008; Bienvenu and Ortiz 2015; Xiao et al. 2018). Ontologies are typically formulated in decidable fragments of first-order logic (FO), with description logics (DLs) being a popular choice (Baader et al. 2017). Given an ontology (or TBox in DL parlance) $T$, a dataset (or ABox) $A$, and a query $q(\vec{x})$, the OMQA task boils down to finding the certain answers, i.e. tuples of constants $\vec{a}$ for which the instantiated query $q(\vec{a})$ is entailed from the knowledge base (KB) ($T, A$). Observe that if the input KB is inconsistent, every answer tuple is trivially a certain answer, so OMQA trivializes.

A prominent approach to tackling this issue is to adopt alternative inconsistency-tolerant semantics in order to be able to extract meaningful information from inconsistent KBs, cf. (Lembo et al. 2010) and surveys (Bienvenu and Bourgaux 2016; Bienvenu 2020). Many of these semantics

are based upon repairs, defined as inclusion-maximal consistent subsets of the ABox. For example, the AR semantics considers the query answers that hold in all repairs, while the brave semantics returns those answers holding in at least one repair. Note that the line of work on repair-based semantics targets scenarios in which the TBox axioms are deemed fully reliable, so inconsistencies derive solely from errors in the ABox. However, in practice, it can be useful to allow for TBox axioms which typically hold but may admit rare exceptions. Such ‘soft’ ontology axioms can be addressed qualitatively, using generalized notions of repair that have been proposed for existential rule ontologies (Eiter, Lukasiewicz, and Predoiu 2016), or employing non-monotonic extensions of DLs that support defeasible axioms cf. (Bonatti, Lutz, and Wolter 2009; Giordano et al. 2013; Britz et al. 2021). Another option is to adopt a quantitative approach, using the recently proposed cost-based semantics for DL KBs (Bienvenu, Bourgaux, and Jean 2024), henceforth referred to as (BBJ 2024) for succinctness.

In a nutshell, the idea is to annotate axioms and assertions with (possibly infinite) weights, which are used to assign a cost to each interpretation based upon the weights of the violated axioms and assertions (and taking into account also the number of violations of each TBox axiom). To query the KB, we may choose either to consider the set of interpretations achieving the optimal cost, or we may fix a cost bound $k$ and consider all interpretations having cost at most $k$. We can then define the sets of certain and possible answers as those answers that hold respectively in all or some interpretation of optimal cost or bounded cost. As noted in (BBJ 2024), the optimal-cost certain answer semantics generalizes both the classical certain answer semantics and the AR semantics based upon weighted ABox repairs. Increasing the cost bound $k$ beyond the optimal cost allows one to identify answers that are robust in the sense that they hold not only for the optimal-cost interpretations. Optimal- and bounded-cost possible answers generalize query satisfiability and can serve to compare candidate answers based upon their incompatibility with the KB.

The computational complexity of querying inconsistent weighted KBs under cost-based semantics was investigated in (BBJ 2024). Five central decision problems were considered: bounded-cost satisfiability (does there exist an interpretation with cost at most $k$?) plus query entailment un-
der the four cost-based semantics. The complexity analysis was fairly comprehensive, considering both combined and data complexity, conjunctive and instance queries, and DLs ranging from the lightweight DL $\mathcal{EL}_⊥$ to the expressive DL $\mathcal{ALCO}$. One important question that was left open, however, was the data complexity of optimal-cost certain semantics (arguably the most useful of the semantics), for which no non-trivial upper bound was provided. Moreover, as the considered DLs allow neither inverse roles nor role inclusions, they do not yield any results for DLs of the DL-Lite family (Calvanese et al. 2007), which are the most commonly utilized in the context of OMQA.

The preceding considerations motivate us to embark on a more detailed data complexity analysis of cost-based semantics, considering various DL-Lite dialects and expressive DLs up to ALCHIO. The results of our study are summarized in Table 1. A first major contribution, detailed in Section 4, is to provide a $\Delta_2^p$ upper bound for the optimal-cost certain and possible semantics, matching an existing lower bound for $\mathcal{EL}_⊥$ and a new lower bound we show for DL-Lite<sub>core</sub>. This result is obtained by using an intricate quotient construction to establish a small interpretation property, which crucially does not depend on the considered cost. In Section 5, we strengthen a number of existing lower bounds for the bounded-cost semantics by showing that they hold even when for cost bound $k=1$, as well as providing some new lower bounds for DL-Lite<sub>core</sub>. Finally, our most challenging and surprising technical result (presented in Section 6) is to show that if we consider DL-Lite<sub>bool</sub><sup>H</sup> ontologies and a fixed cost bound, then certain answers for instance queries and possible answers for conjunctive queries can be computed using first-order rewriting and thus enjoy the lowest possible data complexity ($AC^0$). Detailed proofs can be found in the appendix of the extended version.

## 2 Preliminaries

We recall the syntax & semantics of description logics (DLs) and refer readers to (Baader et al. 2017) for further details.

**Description logic knowledge bases** We consider countably infinite sets $N_C$, $N_R$, and $N_I$ of concept names, role names, and individual names. An inverse role has the form $r^-$, with $r \in N_R$. A role is either a role name or inverse role. We use $N_R^\pm = N_R \cup \{r^- | r \in N_R\}$ for the set of roles. If $r = s^-$ is an inverse role, then $r^-$ denotes $s^-$.

An ALCHIO concept C is built according to the grammar $C, D ::= T | \perp | A | \{a\} | \neg C | C \sqcap D | \exists r. D$ where $A \in N_C$, $r \in N_R^\pm$, and $a \in N_I$. A concept $\{a\}$ is called a nominal. An ALCHIO concept is a nominal-free ALCHIO concept. An $\mathcal{EL}$ concept is an ALCHIO concept that uses neither negation, nor $\perp$, nor inverse roles ($\mathcal{EL}_⊥$ concepts may additionally use $\perp$).

An ALCHIO TBox is a finite set of concept inclusions (CIs) $C \sqsubseteq D$, where C, D are ALCHIO concepts, and role inclusions (RIs) $r \sqsubseteq s$, where $r, s \in N_R^\pm$. An $\mathcal{EL}$ TBox consists only of CIs between $\mathcal{EL}$ concepts. An ABox is a finite set of concept assertions $A(a)$ and role assertions $r(a, b)$ where $A \in N_C$, $r \in N_R$, and $a, b \in N_I$. We use Ind($\mathcal{A}$) for the set of individual names used in $\mathcal{A}$, and $N_C(T)$ (resp. $N_R(T)$) for the set of concept (resp. role) names used in $T$. An

$\mathcal{ALCHIO}$ knowledge base (KB) takes the form $K = (T, \mathcal{A})$ with $T$ an ALCHIO TBox and $\mathcal{A}$ an ABox.

We next introduce the syntax of some DLs of the DL-Lite family. A basic concept has the form $A \lor \exists r$, with $A \in N_C$ and $r \in N_R^\pm$. A DL-Lite<sub>core</sub><sup>H</sup> TBox is a finite set of CIs of the forms $C \sqsubseteq D$ and $C \sqcap D \sqsubseteq \perp$, with C, D basic concepts, and RIs $r \sqsubseteq s$, with $r, s \in N_R^\pm$. We drop superscript $^H$ if no role inclusions are admitted, and replace $\cdot_{\text{core}}$ by $\cdot_{\text{bool}}$ to indicate that C, D may be built from basic concepts using $\neg$, $\sqcap$, $\sqcup$.

The semantics of DL KBs is defined as usual in terms of interpretations $I = (\Delta^I, \cdot^I)$ with $\Delta^I$ the non-empty domain and $\cdot^I$ the interpretation function. An interpretation satisfies a CI $C \sqsubseteq D$ if $C^I \subseteq D^I$ and likewise for RIs. It satisfies an assertion $A(a)$ if $a \in A^I$ and $r(a, b)$ if $(a, b) \in r^I$. This notably requires ABox individuals to be interpreted as themselves, thus enforcing the standard names assumption (SNA) for the ABox individuals. The interpretation $I_\mathcal{A}$ associated with an ABox $\mathcal{A}$ has domain Ind($\mathcal{A}$) and interprets concept and role names according to the assertions of $\mathcal{A}$:

$$A^{I_\mathcal{A}} := \{a | A(a) \in \mathcal{A}\} \quad r^{I_\mathcal{A}} := \{(a, b) | r(a, b) \in \mathcal{A}\}.$$

Given any interpretation $I$, we use $I|_\Delta$ to denote the restriction of $I$ to a subdomain $\Delta \subseteq \Delta^I$.

**Queries** First-order queries are given by formulas in first-order logic with equality. Since we wish to query DL KBs, we consider queries whose relational atoms can be either concept atoms $A(t)$ or role atoms $r(t, t')$, where $A \in N_C$, $r \in N_R$, and $t, t'$ are terms (variables or individuals). We mostly focus on conjunctive queries (CQs) which have the form $\exists \vec{y} \psi$, where $\psi$ is a conjunction of concept and role atoms, and $\vec{y}$ a tuple of variables from $\psi$. Instances queries (IQs) are CQs with a single atom. We also consider acyclic and connected CQs, meaning that the associated undirected graph (containing an edge $\{t, t'\}$ for each role atom $r(t, t')$) has these properties. A Boolean CQ (BCQ) is a CQ that has no free variables. We write $I \models q$ to indicate that an interpretation $I$ satisfies a BCQ $q$.

**Complexity classes** For any syntactic object $O$ such as a TBox, ABox, or query, we use $|O|$ to denote the size of $O$, meaning the encoding of $O$ as a word over a suitable alphabet. Our complexity results concern the well-known complexity classes NP and coNP as well as $\Delta_2^p$ (deterministic polynomial time with access to an NP oracle) and $AC^0$. We omit the formal definition of $AC^0$, which is based upon circuits, as to understand our results, it suffices to know that it is in $AC^0$ (in data complexity) to test whether a Boolean first-order query is satisfied in a finite interpretation.

## 3 Cost-Based Semantics for Weighted KBs

In this section, we recall the definition of cost-based semantics from (BBJ 2024) and introduce the associated reasoning tasks. We also recall and prove some basic properties used in later sections.

Throughout the paper, we work with weighted KBs, whose assertions and axioms are annotated with weights:

**Definition 1.** A weighted knowledge base (WKB) $K_\omega = (T, \mathcal{A})_\omega$ consists of a knowledge base $(T, \mathcal{A})$ and a weight
<table><caption>Table 1: All results are completeness results, unless stated otherwise. †: lower bound from (BBJ 2024). ‡: lower bound for $k \ge 3$ from (BBJ 2024), improved to $k \ge 1$ in the present paper. For CQA, lower bounds already hold for connected acyclic BCQs. Results hold both for binary and unary encoding of weights, except for $\Delta_2^p$-hardness (only for binary encoding).</caption><thead><tr><th></th><th>BCS<sup>k</sup>, IQA<sup>k</sup><sub>p</sub>, CQA<sup>k</sup><sub>p</sub></th><th>IQA<sup>k</sup><sub>c</sub></th><th>CQA<sup>k</sup><sub>c</sub></th><th>BCS, IQA<sub>p</sub>, CQA<sub>p</sub></th><th>IQA<sub>c</sub>, CQA<sub>c</sub></th><th>IQA<sup>opt</sup><sub>p,c</sub>, CQA<sup>opt</sup><sub>p,c</sub></th></tr></thead><tbody><tr><td>EL<sub>⊥</sub> / ALCHIO</td><td>NP<sup>‡</sup><sub>Thm. 1, 3</sub></td><td>coNP<sup>‡</sup><sub>Thm. 1, 4</sub></td><td>coNP<sup>‡</sup><sub>Thm. 1, 4</sub></td><td>NP<sup>†</sup><sub>Thm. 1</sub></td><td>coNP<sup>†</sup><sub>Thm. 1</sub></td><td>Δ<sup>p</sup><sub>2</sub><sup>†</sup><sub>Thm. 2</sub></td></tr><tr><td>DL-Lite<sub>core</sub> / DL-Lite<sup>H</sup><sub>bool</sub></td><td>in AC<sup>0</sup><sub>Thm. 8</sub></td><td>in AC<sup>0</sup><sub>Thm. 8</sub></td><td>coNP<sub>Thm. 1, 7</sub></td><td>NP<sub>Thm. 1, 5</sub></td><td>coNP<sub>Thm. 1, 5</sub></td><td>Δ<sup>p</sup><sub>2</sub><sub>Thm. 2, 6</sub></td></tr></tbody></table>

function $\omega: T \cup A \mapsto \mathbb{N}_{>0} \cup \{\infty\}$. We can similarly define weighted TBoxes ($T_\omega$) and weighted ABoxes ($A_\omega$).

Intuitively, these weights can be viewed as the penalties incurred for violating assertions and axioms: those having cost 1 are the least reliable, while those assigned maximal weight $\infty$ should definitely be satisfied.

Interpretations will then be assigned costs based upon the sets of violations of the TBox axioms and ABox assertions. Note that differently from prior work, we also define violations of role inclusions, given by pairs of domain elements.

**Definition 2.** Given an interpretation $\mathcal{I}$, the set of violations of a concept inclusion $B \sqsubseteq C$ in $\mathcal{I}$ is $vio_{B \sqsubseteq C}(\mathcal{I}) = B^I \setminus C^I$, the set of violations of a role inclusion $r \sqsubseteq s$ in $\mathcal{I}$ is $vio_{r \sqsubseteq s}(\mathcal{I}) = r^I \setminus s^I$, and the violations of an ABox $A$ in $\mathcal{I}$ are $vio_A(\mathcal{I}) = \{\alpha \in A | \mathcal{I} \not\models \alpha\}$.

**Definition 3.** Let $K_\omega = (T, A)_\omega$ be a WKB. The cost of an interpretation $\mathcal{I}$ w.r.t. $K_\omega$ is defined by:

$$ \omega(\mathcal{I}) = \sum_{\tau \in T} \omega(\tau) |vio_{\tau}(\mathcal{I})| + \sum_{\alpha \in vio_A(\mathcal{I})} \omega(\alpha) $$

The optimal cost of $K_\omega$ is $\text{optc}(K_\omega) = \min_{\mathcal{I}}(\omega(\mathcal{I}))$. A WKB $K_\omega$ is k-satisfiable if $\omega(\mathcal{I}) \le k$ for some interpretation $\mathcal{I}$.

We recall next the four cost-based semantics proposed in (BBJ 2024), which depend on whether one considers interpretations whose cost is less than a provided bound, or the interpretations having optimal cost, and whether the query is required to hold in all or at least one such interpretation.

**Definition 4.** Let $q$ be a BCQ, $K_\omega = (T, A)_\omega$ a WKB, and $k$ an integer. We say that $q$ is entailed by $K_\omega$ under

* k-cost bounded certain semantics, written $K_\omega \models_c^k q$, if $\mathcal{I} \models q$ for every interpretation $\mathcal{I}$ with $\omega(\mathcal{I}) \le k$;

* k-cost bounded possible semantics, written $K_\omega \models_p^k q$, if $\mathcal{I} \models q$ for some interpretation $\mathcal{I}$ with $\omega(\mathcal{I}) \le k$;

* opt-cost certain semantics, written $K_\omega \models_c^{opt} q$, if $\mathcal{I} \models q$ for every interpretation $\mathcal{I}$ with $\omega(\mathcal{I}) = \text{optc}(K_\omega)$;

* opt-cost possible semantics, written $K_\omega \models_p^{opt} q$, if $\mathcal{I} \models q$ for some interpretation $\mathcal{I}$ with $\omega(\mathcal{I}) = \text{optc}(K_\omega)$.

These semantics extend to non-Boolean CQs in the expected way, e.g. the opt-cost certain answers to a CQ $q(\vec{x})$ w.r.t. $(T, A)_\omega$ are the tuples $\vec{a}$ from $\text{Ind}(A)$ s.t. $K_\omega \models_c^{opt} q(\vec{a})$.

If the underlying KB is satisfiable, then the certain and possible optimal-cost semantics coincide with query entailment and query satisfiability (or with classical notions of certain and possible answers, in the case of non-Boolean

queries). These semantics are thus intended to be used when the underlying KB is inconsistent. The opt-cost certain answers identifies those answers that hold in the interpretations deemed most likely and have been shown to generalize previously considered weight-based repair semantics (BBJ 2024). By considering values of $k$ beyond $\text{optc}(K_\omega)$, we can use the $k$-cost bounded certain semantics to identify ‘robust’ answers which hold not only in the optimal-cost interpretations but also in those with close-to-optimal cost. By contrast, the opt-cost and $k$-cost bounded possible answers can serve to rank candidate answers based upon their degree of incompatibility with the WKB.

We now formalize the decision problems for cost-based semantics investigated in this paper, which differ depending on which cost bound is used and whether it is given as input:

* Bounded cost satisfiability (BCS) takes as input a WKB $K_\omega = (T, A)_\omega$ and an integer $k$ and decides whether there exists an interpretation $\mathcal{I}$ with $\omega(\mathcal{I}) \le k$.

* k-cost satisfiability (BCS$^k$) takes as input a WKB $K_\omega = (T, A)_\omega$ and decides whether there exists an interpretation $\mathcal{I}$ with $\omega(\mathcal{I}) \le k$.

* Bounded-cost certain (resp. possible) BCQ entailment (CQA$_c$ / CQA$_p$) takes as input a WKB $K_\omega = (T, A)_\omega$, a BCQ $q$ and an integer $k$ and decides whether $K_\omega \models_c^k q$ (resp. $K_\omega \models_p^k q$).

* k-cost certain (resp. possible) BCQ entailment (CQA$_c^k$ / CQA$_p^k$) takes as input a WKB $K_\omega = (T, A)_\omega$ and a BCQ $q$ and decides whether $K_\omega \models_c^k q$ (resp. $K_\omega \models_p^k q$).

* Optimal-cost certain (resp. possible) BCQ entailment (CQA$_c^{opt}$ / CQA$_p^{opt}$) takes as input a WKB $K_\omega = (T, A)_\omega$ and a BCQ $q$ and decides if $K_\omega \models_c^{opt} q$ (resp. $K_\omega \models_p^{opt} q$).

We will also consider the restrictions of the BCQ entailment problems to the case of instance queries, denoted by $\text{IQA}_c$, $\text{IQA}_p$, $\text{IQA}_c^k$, $\text{IQA}_p^k$, $\text{IQA}_c^{opt}$ and $\text{IQA}_p^{opt}$ respectively.

We shall study the data complexity of the preceding reasoning tasks. For the fixed-cost and optimal-cost decision problems, data complexity is measured with respect to the size of the input weighted ABox, while the size of the weighted TBox and query (if present) are treated as constants. For the bounded-cost problems, we measure complexity w.r.t. the weighted ABox and the input integer. Both the ABox weights and the input integer (if present) are assumed to be encoded in binary.

We conclude the section with some easy lemmas, which establish useful reductions between the decision problems.
**Lemma 1.** BCS<sup>*k*</sup> for DL-Lite<sub>core</sub> (resp. <i>EL</i><sub>⊥</sub>) reduces to IQA<sub>*p*</sub><sup>*k*</sup> for DL-Lite<sub>core</sub> (resp. <i>EL</i><sub>⊥</sub>). In particular, the same holds for BCS and IQA<sub>*p*</sub>.

**Lemma 2.** IQA<sub>*p*</sub><sup>*k*</sup> for DL-Lite<sub>core</sub> (resp. <i>EL</i><sub>⊥</sub>) reduces to the complement of IQA<sub>*c*</sub><sup>*k+1*</sup> for DL-Lite<sub>core</sub> (resp. <i>EL</i><sub>⊥</sub>). In particular, IQA<sub>*p*</sub> reduces to the complement of IQA<sub>*c*</sub>.

**Lemma 3.** For every $k \ge 0$, IQA<sub>*p*</sub><sup>*k*</sup> for DL-Lite<sub>core</sub> (resp. <i>EL</i><sub>⊥</sub>) reduces to IQA<sub>*p*</sub><sup>*k+1*</sup> for DL-Lite<sub>core</sub> (resp. <i>EL</i><sub>⊥</sub>) WKBs.

# 4 An Upper Bound for the General Case

The aim of this section is to establish the next two theorems:

**Theorem 1.** CQA<sub>*p*</sub> (resp. CQA<sub>*c*</sub>) for ALCHIO is in NP (resp. in coNP).

**Theorem 2.** CQA<sub>*p*</sub><sup>opt</sup> and CQA<sub>*c*</sub><sup>opt</sup> for ALCHIO are in Δ<sub>*p*</sub><sup>2</sup>.

Starting from an interpretation $\mathcal{I}$ that satisfies (or does not satisfy) the query $q$ of interest, the main technical ingredient is the construction of another interpretation $\mathcal{J}$ that behaves as $\mathcal{I}$ w.r.t. $q$, whose cost is at most the cost of $\mathcal{I}$, and whose domain has a size polynomially bounded by the size of the input ABox $\mathcal{A}$. This is fairly easy if query satisfaction is to be preserved, that is, for CQA<sub>*p*</sub>: one can brutally collapse elements together according to their type using the well-known filtration technique (Baader et al. 2017).

**Lemma 4.** Let $\mathcal{K} = (\mathcal{T}, \mathcal{A})_{\omega}$ be an ALCHIO WKB, $k$ an integer, and $q$ a BCQ. If there exists an interpretation $\mathcal{I}$ such that $\omega(\mathcal{I}) \le k$ and $\mathcal{I} \models q$, then there is an interpretation $\mathcal{J}$ such that $\omega(\mathcal{J}) \le k$ and $\mathcal{J} \models q$, and whose domain $\Delta^{\mathcal{J}}$ has cardinality bounded polynomially in $|\mathcal{A}|$, with $|\mathcal{T}|$ and $|q|$ treated as constants, and independently from $k$.

It becomes more challenging if query non-satisfaction is the property to preserve, that is, to address CQA<sub>*c*</sub>. In particular, the solution adopted in (BBJ 2024, Proposition 8) for ALCO WKBs yields a polynomial bound that depends on the bounded cost $k$. This makes their technique adequate when the cost is fixed, that is, for CQA<sub>*c*</sub><sup>*k*</sup>, or if the encoding of $k$ is given in unary, but otherwise does not provide a polynomial upper bound w.r.t. data complexity. We deeply rework the approach, not only to support ALCHIO WKBs, but also to obtain a cost-independent bound as follows.

**Lemma 5.** Let $\mathcal{K} = (\mathcal{T}, \mathcal{A})_{\omega}$ be an ALCHIO WKB, $k$ an integer, and $q$ a BCQ. If there exists an interpretation $\mathcal{I}$ such that $\omega(\mathcal{I}) \le k$ and $\mathcal{I} \models q$, then there is an interpretation $\mathcal{J}$ such that $\omega(\mathcal{J}) \le k$ and $\mathcal{J} \models q$, and whose domain $\Delta^{\mathcal{J}}$ has cardinality that is bounded polynomially in $|\mathcal{A}|$, with $|\mathcal{T}|$ and $|q|$ treated as constants, and independently from $k$.

With Lemmas 4 and 5, we obtain the NP and coNP upper bounds in Theorem 1 with standard guess-and-check procedures. For Theorem 2, the $\Delta_{2}^{p}$ algorithms proceed similarly but first identify the optimal cost via a binary search, using an exponential bound on the optimal cost (whenever finite).

Now, to prove Lemma 5, we rely on the adaptation of a quotient construction from (Manière 2022, Theorem 8) defined to answer counting conjunctive queries over ALCHI KBs. This construction was already reused by (BBJ 2024) for ALCO WKBs, and it is not too difficult to handle inverse

roles and role inclusions by sticking closer to the original version. From the starting interpretation $\mathcal{I}$, our adaptation differs from theirs as it also takes as a parameter a subset $\mathcal{V} \subseteq \mathcal{T}$ of the considered TBox $\mathcal{T}$. In the constructed interpretation, we violate axioms of $\mathcal{V}$ exactly as in the original interpretation $\mathcal{I}$. Intuitively, one can think of these axioms in $\mathcal{V}$ as so expensive to violate that one cannot do better than in $\mathcal{I}$, while potential violations of axioms from $\mathcal{T} \setminus \mathcal{V}$ can be handled in a more systematic and structured manner. Violations of ABox assertions are easier to control and are preserved exactly as in the original interpretation $\mathcal{I}$. For an interpretation $\mathcal{J}$, we denote $vio_{\mathcal{V}}(\mathcal{J}) := \bigcup_{\tau \in \mathcal{V}} vio_{\tau}(\mathcal{J})$. Adapting the quotient technique yields the following:

**Lemma 6.** Let $\mathcal{K} = (\mathcal{T}, \mathcal{A})$ be an ALCHIO KB and $q$ a BCQ. Let $\mathcal{V} \subseteq \mathcal{T}$ be a subset of $\mathcal{T}$ and $\mathcal{I}$ an interpretation such that $\mathcal{I} \not\models q$. There exists a polynomial $p$ independent of $\mathcal{A}$, and an interpretation $\mathcal{J}$ satisfying the following:

$$1. \quad \mathcal{J} \not\models q; \qquad 3. \quad \forall \tau \in \mathcal{V}, vio_{\tau}(\mathcal{J}) \subseteq vio_{\tau}(\mathcal{I});$$

$$2. \quad vio_{\mathcal{A}}(\mathcal{J}) = vio_{\mathcal{A}}(\mathcal{I}); \quad 4. \quad |\Delta^{\mathcal{J}}| \le p(|\mathcal{A}| + |vio_{\mathcal{V}}(\mathcal{I})|).$$

We now explain how to obtain Lemma 5, with an approach inspired from (Lutz and Manière 2024), where our Lemmas 5 and 6 respectively play the role of their Proposition 2 and Lemma 1. Let $\mathcal{K}_{\omega} = (\mathcal{T}, \mathcal{A})_{\omega}$ be an ALCHIO WKB, $q$ a BCQ, $k$ an integer, and $\mathcal{I}$ an interpretation such that $\mathcal{I} \not\models q$. For a given $\mathcal{V} \subseteq \mathcal{T}$, we use $\mathcal{J}_{\mathcal{V}}$ to denote the interpretation obtained by applying Lemma 6 with $\mathcal{V}$ the input set of axioms. We prove that there exists a subset $\mathcal{V} \subseteq \mathcal{T}$ such that (i) the size of $vio_{\mathcal{V}}(\mathcal{I})$ is bounded by a polynomial in $|\mathcal{A}|$ independent of $k$; and (ii) $\omega(\mathcal{J}_{\mathcal{V}}) \le k$. To do so, we construct a sequence $\mathcal{V}_0 \subseteq \mathcal{V}_1 \subseteq \dots \subseteq \mathcal{V}_n \subseteq \mathcal{T}$ of $\mathcal{V}$'s that all satisfy item (i) and with $\mathcal{V}_n$ also satisfying item (ii). Note that $\mathcal{J}_{\mathcal{V}_n}$ is then the desired interpretation for Lemma 5: item (i) plus Point 4 from Lemma 6 gives the polynomial bound on the size of $\mathcal{J}_{\mathcal{V}_n}$, while item (ii) and Point 1 in Lemma 6 ensure the desired properties w.r.t. the cost and query.

**Initialization.** Set $\mathcal{V}_0 := \emptyset$, which trivially satisfies item (i).

**Induction step.** Assume that, for some $i \ge 0$, we have successfully constructed $\mathcal{V}_i$ satisfying item (i); thus we have a polynomial $p_i$ independent of $k$ such that $|vio_{\mathcal{V}_i}(\mathcal{I})| \le p_i(|\mathcal{A}|)$. If $\mathcal{V}_i$ also satisfies item (ii), then we are done. Otherwise $\omega(\mathcal{J}_{\mathcal{V}_i}) > k$, and since $\omega(\mathcal{I}) \le k$, there exists an assertion or axiom $\tau$ from $\mathcal{K}$ that is violated at least once more in $\mathcal{J}_{\mathcal{V}_i}$ than in $\mathcal{I}$, i.e. $|vio_{\tau}(\mathcal{J}_{\mathcal{V}_i})| > |vio_{\tau}(\mathcal{I})|$. Note that due to Point 2 in Lemma 6, it is then clear that $\tau \notin \mathcal{A}$. Similarly, due to Point 3 in Lemma 6, we have $\tau \notin \mathcal{V}_i$. Therefore $\tau \in \mathcal{T} \setminus \mathcal{V}_i$. We set $\mathcal{V}_{i+1} := \mathcal{V}_i \cup \{\tau\}$. It remains to verify that $\mathcal{V}_{i+1}$ satisfies item (i). Note that $vio_{\mathcal{V}_{i+1}}(\mathcal{I}) = vio_{\mathcal{V}_i}(\mathcal{I}) \cup vio_{\tau}(\mathcal{I})$. The size of $vio_{\mathcal{V}_i}(\mathcal{I})$ is bounded adequately by $p_i(|\mathcal{A}|)$. For the size of $vio_{\tau}(\mathcal{I})$, recall that by choice of $\tau$ we have $|vio_{\tau}(\mathcal{I})| < |vio_{\tau}(\mathcal{J}_{\mathcal{V}_i})|$. We brutally bound $|vio_{\tau}(\mathcal{J}_{\mathcal{V}_i})|$ by $|\Delta^{\mathcal{J}_{\mathcal{V}_i}}|^2$. By Point 4 in Lemma 6, $\Delta^{\mathcal{J}_{\mathcal{V}_i}}$ has size bounded by $p(|\mathcal{A}| + |vio_{\mathcal{V}_i}(\mathcal{I})|)$, thus by $p(|\mathcal{A}| + p_i(|\mathcal{A}|))$. Overall, the size of $vio_{\mathcal{V}_{i+1}}(\mathcal{I})$ is bounded by $p_{i+1}(|\mathcal{A}|)$ where $p_{i+1}(x) := p_i(x) + (p(x + p_i(x)))^2$ is the desired polynomial independent of $k$.

Note that this procedure is guaranteed to terminate in at most $|\mathcal{T}|$ steps, which concludes the proof.
# 5 Lower Bounds

We first refine some existing lower bounds for the fixed-cost decision problems in $\mathcal{EL}_\perp$, then prove the lower bounds for DL-Lite listed in Table 1.

## 5.1 Lower Bounds in Extensions of $\mathcal{EL}_\perp$

We begin with two lower bounds showing that even if the cost $k$ is fixed to 1, all considered reasoning tasks are NP-complete (or coNP-complete, depending on the task) already for $\mathcal{EL}_\perp$ WKBs. These results notably improve those from (BBJ 2024), where the cost was fixed to 3. Lemma 3 lifts our hardness proof to any fixed $k \ge 1$, and since the case of fixed $k = 0$ coincides with the usual semantics of $\mathcal{EL}$ KBs, the complexity w.r.t. fixed cost is now well understood.

**Theorem 3.** For every $k \ge 1$, $BCS^k$, $IQA_p^k$ and $CQA_p^k$ for $\mathcal{EL}_\perp$ are NP-hard.

*Proof sketch.* The reduction is from 3-SAT. Given a 3-CNF formula $\phi := \bigwedge_{i=1}^l \bigvee_{j=1}^3 l_{i,j}$, where each $l_{i,j}$ is a literal over $v_1, \dots, v_n$, we construct a WKB $(T, A_\phi)_\omega$. The ABox $A_\phi$ contains False(a), Bool(a), and the additional assertions:

$$ \begin{array}{l@{\quad}l@{\quad}l} \text{Var}(v_k) & \text{for } 1 \le k \le n & \text{clause}(a, c_i) \text{ for } 1 \le i \le l \\ \text{pos}_j(c_i, v_k) & \text{for } l_{i,j} = v_k & \text{neg}_j(c_i, v_k) \text{ for } l_{i,j} = \neg v_k \end{array} $$

The TBox $T$ has the following axioms:

$$ \begin{array}{l} \text{Bool} \sqsubseteq \text{True} \quad \text{True} \sqcap \text{False} \sqsubseteq \perp \quad \exists \text{clause}. \text{False} \sqsubseteq \text{True} \\ \text{Var} \sqsubseteq \exists \text{val}. \text{Bool} \quad \exists \text{val}. \text{True} \sqsubseteq \text{True} \quad \exists \text{val}. \text{False} \sqsubseteq \text{False} \end{array} $$

$$ \exists \text{pos}_1. \text{False} \sqcap \exists \text{pos}_2. \text{False} \sqcap \exists \text{pos}_3. \text{False} \sqsubseteq \text{False} $$

(the six other combinations...)

$$ \exists \text{neg}_1. \text{True} \sqcap \exists \text{neg}_2. \text{True} \sqcap \exists \text{neg}_3. \text{True} \sqsubseteq \text{False} $$

The function $\omega$ assigns $\infty$ to all axioms and assertions, except for $\text{Bool} \sqsubseteq \text{True}$, which has weight 1. One can verify that $\phi$ is satisfiable iff $(T, A_\phi)_\omega$ is 1-satisfiable. $\square$

For the case of $IQA_c^k$, we could use Lemma 2 to directly obtain a coNP-hardness proof for $k \ge 2$. We instead re-adapt the above proof to strengthen the result to every $k \ge 1$. Note that concept disjointness axioms are not even needed here.

**Theorem 4.** For every $k \ge 1$, $IQA_c^k$ and $CQA_c^k$ for $\mathcal{EL}$ are coNP-hard.

## 5.2 Lower Bounds in the DL-Lite Family

We now turn to the DL-Lite family, which inherits the upper bounds from Theorems 1 and 2. We begin with a proof that, when $k$ is allowed to vary, all considered reasoning tasks are NP-hard (resp. coNP-hard) already for DL-Lite core WKBs.

**Theorem 5.** BCS, $IQA_p$ and $CQA_p$ for DL-Lite core are NP-hard. $IQA_c$ and $CQA_c$ for DL-Lite core WKBs are coNP-hard.

Note that, by virtue of Lemmas 1 and 2, it suffices to prove that BCS for DL-Lite core is NP-hard.

*Proof sketch.* We reduce from 3-COL, that is deciding whether a given graph $G = (V, \mathcal{E})$ is 3-colourable. All axioms of $T$ are given infinite weight by $\omega$ and are as follows:

$$ \exists s_i \sqcap \exists t_j \sqsubseteq \perp \text{ for } s, t \in \{\text{r, g, b}\}, s \neq t, \text{ and } i, j \in \{1, 2\} \\ \exists s_1 \sqcap \exists s_2 \sqsubseteq \perp \text{ for } s \in \{\text{r, g, b}\} $$

We choose an orientation $\mathcal{E}'$ of $\mathcal{E}$: for each $\{u, v\} \in \mathcal{E}$, we add either $(u, v)$ or $(v, u)$ in $\mathcal{E}'$. For each $e = (u, v) \in \mathcal{E}'$ and each $s \in \{\text{r, g, b}\}$, we add $s_1(u, e)$ and $s_2(v, e)$ in the ABox $A_G$. Assertions in $A_G$ are given weight 1 by $\omega$. It can be verified that $G \in \text{3-COL}$ iff $(T, A_G)_\omega$ is $4|\mathcal{E}|$-satisfiable. $\square$

For optimal cost semantics, we establish a matching $\Delta_2^p$ lower bound. The proof adapts an existing construction from (Bourgaux 2016, Proposition 6.2.4) that establishes $\Delta_2^p$-hardness of query entailment for DL-Lite KBs under preferred repair semantics, by reduction from deciding if a given variable is true in the lexicographically maximum truth assignment satisfying a given satisfiable CNF. We point out that, unlike the other lower bounds listed in Table 1, this result crucially relies upon a binary encoding of weights, intuitively because exponentially large weights are needed to perform lexicographic comparison of satisfying valuations.

**Theorem 6.** $IQA_p^{opt}$, $IQA_c^{opt}$, $CQA_p^{opt}$, and $CQA_c^{opt}$ for DL-Lite core are $\Delta_2^p$-hard.

We now move to the case in which $k$ is fixed. Notice indeed that the lower bound from Theorem 5 strongly relies on a varying $k$. For the certain semantics, we show that coNP-hardness holds even if $k$ is fixed to 1, if we consider CQs. The proof is strongly inspired by the one of Theorem 4, especially with how to simulate the truth value assignment. The main difference is that we use acyclic CQs to circumvent the lack of nested concepts in DL-Lite core.

**Theorem 7.** For every $k \ge 1$, $CQA_c^k$ for DL-Lite core is coNP-hard. This holds already for connected acyclic BCQs and without concept disjointness axioms.

# 6 Positive Results in the DL-Lite Family

In light of the lower bounds established in the previous section, we can only hope to achieve tractability for the DL-Lite family under a fixed cost (see Theorem 5). Furthermore, under the certain semantics, we established that $CQA_c^k$ answering is coNP-hard (Theorem 7) already for DL-Lite core and $k = 1$. This leaves us with two promising settings to explore: $CQA_p^k$ and $IQA_c^k$ for DL-Lite core. This section establishes that both reasoning tasks enjoy the lowest possible complexity, that is, $AC^0$. Furthermore, we can even push this positive result to one of the most expressive logics of the DL-Lite family, namely $DL-Lite_{bool}^H$.

**Theorem 8.** For every integer $k \ge 1$, $CQA_p^k$ and $IQA_c^k$ for DL-Lite $bool$ are in $AC^0$.

Our approach is based on first-order (FO) rewriting: given the weighted TBox $T_{\omega_T}$, query $q$ and cost $k$, we construct an FO-query $q'$ such that for every weighted ABox $A_{\omega_A}$, the following, here stated for $CQA_p^k$, holds:

$$ (T, A)_{\omega_T \cup \omega_A} \models_p^k q \quad \text{iff} \quad \mathcal{I}_{A_{\omega_A}} \models q' $$

To make this formulation fully precise, we need to define the FO-interpretation $\mathcal{I}_{A_{\omega_A}}$ associated with a weighted ABox $A_{\omega_A}$, over which the rewritten query $q'$ is evaluated. We argue that $A_{\omega_A}$ can be seen as a usual ABox augmented with extra assertions about the weights. We denote by $A_k^{\omega_A}$ the
extension of $\mathcal{A}$ with special concept and role assertions that encapsulate the relevant information about weights w.r.t. the fixed cost bound $k$: if a concept assertion $\omega_{\mathcal{A}}(\mathcal{A}(a)) = n$, then we add the assertion $W_{\mathcal{A}}^n(a)$ if $n \le k$, or assertion $W_{\mathcal{A}}^{\infty}(a)$ if $n > k$. We proceed similarly for each role assertion $r(a, b)$, adding respectively $w_r^t(a, b)$ or $w_r^{\infty}(a, b)$. Notice that we only need to introduce $(k+1)(N_{\mathcal{C}}(\mathcal{A}) + N_{\mathcal{R}}(\mathcal{A}))$ fresh predicates and that computing $\mathcal{A}_k^{\omega_{\mathcal{A}}}$ from any reasonable representation of $\mathcal{A}_{\omega_{\mathcal{A}}}$ can be seen as a pre-processing step achieved by an $\mathcal{AC}^0$ transducer. As $\mathcal{A}_k^{\omega_{\mathcal{A}}}$ is a usual ABox, its corresponding interpretation $\mathcal{I}_{\mathcal{A}_{\omega_{\mathcal{A}}}}$ is well defined and can serve as the desired interpretation $\mathcal{I}_{\mathcal{A}_{\omega_{\mathcal{A}}}}$.

Before explaining how to construct $q'$, we sketch the main argument that allows for such a rewriting to exist and that ensures completeness of the claim (i.e. the $\Rightarrow$ direction in the formulation above). It relies on a (very!) small interpretation property: if an interpretation witnesses the desired behaviour w.r.t. the query and within the fixed cost, then there exists one that is completely trivial except on a small domain whose size is bounded by a constant w.r.t. the input weighted ABox. The different possibilities to interpret such a constant-size domain can thus all be encapsulated in the rewritten query $q'$. To facilitate the understanding of the rewriting, we first present this small interpretation property.

## 6.1 A (Very) Small Interpretation Property

Consider a WKB $\mathcal{K} = (\mathcal{T}, \mathcal{A})_{\omega}$, a fixed cost $k$ and a BCQ $q$. We introduce two distinct notions of types. The first is the usual one in DLs: a 1-type $t$ is a subset of $N_{\mathcal{C}}(\mathcal{T}) \cup \{\exists r \mid r \in N_{\mathcal{R}}^{\pm}(\mathcal{T})\}$. The 1-type of an element $e \in \Delta^{\mathcal{T}}$ is $tp_{\mathcal{I}}(e) := \{\mathcal{A} \mid e \in \mathcal{A}^{\mathcal{I}}\} \cup \{\exists r \mid e \in (\exists r)^{\mathcal{I}}, r \in N_{\mathcal{R}}^{\pm}\}$. This notion of 1-type captures the basic DL-Lite concepts, and thus, if two elements $d$ and $e$ have the same 1-type, then they violate exactly the same DL-Lite bool CIs.

The second notion of type is intended to capture the concepts that hold due to the ABox assertions. We define the ABox type $tp_{\mathcal{A}}(a)$ of $a \in \mathrm{Ind}(\mathcal{A})$ as:

$$tp_{\mathcal{A}}(a) := tp_{\mathcal{I}_{\mathcal{A}}}(a) \cup \{\exists^{>k} r \mid \mathcal{A} \models \exists^{>k} r, r \in N_{\mathcal{R}}^{\pm}(\mathcal{T})\},$$

where $\mathcal{A} \models \exists^{>k} r$ means that there exists (at least) $k+1$ distinct individuals $b_1, \dots, b_{k+1} \in N_1$ such that $r(a, b_1), \dots, r(a, b_{k+1}) \in \mathcal{A}$ (or $r(b_1, a), \dots, r(b_{k+1}, a) \in \mathcal{A}$ if $r$ is an inverse role). Notice that there are at most $2^{|N_{\mathcal{C}}(\mathcal{T})|+2^{|N_{\mathcal{R}}(\mathcal{T})|}}$ possible 1-types, and at most $2^{|N_{\mathcal{C}}(\mathcal{T})|+4^{|N_{\mathcal{R}}(\mathcal{T})|}}$ possible ABox types.

We write $r \sqsubseteq_{\mathcal{T}} s$ if $(r, s)$ is in the transitive closure of $\{(p, p) \mid p \in N_{\mathcal{R}}^{\pm}\} \cup \{(p, q) \in N_{\mathcal{R}}^{\pm} \times N_{\mathcal{R}}^{\pm} \mid p \sqsubseteq q \in \mathcal{T}\}$. The following observation motivates the extension of 1-types into ABox types when a fixed cost $k$ is considered:

**Lemma 7.** Consider an interpretation $\mathcal{I}$ whose cost is $\le k$. For every individual $a$ and role $r \in N_{\mathcal{R}}^{\pm}$, if $\exists^{>k} r \in tp_{\mathcal{A}}(a)$, then $\exists s \in tp_{\mathcal{I}}(a)$ for every role $s \in N_{\mathcal{R}}^{\pm}$ such that $r \sqsubseteq_{\mathcal{T}} s$.

We now prove that, if there exists an interpretation $\mathcal{I}$ whose cost is $\le k$, then we find an interpretation $\mathcal{J}$ that behaves as $\mathcal{I}$ w.r.t. the query $q$, and whose cost is also $\le k$, with all violations concentrated in a predictable portion of its domain. This portion of the domain of $\mathcal{J}$ is of course small,

since the maximum number of violations is $k$, thus involving at most $2k$ distinct elements. By 'predictable', we mean that these violations take place among a small number of special individuals (constant number with respect to $k$) that can easily be identified, and on a small set of additional domain elements. To identify these special individuals, we rely on the following intuition: if an ABox type $t$ is realized more than $2k$ times in $\mathcal{A}$, then there is a way to complete $t$ without any 'local' violation. Indeed, if it was impossible to do so, then $t$ being realized more than $2k$ times would always result in more than $k$ violations and thus in a cost exceeding $k$, contradicting the very existence of $\mathcal{I}$. Therefore, only individuals with a rare ABox type may require a special treatment to keep the cost less than $k$. Formally, we say that an ABox type $t$ is rare in $\mathcal{A}$ if $\#\{a \in \mathrm{Ind}(\mathcal{A}) \mid tp_{\mathcal{A}}(a) = t\} \le 2k$, and we use $\mathrm{RT}(\mathcal{A})$ for the set of rare ABox types in $\mathcal{A}$.

Now, when we start from an interpretation $\mathcal{I}$ with cost $\le k$ and attempt to build $\mathcal{J}$, we preserve the interpretation of concepts and roles from $\mathcal{I}$ on those special individuals that have a rare ABox type. For $\mathcal{J}$ to behave like $\mathcal{I}$ with respect to the query $q$, we also preserve the interpretation on individuals occurring in $q$. We define the pre-core $\mathrm{pc}(\mathcal{A})$ as the set of individuals from $\mathcal{A}$ that have a rare ABox type, plus those query-related individuals, that is:

$$\mathrm{pc}(\mathcal{A}) := \{a \mid tp_{\mathcal{A}}(a) \in \mathrm{RT}(\mathcal{A})\} \cup \mathrm{Ind}(q).$$

Unfortunately, the pre-core does not contain all the individuals that may be forced to participate in violations. As the following example illustrates, elements 'close' to the pre-core may also be forced to do so.

**Example 1.** Consider the fixed cost $k := 3$ and the ABox $\mathcal{A} := \{\mathcal{A}(a_0)\} \cup \bigcup_{i=0}^7 \{r(a_i, b_i), t(b_i, c_i)\}$. The ABox type of $a_0$ is rare, others are not. Consider the TBox $\mathcal{T}$ with axioms:

$$\mathcal{A} \sqsubseteq \exists u \sqcap \neg \exists s \quad \exists u \sqsubseteq \exists r \sqcap \neg \exists s \quad \exists t \sqsubseteq \exists s \quad r \sqsubseteq s$$
and assign cost 1 to all $t$ assertions, cost 2 to axiom $r \sqsubseteq s$, and infinite cost to other assertions and axioms. Every interpretation with cost $\le 3$ violates the assertion $t(b_0, c_0)$, which is somewhat surprising as both involved individuals have ABox types that can otherwise be instantiated in a way that does not violate anything. However, $b_0$ and $c_0$ happen to be 'close', i.e. at distance less than $k = 3$, to $a_0$. The rare type of $a_0$ can then impact $b_0$ and $c_0$ as seen above.

To capture those individuals that may be affected by elements from the pre-core, we essentially explore the neighbourhood of the latter. For $a, b \in \mathrm{Ind}(\mathcal{A})$, we write a $\rightsquigarrow_1 b$ if there exists a role $r \in N_{\mathcal{R}}^{\pm}$ and an assertion $r(a, b)$ in $\mathcal{A}$ and $\exists^{>k} r \notin tp_{\mathcal{A}}(a)$. When exploring neighbours, the reason we exclude roles $r$ such that $\exists^{>k} r \in tp_{\mathcal{A}}(a)$ comes from Lemma 7: it guarantees that element $a$ satisfies $\exists r$, so the potential violations on a do not impact the $r$-edges to $b$. We then denote a $\rightsquigarrow_{i+1} c$ if there exists $b$ such that a $\rightsquigarrow_i b$ and $b \rightsquigarrow_1 c$. The core of $\mathcal{A}$, denoted $\mathrm{core}(\mathcal{A})$, is now defined as:

$$\mathrm{core}(\mathcal{A}) := \mathrm{pc}(\mathcal{A}) \cup \{b \mid a \rightsquigarrow_i b, a \in \mathrm{pc}(\mathcal{A}), i \le k+1\}.$$

Notice that we stop the exploration of the neighbourhood of $\mathrm{pc}(\mathcal{A})$ at depth $k+1$. This is simply because the special behaviour of a pre-core element can only "cascade" to neighbours by enforcing a violation at each layer; thus, impacted elements cannot be further than $(k+1)$-away.
We can now state our key technical lemma. Note that Points $5_p$ and $5_c$ are used respectively to handle the possible and certain semantics. Recall that Theorem 7 established coNP-hardness for CQA<sub>c</sub><sup>k</sup>, which is why Point 5_c only concerns the case where $q$ is an IQ.

**Lemma 8.** Let $\mathcal{K} = (\mathcal{T}, \mathcal{A})_\omega$ be a WKB, $q$ a BCQ, and $k$ a fixed cost. If there exists an interpretation $\mathcal{I}$ with cost $\le k$, then there exists an interpretation $\mathcal{J}$ such that:

1. $\Delta^{\mathcal{J}} = \text{Ind}(\mathcal{A}) \cup W$ for some $W \subseteq \{w_t \mid t \text{ is a 1-type}\}$;

2. $\mathcal{J}|_{\text{pc}(\mathcal{A})} = \mathcal{I}|_{\text{pc}(\mathcal{A})}$;

3. $\omega(\mathcal{J}) = \omega(\mathcal{J}|_{\text{core}(\mathcal{A}) \cup W})$;

4. $\omega(\mathcal{J}) \le k$;

5.p. If $\mathcal{I} \models q$, then $\mathcal{J}|_{\text{core}(\mathcal{A}) \cup W} \models q$ (and thus $\mathcal{J} \models q$);

5_c. If q is an IQ and $\mathcal{I} \not\models q$, then $\mathcal{J} \not\models q$.

## 6.2 Construction of the FO-Rewriting

Consider a DL-Lite<sub>bool</sub><sup>H</sup> TBox $\mathcal{T}$, a weight function $\omega_{\mathcal{T}}$ for $\mathcal{T}$, fixed cost $k$, and BCQ $q$. We now proceed to the actual construction of the rewritten query $q'$. Notice that the pre-core always has size at most $P_0 := 2k \times 2^{|N_c(\mathcal{T})|+4|N_R(\mathcal{T})|} + |q|$ (at most $2k$ copies of each rare ABox type, plus the individuals in $q$). For each individual $a$, there exist at most $2k|N_R(\mathcal{T})|$ distinct individuals $b$ such that a $\rightsquigarrow_1$ $b$. Therefore, the size of every core, regardless of the specific ABox, is bounded by $P_0 \times (2k|N_R(\mathcal{T})|)^k$. We let $M_{\mathcal{T},q,k}$ be the above quantity plus the number of possible 1-types, that is:

$$M_{\mathcal{T},q,k} := P_0 \times (2k|N_R(\mathcal{T})|^k + 2^{|N_c(\mathcal{T})|+2|N_R(\mathcal{T})|})$$

The number $M_{\mathcal{T},q,k}$ gives an upper bound on the maximal size of the domain core($\mathcal{A}$) $\cup W$ involved in the construction of interpretation $\mathcal{J}$ in Lemma 8. Note that Points 3, $5_p$ and $5_c$ also guarantee that core($\mathcal{A}$) $\cup W$ contains all the relevant information regarding violations and query satisfaction.

The rewritten query $q'$ considers each relevant interpretation $\mathcal{M}$, up to isomorphism, whose domain $\Delta^M$ has size at most $M_{\mathcal{T},q,k}$ and tries to match the 'individual part' of $\mathcal{M}$ (that is, the core($\mathcal{A}$) part, as opposed to the $W$ part) in the input $\mathcal{A}_{\omega_A}$. The rewriting must also check that each remaining individual from $\mathcal{A}_{\omega_A}$ can be interpreted in a manner that is compatible w.r.t. the considered $\mathcal{M}$, in the sense that it shall not introduce any violations (nor satisfy the query, in the case of the certain semantics). To achieve this, we specify along with $\mathcal{M}$ its intended individual part as a subdomain $\Gamma \subseteq \Delta^M$ and the allowed ABox violations as a weighted ABox $\mathcal{V}_\nu$. We call such a triple $(\mathcal{M}, \Gamma, \mathcal{V}_\nu)$ a strategy for $(\mathcal{T}_{\omega_\Gamma}, q, k)$ if $\text{Ind}(\mathcal{V}) \subseteq \Gamma$ and $\omega_\Gamma(\mathcal{M}) + \sum_{\alpha \in \mathcal{V}} \nu(\alpha) \le k$.

We differentiate between p-strategies, used for CQA<sub>p</sub><sup>k</sup>, and c-strategies, used for IQA<sub>c</sub><sup>k</sup>. A p-strategy is a strategy $(\mathcal{M}, \Gamma, \mathcal{V}_\nu)$ that additionally satisfies $\mathcal{M} \models q$. An ABox type $t$ is p-safe for a p-strategy $\sigma = (\mathcal{M}, \Gamma, \mathcal{V}_\nu)$ if there exists a 1-type $t'$ such that:

1. for every $A \in N_c(\mathcal{T})$, if $A \in t$, then $A \in t'$;

2. for every $r \in N_R^{\pm}(\mathcal{T})$, if $\exists r \in t$, then $\exists r \in t'$;

3. $t'$ does not violate any CIs from $\mathcal{T}$;

4. for every $r \in N_R^{\pm}(\mathcal{T})$, if $\exists r \in t'$, then $\exists s \in t'$ for every $s \in N_R^{\pm}(\mathcal{T})$ with $r \subseteq_{\mathcal{T}} s$;

5. for every $r \in N_R^{\pm}(\mathcal{T})$, if $\exists r \in t'$, then there exists $d \in \Delta^M$ such that for every $s \in N_R^{\pm}(\mathcal{T})$ with $r \subseteq_{\mathcal{T}} s$, we have $\exists s^- \in \text{tp}_{\mathcal{M}}(d)$.

Recall that we need only to define c-strategies for the case where $q$ is an IQ. We may assume w.l.o.g. that $q$ is a concept IQ<fnref n="1" />. A c-strategy for $(\mathcal{T}_{\omega_\Gamma}, q, k)$ is a strategy $\sigma = (\mathcal{M}, \Gamma, \mathcal{V}_\nu)$ such that $\text{Ind}(q) \subseteq \Gamma$ and $\mathcal{M} \not\models q$, and an ABox type $t$ is c-safe for $\sigma$ if there exists a 1-type $t'$ that satisfies Conditions 1–5 of p-safe types, plus the following condition:

6. if $q = \exists y A(y)$, then $A \notin t'$.

The rewritten FO-query $q'$ is now obtained as the disjunction of subqueries $q_\sigma$, where each $\sigma$ is a p-strategy (resp. c-strategy) for $(\mathcal{T}_{\omega_\Gamma}, q, k)$. Now, for a given $\sigma := (\mathcal{M}, \Gamma, \mathcal{V}_\nu)$, the subquery $q_\sigma$ uses one existentially quantified variable $v_d$ for each $d \in \Gamma$, and attempts to identify a subpart of the input weighted ABox $\mathcal{A}_{\omega_A}$ that could be interpreted as $\mathcal{M}|_\Gamma$, up to the violations described in $\mathcal{V}_\nu$. For example, if $d \notin \mathcal{A}^M$ and $A(d) \in \mathcal{V}$, then $q_\sigma$ contains the following subquery $A(v_d) \rightarrow W_A^{\nu(\mathcal{A}(d))}(v_d)$, enforcing that variable $v_d$ can only be mapped on an individual such that $A(a) \in \mathcal{A}$ if $\omega_A$ and $\nu$ agree on the cost of the assertion $A(a)$. Using a universally quantified variable, $q_\sigma$ also makes sure that all other individuals in $\mathcal{A}$ have an ABox type that is p-safe (resp. c-safe) w.r.t. $\sigma$. It is indeed clear, examining the very local requirements defining safe types that 'having a safe p- (or c-) type' can be verified using an appropriate FO-subquery.

In this manner, we can construct FO-queries $q'_p$ and $q'_c$, respectively based on p- and c-strategies, such that the following properties hold, concluding the proof of Theorem 8:

**Lemma 9.** Let $\mathcal{T}_{\omega_\Gamma}$ be a weighted DL-Lite<sub>bool</sub><sup>H</sup> TBox, $k$ an integer, and $q$ a BCQ. For every weighted ABox $\mathcal{A}_{\omega_A}$:

$$ (\mathcal{T}, \mathcal{A})_{\omega_\Gamma \cup \omega_A} \models_p^k q \quad \text{iff} \quad \mathcal{I}_{\mathcal{A}_{\omega_A}} \models q'_p $$

Furthermore, if $q$ is an IQ, then:

$$ (\mathcal{T}, \mathcal{A})_{\omega_\Gamma \cup \omega_A} \not\models_c^k q \quad \text{iff} \quad \mathcal{I}_{\mathcal{A}_{\omega_A}} \models q'_c $$

## 7 Conclusion

Our results significantly improve our understanding of the data complexity of query entailment under recently introduced cost-based semantics. In particular, we have proved a $\Delta_2^p$ upper bound for the optimal-cost certain and possible semantics, yielding tight complexity bounds for a wide range of lightweight and expressive DLs, up to ALCHIO and covering also prominent DL-Lite dialects. Moreover, we obtained surprising tractability results, showing that fixed-cost possible semantics (for CQs) and certain semantics (for IQs) in DL-Lite<sub>bool</sub><sup>H</sup> enjoy the same low $AC^0$ complexity as classical CQ answering in DL-Lite. We expect our upper bounds can be adapted to also handle negative role inclusions (to cover also DL-Lite<sub>R</sub>). For DLs with functionality or number restrictions, it does not suffice to work with finite interpretations, so wholly different methods are required. Developing a practical implementation of the FO-rewritings for the identified tractable cases is another interesting direction.

<footnote n="1">¹IQs of the form $\exists y r(a, y)$ (resp. $\exists x y r(x, y)$) can be handled by adding infinite-weight CIs $\exists r \subseteq B, B \subseteq \exists r$ for a fresh concept name $B$, and using the IQ $B(a)$ (resp. $\exists x.B(x)$) instead.</footnote>
Acknowledgments

The authors acknowledge the financial support of the ANR AI Chair INTENDED (ANR-19-CHIA-0014) and the Federal Ministry of Research, Technology and Space of Germany and by Sächsische Staatsministerium für Wissenschaft, Kultur und Tourismus in the programme Center of Excellence for AI-research “Center for Scalable Data Analytics and Artificial Intelligence Dresden/Leipzig”, project identification number: ScaDS.AI.

References

Baader, F.; Horrocks, I.; Lutz, C.; and Sattler, U. 2017. *An Introduction to Description Logic*. Cambridge University Press.

Bienvenu, M. 2020. A Short Survey on Inconsistency Handling in Ontology-Mediated Query Answering. *Künstliche Intell.*, 34(4): 443–451.

Bienvenu, M.; and Bourgaux, C. 2016. Inconsistency-Tolerant Querying of Description Logic Knowledge Bases. In *Reasoning Web Tutorial Lectures*.

Bienvenu, M.; Bourgaux, C.; and Jean, R. 2024. Cost-Based Semantics for Querying Inconsistent Weighted Knowledge Bases. In *Proceedings of KR*.

Bienvenu, M.; and Ortiz, M. 2015. Ontology-Mediated Query Answering with Data-Tractable Description Logics. In *Reasoning Web Tutorial Lectures*.

Bonatti, P. A.; Lutz, C.; and Wolter, F. 2009. The Complexity of Circumscription in DLs. *J. Artif. Intell. Res.*, 35: 717–773.

Bourgaux, C. 2016. *Inconsistency handling in ontology-mediated query answering*. (Gestion des incohérences pour l'accès aux données en présence d'ontologies). Ph.D. thesis, University of Paris-Saclay, France.

Britz, K.; Casini, G.; Meyer, T.; Moodley, K.; Sattler, U.; and Varzinczak, I. 2021. Principles of KLM-style Defeasible Description Logics. *ACM Trans. Comput. Log.*, 22(1): 1:1–1:46.

Calvanese, D.; De Giacomo, G.; Lembo, D.; Lenzerini, M.; and Rosati, R. 2007. Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-Lite Family. *Journal of Automated Reasoning (JAR)*.

Eiter, T.; Lukasiewicz, T.; and Predoiu, L. 2016. Generalized Consistent Query Answering under Existential Rules. In *Proceedings of KR*.

Giordano, L.; Gliozzi, V.; Olivetti, N.; and Pozzato, G. L. 2013. A non-monotonic Description Logic for reasoning about typicality. *Artif. Intell.*, 195: 165–202.

Lembo, D.; Lenzerini, M.; Rosati, R.; Ruzzi, M.; and Savo, D. F. 2010. Inconsistency-Tolerant Semantics for Description Logics. In *Proceedings of RR*.

Lutz, C.; and Manière, Q. 2024. Adding Circumscription to Decidable Fragments of First-Order Logic: A Complexity Rollercoaster. In *Proceedings of KR*, 531–541.

Manière, Q. 2022. *Counting queries in ontology-based data access*. (Requêtes de comptage pour l'accès aux données en présence d'ontologies). Ph.D. thesis, University of Bordeaux, France.

Poggi, A.; Lembo, D.; Calvanese, D.; De Giacomo, G.; Lenzerini, M.; and Rosati, R. 2008. Linking Data to Ontologies. *Journal of Data Semantics*, 10: 133–173.

Xiao, G.; Calvanese, D.; Kontchakov, R.; Lembo, D.; Poggi, A.; Rosati, R.; and Zakharyaschev, M. 2018. Ontology-Based Data Access: A Survey. In *Proceedings of IJCAI*.