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

HAL
open science

# Queries With Exact Truth Values on Concept and Role Atoms in Paraconsistent Description Logics

Meghyn Bienvenu, Camille Bourgaux, Daniil Kozhemiachenko

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

## To cite this version:

Meghyn Bienvenu, Camille Bourgaux, Daniil Kozhemiachenko. Queries With Exact Truth Values on Concept and Role Atoms in Paraconsistent Description Logics. Journal of Artificial Intelligence Research, 2026, 85, 10.1613/jair.1.18676. hal-05527427

HAL Id: hal-05527427

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

Submitted on 25 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished 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_3.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Queries With Exact Truth Values on Concept and Role Atoms in Paraconsistent Description Logics

MEGHYN BIENVENU, Université de Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, France

CAMILLE BOURGAUX, DI ENS, ENS, CNRS, PSL University & Inria, France

DANIIL KOZHEMIACHENKO*, Aix-Marseille Univ, CNRS, LIS, France and Université de Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, France

We present a novel approach to querying classically inconsistent description logic (DL) knowledge bases by adopting a paraconsistent semantics with the four 'Belnapian' values: *exactly true* (T), *exactly false* (F), *both* (B), and *neither* (N). In contrast to prior studies on paraconsistent DLs, we allow truth value operators in the query language over concept and role atoms, which can be used to differentiate between answers obtained from contradictory evidence and those based upon only positive evidence. We present a reduction to classical DL query answering that allows us to pinpoint the precise combined and data complexity of answering queries with values in paraconsistent *ALCHI* with two- and four-valued roles and their sublogics. Notably, we show that tractable data complexity is retained for Horn DLs. We also present a comparison with repair-based inconsistency-tolerant semantics, showing that the two approaches are incomparable: if we consider queries with the T (exactly true) operator, then we neither over-approximate the most cautious repair-based semantics, nor under-approximate the least cautious ones.

**JAIR Associate Editor:** Fabrizio Riguzzi

**JAIR Reference Format:**

Meghyn Bienvenu, Camille Bourgaux, and Daniil Kozhemiachenko. 2026. Queries With Exact Truth Values on Concept and Role Atoms in Paraconsistent Description Logics. *Journal of Artificial Intelligence Research* 85, Article 19 (February 2026), 32 pages. doi: 10.1613/jair.1.18676

## 1 Introduction

Ontology-mediated query answering (OMQA) has been extensively studied over the past fifteen years as a promising paradigm for querying incomplete and heterogeneous data (Bienvenu and Ortiz 2015; Poggi et al. 2008; Xiao et al. 2018). In a nutshell, OMQA enriches the data with an ontology that provides both a convenient vocabulary for query formulation and domain knowledge that is exploited when answering queries. Ontologies are typically formulated in logic-based languages (description logics, DLs, being a popular choice) and equipped with a first-order logic semantics, whereby a Boolean ('yes or no') query is deemed to hold whenever it is entailed from the logical theory consisting of the data and ontology. An important practical concern with (traditional) OMQA is its lack of robustness in the presence of contradictory information, as every Boolean query is entailed from an inconsistent knowledge base.

Authors' Contact Information: Meghyn Bienvenu, ORCID: 0000-0001-6229-8103, meghyn.bienvenu@u-bordeaux.fr, Université de Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, Talence, France; Camille Bourgaux, ORCID: 0000-0002-8806-6682, camille.bourgaux@ens.fr, DI ENS, ENS, CNRS, PSL University & Inria, Paris, France; Daniil Kozhemiachenko, ORCID: 0000-0002-1533-8034, daniil.kozhemiachenko@lis-lab.fr, Aix-Marseille Univ, CNRS, LIS, Marseille, France and Université de Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, Talence, France.

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

This work is licensed under a Creative Commons Attribution International 4.0 License.

© 2026 Copyright held by the owner/author(s).

DOI: 10.1613/jair.1.18676

<footnote>*Corresponding Author.</footnote>
A prominent approach to tackling data inconsistencies in OMQA is to adopt inconsistency-tolerant semantics based upon repairs, defined as inclusion-maximal subsets of the data that are consistent with the ontology. Arguably the most natural repair-based semantics is the AR semantics (Lembo et al. 2010) that considers those answers that hold w.r.t. each repair, inspired by analogous semantics for inconsistent databases (Arenas et al. 1999). Other commonly considered repair semantics include the more permissive *brave* semantics (Bienvenu and Rosati 2013), which only requires an answer to hold in at least one repair, and the more cautious IAR semantics (Lembo et al. 2010), which queries the intersection of all repairs. Several other repair-based semantics, incorporating closure operations or various kinds of preferences, have been explored (cf. the surveys by Bienvenu (2020) and Bienvenu and Bourgaux (2016) for an overview of repair-based semantics for DL knowledge bases).

Paraconsistent logics represent another natural approach to obtaining meaningful answers from contradictory knowledge bases. Whereas repair-based semantics are defined in terms of the consistent subsets of the inconsistent theory, paraconsistent logic semantics, often based upon extended sets of truth values, make it possible for classically inconsistent theories to possess models. A common approach is to augment the classical set of truth values {T, F} with two additional elements — B (both true and false) and N (neither true nor false).<fnref n="1" /> The four values can be interpreted as four kinds of information one can have on a given assertion A(a): only be told that A(a) is true, only be told that A(a) is false, be told that A(a) is both true and false, and be told nothing about A(a).² The truth and falsity conditions of Boolean connectives ¬, ∨, and ∧ are then defined as follows:

* $\neg A(a)$ is true if $A(a)$ is false and vice versa;

* $[A \sqcap B](a)$ is true if $A(a)$ and $B(a)$ are true, and false if $A(a)$ or $B(a)$ is false;

* $[A \sqcup B](a)$ is true if $A(a)$ or $B(a)$ is true, and false if $A(a)$ and $B(a)$ are false.

Paraconsistent DLs were first introduced by Odintsov and Wansing (2003) and have since then been extensively studied. In particular, four-valued counterparts of expressive description logics such as *SHOIN(D)* and *SROIQ* were considered (Ma and Hitzler 2009; Ma, Lin, et al. 2006; Maier 2010; Maier et al. 2013). Moreover, DLs with non-standard propositional connectives (i.e., whose semantics differ from the one by Belnap (1977a,b) and Dunn (1976)) were studied by Zhang, Xiao, et al. (2014). Most work on paraconsistent DLs has focused on standard reasoning tasks, namely, axiom entailment and consistency checking. Paraconsistent OMQA has received comparatively less attention and, to the best of our knowledge, has only been considered by Nguyen and Szałas (2012) and Zhou et al. (2012). Moreover, the query language they use has an unfortunate drawback: given a knowledge base *K* and a concept A, it is impossible to write a query *q* whose set of answers only contains individuals *a* for which *A(a)* is *exactly true* (i.e., has value T). Indeed, we observe (Proposition 3.2) that for Horn DLs, existing approaches to paraconsistent query answering correspond to simply ignoring negative axioms and thus fail to benefit from the four-valued semantics.

*Contributions.* Our first main contribution is thus to introduce a new query language for paraconsistent DLs that extends the query language of Zhou et al. (2012) with value operators, enabling us to differentiate between *at least true* and *exactly true* answers to queries. We explore the computational properties of answering such queries and show, using a translation to classical OMQA, that both the data and combined complexity of paraconsistent query answering in Horn description logic ontologies is the same as that of certain answers under the classical OMQA semantics. For expressive DLs, paraconsistent query answering has the same combined complexity as classical OMQA but in some cases has a slightly higher data complexity. Overall, our results show that our paraconsistent query language is more computationally well-behaved than repair-based semantics (cf. Tables 1, 2, 3).

This brings us to our second contribution: a comparison of paraconsistent and repair-based OMQA semantics. Indeed, while the two approaches share similar motivations, to the best of our knowledge, the relationship

<footnote n="1">¹Some work considers only {T, B, F} (Zhang, Lin, and Wang 2010) or adds other truth values (Kaminski et al. 2015).
²The interpretation is due to Belnap (1977a,b) and Dunn (1976), whence the values T, B, N, and F are sometimes called 'Belnapian'.</footnote>
between them has not been explored. We present results showing that the two approaches are incomparable. More precisely, we show that if we consider queries with the T (exactly true) operator (which being more restrictive are better suited to approximating repair-based semantics), then we neither over-approximate IAR, i.e., we miss some of the 'surest' answers according to repair-based semantics, nor under-approximate brave and CAR (a variant of AR based on closed repairs), meaning that some answers are not retained even under the most permissive repair-based semantics. This incompatibility result is generally phrased so as to apply to other paraconsistent DL semantics verifying some basic properties.

An additional contribution is a comparison of several paraconsistent semantics for DLs. Indeed, in the case where not only concept assertions but also role assertions can take four values, different proposals have been made in the literature on how to interpret existential and universal role restrictions, and there has been little discussion of the properties of these semantics. Hence, to justify the semantics for four-valued roles that we adopt in this work, we compare existing semantics according to a couple of desirable properties.

This paper is an extended version of an earlier conference paper (Bienvenu, Bourgaux, and Kozhemiachenko 2024). The novel contribution compared to the conference paper is the study of queries with truth values in paraconsistent description logics with four-valued roles (Section 6). We also include the proofs that were omitted from the conference paper.

*Plan of the Paper.* Our paper is structured as follows. In Section 2, we define the syntax and semantics of a four-valued version of *ALCHI* where the four truth values apply to concept assertions but not to role assertions, in line with a large part of prior work on paraconsistent DL. Sections 3 and 4 are dedicated to syntax and semantics of the queries incorporating Belnapian values and an analysis of their computational properties. In Section 5, we formally compare paraconsistent and repair-based semantics and present a general incompatibility result. In Section 6, we expand our results to paraconsistent DLs with four-valued roles, i.e., where role assertions are also evaluated using the four Belnapian values. Finally, we conclude in Section 7 with a short discussion of future work.

## 2 Four-Valued *ALCHI* and Its Fragments

In this section, we provide the syntax and semantics of four-valued DLs, equipped with a new constructor Δ that was previously added to Belnap-Dunn propositional logic and its first-order expansion by Sano and Omori (2014), and which can be intuitively interpreted as follows: ΔA(a) means that A(a) is true and ¬ΔA(a) that A(a) is not true (as opposed to ¬A(a) which means that A(a) is false). As we will see in Sections 2.2 and 2.3, Δ will also allow for more convenient formulations of different types of inclusion and disjointness axioms.

### 2.1 Syntax

A DL language $\mathcal{L}$ is defined via grammar rules using three mutually disjoint countable sets of concept, role, and individual names, denoted by CN, RN and IN, respectively. We also let RN$^{±}$ = RN ∪ {R$^{-}$ | R ∈ RN} be the set of roles and inverse roles. Given a DL language $\mathcal{L}$, an $\mathcal{L}_{\Delta}^{4}$ knowledge base (KB) $\mathcal{K}$ = ⟨T, A⟩ consists of a finite set A of concept and role assertions of the form A(a) and R(a, b) respectively, with a, b ∈ IN, A ∈ CN, and R ∈ RN, called the ABox, and a finite set T of axioms whose form depends on the DL $\mathcal{L}$, called the TBox. An $\mathcal{ALCHI}_{\Delta}^{4}$ TBox contains role inclusions of the form S ⊑ S' where S, S' ∈ RN$^{±}$ and concept inclusions of the form C ⊑ D where C and D are $\mathcal{ALCHI}_{\Delta}^{4}$ concepts built using the following grammar:

$$C := T \mid \bot \mid A \mid \neg C \mid \Delta C \mid C \sqcap C \mid C \sqcup C \mid \exists S.C \mid \forall S.C$$

with A ∈ CN and S ∈ RN$^{±}$. We also write C ≡ D as a shorthand for {C ⊑ D, D ⊑ C}. We sometimes use • and ◦ to denote binary connectives from {∩, ∪} and Q and $\overline{Q}$ for quantifiers from {∃, ∀}, assuming that • ≠ ◦ and Q ≠ $\overline{Q}$.
An *L* KB is defined as an *L*<sub>Δ</sub><sup>4</sup> KB except that it cannot contain Δ. Besides *ALCHI*, we will consider the following DL languages which are sub-languages of *ALCHI*: *ALCH* has no inverse roles, *ALCI* has no role inclusions, *ALC* has neither, *ELHI*<sub>⊥</sub> does not allow ⊔, ∀ and ¬, and *ELH*<sub>⊥</sub>, *ELI*<sub>⊥</sub> and *EL*<sub>⊥</sub> are obtained from *ELHI*<sub>⊥</sub> by disallowing inverse roles, role inclusions, and both respectively. Finally DL-Lite<sub>core</sub> TBoxes contain concept inclusions of the form B<sub>1</sub> ⊑ B<sub>2</sub> or B<sub>1</sub> ⊑ ¬B<sub>2</sub> with B := A | ∃S.⊥. The logic *ELHI*<sub>⊥</sub> and its sub-logics are *Horn DLs* (note that we consider DL-Lite<sub>core</sub> to be a sub-logic of *ELHI*<sub>⊥</sub>, since under the classical, two-valued semantics, concept inclusions of the form B<sub>1</sub> ⊑ ¬B<sub>2</sub> can be equivalently written B<sub>1</sub> ⊓ B<sub>2</sub> ⊑ ⊥). We use the term *propositional TBoxes* to refer to TBoxes that do not use the ∃ and ∀ constructors.

## 2.2 Semantics

The semantics of *L*<sub>Δ</sub><sup>4</sup> is defined through interpretations, which differ from classical DL interpretations in that they define both *positive* and *negative extensions* of concepts. A 4-interpretation is a tuple *I* = ⟨Δ<sup>*I*</sup>, .<sup>*I*</sup><sub>*p*</sub>, .<sup>*I*</sup><sub>*n*</sub>⟩ with a domain Δ<sup>*I*</sup> ≠ ∅, and two interpretation functions .<sup>*I*</sup><sub>*p*</sub> and .<sup>*I*</sup><sub>*n*</sub> that map each concept name A ∈ CN to A<sup>*I*</sup><sub>*p*</sub> ⊑ Δ<sup>*I*</sup> and A<sup>*I*</sup><sub>*n*</sub> ⊑ Δ<sup>*I*</sup> respectively, each role name R ∈ RN to R<sup>*I*</sup><sub>*p*</sub> = R<sup>*I*</sup><sub>*n*</sub> ⊑ Δ<sup>*I*</sup> × Δ<sup>*I*</sup> and each individual name a ∈ IN to a<sup>*I*</sup><sub>*p*</sub> = a<sup>*I*</sup><sub>*n*</sub> ∈ Δ<sup>*I*</sup>. For role and individual names interpretations, we can thus omit p and n and simply write R<sup>*I*</sup> and a<sup>*I*</sup>. The interpretation functions .<sup>*I*</sup><sub>*p*</sub> and .<sup>*I*</sup><sub>*n*</sub> are extended to complex *ALCHI*<sub>Δ</sub><sup>4</sup> concepts and roles as follows:

$$(R^-,)^I = \{(y, x) | (x, y) \in R^I\} \qquad (1)$$

$$\top^{I_n} = \emptyset$$

$$(\neg C)^{I_p} = C^{I_n} \qquad (\neg C)^{I_n} = C^{I_p}$$

$$(\Delta C)^{I_p} = C^{I_p} \qquad (\Delta C)^{I_n} = \Delta^I \setminus C^{I_p}$$

$$(C \sqcap D)^{I_p} = C^{I_p} \sqcap D^{I_p} \qquad (C \sqcap D)^{I_n} = C^{I_n} \sqcup D^{I_n}$$

$$(\forall S.C)^{I_p} = \{x \mid \forall y : (x, y) \in S^I \Rightarrow y \in C^{I_p}\} \qquad (\forall S.C)^{I_n} = \{x \mid \exists y : (x, y) \in S^I \& y \in C^{I_n}\}$$

The semantics of the remaining connectives is given by:

$$C \sqcup D := \neg(\neg C \sqcap \neg D) \qquad \exists S.C := \neg\forall S.\neg C \qquad \perp := \neg T$$

which yield, as expected, ⊥<sup>*I*</sup><sub>*p*</sub> = ∅, ⊤<sup>*I*</sup><sub>*n*</sub> = Δ<sup>*I*</sup>, (C ⊔ D)<sup>*I*</sup><sub>*p*</sub> = C<sup>*I*</sup><sub>*p*</sub> ∪ D<sup>*I*</sup><sub>*p*</sub>, (C ⊔ D)<sup>*I*</sup><sub>*n*</sub> = C<sup>*I*</sup><sub>*n*</sub> ∩ D<sup>*I*</sup><sub>*n*</sub>, and

$$(\exists S.C)^{I_p} = \{x \mid \exists y : (x, y) \in S^I \& y \in C^{I_p}\} \qquad (\exists S.C)^{I_n} = \{x \mid \forall y : (x, y) \in S^I \Rightarrow y \in C^{I_n}\}.$$

Given a 4-interpretation *I* = ⟨Δ<sup>*I*</sup>, .<sup>*I*</sup><sub>*p*</sub>, .<sup>*I*</sup><sub>*n*</sub>⟩, *a* ∈ IN and a concept C, we will say that

* C(a) is exactly true in *I* if a<sup>*I*</sup> ∈ C<sup>*I*</sup><sub>*p*</sub> \ C<sup>*I*</sup><sub>*n*</sub>;

* C(a) is both true and false in *I* if a<sup>*I*</sup> ∈ C<sup>*I*</sup><sub>*p*</sub> ∩ C<sup>*I*</sup><sub>*n*</sub>;

* C(a) is neither true nor false in *I* if a<sup>*I*</sup> ∉ C<sup>*I*</sup><sub>*p*</sub> ∪ C<sup>*I*</sup><sub>*n*</sub>;

* C(a) is exactly false in *I* if a<sup>*I*</sup> ∈ C<sup>*I*</sup><sub>*n*</sub> \ C<sup>*I*</sup><sub>*p*</sub>.

A 4-interpretation *I* = ⟨Δ<sup>*I*</sup>, .<sup>*I*</sup><sub>*p*</sub>, .<sup>*I*</sup><sub>*n*</sub>⟩ satisfies an assertion A(a) (resp. R(a, b)), if a<sup>*I*</sup> ∈ A<sup>*I*</sup><sub>*p*</sub> (resp. (a<sup>*I*</sup>, b<sup>*I*</sup>) ∈ R<sup>*I*</sup>). It satisfies a role inclusion S ⊑ S' if S<sup>*I*</sup> ⊑ S'<sup>*I*</sup>, and it satisfies a concept inclusion C ⊑ D if C<sup>*I*</sup><sub>*p*</sub> ⊑ D<sup>*I*</sup><sub>*p*</sub>. We write *I* |=<sub>4</sub> φ to indicate that *I* satisfies an assertion or an axiom φ. A 4-interpretation *I* is a 4-model of a KB K = ⟨T, A⟩, denoted *I* |=<sub>4</sub> K, if *I* |=<sub>4</sub> φ for every φ ∈ T ∪ A. Finally, we say that K 4-entails an assertion or inclusion φ, denoted K |=<sub>4</sub> φ, if *I* |=<sub>4</sub> φ for every 4-model *I* of K.

The semantics of the classical DL *ALCHI* is defined using interpretations with a single interpretation function *I* = ⟨Δ<sup>*I*</sup>, .<sup>*I*</sup><sub>*p*</sub>⟩ where .<sup>*I*</sup><sub>*p*</sub> behaves as the positive interpretation function .<sup>*I*</sup><sub>*p*</sub> except that (¬C)<sup>*I*</sup> = Δ<sup>*I*</sup> \ C<sup>*I*</sup> (i.e., the negation is defined classically instead of being paraconsistent). We use *I* |=<sub>*K*</sub> to denote that *I* is a (classical) model of *K*, and *K* |=<sub>*φ*</sub> to denote that *K* (classically) entails *φ*.
Note that four-valued paraconsistent DLs are sometimes defined with *four-valued roles*, i.e., possibly $R^{I_p} \neq R^{I_n}$ (cf. (Kamide 2013; Maier et al. 2013; Zhang, Xiao, et al. 2014) for possible approaches). To facilitate the presentation, we first provide our results for *two-valued roles*. Then, in Section 6, we discuss alternative interpretations of four-valued roles and show how to transfer our results into that setting.

**Example 2.1.** Assume that a university created the following knowledge base $\mathcal{K}_U = \langle \mathcal{T}_U, A_U \rangle$.

$$ \mathcal{T}_U = \{ \text{Prf} \equiv \text{Full} \sqcup \text{Asc}, \exists \text{headof.Chair} \sqsubseteq \text{Full}, \text{Prf} \sqsubseteq \neg \text{Course}, \text{Full} \sqsubseteq \neg \text{Asc} \} $$

$$ \mathcal{A}_U = \{ \text{headof}(\text{ann}, \text{AI}), \text{Chair}(\text{AI}), \text{Asc}(\text{ann}) \} $$

The TBox expresses that there are two kinds of professors (Prf), full and associate professors (Full, Asc), that heads of chairs are full professors, that professors are not courses, and full professors not associate professors. The ABox states that Ann is an associate professor and head of the AI chair.

If $\mathcal{K}_U$ is interpreted as a *classical* ($\mathcal{A}LCHI$) KB, $\mathcal{K}_U$ is *inconsistent*: there is no classical model of $\mathcal{K}_U$ since Ann cannot be a full professor and an associate professor at the same time. Hence, everything is entailed from $\mathcal{K}_U$, for example $\mathcal{K}_U \models \text{Course}(\text{ann})$. If $\mathcal{K}_U$ is interpreted as a *paraconsistent* ($\mathcal{A}LCHI_\Delta^4$) KB, however, there are 4-models of $\mathcal{K}_U$ since $\text{ann}^I$ can belong to $\text{Asc}^{I_p}$ and $\text{Asc}^{I_n}$. Actually, this is the case in every 4-model, i.e., $\mathcal{K}_U \models_4 \text{Asc}(\text{ann})$ and $\mathcal{K}_U \models_4 \neg \text{Asc}(\text{ann})$. Using 4-interpretations allows us to obtain more meaningful answers from a classically inconsistent KB (for example, $\mathcal{K}_U \not\models_4 \text{Course}(\text{ann})$).

In the classical setting, $\text{Full} \sqsubseteq \neg \text{Asc}$ and $\text{Full} \sqcap \text{Asc} \sqsubseteq \perp$ are equivalent. However, this is not the case in the paraconsistent setting: if we replace the former by the latter in $\mathcal{T}_U$, then $\mathcal{K}_U$ has no 4-models. It is thus important to carefully write the TBox axioms to reflect the intended meaning. In particular, we can define axioms of different strengths. For example, it may be reasonable to assume that courses and professors should be truly disjoint while one can permit contradictions in concepts governing different kinds of professors (e.g., in the situation above, Ann has been recently appointed the head of the AI chair but her promotion to full professor has not been finalised, so the fact that she is both an associate and full professor only indicates a minor anomaly in $\mathcal{K}_U$). In this case, however, it is reasonable to add *contrapositives* of axioms with negations (i.e., $\text{Asc} \sqsubseteq \neg \text{Full}$). This will exclude 4-interpretations in which $\text{Full}(a)$ is *exactly true* and $\text{Asc}(a)$ is *both true and false*.

Besides replacing $\text{Prf} \sqsubseteq \neg \text{Course}$ by $\text{Course} \sqcap \text{Prf} \sqsubseteq \perp$, one can enforce disjointness between Prf and Course in several ways using our new $\Delta$ operator. First, with $\text{Prf} \sqsubseteq \neg \Delta \text{Course}$. Second, one can stipulate that Prf and Course *behave classically*. $\Delta$ allows for the following compact representation of this requirement: $\neg \text{Prf} \equiv \neg \Delta \text{Prf}$ (an alternative representation is $\top \sqsubseteq \text{Prf} \sqcup \neg \text{Prf}$ and $\text{Prf} \sqcap \neg \text{Prf} \sqsubseteq \perp$). It is important to note that classicality is stronger than disjointness because the latter permits the existence of some $a$ such that $\text{Prf}(a)$ is both true and false or neither true nor false in a 4-interpretation while the former does not.

## 2.3 Capturing Different Inclusion Semantics With $\Delta$

We recall different interpretations of $\sqsubseteq$ from the literature.

**Definition 2.2 (Alternative inclusions).** Let $\mathcal{I} = \langle \Delta^I, \cdot^{I_p}, \cdot^{I_n} \rangle$ be a 4-interpretation and C, D be two concepts.

* C is *internally included* in D ($\mathcal{I} \models_4 C \sqsubseteq D$) iff $C^{I_p} \subseteq D^{I_p}$.

* C is *materially included* in D ($\mathcal{I} \models_4 C \sqsubseteq^m D$) iff $\Delta^I \setminus C^{I_n} \subseteq D^{I_p}$.

* C is *strongly included* in D ($\mathcal{I} \models_4 C \sqsubseteq^\pm D$) iff $C^{I_p} \subseteq D^{I_p}$ and $D^{I_n} \subseteq C^{I_n}$.

* C is *quasi-classically included* in D ($\mathcal{I} \models_4 C \sqsubseteq^{qc} D$) iff C is internally, strongly, and materially included in D. We also use $C \equiv^x D$ as a shorthand for $\{C \sqsubseteq^x D, D \sqsubseteq^x C\}$ with $x \in \{\pm, m, qc\}$.

Internal, material, and strong inclusions were presented by Ma, Hitzler, and Lin (2007) and correspond to three eponymous four-valued implications by Arieli and Avron (1996, 1998). The quasi-classical inclusion proposed
by Zhang, Xiao, et al. (2014) combines all three notions. We have chosen to work with internal inclusion, but will show how △ allows us to reduce the other interpretations of ⊑ to this one.

**PROPOSITION 2.3.** For every pair of $\mathcal{A}LCHI_{\Delta}^4$ concepts (C, D) and $x \in \{\text{m}, \pm, \text{qc}\}$, there is an $\mathcal{A}LCHI_{\Delta}^4$ concept inclusion $\phi_x$ such that for every 4-interpretation $I$, it holds that

$$I \models_4 C \sqsubseteq^x D \text{ iff } I \models_4 \phi_x.$$

**PROOF.** For material inclusion, $I \models_4 C \sqsubseteq^m D$ iff $I \models_4 T \sqsubseteq \neg C \sqcup D$. For strong inclusion, it is immediate that $I \models_4 C \sqsubseteq^\pm D$ iff $I \models_4 C \sqsubseteq D$ and $I \models_4 \neg D \sqsubseteq \neg C$, whence,

$$I \models_4 C \sqsubseteq^\pm D \text{ iff } I \models_4 T \sqsubseteq (\neg \Delta C \sqcup D) \sqcap (\neg C \sqcup \neg \Delta \neg D).$$

Finally, $I \models_4 C \sqsubseteq^{qc} D$ iff $I \models_4 C \sqsubseteq^m D$ and $I \models_4 C \sqsubseteq^\pm D$, so $I \models_4 C \sqsubseteq^{qc} D$ is equivalent to

$$I \models_4 T \sqsubseteq (\neg C \sqcup D) \sqcap (\neg \Delta C \sqcup D) \sqcap (\neg C \sqcup \neg \Delta \neg D).$$

□

The preceding proof shows how △ allows us to succinctly capture different forms of inclusions *without the need to introduce additional concept names* (which would complicate later technical constructions, hence the interest in employing △). Indeed, while △ can be simulated, this requires us to add new concept names: $\neg \Delta C$ can be expressed with a fresh C' such that $C \sqcap C' \sqsubseteq \perp$ and $T \sqsubseteq C \sqcup C'$ and $\neg \Delta \neg D$ can be replaced by $D''$ such that $\neg D \sqcap D'' \sqsubseteq \perp$ and $T \sqsubseteq \neg D \sqcup D''$.

## 2.4 Negation Normal Form (NNF)

$\mathcal{A}LCHI_{\Delta}^4$ knowledge bases can be put into negation normal form (NNF) in polynomial time. We will focus on KBs in NNF to establish the complexity of reasoning when translating four-valued KBs to classical KBs (note that Maier et al. (2013) perform this transformation of the KB into NNF while translating it). The difference between our work and that by Maier et al. (2013) is the use of the △ constructor.

**Definition 2.4.** We say that an $\mathcal{A}LCHI_{\Delta}^4$ concept C is in *negation normal form (NNF)* if C is built from concepts A, $\neg A$, $\Delta A$, $\neg \Delta A$, $\neg \Delta \neg A$, and $\neg \Delta \neg \Delta A$ ($A \in \text{CN}$) using binary connectives and quantifiers.

**PROPOSITION 2.5.** Let $\mathcal{T}$ be an $\mathcal{A}LCHI_{\Delta}^4$ TBox. There exists a TBox NNF($\mathcal{T}$) such that all concepts occurring in it are in NNF and $I \models_4 \mathcal{T}$ iff $I \models_4 \text{NNF}(\mathcal{T})$ for any 4-interpretation $I$.

**PROOF.** We define NNF($\mathcal{T}$) as follows: all role inclusions remain as in $\mathcal{T}$; for each concept inclusion $C \sqsubseteq D$, we apply the following transformations to C and D.

$$\neg T \rightsquigarrow \perp \qquad \neg T \rightsquigarrow T$$

$$\neg \neg C \rightsquigarrow C \qquad \neg (C \circ D) \rightsquigarrow \neg C \circ \neg D$$

$$\neg Q_S.C \rightsquigarrow \overline{Q_S}.\neg C \qquad \Delta \Delta C \rightsquigarrow \Delta C$$

$$\Delta(C \circ D) \rightsquigarrow \Delta C \circ \Delta D \qquad \Delta Q_S.C \rightsquigarrow Q_S.\Delta C$$

$$\Delta \neg \Delta C \rightsquigarrow \neg \Delta C$$

It can be verified using (1) that the transformations preserve the concept interpretations, which yields the result. □

## 2.5 Reductions Between $\mathcal{A}LCHI_{\Delta}^4$ and $\mathcal{A}LCHI$

We show that $\mathcal{A}LCHI_{\Delta}^4$ and $\mathcal{A}LCHI$ are equally expressive. Using Proposition 2.5, we can construct an embedding of 4-valued knowledge bases into the classical ones. The embedding follows the idea of Ma, Hitzler, and Lin (2007): we encode positive and negative interpretations separately. The only difference in our case is that we need to account for △.
Definition 2.6 (Classical counterparts). Let $\mathcal{K} = \langle \mathcal{T}, \mathcal{A} \rangle$ be an $\mathcal{A}\mathcal{L}\mathcal{C}\mathcal{H}\mathcal{I}_{\Delta}^4$ KB with $\mathcal{T}$ in NNF. We define its classical counterpart $\mathcal{K}^{\text{cl}} = \{\phi^{\text{cl}} | \phi \in \mathcal{K}\}$ as follows:

$$ (C \sqsubseteq D)^{\text{cl}} = C^{\text{cl}} \sqsubseteq D^{\text{cl}} $$

$$ (A(a))^{\text{cl}} = A^{\text{cl}}(a) $$

$$ (S \sqsubseteq S')^{\text{cl}} = S \sqsubseteq S' $$

$$ (R(a, b))^{\text{cl}} = R(a, b) $$

where C, D are $\mathcal{A}\mathcal{L}\mathcal{C}\mathcal{H}\mathcal{I}_{\Delta}^4$ concepts, S, S' ∈ RN$^{\pm}$, A ∈ CN, R ∈ RN. For C in NNF, C$^{cl}$ is defined as follows:

$$ A^{\text{cl}} = A^{+} $$

$$ (\neg A)^{\text{cl}} = A^{-} $$

$$ (\Delta A)^{\text{cl}} = A^{+} $$

$$ (\neg \Delta A)^{\text{cl}} = \neg A^{+} $$

$$ (\Delta \neg A)^{\text{cl}} = A^{-} $$

$$ (\neg \Delta \neg A)^{\text{cl}} = \neg A^{-} $$

$$ (C \circ D)^{\text{cl}} = C^{\text{cl}} \circ D^{\text{cl}} $$

$$ (QS.C)^{\text{cl}} = QS.C^{\text{cl}} $$

Let $\mathcal{I} = \langle \Delta^{\mathcal{I}}, \cdot_{\mathcal{I}_p}, \cdot_{\mathcal{I}_n} \rangle$ be a 4-valued interpretation. The classical counterpart $\mathcal{I}^{\text{cl}} = \langle \Delta^{\mathcal{I}^{\text{cl}}}, \cdot_{\mathcal{I}^{\text{cl}}} \rangle$ of $\mathcal{I}$ is as follows:

$$ \Delta^{\mathcal{I}^{\text{cl}}} = \Delta^{\mathcal{I}} $$

(3)

$$ a^{\mathcal{I}^{\text{cl}}} = a^{\mathcal{I}} $$

$$ R^{\mathcal{I}^{\text{cl}}} = R^{\mathcal{I}} $$

$$ (a \in \text{IN}, R \in \text{RN}) $$

$$ (A^{+})^{\mathcal{I}^{\text{cl}}} = A^{\mathcal{I}_p} $$

$$ (A^{-})^{\mathcal{I}^{\text{cl}}} = A^{\mathcal{I}_n} $$

$$ (A \in \text{CN}) $$

**PROPOSITION 2.7.** Let $\mathcal{K}$ be an $\mathcal{A}\mathcal{L}\mathcal{C}\mathcal{H}\mathcal{I}_{\Delta}^4$ knowledge base in NNF, $\mathcal{I}$ be a 4-valued interpretation, and $\phi$ be a concept inclusion, role inclusion, or assertion. Then $\mathcal{K} \models_4 \phi$ iff $\mathcal{K}^{\text{cl}} \models \phi^{\text{cl}}$ and, moreover, $\mathcal{I} \models_4 \mathcal{K}$ iff $\mathcal{I}^{\text{cl}} \models \mathcal{K}^{\text{cl}}$.

**PROOF.** Let $\mathcal{K} \models_4 \phi$ and $\mathcal{I} = \langle \Delta^{\mathcal{I}}, \cdot_{\mathcal{I}_p}, \cdot_{\mathcal{I}_n} \rangle$ be a 4-interpretation that falsifies the entailment. We show that $\mathcal{I}^{\text{cl}} \models \mathcal{K}^{\text{cl}}$ and $\mathcal{I}^{\text{cl}} \nvDash \phi^{\text{cl}}$, so that $\mathcal{K}^{\text{cl}} \nvDash \phi^{\text{cl}}$. Since role interpretations are not affected by $\cdot^{\text{cl}}$, it suffices to show that $(C^{\text{cl}})^{\mathcal{I}^{\text{cl}}} = C^{\mathcal{I}_p}$ for every concept C. We proceed by induction on C. The proof is mostly the same as that of Maier et al. (2013, Proposition 38), so we only consider the cases with $\Delta$. The cases of $C = \Delta A$ and $C = \Delta \neg A$ are straightforward since $(\Delta D)^{\mathcal{I}_p} = D^{\mathcal{I}_p}$ for any concept D. Next, let $C = \neg \Delta A$. Then $(\neg \Delta A)^{\mathcal{I}_p} = \Delta^{\mathcal{I}} \setminus A^{\mathcal{I}_p} = \Delta^{\mathcal{I}^{\text{cl}}} \setminus (A^{+})^{\mathcal{I}^{\text{cl}}} = (\neg A^{+})^{\mathcal{I}^{\text{cl}}}$, as required. The case of $C = \neg \Delta \neg A$ can be tackled similarly: $(\neg \Delta \neg A)^{\mathcal{I}_p} = (\Delta \neg A)^{\mathcal{I}_n} = \Delta^{\mathcal{I}} \setminus (\neg A)^{\mathcal{I}_p} = \Delta^{\mathcal{I}} \setminus A^{\mathcal{I}_n} = \Delta^{\mathcal{I}^{\text{cl}}} \setminus (A^{-})^{\mathcal{I}^{\text{cl}}} = (\neg A^{-})^{\mathcal{I}^{\text{cl}}}$, as required. This also shows that $\mathcal{I} \models_4 \mathcal{K}$ iff $\mathcal{I}^{\text{cl}} \models \mathcal{K}^{\text{cl}}$.

For the converse, let $\mathcal{I} = \langle \Delta^{\mathcal{I}}, \cdot^{\mathcal{I}} \rangle$ be a classical interpretation that witnesses $\mathcal{K}^{\text{cl}} \nvDash \phi^{\text{cl}}$. We define its 4-counterpart $\mathcal{I}^4 = \langle \Delta^{\mathcal{I}^4}, \cdot_{\mathcal{I}_p}^{\mathcal{I}^4}, \cdot_{\mathcal{I}_n}^{\mathcal{I}^4} \rangle$ as follows: $A_{\mathcal{I}_p}^{\mathcal{I}^4} = (A^{+})^{\mathcal{I}}$ and $A_{\mathcal{I}_n}^{\mathcal{I}^4} = (A^{-})^{\mathcal{I}}$ for $A \in \text{CN}$; $R^{\mathcal{I}^4} = R^{\mathcal{I}}$ for $R \in \text{RN}$ and $a^{\mathcal{I}^4} = a^{\mathcal{I}}$ for $a \in \text{IN}$. We can show that $\mathcal{I}^4 \models_4 \mathcal{K}$ and $\mathcal{I}^4 \nvDash_4 \phi$ by proving, via structural induction, that $C_{\mathcal{I}_p}^{\mathcal{I}^4} = (C^{\text{cl}})^{\mathcal{I}}$ for every concept C. $\square$

We have just seen how to reduce 4-entailment to classical entailment. To obtain a reduction in the other direction, we shall exploit the essentially two-valued behaviour of $\Delta$. We use $\chi^{\Delta}$ to denote the result of putting $\Delta$ in front of every concept name occurring in $\chi$.

**LEMMA 2.8.** Let $\mathcal{K} = \langle \mathcal{T}, \mathcal{A} \rangle$ be an $\mathcal{A}\mathcal{L}\mathcal{C}\mathcal{H}\mathcal{I}$ knowledge base in NNF. Then it holds that $\{ \cdot^{\mathcal{I}} | \mathcal{I} \models \mathcal{K}, \mathcal{I} = \langle \Delta^{\mathcal{I}}, \cdot^{\mathcal{I}} \rangle \} = \{ \cdot_{\mathcal{I}_p}^{\mathcal{I}^4} | \mathcal{I}_4 \models_4 \mathcal{K}^{\Delta}, \mathcal{I}^4 = \langle \Delta^{\mathcal{I}^4}, \cdot_{\mathcal{I}_p}^{\mathcal{I}^4}, \cdot_{\mathcal{I}_n}^{\mathcal{I}^4} \rangle \}$.

**PROOF.** Let $\mathcal{I} = \langle \Delta^{\mathcal{I}}, \cdot^{\mathcal{I}} \rangle$ be a classical model of $\mathcal{K}$. Now, let $\cdot_{\mathcal{I}_n}^{\mathcal{I}^4}$ be arbitrary and $\cdot_{\mathcal{I}_p}^{\mathcal{I}^4} = \cdot^{\mathcal{I}}$ and define $\mathcal{I}^4 = \langle \Delta^{\mathcal{I}}, \cdot_{\mathcal{I}_p}^{\mathcal{I}^4}, \cdot_{\mathcal{I}_n}^{\mathcal{I}^4} \rangle$. We show that $\mathcal{I}_4 \models_4 \mathcal{K}^{\Delta}$. Since $\cdot^{\Delta}$ does not affect role names, it suffices to check that $(C^{\Delta})^{\mathcal{I}_p} = C^{\mathcal{I}}$ for every concept. We proceed by induction on C. The basis case of $C = A$ and $C^{\Delta} = \Delta A$ follows by the construction of $\mathcal{I}_4$ since $(\Delta A)^{\mathcal{I}_p} = A^{\mathcal{I}_p} = A^{\mathcal{I}}$. If $C = \neg A$, we have that

$$ (\neg A)^{\mathcal{I}} = \Delta^{\mathcal{I}} \setminus A^{\mathcal{I}} = \Delta^{\mathcal{I}} \setminus A^{\mathcal{I}_p^{\mathcal{I}^4}} = (\Delta A)^{\mathcal{I}_n^{\mathcal{I}^4}} = (\neg \Delta A)^{\mathcal{I}_p^{\mathcal{I}^4}} $$
The cases of other connectives and quantifiers can be shown by a straightforward application of the induction hypothesis.

For the other direction, let $\mathcal{I}^4 = \langle \Delta^{\mathcal{I}^4}, .^{\mathcal{I}_p^4}, .^{\mathcal{I}_n^4} \rangle$ be a 4-model of $\mathcal{K}^{\Delta}$ and define $\mathcal{I} = \langle \Delta^{\mathcal{I}^4}, .^{\mathcal{I}} \rangle$ with $\cdot^{\mathcal{I}} = \cdot^{\mathcal{I}_p^4}$. To show that $\mathcal{I} \models \mathcal{K}$, it again suffices to check that $C^{\mathcal{I}} = (C^{\Delta})^{\mathcal{I}_p^4}$ for every concept C, and the proof is similar to the one for the first direction. $\square$

From the preceding lemma, it straightforwardly follows that:

**PROPOSITION 2.9.** Let $\mathcal{K}$ be an $\mathcal{ALCHI}$ knowledge base in NNF and $\phi$ a concept inclusion, role inclusion, or assertion. Then $\mathcal{K} \models \phi$ iff $\mathcal{K}^{\Delta} \models_4 \phi^{\Delta}$.

The next statement then follows from Propositions 2.7 and 2.9 and the complexity of $\mathcal{ALCHI}$ (Tobies 2001).

**THEOREM 2.10.** Axiom or assertion entailment in $\mathcal{ALCHI}_{\Delta}^{4}$ is ExpTime-complete.

## 2.6 Horn DLs

As seen in Example 2.1, $A \sqcap B \sqsubseteq \perp$, $A \sqsubseteq \neg B$ and $B \sqsubseteq \neg A$ have different semantics in the four-valued setting. Hence, to be able to define $\mathcal{L}_{\Delta}^4$ KBs that are really paraconsistent for DLs $\mathcal{L}$ that normally have $\perp$ but no negation, such as $\mathcal{EL}\mathcal{HI}_{\perp}$ and its sub-logics, we need to use syntactic variants that may also express ‘weak disjointness’ with $\neg$. An $\mathcal{EL}\mathcal{HI}_{\neg\Delta}^4$ TBox contains inclusions of one of the following forms (extending $\mathcal{EL}\mathcal{HI}_{\perp}$ TBoxes in normal form):

$$S \sqsubseteq S'$$

$$A \sqsubseteq \exists S.B$$

$$\exists S.A \sqsubseteq C$$

$$A \sqcap B \sqsubseteq C$$

$$A \sqsubseteq \neg B$$

with $S, S' \in \text{RN}^{\pm}$, $A, B \in \text{CN} \cup \{\text{T}\}$ and $C \in \text{CN} \cup \{\text{T}, \perp\}$. We do not include the $\Delta$ operator in this syntax because we can equivalently add $\Delta$ anywhere in the above inclusions without changing the inclusion satisfaction condition, except in the case of $A \sqsubseteq \neg \Delta B$, but as mentioned in Example 2.1, $A \sqsubseteq \neg \Delta B$ is equivalent to $A \sqcap B \sqsubseteq \perp$. We keep the language name in the form of $\mathcal{L}_{\Delta}^4$ only for homogeneity. We denote by $\mathcal{EL}_{\neg\Delta}^4$, $\mathcal{EL}\mathcal{I}_{\neg\Delta}^4$ and $\mathcal{EL}\mathcal{H}_{\neg\Delta}^4$ the fragments of $\mathcal{EL}\mathcal{HI}_{\neg\Delta}^4$ that correspond to $\mathcal{EL}_{\perp}$, $\mathcal{EL}\mathcal{I}_{\perp}$ and $\mathcal{EL}\mathcal{H}_{\perp}$ respectively.

It is easily checked that for every $\mathcal{L}_{\neg\Delta}^4$ KB $\mathcal{K}$ with $\mathcal{L} \in \{\mathcal{EL}\mathcal{HI}, \mathcal{EL}\mathcal{I}, \mathcal{EL}\mathcal{H}, \mathcal{EL}\}\$, its classical counterpart $\mathcal{K}^{\text{cl}}$ is an $\mathcal{L}_{\perp}$ KB. Indeed, from the definition of $\mathcal{EL}\mathcal{HI}_{\neg\Delta}^4$, $\mathcal{K}$ is in NNF and does not contain $\Delta$, so $^{\text{cl}}$ only adds superscript + on all concept names but those that occur under $\neg$ in inclusions of the form $A \sqsubseteq \neg B$, which become $A^+ \sqsubseteq \neg B^-$. It follows that $\mathcal{L}_{\neg\Delta}^4$ has the same complexity as $\mathcal{L}_{\perp}$.

Note however that Proposition 2.3 does not hold for $\mathcal{EL}\mathcal{HI}_{\neg\Delta}^4$. Indeed, as already noted by Maier et al. (2013), material and strong inclusions require non-Horn concept inclusions.

## 3 Queries With Exact Truth Values

Before introducing our novel approach to querying four-valued DL KBs, let us recall the query language and semantics considered by Zhou et al. (2012).

**Definition 3.1.** Let Var be a set of variables disjoint from IN and Term = Var $\cup$ IN. A conjunctive query (CQ) has the form $q := \exists y_1 ... y_m : \varphi$ where $y_1, ..., y_m \in \text{Var}$ and $\varphi$ is a conjunction of atoms of the form $R(t, t')$ or $A(t)$ with $t, t' \in \text{Term}$, $R \in \text{RN}$ and $A \in \text{CN}$. A CQ $q$ is Boolean (BCQ) if no variable occurs in it freely. We will use terms($q$) to refer to the set of terms occurring in $q$.

A KB $\mathcal{K}$ 4-entails a BCQ $q$ ($\mathcal{K} \models_4 q$) if for every 4-model $\mathcal{I} = \langle \Delta^{\mathcal{I}}, \cdot^{\mathcal{I}_p}, \cdot^{\mathcal{I}_n} \rangle$ of $\mathcal{K}$, there is a match $\pi : \text{terms}(q) \mapsto \Delta^{\mathcal{I}}$ such that for every $c \in \text{IN}$, $\pi(c) = c^{\mathcal{I}}$, and for every $R(t_1, t_2)$ (resp. $A(t)$) that occurs in $q$, $(\pi(t_1), \pi(t_2)) \in \mathbb{R}^{\mathcal{I}}$ (resp. $\pi(t) \in A^{\mathcal{I}_p}$).

We make an important observation not explicit in the work by Zhou et al. (2012), namely, that in the case of Horn DLs, answering CQs under paraconsistent semantics amounts to answering them classically over the
‘positive’ part of the KB obtained by dropping the weak disjointness axioms. Recall that a classical, two-valued,
KB $\mathcal{K}$ entails a BCQ $\mathbf{q}$, denoted $\mathcal{K} \models \mathbf{q}$, iff there is a match for $\mathbf{q}$ in every model of $\mathcal{K}$.

PROPOSITION 3.2. If $\mathcal{K}$ is an $\mathcal{EL}\mathcal{HI}_{\neg\triangle}}^4$ KB and $\mathcal{K}^+$ denotes the $\mathcal{EL}\mathcal{HI}$ KB obtained from $\mathcal{K}$ by dropping all inclusions of the form $A \sqsubseteq \neg B$, then for every BCQ $\mathbf{q}$, $\mathcal{K} \models_4 \mathbf{q}$ iff $\mathcal{K}^+ \models \mathbf{q}$.

PROOF. Assume that $\mathcal{K} \models_4 \mathbf{q}$. If $\mathcal{K}^+$ has no classical model, then $\mathcal{K}^+ \models \mathbf{q}$. Otherwise, let $\mathcal{I} = \langle \Delta^I, \cdot_I \rangle$ be a model of $\mathcal{K}^+$. Define $\mathcal{J} = \langle \Delta^I, \cdot_I, \cdot_{I_n} \rangle$ with $A_{I_n} = \Delta^I$ for every $A \in \text{CN}$. Since $\neg$ only occurs in inclusions of the form $A \sqsubseteq \neg B$ in $\mathcal{K}$, it is easy to check that $\mathcal{J} \models_4 \mathcal{K}$. It follows that $\mathcal{J} \models_4 \mathbf{q}$, which implies the existence of a match for $\mathbf{q}$ in $\mathcal{I}$ by construction of $\mathcal{J}$. Hence $\mathcal{K}^+ \models \mathbf{q}$.

In the other direction, if $\mathcal{K} \nvDash_4 \mathbf{q}$, then there exists a 4-model $\mathcal{J} = (\Delta^J, \cdot_J, \cdot_{J_n})$ of $\mathcal{K}$ such that $\mathcal{J} \nvDash_4 \mathbf{q}$. Let $\mathcal{I} = (\Delta^I, \cdot_I)$. Again, it is easy to check that $\mathcal{I} \models \mathcal{K}^+$. Thus $\mathcal{I}$ is a model of $\mathcal{K}^+$ such that there is no match for $\mathbf{q}$ in $\mathcal{I}$, so $\mathcal{K}^+ \nvDash \mathbf{q}$. $\square$

**3.1 Language and Semantics**

The fact that paraconsistent query answering in Horn DLs basically amounts to ignoring axioms with negation
provides strong motivation for exploring a more expressive query language that better exploits the paraconsistent
semantics. We propose such a language by introducing four *value operators* corresponding to Belnapian values.

*Definition 3.3 (Queries with values)*. A conjunctive query with values (CQV) is a CQ whose atoms are of the form $R(t, t')$, $A(t)$ or $X(A(t))$ with $X \in \{\mathbf{T}, \mathbf{B}, \mathbf{N}, \mathbf{F}\}$. A Boolean CQV (BCQV) has no free variables. We use terms($\mathbf{q}$) for the set of terms occurring in a CQV $\mathbf{q}$.

Next, we illustrate the intuitive use of value operators.

*Example 3.4.* Let $\mathcal{K}'_U = (\mathcal{T}_U \cup \mathcal{T}', \mathcal{A}_U \cup \mathcal{A}')$ extend $\mathcal{K}_U$ from Example 2.1. The additional TBox axioms state that one should not be a teaching assistant (TA) and a professor (Prf), that a course should not be a graduate course (Gr) and an obligatory course (Obl) and that every professor teaches some graduate course. Additional ABox assertions give information about the courses (formal verification *fv*, algorithms *alg*, logic *log*, and automata theory *at*) taught by four persons as well as the positions they hold.

$$
\begin{align*}
\mathcal{T}' &= \{ \text{TA} \sqsubseteq \neg \text{Prf}, \text{Prf} \sqsubseteq \neg \text{TA}, \text{Prf} \sqsubseteq \exists \text{teaches}.\text{Gr}, \text{Gr} \sqsubseteq \neg \text{Obl}, \text{Obl} \sqsubseteq \neg \text{Gr} \} \\
\mathcal{A}' &= \left\{ \begin{array}{llll}
\text{teaches}(\text{ann}, \text{fv}), & \text{teaches}(\text{ann}, \text{alg}), & \text{teaches}(\text{ann}, \text{log}), & \text{teaches}(\text{bea}, \text{log}), \\
\text{teaches}(\text{bea}, \text{alg}), & \text{Obl}(\text{log}), & \text{Gr}(\text{log}), & \text{Obl}(\text{alg}), \\
\text{TA}(\text{bea}), & \text{TA}(\text{claire}), & \text{Asc}(\text{diane}) &
\end{array} \right\}
\end{align*}
$$

Now, consider the following queries:

$$
\mathbf{q}_1 := \text{teaches}(x, y) \wedge \mathbf{T}(\text{Gr}(y))
$$

$$
\mathbf{q}_2 := \text{teaches}(x, y) \wedge \mathbf{N}(\text{Gr}(y)) \wedge \mathbf{N}(\text{Obl}(y))
$$

$$
\mathbf{q}_3 := \text{teaches}(x, y) \wedge \mathbf{T}(\mathbf{TA}(x)) \wedge \mathbf{B}(\mathbf{Obl}(y))
$$

$$
\mathbf{q}_4 := \exists y : \mathbf{T}(\mathbf{Asc}(x)) \wedge \mathbf{T}(\mathbf{Gr}(y)) \wedge \mathbf{teaches}(x, y)
$$

Intuitively, $\mathbf{q}_1$, $\mathbf{q}_2$, and $\mathbf{q}_3$ look for pairs of persons and courses they teach such that: the course is a graduate course ($\mathbf{q}_1$), the kind of course is not specified ($\mathbf{q}_2$), or the person is a teaching assistant and there is contradictory information about the course being obligatory ($\mathbf{q}_3$). One can imagine using $\mathbf{q}_2$ and $\mathbf{q}_3$ to curate the university course database: $\mathbf{q}_2$ will find courses for which some information is missing and $\mathbf{q}_3$ (or a simpler version $\mathbf{B}(\text{Obl}(y))$) will find courses for which contradictory information is provided. On the other hand, $\mathbf{q}_1$ will provide answers for which the kind of the course is not contradicted, hence that we presumably can trust even from the uncurated database.
We thus expect (ann, fv) to be the unique answer for q₁, since alg is an obligatory (whence, not a graduate) course. Moreover, log is also registered as an obligatory course, which contradicts that it is a graduate course. Regarding q₂, we expect the unique answer (claire, at), since automata theory is the only course about which it is not specified whether it is graduate or obligatory. Finally, we expect that (bea, log) is the unique answer for q₃. Indeed, Bea is the only teaching assistant who teaches logic since we have $K'_{U} \models_{\neg} \neg A(ann)$ using the assertion from Example 2.1 that Ann is an associate professor. Regarding q₄, which asks for associate professors that teach some graduate course, we expect that **diane** is the only answer. Indeed, Diane is the only one who is undoubtedly an associate professor (recall from Example 2.1 that Ann is a head of a chair which means that she is supposed to be a full professor even though she is listed as an associate). Moreover, although no course taught by Diane is mentioned in the ABox, we know that associate professors should teach at least one graduate course. As this is not contradicted, **diane** should be the only answer to q₄.

To give the formal semantics of CQVs, we will need to refer to different sets of the query atoms, depending on which value operators they use.

**Definition 3.5 (Atom sets in CQVs).** Let atoms(q) be the set of all atoms occurring in q and define for X, Y ∈ {T, B, N, F}:

$$ \text{atoms}^{X}(q) = \{A(t) \mid X(A(t)) \in \text{atoms}(q)\} $$

$$ \text{atoms}^{XY}(q) = \text{atoms}^{X}(q) \cup \text{atoms}^{Y}(q) $$

$$ \text{atoms}^{+}(q) = \{A(t) \mid A(t) \in \text{atoms}(q)\} \cup \text{atoms}^{\text{TB}}(q) $$

We are now ready to define the semantics of CQVs. Intuitively, we require that every 4-model satisfies the 'at least true/false' conditions expressed by the query and that there exists a 4-model witnessing the 'exactly true/false' conditions.

**Definition 3.6 (CQV answers).** A KB K 4-entails a BCQV q (K $\models$₄ q) if the following conditions hold:

(1) For every 4-model $\mathcal{I} = \langle \Delta^I, \cdot_I^p, \cdot_I^n \rangle$ of K, there is a match $\pi : \text{terms}(q) \mapsto \Delta^I$ such that for every $c \in \text{IN}$, $\pi(c) = c^I$, and

* $(\pi(t_1), \pi(t_2)) \in \mathbb{R}^I$ for every $R(t_1, t_2) \in \text{atoms}(q)$;

* $\pi(t) \in A_I^p$ for every $A(t) \in \text{atoms}^{+}(q)$;

* $\pi(t) \in A_I^n$ for every $A(t) \in \text{atoms}^{\text{BF}}(q)$.

(2) There exists a 4-model $\mathcal{I} = \langle \Delta^I, \cdot_I^p, \cdot_I^n \rangle$ of K and a match $\pi$ as required above which is additionally such that

* $\pi(t) \notin A_I^n$ for every $A(t) \in \text{atoms}^{\text{TN}}(q)$;

* $\pi(t) \notin A_I^p$ for every $A(t) \in \text{atoms}^{\text{FN}}(q)$.

We say that $\vec{a}$ is a four-valued paraconsistent answer to a CQV $q(\vec{x})$ with free variables $\vec{x}$ over K, denoted $\vec{a} \in \text{ans}_4(q(\vec{x}), K)$, if $K \models_4 q(\vec{a})$ where $q(\vec{a})$ is the Boolean query obtained by replacing the variables from $\vec{x}$ with the constants from $\vec{a}$.

When q is just a CQ, the semantics coincides with the one given in Definition 3.1. Indeed, in this case atoms<sup>BF</sup>(q), atoms<sup>TN</sup>(q) and atoms<sup>FN</sup>(q) are empty so the condition reduces to item 1 restricted to its first two points.

One can interpret value operators as follows: $K \models_4 T(A(a))$ means that there is sufficient evidence to conclude $A(a)$ from K and no evidence for $\neg A(a)$; dually, if $K \models_4 F(A(a))$, then we can conclude $\neg A(a)$ from K but cannot derive $A(a)$; $K \models_4 B(A(a))$ means that the evidence regarding $A(a)$ is contradictory; finally, if $K \models_4 N(A(a))$, then we do not have sufficient information to conclude that $A(a)$ is true nor to conclude that it is false. Intuitively, condition 2 in Definition 3.6 considers the 'negative support' of the query atoms. This allows for distinction between $A(a)$ being exactly true and at least true (i.e., true and maybe false) and likewise between exactly false and
at least false. We will see in Example 3.13 that it is impossible to achieve this without value operators. This also means that $|\equiv_4$-inconsistent KBs do not entail arbitrary CQVs. Indeed, observe that for $X \neq B$ and $\mathcal{K} |\equiv_4 X(A(a))$, condition 2 implies that $\mathcal{K}$ has 4-models.

**Remark 1.** Note that the semantics of value operators is only defined w.r.t. classes of models (the models of the considered KB). In particular, we do not define what it would mean for a 4-interpretation to satisfy, e.g., $X(A(a))$. Thus, value operators cannot be used in KBs. They cannot be replaced with $\Delta$ either: $\mathcal{K} |\equiv_4 T(A(a))$ is not equivalent to the statement '$a \in A^{I_p}$ and $a \notin A^{I_n}$ in all 4-models of $\mathcal{K}$'. Similarly, $\mathcal{K} |\equiv_4 N(A(a))$ and $\mathcal{K} |\equiv_4 F(A(a))$ are not equivalent to '$a \notin A^{I_p}$ and $a \notin A^{I_n}$ in all 4-models of $\mathcal{K}$' and '$a \notin A^{I_p}$ and $a \in A^{I_n}$ in all 4-models of $\mathcal{K}$'. Observe that these statements can be expressed as $\mathcal{K} |\equiv_4 [\Delta A \sqcap \neg \Delta \neg A](a), \mathcal{K} |\equiv_4 [\neg \Delta A \sqcap \neg \Delta \neg A](a)$, and $\mathcal{K} |\equiv_4 [\neg \Delta A \sqcap \Delta \neg A](a)$, respectively.

A straightforward check of the KB and queries in Example 3.4 shows that the proposed query semantics gives the expected answers:

$$ \text{ans}_4(\mathbf{q}_1(x, y), \mathcal{K}'_U) = \{(\text{ann}, \text{fv})\} $$

$$ \text{ans}_4(\mathbf{q}_2(x, y), \mathcal{K}'_U) = \{(\text{claire}, \text{at})\} $$

$$ \text{ans}_4(\mathbf{q}_3(x, y), \mathcal{K}'_U) = \{(\text{bea}, \text{log})\} $$

$$ \text{ans}_4(\mathbf{q}_4(x), \mathcal{K}'_U) = \{(\text{diane})\} $$

This example illustrates that value operators allow for a compact and intuitive representation of queries such as ‘a person who teaches an unspecified course’, or ‘a person who teaches a graduate-level course’ (meaning a course that is labelled as a graduate-level one *without contradiction*).

**Remark 2.** When used over existentially quantified variables, the semantics of the value operators remains quite lax. Consider for example $\mathcal{T} = \{B \sqsubseteq \neg A\}$, $\mathcal{A} = \{R(a, b), A(b), B(b)\}$ and $\mathbf{q} = \exists x : R(a, x) \wedge T(A(x))$. It holds that $\mathcal{K} |\equiv_4 \mathbf{q}$ because every 4-model of $\mathcal{K}$ is such that $(a^I, b^I) \in R^I$ and $b^I \in A^{I_p}$, satisfying item 1 of Definition 3.6, and there exists a 4-model $\mathcal{J}$ of $\mathcal{K}$ such that $(a^I, x) \in R^\mathcal{J}, x \in A^{\mathcal{J}_p}$, and $x \notin A^{\mathcal{J}_n}$ for some $x \neq b^\mathcal{J}$, satisfying item 2. Value operators are thus intended to be used preferentially on answer variables or constants.

We conclude by briefly discussing alternative semantics we could consider for CQVs and why they are not satisfactory. First, if we drop item 2 from Definition 3.6, then the semantics of the value operators is overly permissive. For example, $T(A(a)), F(A(a)), B(A(a))$ and $N(A(a))$ would all be entailed from $\langle\{B \sqsubseteq \neg A\}, \{A(a), B(a)\}\rangle$. If instead we adopt a naive ‘certain answers semantics’ by considering that $T(A(a))$ (resp. $F(A(a)), B(A(a)), N(A(a))$) is entailed if every 4-model of the KB is such that $A(a)$ is exactly true (resp. exactly false, both true and false, neither true nor false), then the semantics of the value operators is too strict. For example, $T(A(a))$ would then not be entailed by $\{A(a)\}$ and an empty TBox because there are 4-models of this KB such that $a^I$ is both in $A^{I_p}$ and $A^{I_n}$.

## 3.2 Relationship to Classical BCQ Entailment

We now briefly show how BCQV entailment from a four-valued KB and classical BCQ entailment can be related. Given an $\mathcal{ALCH}^4_\Delta$ KB $\mathcal{K}$ and a BCQV $\mathbf{q}$ such that the only value operators in $\mathbf{q}$ are $T$ and $F$, let $\mathcal{K}^b$ and $\mathbf{q}^b$ be the results of removing all occurrences of $\Delta$ in $\mathcal{K}$ and replacing every $T(A(t))$ and $F(A(t))$ in $\mathbf{q}$ by $A(t)$ and $\neg A(t)$ respectively. We first show that the query semantics is sound w.r.t. classical certain answers. Recall that in the classical, two-valued, setting, the semantics of a BCQ extended with negated atoms of the form $\neg A(t)$ is as expected: $\mathcal{K}^b |\equiv \mathbf{q}^b$ iff there is a match $\pi$ for $\mathbf{q}^b$ in every model $\mathcal{I} = \langle\Delta^I, \cdot^I\rangle$ of $\mathcal{K}^b$, i.e., in particular, such that $\pi(t) \notin A^I$ for every $\neg A(t)$ in $\mathbf{q}^b$.

We begin with a technical lemma.
**LEMMA 3.7.** For every classical (two-valued) model $\mathcal{I} = \langle \Delta^I, \cdot^I \rangle$ of $\mathcal{K}^b$, the 4-valued counterpart $\mathcal{I}^4$ of $\mathcal{I}$ defined by $\mathcal{I}^4 = \langle \Delta^I, \cdot^I, \cdot^I, \cdot^I \rangle$ with $A^I_p = A^I$ and $A^I_n = \Delta^I \setminus A^I$ for all $A \in \text{CN}$, $R^{\mathcal{I}^4} = R^I$ for all $R \in \text{RN}$, and $a^{\mathcal{I}^4} = a^I$ for $a \in \text{IN}$ is such that $\mathcal{I}^4 \models_4 \mathcal{K}$.

**PROOF.** We show that $\mathcal{I}^4 \models_4 \mathcal{K}$ by proving by structural induction that for every $\mathcal{A}LCH\mathcal{I}^4_\Delta$ concept C, $C^{\mathcal{I}^4_p} = (C^b)^I$ and $C^{\mathcal{I}^4_n} = \Delta^I \setminus (C^b)^I$. For the base case, we have $A^b = A$ and by construction, $A^{\mathcal{I}^4_p} = A^I$ and $A^{\mathcal{I}^4_n} = \Delta^I \setminus A^{\mathcal{I}^4_p} = \Delta^I \setminus A^I$.

For the induction step, let C be an $\mathcal{A}LCH\mathcal{I}^4_\Delta$ concept, and assume that the property has been shown for all subconcepts. If C = $\neg D$, then $C^{\mathcal{I}^4_p} = D^{\mathcal{I}^4_n} = \Delta^I \setminus (D^b)^I = (\neg D^b)^I = (C^b)^I$ and $C^{\mathcal{I}^4_n} = D^{\mathcal{I}^4_p} = (D^b)^I = \Delta^I \setminus (\neg D^b)^I = \Delta^I \setminus (C^b)^I$.

If C = $\Delta D$, $C^{\mathcal{I}^4_p} = D^{\mathcal{I}^4_p} = (D^b)^I = (C^b)^I$ and $C^{\mathcal{I}^4_n} = \Delta^I \setminus D^{\mathcal{I}^4_p} = \Delta^I \setminus (D^b)^I = \Delta^I \setminus (C^b)^I$. Finally, if C = $D_1 \sqcap D_2$, C = $D_1 \sqcup D_2$, C = $\exists R.D$ or C = $\forall R.D$, observe from (1) that $\cdot^{\mathcal{I}^4_p}$ and $\cdot^I$ behave in the same way. We thus obtain $C^{\mathcal{I}^4_p} = (C^b)^I$ directly from the fact that, e.g., $C^b = D_1^b \sqcap D_2^b$. We show that $C^{\mathcal{I}^4_n} = \Delta^I \setminus (C^b)^I$ for the case C = $D_1 \sqcap D_2$ (the other cases can be shown analogously): $C^{\mathcal{I}^4_n} = D_1^{\mathcal{I}^4_n} \cup D_2^{\mathcal{I}^4_n} = (\Delta^I \setminus (D_1^b)^I) \cup (\Delta^I \setminus (D_2^b)^I) = \Delta^I \setminus ((D_1^b)^I \cap (D_2^b)^I) = \Delta^I \setminus (C^b)^I$. $\square$

Now, using Lemma 3.7, we can prove the soundness of our query semantics.

**PROPOSITION 3.8.** $\mathcal{K} \models_4 q$ implies $\mathcal{K}^b \models q^b$.

**PROOF.** Assume that $\mathcal{K}^b \nvDash q^b$. Since $\mathcal{K}^b \nvDash q^b$, there is a classical model $\mathcal{I} = \langle \Delta^I, \cdot^I \rangle$ of $\mathcal{K}^b$ where there is no match $\pi : \text{terms}(q^b) \mapsto \Delta^I$ such that

* $\pi(c) = c^I$ for each $c \in \text{IN}$;

* $(\pi(t), \pi(t')) \in R^I$ for each $R(t, t') \in \text{atoms}(q^b)$;

* $\pi(t) \in A^I$ for each $A(t) \in \text{atoms}(q^b)$;

* $\pi(t) \notin A^I$ for each $\neg A(t) \in \text{atoms}(q^b)$.

Now let $\mathcal{I}^4 = \langle \Delta^I, \cdot^I, \cdot^I, \cdot^I \rangle$ be the 4-valued counterpart of $\mathcal{I}$ as defined in Lemma 3.7. Recall that $A^{\mathcal{I}^4_p} = A^I$ and $A^{\mathcal{I}^4_n} = \Delta^I \setminus A^I$ for all $A \in \text{CN}$. Hence, there is no match $\pi : \text{terms}(q) \mapsto \Delta^I$ such that

* $\pi(c) = c^{\mathcal{I}^4}$ for each $c \in \text{IN}$;

* $(\pi(t), \pi(t')) \in R^{\mathcal{I}^4}$ for each $R(t, t') \in \text{atoms}(q)$;

* $\pi(t) \in A^{\mathcal{I}^4_p}$ for each $A(t) \in \text{atoms}^+(q)$;

* $\pi(t) \in A^{\mathcal{I}^4_n}$ for each $A(t) \in \text{atoms}^{\text{BF}}(q)$.

However, since we know from Lemma 3.7 that $\mathcal{I}^4 \models_4 \mathcal{K}$, the existence of such a match is required by item 1 of Definition 3.6 for $\mathcal{K} \models_4 q$ to hold. Thus, $\mathcal{K} \not\models_4 q$. $\square$

The converse of Proposition 3.8 holds only for classically satisfiable Horn KBs. Again, we begin with showing a technical statement.

**LEMMA 3.9.** Let $\mathcal{K} = \langle \mathcal{T}, \mathcal{A} \rangle$ be a classically satisfiable $\mathcal{ELH}\mathcal{I}_\neg$ KB and $\mathcal{J}_\mathcal{K} = \langle \Delta^{\mathcal{J}_\mathcal{K}}, \cdot^{\mathcal{J}_\mathcal{K}} \rangle$ be its two-valued universal model. For every 4-model $\mathcal{I} = \langle \Delta^I, \cdot^I, \cdot^I, \cdot^I \rangle$ of $\mathcal{K}$, there is a homomorphism between $\mathcal{J}_\mathcal{K}$ and $\langle \Delta^I, \cdot^I \rangle$, i.e., there exists $h : \Delta^{\mathcal{J}_\mathcal{K}} \mapsto \Delta^I$ such that:

* $h(a^{\mathcal{J}_\mathcal{K}}) = a^I$ for every $a \in \text{IN}$;

* $(c, d) \in R^{\mathcal{J}_\mathcal{K}}$ implies $(h(c), h(d)) \in R^I$;

* $c \in A^{\mathcal{J}_\mathcal{K}}$ implies $h(c) \in A^{\mathcal{I}_p}$.
PROOF. Assume that $\mathcal{K} = \langle \mathcal{T}, \mathcal{A} \rangle$ is a classically satisfiable $\mathcal{ELHI}_\neg \Delta$ KB. We recall (see e.g. (Baader, Horrocks, et al. 2017, §7.2.2)) that a two-valued universal model for $\mathcal{K}$ can be defined as $\mathcal{J}_{\mathcal{K}} = \bigcup_{i \ge 0} \mathcal{J}_i$ where $\Delta^{\mathcal{J}_0} = \text{IN}$ and $^{\cdot} \mathcal{J}_0$ is as follows:

* $a^{\mathcal{J}_0} = a$ for every $a \in \text{IN}$;

* $A^{\mathcal{J}_0} = \{a \mid A(a) \in \mathcal{A}\}$ for every $A \in \text{CN}$;

* $R^{\mathcal{J}_0} = \{(a, b) \mid R(a, b) \in \mathcal{A}\}$ for every $R \in \text{RN}$;

and the interpretation $\mathcal{J}_{i+1}$ results from applying one of the rules below to $\mathcal{J}_i$ (ignoring TBox inclusions with $\perp$ in the right-hand side).

(1) If $S_1 \sqsubseteq S_2 \in \mathcal{T}$ and $(d,e) \in S_1^{\mathcal{J}_i}$, then $S_2^{\mathcal{J}_{i+1}} = S_2^{\mathcal{J}_i} \cup \{(d,e)\}$.

(2) If $A_1 \sqcap A_2 \sqsubseteq B \in \mathcal{T}$ and $d \in A_1^{\mathcal{J}_i} \cap A_2^{\mathcal{J}_i}$, then $B^{\mathcal{J}_{i+1}} = B^{\mathcal{J}_i} \cup \{d\}$.

(3) If $\exists S.A \sqsubseteq B \in \mathcal{T}$, $(d, e) \in S^{\mathcal{J}_i}$, and $e \in A^{\mathcal{J}_i}$, then $B^{\mathcal{J}_{i+1}} = B^{\mathcal{J}_i} \cup \{d\}$.

(4) If $A \sqsubseteq \exists S.B \in \mathcal{T}$ and $d \in A^{\mathcal{J}_i}$, then $\Delta^{\mathcal{J}_{i+1}} = \Delta^{\mathcal{J}_i} \cup \{x\}$, $S^{\mathcal{J}_{i+1}} = S^{\mathcal{J}_i} \cup \{(d,x)\}$ and $B^{\mathcal{J}_{i+1}} = B^{\mathcal{J}_i} \cup \{x\}$ where $x \notin \Delta^{\mathcal{J}_i}$ is a fresh domain element.

Now let $\mathcal{I} = \langle \Delta^I, \cdot^{\mathcal{I}_p}, \cdot^{\mathcal{I}_n} \rangle$ be a 4-model of $\mathcal{K}$. It is easy to build inductively a homomorphism $h := \bigcup_{i \ge 0} h_i$ as required. We start by setting $h_0$ equal to the identity function on IN and observe that:

* $h_0(a^{\mathcal{J}_0}) = a^I$ for every $a \in \text{IN}$;

* $(c, d) \in R^{\mathcal{J}_0}$ implies $R(c, d) \in \mathcal{A}$, so $(h_0(c), h_0(d)) \in R^I$;

* $c \in A^{\mathcal{J}_0}$ implies $A(c) \in \mathcal{A}$ so $h_0(c) \in A^{\mathcal{I}_p}$.

Then for every $i \ge 0$, if $h_i : \Delta^{\mathcal{J}_i} \mapsto \Delta^I$ is a homomorphism from $\mathcal{J}_i$ to $\langle \Delta^I, \cdot^{\mathcal{I}_p} \rangle$, we build a homomorphism $h_{i+1} : \Delta^{\mathcal{J}_{i+1}} \mapsto \Delta^I$ from $\mathcal{J}_{i+1}$ to $\langle \Delta^I, \cdot^{\mathcal{I}_p} \rangle$ as follows. If $\mathcal{J}_{i+1}$ has been obtained from $\mathcal{J}_i$ by applying rule 1, 2 or 3, let $h_i = h_{i+1}$. Since $\mathcal{I}$ is a model of $\mathcal{T}$, it is easy to check that $h_{i+1}$ is still a homomorphism. Otherwise, if $\mathcal{J}_{i+1}$ has been obtained from $\mathcal{J}_i$ by applying rule 4 to $A \sqsubseteq \exists S.B \in \mathcal{T}$ and $d \in A^{\mathcal{J}_i}$, by induction we obtain $h_i(d) \in A^{\mathcal{I}_p}$. So, since $\mathcal{I} \models_4 A \sqsubseteq \exists S.B$, there must exist $e$ such that $(h_i(d), e) \in S^I$ and $e \in B^{\mathcal{I}_p}$ and we define $h_{i+1}(x) = e$, so that $(h_{i+1}(d), h_{i+1}(x)) \in S^I$ and $h_{i+1}(x) \in B^{\mathcal{I}_p}$. $\square$

PROPOSITION 3.10. If $\mathcal{K}$ is a classically satisfiable $\mathcal{ELHI}_{\neg \Delta}^4$ KB and $\mathcal{F}$ does not occur in $\mathbf{q}$ (i.e., the only value operator in $\mathbf{q}$ is $\mathcal{T}$), then $\mathcal{K}^b \models \mathbf{q}^b$ implies $\mathcal{K} \models_4 \mathbf{q}$.

PROOF. Let $\mathcal{K}$ and $\mathbf{q}$ be such that $\mathcal{K}^b \models \mathbf{q}^b$ and the conditions of the statement hold. Assume for a contradiction that $\mathcal{K} \not\models_4 \mathbf{q}$, i.e., that one of the following conditions holds.

(i) There exists a 4-model $\mathcal{I} = \langle \Delta^I, \cdot^{\mathcal{I}_p}, \cdot^{\mathcal{I}_n} \rangle$ of $\mathcal{K}$ such that there is no match $\pi : \text{terms}(\mathbf{q}) \mapsto \Delta^I$ as required by item 1 of Definition 3.6.

(ii) For every 4-model $\mathcal{I} = \langle \Delta^I, \cdot^{\mathcal{I}_p}, \cdot^{\mathcal{I}_n} \rangle$ of $\mathcal{K}$ and every match $\pi$ as required by item 1 of Definition 3.6, there exists $\text{T}(A(t)) \in \text{atoms}(\mathbf{q})$ such that $\pi(t) \in A^{\mathcal{I}_n}$.

In case (i), first note that since $\mathcal{ELHI}_{\neg \Delta}^4$ KBs actually do not contain $\Delta$, we have $\mathcal{K} = \mathcal{K}^b$ and so $\mathcal{I} \models_4 \mathcal{K}$ means that $\mathcal{I} \models_4 \mathcal{K}^b$. Hence, by Lemma 3.9, there is a homomorphism $h : \Delta^{\mathcal{J}_{\mathcal{K}}} \mapsto \Delta^I$ from the two-valued universal model $\mathcal{J}_{\mathcal{K}}$ of $\mathcal{K}^b$ and $\langle \Delta^I, \cdot^{\mathcal{I}_p} \rangle$ such that:

* $h(a^{\mathcal{J}_{\mathcal{K}}}) = a^I$ for every $a \in \text{IN}$,

* $(c, d) \in R^{\mathcal{J}_{\mathcal{K}}}$ implies $(h(c), h(d)) \in R^I$,

* $c \in A^{\mathcal{J}_{\mathcal{K}}}$ implies $h(c) \in A^{\mathcal{I}_p}$.

Since $\mathcal{J}_{\mathcal{K}} \models \mathcal{K}^b$, $\mathcal{K}^b \models \mathbf{q}^b$ implies that $\mathcal{J}_{\mathcal{K}} \models \mathbf{q}^b$, so there is a match $\pi$ for $\mathbf{q}^b$ in $\mathcal{J}_{\mathcal{K}}$. We show that $\pi' = h \circ \pi$ is a match for $\mathbf{q}$ in $\mathcal{I}$ as required by item 1 of Definition 3.6, contradicting (i). For every $c \in \text{IN}$, $\pi'(c) = h(\pi(c)) = h(c^{\mathcal{J}_{\mathcal{K}}}) = c^I$, and

* for each $R(t_1, t_2) \in \text{atoms}(\mathbf{q})$, we have $(\pi(t_1), \pi(t_2)) \in R^{\mathcal{J}_{\mathcal{K}}}$, so $(h(\pi(t_1)), h(\pi(t_2))) = \pi'(t_1), \pi'(t_2)) \in R^I$,
• for every $A(t) \in \text{atoms}(\mathbf{q})$, $A(t) \in \text{atoms}(\mathbf{q}^b)$ so $\pi(t) \in A^{\mathcal{J}_K}$ and $h(\pi(t)) = \pi'(t) \in A^{I_p}$,

• for every $\mathbf{T}(A(t)) \in \text{atoms}(\mathbf{q})$, $A(t) \in \text{atoms}(\mathbf{q}^b)$ so as above $\pi'(t) \in A^{I_p}$.

In case (ii), let $\mathcal{J}$ be a two-valued model of $\mathcal{K}^b$, and let $\mathcal{J}^4 = \langle\Delta^{\mathcal{J}}, \cdot^{\mathcal{J}_p}, \cdot^{\mathcal{J}_n}\rangle$ be the 4-valued counterpart of $\mathcal{J}$ as defined in Lemma 3.7. By construction, for every $A \in \text{CN}$, there is no $e \in \Delta^{\mathcal{J}}$ such that $e \in A^{\mathcal{J}_p} \cap A^{\mathcal{J}_n}$. In particular, for every match $\pi$ of $\mathbf{q}$ in $\mathcal{J}^4$ as required by item 1 of Definition 3.6, for every $\mathbf{T}(A(t)) \in \text{atoms}(\mathbf{q})$, since $\pi(t) \in A^{\mathcal{J}_p}$ is required by the definition of $\pi$, it follows that $\pi(t) \notin A^{\mathcal{J}_n}$. Hence, $\mathcal{J}^4$ is a 4-model of $\mathcal{K}$ that contradicts (ii).

We obtain a contradiction in both cases. Hence, we conclude that $\mathcal{K} \models_4 \mathbf{q}$. $\square$

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

Propositions 3.8 and 3.10 ensure that when a Horn KB is classically satisfiable, the paraconsistent answers to $\mathbf{q}$ are the same as the classical answers of $\mathbf{q}^b$, which is intuitively a desirable property. It does not hold, however, if $\sqcup$ is present, even for assertion entailment, as shown by the following example.

**Example 3.11.** Let $\mathcal{A} = \{C(a)\}$ and $\mathcal{T} = \{C \sqsubseteq \neg B, C \sqsubseteq A \sqcup B\}$. $\mathcal{K}$ is consistent and $\mathcal{K} \models A(a)$. However, $\mathcal{K} \not\models_4 A(a)$ because of the following 4-model of $\mathcal{K}$: $A^{I_p} = A^{I_n} = \emptyset$, $B^{I_p} = B^{I_n} = \{a^I\}$, $C^{I_p} = \{a^I\}$ and $C^{I_n} = \emptyset$.

Alternative paraconsistent logics have been proposed to address this arguably counter-intuitive behaviour. For example, Zhang, Xiao, et al. (2014) propose a strong interpretation of disjunction (we denote it $\sqcup^S$) which allows for the disjunctive syllogism<fnref n="3" /> that fails for $\sqcup$. However, it also behaves in a non-standard manner as $A(a) \nvDash_4 (A \sqcup^S B)(a)$. In general, it is unavoidable that paraconsistent logic shows some unexpected behaviour when compared to classical semantics since its basis is to reject some traditional inference principles in order to be able to cope with contradictory information. Regarding the second restriction of Proposition 3.10, the following example illustrates the issue with $\mathbf{F}$.

**Example 3.12.** Let $\mathcal{A} = \{A(a), C(a)\}$ and $\mathcal{T} = \{A \sqsubseteq \exists R \top, \exists R.B \sqsubseteq B, B \sqsubseteq \neg C, C \sqsubseteq \neg B\}$, and assume that $\mathbf{q} = \exists x : R(a, x) \wedge F(B(x))$, i.e., $\mathbf{q}^b = \exists x : R(a, x) \wedge \neg B(x)$. $\mathcal{K} = \mathcal{K}^b$ is consistent and $\mathcal{K}^b \models \mathbf{q}^b$ but $\mathcal{K} \nvDash_4 \mathbf{q}$. Indeed, the following 4-interpretation $\mathcal{I}$ is such that $\mathcal{I} \models_4 \mathcal{K}$ but there is no match for $\mathbf{q}$ in $\mathcal{I}$ as required by item 1 of Definition 3.6: $R^I = \{(a^I, e)\}$, $A^{I_p} = \{a^I\}$, $A^{I_n} = \emptyset$, $B^{I_p} = \{a^I, e\}$, $B^{I_n} = \{a^I\}$, $C^{I_p} = \{a^I\}$ and $C^{I_n} = \{a^I, e\}$.

## 3.3 Comparison With Other Query Languages

We now compare our query language with those proposed in the literature on paraconsistent DLs. As already mentioned, CQVs extend CQs, and their semantics is compatible with the one considered by Zhou et al. (2012). Nguyen and Szałas (2012) consider ground queries defined as conjunctions of complex assertions of the form $C(a)$ (with $C$ a potentially complex concept), $R(a, b)$, $\neg R(a, b)$ and $a \neq b$, interpreted in the expected manner. In particular, $\neg R(a, b)$ is entailed from $\mathcal{K}$ if $(a^I, b^I) \in R^{I_n}$ (Nguyen and Szałas (2012) consider logics allowing roles with independent positive and negative extensions). Even if CQVs do not allow directly for the use of $\mathcal{A}LCHI^4_\Delta$ complex concepts, it is always possible to introduce a concept name $A$ and add $C \equiv A$ and $\neg C \equiv \neg A$ to the TBox. This will ensure that $A^{I_p} = C^{I_p}$ and $A^{I_n} = C^{I_n}$.

One can see that $\mathbf{q}_2$ from Example 3.4 does not have an analogue in the languages of Zhou et al. (2012) and Nguyen and Szałas (2012) since they cannot express that ‘$A(a)$ is not true’ or ‘$A(a)$ is not false’ which is required for the $\mathbf{N}$ operator. $\mathbf{B}(A(a))$, on the other hand, can be expressed as $A(a) \wedge \neg A(a)$ in the language of Nguyen and Szałas (2012). Note, however, that this cannot be directly expressed with the CQs considered by Zhou et al. (2012). Moreover, since they consider DL-Lite ontologies, they cannot use $A(a) \wedge A'(a)$ and a definition $\neg A \equiv A'$ to capture such a query.

<footnote n="3">³The disjunctive syllogism is the inference rule that allows us to derive that $Q$ is true from the facts that ‘$P$ or $Q$’ is true and $P$ is false.</footnote>
The inability to express statements such as 'A(a) is not true' or 'A(a) is not false' prevents both of these query languages from capturing the value operators T and F. The following example illustrates the impact of omitting T from the queries of Example 3.4.

**Example 3.13.** Consider the following queries and a knowledge base $\mathcal{K}'_U$ given in Example 3.4.

$$ q_1^b := \text{teaches}(x, y) \wedge \text{Gr}(y) $$

$$ q_4^b := \exists y : \text{Asc}(x) \wedge \text{Gr}(y) \wedge \text{teaches}(x, y) $$

It is clear that $(\text{bea}, \text{log}) \in \text{ans}_4(q_1^b(x, y), \mathcal{K}'_U)$ and $\text{ann} \in \text{ans}_4(q_4^b(x), \mathcal{K}'_U)$. However, this would be problematic as there is an obvious contradiction considering $\text{log}$, whence one cannot be sure whether logic counts as a graduate or obligatory course. Thus, it might happen that Bea does not teach any graduate courses. Likewise, $\mathcal{K}'_U$ contains a contradiction w.r.t. Ann's position, whence it is unclear whether she is still an associate professor or already a full professor.

# 4 Complexity of Query Answering

In this section, we establish the complexity of answering CQVs. We do this by constructing a reduction of CQV answering to answering unions of conjunctive queries (UCQs) over classically interpreted knowledge bases, using the classical counterpart $\mathcal{K}^{\text{cl}}$ of an $\mathcal{ALCHI}_{\Delta}^4$ KB $\mathcal{K}$ defined in Definition 2.6. Recall that in this KB, concept names $A^+$ and $A^-$ intuitively represent the positive and negative interpretations of concept A. In the following definition, $q^+$ intuitively checks item 1 of Definition 3.6, while $q^{\text{ctr}}$ will be used to check whether satisfying $q^+$ contradicts item 2 of Definition 3.6, using the canonical ABox $\mathcal{A}_q$ for $q^+$.

**Definition 4.1.** Let $\mathbf{q} = \exists \vec{y} : \phi$ be a Boolean CQV and let further $\text{IN}_q = \{c_x | x \in \text{Var} \text{ occurs in } \mathbf{q}\}$ be a fresh set of individuals (occurring neither in $\mathbf{q}$ nor the considered KB). For $t \in \text{IN}$ occurring in $\mathbf{q}$, we will abuse notation and use $c_t$ to refer to the individual $t$. Using the sets of atoms from Definition 3.5, we define

$$ q^+ := \exists \vec{y} : \bigwedge_{R(t,t') \in \text{atoms}(\mathbf{q})} R(t,t') \wedge \bigwedge_{A(t) \in \text{atoms}^+(\mathbf{q})} A^+(t) \wedge \bigwedge_{A(t) \in \text{atoms}^{\text{BF}}(\mathbf{q})} A^-(t) $$

$$ q^{\text{ctr}} := \bigvee_{A(t) \in \text{atoms}^{\text{TN}}(\mathbf{q})} A^-(c_t) \vee \bigvee_{A(t) \in \text{atoms}^{\text{FN}}(\mathbf{q})} A^+(c_t) $$

$$ \mathcal{A}_q := \{R(c_t, c_{t'}) | R(t, t') \in \text{atoms}(q^+)\} \cup \{A^+(c_t) | A^+(t) \in \text{atoms}(q^+)\} \cup \{A^-(c_t) | A^-(t) \in \text{atoms}(q^+)\} $$

We are now ready to state our main result.

**THEOREM 4.2.** Let $\mathcal{K}$ be an $\mathcal{ALCHI}_{\Delta}^4$ KB and $\mathbf{q}$ be a BCQV.

$$ \mathcal{K} \models_4 \mathbf{q} \text{ iff } \mathcal{K}^{\text{cl}} \models \mathbf{q}^+ \text{ and } \mathcal{K}^{\text{cl}} \cup \mathcal{A}_q \nvDash \mathbf{q}^{\text{ctr}} $$

**PROOF.** (⇒) For the first direction, assume that $\mathcal{K} \models_4 \mathbf{q}$. Let $\mathcal{I}^{\text{cl}} = \langle \Delta^{\mathcal{I}^{\text{cl}}}, \cdot^{\mathcal{I}^{\text{cl}}} \rangle$ be a (classical) model of $\mathcal{K}^{\text{cl}}$ and $(\mathcal{I}^{\text{cl}})^4 = \langle \Delta^{(\mathcal{I}^{\text{cl}})^4}, \cdot^{(\mathcal{I}^{\text{cl}})^4}, \cdot^{(\mathcal{I}^{\text{cl}})^4}_p, \cdot^{(\mathcal{I}^{\text{cl}})^4}_n \rangle$ be its 4-counterpart defined as in the proof of Proposition 2.7, which satisfies $(\mathcal{I}^{\text{cl}})^4 \models_4 \mathcal{K}$. Thus, by item 1 of Definition 3.6 there is a match $\pi : \text{terms}(\mathbf{q}) \mapsto \Delta^{(\mathcal{I}^{\text{cl}})^4} = \Delta^{\mathcal{I}^{\text{cl}}}$ such that $\pi(c) = c^{(\mathcal{I}^{\text{cl}})^4} = c^{\mathcal{I}^{\text{cl}}}$ for every $c \in \text{IN}$, and

* $(\pi(t_1), \pi(t_2)) \in \mathcal{R}^{(\mathcal{I}^{\text{cl}})^4} = \mathcal{R}^{\mathcal{I}^{\text{cl}}}$ for each $R(t_1, t_2) \in \text{atoms}(\mathbf{q})$;

* $\pi(t) \in A^{(\mathcal{I}^{\text{cl}})^4}_p = (A^+)^{\mathcal{I}^{\text{cl}}}$ for each $A(t) \in \text{atoms}^+(\mathbf{q})$; and

* $\pi(t) \in A^{(\mathcal{I}^{\text{cl}})^4}_n = (A^-)^{\mathcal{I}^{\text{cl}}}$ for each $A(t) \in \text{atoms}^{\text{BF}}(\mathbf{q})$.

Hence, by definition of $q^+$, $\pi$ is a match for $q^+$ in $\mathcal{I}^{\text{cl}}$. It follows that $\mathcal{K}^{\text{cl}} \models q^+$.

Moreover, by item 2 of Definition 3.6, there exists a 4-model $\mathcal{I}' = \langle \Delta^{\mathcal{I}'}, \cdot^{\mathcal{I}'}, \cdot^{\mathcal{I}'_p}, \cdot^{\mathcal{I}'_n} \rangle$ of $\mathcal{K}$ and a match $\pi : \text{terms}(\mathbf{q}) \mapsto \Delta^{\mathcal{I}'}$ such that $\pi(c) = c^{\mathcal{I}'}$ for every $c \in \text{IN}$, and
* $(\pi(t_1), \pi(t_2)) \in R^{I'}$ for every $R(t_1, t_2) \in \text{atoms}(q)$;

* $\pi(t) \in A_{I_p'}^J$ for every $A(t) \in \text{atoms}(q)$;

* $\pi(t) \in A_{I_p'}^J$ and $\pi(t) \notin A_{I_n'}^J$ for every $T(A(t)) \in \text{atoms}(q)$;

* $\pi(t) \in A_{I_n'}^J$ and $\pi(t) \notin A_{I_p'}^J$ for every $F(A(t)) \in \text{atoms}(q)$;

* $\pi(t) \in A_{I_p'}^J \cap A_{I_n'}^J$ for every $B(A(t)) \in \text{atoms}(q)$;

* $\pi(t) \notin A_{I_p'}^J \cup A_{I_n'}^J$ for every $N(A(t)) \in \text{atoms}(q)$.

Let $I^{\prime \mathrm{cl}}$ be the classical counterpart of $I'$ (cf. Definition 2.6). By Proposition 2.7, $I^{\prime \mathrm{cl}} \models \mathcal{K}^{\mathrm{cl}}$. Let $\mathcal{J}$ be the classical interpretation defined by modifying $I^{\prime \mathrm{cl}}$ so that the individuals from $\mathrm{IN}_q$ are interpreted as follows: $c_t^J = \pi(t)$ for every $c_t \in \mathrm{IN}_q$. We show that $\mathcal{J} \models \mathcal{K}^{\mathrm{cl}} \cup \mathcal{A}_q$. Since $I^{\prime \mathrm{cl}} \models \mathcal{K}^{\mathrm{cl}}$, we have $\mathcal{J} \models \mathcal{K}^{\mathrm{cl}}$. Moreover:

* for every $R(c_t, c_{t'}) \in \mathcal{A}_q$, we have $(c_t^J, c_{t'}^J) = (\pi(t), \pi(t')) \in R^{I'} = R^{I^{\prime \mathrm{cl}}} = R^J$ since $R(t, t') \in \text{atoms}(q^+)$, hence $R(t, t') \in \text{atoms}(q)$, and $\pi$ is a match for $q$ in $I'$;

* for every $A^+(c_t) \in \mathcal{A}_q$: since $A^+(t) \in \text{atoms}(q^+)$, either $A(t)$, $T(A(t))$, or $B(A(t))$ is in $q$. Moreover, as $\pi$ is a match for $q$ in $I'$, $c_t^J = \pi(t) \in A_{I_p'}^J$, so $c_t^J \in (A^+)^{I^{\prime \mathrm{cl}}} = (A^+)^J$;

* for every $A^-(c_t) \in \mathcal{A}_q$: since $A^-(t) \in \text{atoms}(q^+)$, either $F(A(t))$ or $B(A(t))$ is in $q$. Moreover, as $\pi$ is a match for $q$ in $I'$, $c_t^J = \pi(t) \in A_{I_n'}^J$, so $c_t^J \in (A^-)^{I^{\prime \mathrm{cl}}} = (A^-)^J$.

Thus, $\mathcal{J} \models \mathcal{A}_q$, whence $\mathcal{J} \models \mathcal{K}^{\mathrm{cl}} \cup \mathcal{A}_q$. In addition, for every term $t$ of $q$, we have that $c_t^J = \pi(t)$ (this follows from the definition of $c_t^J$ if $c_t \in \mathrm{IN}_q$ and otherwise, if $c_t = t \in \mathrm{IN}$, we have $t^J = t^{I^{\prime \mathrm{cl}}} = t^{I'} = \pi(t)$). Hence,

* for each $T(A(t)) \in \text{atoms}(q)$: since $\pi(t) \notin A_{I_n'}^J$ due to the definition of $I'$, it follows that $c_t^J = \pi(t) \notin (A^-)^{I^{\prime \mathrm{cl}}} = (A^-)^J$, i.e., $\mathcal{J} \not\models A^-(c_t)$;

* for each $F(A(t)) \in \text{atoms}(q)$: since $\pi(t) \notin A_{I_p'}^J$ by the definition of $I'$, it follows that $c_t^J = \pi(t) \notin (A^+)^{I^{\prime \mathrm{cl}}} = (A^+)^J$, i.e., $\mathcal{J} \not\models A^+(c_t)$;

* for every $N(A(t)) \in \text{atoms}(q)$: since $\pi(t) \notin A_{I_p'}^J \cup A_{I_n'}^J$ by definition of $I'$, it follows that $\mathcal{J} \not\models A^+(c_t)$ and $\mathcal{J} \not\models A^-(c_t)$.

It follows that $\mathcal{J} \not\models q_{\mathrm{ctr}}$, thus $\mathcal{K}^{\mathrm{cl}} \cup \mathcal{A}_q \not\models q_{\mathrm{ctr}}$.

($\Leftarrow$) For the converse direction, assume that $\mathcal{K}^{\mathrm{cl}} \models q^+$ and $\mathcal{K}^{\mathrm{cl}} \cup \mathcal{A}_q \not\models q_{\mathrm{ctr}}$. Note that there exist 4-models of $\mathcal{K}$ because $\mathcal{K}^{\mathrm{cl}}$ has classical models (otherwise it would hold that $\mathcal{K}^{\mathrm{cl}} \cup \mathcal{A}_q \models q_{\mathrm{ctr}}$) and the 4-counterparts of these models as defined in the proof of Proposition 2.7 are 4-models of $\mathcal{K}$. For every $\mathcal{I} \models_4 \mathcal{K}$, by Proposition 2.7, the classical counterpart $\mathcal{I}^{\mathrm{cl}}$ of $\mathcal{I}$ is a model of $\mathcal{K}^{\mathrm{cl}}$. Thus, since $\mathcal{K}^{\mathrm{cl}} \models q^+$, $\mathcal{I}^{\mathrm{cl}} \models q^+$. It follows that there is a match $\pi$ for $q^+$ in $\mathcal{I}^{\mathrm{cl}}$. Hence $\pi$ : terms($q$) $\mapsto$ $\Delta^{\mathcal{I}^{\mathrm{cl}}} = \Delta^{\mathcal{I}}$ is such that $\pi(c) = c^{\mathcal{I}^{\mathrm{cl}}} = c^{\mathcal{I}}$ for all $c \in \mathrm{IN}$, and

* $(\pi(t_1), \pi(t_2)) \in R^{\mathcal{I}^{\mathrm{cl}}} = R^{\mathcal{I}}$ for each $R(t_1, t_2) \in \text{atoms}(q)$;

* $\pi(t) \in (A^+)^{\mathcal{I}^{\mathrm{cl}}} = A_{I_p}^J$ for every $A(t) \in \text{atoms}^+(q)$; and

* $\pi(t) \in (A^-)^{\mathcal{I}^{\mathrm{cl}}} = A_{I_n}^J$ for every $A(t) \in \text{atoms}^-(q)$.

It follows that $\pi$ is a match for $q$ in $\mathcal{I}$ as required by item 1 of Definition 3.6.

Moreover, since $\mathcal{K}^{\mathrm{cl}} \cup \mathcal{A}_q \not\models q_{\mathrm{ctr}}$, there is a (classical) model $\mathcal{J} = \langle \Delta^{\mathcal{J}}, \cdot^{\mathcal{J}} \rangle$ of $\mathcal{K}^{\mathrm{cl}} \cup \mathcal{A}_q$ such that $\mathcal{J} \not\models q_{\mathrm{ctr}}$. Let now $\mathcal{J}^4 = \langle \Delta^{\mathcal{J}^4}, \cdot_{\mathcal{J}^4}^4, \cdot_{\mathcal{J}^4}^4 \rangle$ be the 4-counterpart of $\mathcal{J}$ as defined in the proof of Proposition 2.7. Since $\mathcal{J} \models \mathcal{K}^{\mathrm{cl}}$, we have shown in the proof of Proposition 2.7 that $\mathcal{J}^4 \models_4 \mathcal{K}$. Let $\pi$ : terms($\mathcal{q}$) $\mapsto$ $\Delta^{\mathcal{J}^4}$ be such that $\pi(t) = c_t^J$ for every term $t$ of $\mathcal{q}$. We show that $\pi$ is a match for $\mathcal{q}$ in $\mathcal{J}^4$ as required by item 2 of Definition 3.6.

* For every $c \in \mathrm{IN}$, $\pi(c) = c^J = c^{\mathcal{J}^4}$.

* For each $R(t_1, t_2) \in \text{atoms}(q)$, since $\mathcal{J} \models \mathcal{A}_q$ and $R(c_{t_1}, c_{t_2}) \in \mathcal{A}_q$, then $(\pi(t_1), \pi(t_2)) = (c_{t_1}^J, c_{t_2}^J) \in R^{\mathcal{J}} = R^{\mathcal{J}^4}$.
<table><caption>Table 1. Complexity of BUCQ entailment over classical KBs. See the surveys by Bienvenu and Ortiz (2015) for $\mathcal{ELHI}_{\perp}$ and its sublogics and by Ortiz and Šimkus (2012) for $\mathcal{ALC}$ and its extensions.</caption><thead><tr><th></th><th>Combined</th><th>Data</th></tr></thead><tbody><tr><td>ALCI, ALCHI</td><td>2ExpTime-c.</td><td>coNP-c.</td></tr><tr><td>ALC, ALCH</td><td>ExpTime-c.</td><td>coNP-c.</td></tr><tr><td>ELI<sub>⊥</sub>, ELHI<sub>⊥</sub></td><td>ExpTime-c.</td><td>P-c.</td></tr><tr><td>EL<sub>⊥</sub>, ELH<sub>⊥</sub></td><td>NP-c.</td><td>P-c.</td></tr><tr><td>DL-Lite<sub>core</sub></td><td>NP-c.</td><td>AC<sup>0</sup></td></tr></tbody></table>

<table><caption>Table 2. Complexity of BCQV entailment over four-valued KBs.</caption><thead><tr><th></th><th>Combined</th><th>Data</th></tr></thead><tbody><tr><td>ALCI<sup>4</sup><sub>Δ</sub>, ALCHI<sup>4</sup><sub>Δ</sub></td><td>2ExpTime-c.</td><td>BH<sub>2</sub>-c.</td></tr><tr><td>ALC<sup>4</sup><sub>Δ</sub>, ALCH<sup>4</sup><sub>Δ</sub></td><td>ExpTime-c.</td><td>BH<sub>2</sub>-c.</td></tr><tr><td>ELI<sub>-Δ</sub><sup>4</sup>, ELHI<sub>-Δ</sub><sup>4</sup></td><td>ExpTime-c.</td><td>P-c.</td></tr><tr><td>EL<sub>-Δ</sub><sup>4</sup>, ELH<sub>-Δ</sub><sup>4</sup></td><td>NP-c.</td><td>P-c.</td></tr><tr><td>DL-Lite<sub>core</sub><sup>4</sup></td><td>NP-c.</td><td>AC<sup>0</sup></td></tr></tbody></table>

* For each $A(t) \in \text{atoms}(q)$, $A^+(t) \in \text{atoms}(q^+)$, so $A^+(c_t) \in \mathcal{A}_q$ and since $\mathcal{J} \models \mathcal{A}_q$, then $\pi(t) = c_t^J \in (A^+)^J = \mathcal{A}_p^J$.

* For every $T(A(t)) \in \text{atoms}(q)$, $A^+(t) \in \text{atoms}(q^+)$. So, we obtain as above that $\pi(t) \in \mathcal{A}_p^J$. Moreover, since $\mathcal{J} \nvDash q_{\text{ctr}}$, and in particular $\mathcal{J} \nvDash A^-(c_t)$, we have $\pi(t) = c_t^J \notin (A^-)^J$, i.e., $\pi(t) \notin \mathcal{A}_p^J$.

* For every $F(A(t)) \in \text{atoms}(q)$, $A^-(t) \in \text{atoms}(q^-)$, so $A^-(c_t) \in \mathcal{A}_q$. Since $\mathcal{J} \models \mathcal{A}_q$, we thus have $\pi(t) = c_t^J \in (A^-)^J = \mathcal{A}_p^J$. Moreover, since $\mathcal{J} \nvDash q_{\text{ctr}}$, and in particular $\mathcal{J} \nvDash A^+(c_t)$, we have $\pi(t) = c_t^J \notin (A^+)^J$, i.e., $\pi(t) \notin \mathcal{A}_p^J$.

* For every $B(A(t)) \in \text{atoms}(q)$, $\{A^+(t), A^-(t)\} \subseteq \text{atoms}(q^+)$. So, we obtain as before that $\pi(t) \in (A^+)^J \cap (A^-)^J$, i.e., $\pi(t) \in \mathcal{A}_p^J \cap \mathcal{A}_p^J$.

* For every $N(A(t)) \in \text{atoms}(q)$, since $\mathcal{J} \nvDash q_{\text{ctr}}$, and in particular $\mathcal{J} \nvDash A^-(c_t)$ and $\mathcal{J} \nvDash A^+(c_t)$, $\pi(t) = c_t^J \notin (A^+)^J \cup (A^-)^J$, i.e., $\pi(t) \notin \mathcal{A}_p^J \cup \mathcal{A}_p^J$.

Hence, $\mathcal{K} \models_4 q$.

□

Using Theorem 4.2 and the complexity results for classical DL KBs recalled in Table 1, we obtain tight complexity results for BCQV entailment in $\mathcal{ALCHI}_{\Delta}^4$ and its sublogics, showing that answering queries with values over paraconsistent KBs is often not harder than standard BUCQ answering. The only case where we note a complexity increase is the data complexity of $\mathcal{ALC}$ and its extensions.

**THEOREM 4.3.** *The results stated in Table 2 hold.*

*PROOF.* By Theorem 4.2, $\mathcal{K} \models_4 q$ iff $\mathcal{K}^\text{cl} \models q^+$ and $\mathcal{K}^\text{cl} \cup \mathcal{A}_q \nvDash q_{\text{ctr}}$ so if BUCQ (Boolean union of conjunctive queries) entailment over classical $\mathcal{L}$ KBs is in a complexity class $\mathcal{C}$, BCQV entailment over $\mathcal{L}_{\Delta}^4$ KBs can be decided by a Turing machine with a $\mathcal{C}$-oracle (making one $\mathcal{C}$-call and one co-$\mathcal{C}$-call). Recall that if $\mathcal{K}$ is an $\mathcal{L}_{\Delta}^4$ KB with $\mathcal{L} \in \{\mathcal{ELHI}, \mathcal{ELI}, \mathcal{ELH}, \mathcal{EL}\}$, $\mathcal{K}^\text{cl}$ is an $\mathcal{L}_{\perp}$ KB. Moreover, $q_{\text{ctr}}$ is actually a disjunction of at most 2 $|q|$ assertions and in the case of Horn DLs, $\mathcal{K}^\text{cl} \cup \mathcal{A}_q \nvDash q_{\text{ctr}}$ iff $\mathcal{K}^\text{cl} \cup \mathcal{A}_q \nvDash \alpha$ for every assertion $\alpha$ that occurs in $q_{\text{ctr}}$.
<table><caption>Table 3. Complexity of BCQ entailment under repair-based inconsistency-tolerant semantics (for comparison, cf. Section 5). These results can be found in (Bienvenu and Bourgaux 2016; Rosati 2011) or are simple adaptations of existing results.</caption><thead><tr><th></th><th>AR</th><th>Combined<br>IAR</th><th>brave</th><th>AR</th><th>Data<br>IAR</th><th>brave</th></tr></thead><tbody><tr><td>ALCI, ALCHI</td><td>2ExpTime-c.</td><td>2ExpTime-c.</td><td>2ExpTime-c.</td><td>Π<sub>2</sub><sup>P</sup>-c.</td><td>Π<sub>2</sub><sup>P</sup>-c.</td><td>Σ<sub>2</sub><sup>P</sup>-c.</td></tr><tr><td>ALC, ALCH</td><td>ExpTime-c.</td><td>ExpTime-c.</td><td>ExpTime-c.</td><td>Π<sub>2</sub><sup>P</sup>-c.</td><td>Π<sub>2</sub><sup>P</sup>-c.</td><td>Σ<sub>2</sub><sup>P</sup>-c.</td></tr><tr><td>ELI<sub>⊥</sub>, ELHI<sub>⊥</sub></td><td>ExpTime-c.</td><td>ExpTime-c.</td><td>ExpTime-c.</td><td>coNP-c.</td><td>coNP-c.</td><td>NP-c.</td></tr><tr><td>EL<sub>⊥</sub>, ELH<sub>⊥</sub></td><td>Π<sub>2</sub><sup>P</sup>-c.</td><td>Δ<sub>2</sub><sup>P</sup>[O(log(n))]-c.</td><td>NP-c.</td><td>coNP-c.</td><td>coNP-c.</td><td>NP-c.</td></tr><tr><td>DL-Lite<sub>core</sub></td><td>Π<sub>2</sub><sup>P</sup>-c.</td><td>NP-c.</td><td>NP-c.</td><td>coNP-c.</td><td>AC<sup>0</sup></td><td>AC<sup>0</sup></td></tr></tbody></table>

Since assertion entailment can be done in polynomial time w.r.t. combined complexity for $\mathcal{EL}_⊥$, $\mathcal{ELH}_⊥$ and DL-Lite<sub>core</sub> (Baader, Brandt, et al. 2005; Calvanese et al. 2007), the NP-call to decide $\mathcal{K}^c \models q^+$ and the P-calls to decide $\mathcal{K}^c \cup \mathcal{A}_q \nvDash \alpha$ for each $\alpha$ can be combined in a single NP-call.

Lower bounds for $\mathcal{L}$ transfer to $\mathcal{L}_\Delta^4$ by Lemma 2.8: given an $\mathcal{L}$ KB $\mathcal{K}$ and BCQ $\mathbf{q}$, $\mathcal{K} \models q$ iff $\mathcal{K}^\Delta \models_4 q$ (since there exists a match for $\mathbf{q}$ in every model $\mathcal{I}$ of $\mathcal{K}$ iff there exists a match for $\mathbf{q}$ in the positive extension of every 4-model $\mathcal{I}_4$ of $\mathcal{K}^\Delta$).

We obtain the remaining $BH_2$ lower bound via a reduction from the $BH_2$-complete problem SAT-UNSAT: given a pair $(\varphi_1, \varphi_2)$ of propositional formulas, decide whether $\varphi_1$ is satisfiable and $\varphi_2$ is unsatisfiable. We assume that $\varphi_1$ and $\varphi_2$ are sets of clauses such that each clause has exactly 2 positive and 2 negative literals, and any of the four positions in a clause can be filled instead by one of the truth constants true and false (this is w.l.o.g. since 2+2SAT is NP-complete (Schaerf 1993)). Let $\varphi_1$ and $\varphi_2$ be two set of clauses $\{c_1^1, \dots, c_{m_1}^1\}$ and $\{c_1^2, \dots, c_{m_2}^2\}$ respectively, over variables $x_1^1, \dots, x_{n_1}^1$ and $x_1^2, \dots, x_{n_2}^2$ respectively. We define an $\mathcal{ALC}_\Delta^4$ knowledge base $\mathcal{K} = (\mathcal{T}, \mathcal{A})$ and a BCQ $\mathbf{q}$ as follows:

$$
\begin{align*}
\mathcal{A} &= \{\text{Var}(x_j^i) \mid 1 \le i \le 2, 1 \le j \le n_i\} \cup \{\text{F}(f), \text{T}(t)\} \\
&\quad \cup \{\text{Sat}(\varphi_1)\} \cup \{\text{Cl}(\varphi_i, c_k^i) \mid 1 \le i \le 2, 1 \le k \le m_i\} \cup \\
&\quad \cup \{\text{P}_l(c_k^i, x_j^i) \mid l \in \{1, 2\}, x_j^i \text{ is the } l^{th} \text{ positive literal of } c_k^i\} \cup \\
&\quad \cup \{\text{N}_l(c_k^i, x_j^i) \mid l \in \{1, 2\}, \neg x_j^i \text{ is the } l^{th} \text{ negative literal of } c_k^i\} \\
\mathcal{T} &= \{\text{Var} \sqsubseteq \text{T} \sqcup \text{F}, \text{T} \sqsubseteq \neg \text{F}, \text{F} \sqsubseteq \neg \text{T}\} \cup \\
&\quad \cup \{\exists \text{P}_1. \text{F} \sqcap \exists \text{P}_2. \text{F} \sqcap \exists \text{N}_1. \text{T} \sqcap \exists \text{N}_2. \text{T} \sqsubseteq \text{NotSat}\} \cup \\
&\quad \cup \{\exists \text{Cl}. \text{NotSat} \sqsubseteq \text{NotSat}, \text{NotSat} \sqsubseteq \neg \text{Sat}\} \\
\mathbf{q} &= \text{T}(\text{Sat}(\varphi_1)) \wedge \text{NotSat}(\varphi_2)
\end{align*}
$$

We show that $\mathcal{K} \models_4 q$ iff $\varphi_1$ is satisfiable and $\varphi_2$ is unsatisfiable.

(⇒) Assume that $\mathcal{K} \models_4 q$. Since $\mathcal{K} \models_4 \text{T}(\text{Sat}(\varphi_1))$, by item 2 of Definition 3.6, there exists a 4-model $\mathcal{I} = (\Delta^I, \cdot_{I_p}, \cdot_{I_n})$ of $\mathcal{K}$ such that $\varphi_1^I \notin \text{Sat}^{I_n}$. Since $\mathcal{I} \models_4 \text{NotSat} \sqsubseteq \neg \text{Sat}$, it follows that $\varphi_1^I \notin \text{NotSat}^{I_p}$. Hence, for every $1 \le k \le m_1$, $c_k^1 \notin \text{NotSat}^{I_p}$. It follows that for every $1 \le k \le m_1$, at least one of the following conditions holds: either (i) $x_j^1$ is a positive literal of $c_k^1$ and $x_j^1 \notin \text{T}^{I_p}$, so $x_j^1 \in \text{T}^{I_p}$ (since either $x_j^1 \in \text{Var}^{I_p}$ or $x_j^1 = t$) or (ii) $\neg x_j^1$ is a negative literal of $c_k^1$ and $x_j^1 \notin \text{T}^{I_p}$, so $x_j^1 \in \text{T}^{I_p}$ (since either $x_j^1 \in \text{Var}^{I_p}$ or $x_j^1 = f$). Let $\nu$ be the valuation of $x_1^1, \dots, x_{n_1}^1$ defined by $\nu(x_j^1) = \text{true}$ iff $x_j^1 \in \text{T}^{I_p}$. For every $1 \le k \le m_1$, if we are in case (i), there is
a positive literal $x_j^1$ of $c_k^1$ such that $v(x_j^1) = \text{true}$, and if we are in case (ii), there is a negative literal $\neg x_j^1$ of $c_k^1$ such that $v(x_j^1) = \text{false}$. Hence, $v$ satisfies all clauses of $\varphi_1$, so $\varphi_1$ is satisfiable.

Next let $v$ be a valuation of $x_1^2, \dots, x_{n_2}^2$, and define a 4-interpretation $\mathcal{I}^v$ as follows:

* $\Delta^{\mathcal{I}^v}$ is the set of individuals that occur in $\mathcal{A}$,

* $A_n^{\mathcal{I}^v} = \Delta^{\mathcal{I}^v}$ for every $A \in \text{CN}$,

* $\text{Var}_{\ell}^{\mathcal{I}^v}, \text{P}_{\ell}^{\mathcal{I}^v}, \text{N}_{\ell}^{\mathcal{I}^v}, \text{CI}^{\mathcal{I}^v}$ and $\text{Sat}_{\ell}^{\mathcal{I}^v}$ correspond exactly to the assertions in $\mathcal{A}$,

* $\mathcal{T}_{\ell}^{\mathcal{I}^v} = \{t\} \cup \{x_j^2 \mid v(x_j^2) = \text{true}\} \cup \{x_1^1, \dots, x_{n_1}^1\}$,

* $\mathcal{F}_{\ell}^{\mathcal{I}^v} = \{f\} \cup \{x_j^2 \mid v(x_j^2) = \text{false}\} \cup \{x_1^1, \dots, x_{n_1}^1\}$, and

* $\text{NotSat}_{\ell}^{\mathcal{I}^v} = \{c_k^2 \mid v(c_k^2) = \text{false}\} \cup \{\varphi_2 \mid \text{if } v(\varphi_2) = \text{false}\} \cup \{\varphi_1, c_1^1, \dots, c_{m_1}^1\}$.

It is easy to check that $\mathcal{I}^v \models_4 \mathcal{K}$. Hence, since $\mathcal{K} \models_4 \text{NotSat}(\varphi_2)$, by item 1 of Definition 3.6, it must be the case that $\varphi_2^{\mathcal{I}^v} \in \text{NotSat}_{\ell}^{\mathcal{I}^v}$, i.e., $v$ falsifies $\varphi_2$. Since this is true for every valuation $v$, $\varphi_2$ is unsatisfiable.

($\Leftarrow$) Assume that $\varphi_1$ is satisfiable and $\varphi_2$ is unsatisfiable. Take a valuation $v$ of $x_1^1, \dots, x_{n_1}^1$ that satisfies $\varphi_1$, and let $\mathcal{I}^v$ be the 4-interpretation defined as follows:

* $\Delta^{\mathcal{I}^v}$ is the set of individuals that occur in $\mathcal{A}$,

* $A_n^{\mathcal{I}^v} = \Delta^{\mathcal{I}^v}$ for every $A \in \text{CN}$ except $\text{Sat}$, for which we define $\text{Sat}_n^{\mathcal{I}^v} = \{\varphi_2, c_1^2, \dots, c_{m_2}^2\}$,

* $\text{Var}_{\ell}^{\mathcal{I}^v}, \text{P}_{\ell}^{\mathcal{I}^v}, \text{N}_{\ell}^{\mathcal{I}^v}, \text{CI}^{\mathcal{I}^v}$ and $\text{Sat}_{\ell}^{\mathcal{I}^v}$ correspond exactly to the assertions in $\mathcal{A}$,

* $\mathcal{T}_{\ell}^{\mathcal{I}^v} = \{t\} \cup \{x_j^1 \mid v(x_j^1) = \text{true}\} \cup \{x_1^2, \dots, x_{n_2}^2\}$,

* $\mathcal{F}_{\ell}^{\mathcal{I}^v} = \{f\} \cup \{x_j^1 \mid v(x_j^1) = \text{false}\} \cup \{x_1^2, \dots, x_{n_2}^2\}$, and

* $\text{NotSat}_{\ell}^{\mathcal{I}^v} = \{\varphi_2, c_1^2, \dots, c_{m_2}^2\}$.

It is easy to check that $\mathcal{I}^v \models_4 \mathcal{K}$. In particular, since $v$ satisfies every clause of $\varphi_1$, there is no $c_k^1$ such that $c_k^1 \models_{\ell}^{\mathcal{I}^v} \in (\exists P_1 \land \exists P_2 \land \exists N_1 \land \exists N_2 \land \mathcal{T}) \models_{\ell}^{\mathcal{I}^v}$. It is thus a 4-model of $\mathcal{K}$ such that $\varphi_1^{\mathcal{I}^v} \notin \text{Sat}_{n}^{\mathcal{I}^v}$. Since every 4-model $\mathcal{I}$ of $\mathcal{K}$ is such that $\varphi_1^{\mathcal{I}} \in \text{Sat}_{\ell}^{\mathcal{I}}$ because $\text{Sat}(\varphi_1) \in \mathcal{A}$, it follows by Definition 3.6 that $\mathcal{K} \models_4 \text{T}(\text{Sat}(\varphi_1))$.

Next let $\mathcal{I} = (\Delta^{\mathcal{I}}, \mathcal{I}_p, \mathcal{I}_n)$ be a 4-model of $\mathcal{K}$, and let $v$ be the valuation of $x_1^2, \dots, x_{n_2}^2$ defined by $v(x_j^2) = \text{true}$ iff $x_j^2 \in \mathcal{T}_{\ell}^{\mathcal{I}_p}$. Since $\varphi_2$ is unsatisfiable, there exists $c_k^2$ such that $v(c_k^2) = \text{false}$. It follows that for every positive literal $x_j^2$ of $c_k^2$, $v(x_j^2) = \text{false}$ i.e., $x_j^2 \notin \mathcal{T}_{\ell}^{\mathcal{I}_p}$, which implies $x_j^2 \in \mathcal{F}_{\ell}^{\mathcal{I}_p}$, and for every negative literal $\neg x_j^2$ of $c_k^2$, $v(x_j^2) = \text{true}$, i.e., $x_j^2 \in \mathcal{T}_{\ell}^{\mathcal{I}_p}$. Hence, $c_k^2 \in \text{NotSat}_{\ell}^{\mathcal{I}_p}$, so that $\varphi_2^{\mathcal{I}} \in \text{NotSat}_{\ell}^{\mathcal{I}_p}$. It follows by Definition 3.6 that $\mathcal{K} \models_4 \text{NotSat}(\varphi_2)$. We may therefore conclude that $\mathcal{K} \models_4 \mathbf{q}$. $\square$

# 5 Comparison With Repair-Based Semantics

In this section, we compare paraconsistent querying semantics with existing repair-based semantics. When dealing with repair-based semantics, we assume a *classically consistent* TBox, i.e., we assume that if a KB is inconsistent, it is due to errors in the ABox. For our comparison, we will naturally consider the popular AR semantics, which deems a tuple to be an answer if it holds w.r.t. every repair, i.e., w.r.t. every inclusion-maximal subset of the ABox consistent with the TBox. We shall further consider repair-based semantics that provide minimal under-approximation and maximal over-approximations of AR (Bienvenu and Bourgaux 2016): IAR, brave and CAR. The IAR semantics retains only the “safest” answers that are true in the intersection of the repairs, while the brave semantics considers all answers that hold in at least one repair. Finally, the CAR semantics over-approximates the AR semantics in a way that is incomparable with brave, by incorporating a closure operation on the ABox. The latter semantics may seem closer in spirit to paraconsistent reasoning, where the positive extensions retain all consequences of the axioms.
The formal definitions of repairs and the considered repair-based semantics follow. Recall that ABox $\mathcal{A}$ is called $\mathcal{T}$-consistent if the KB $\langle \mathcal{T}, \mathcal{A} \rangle$ is (classically) consistent. In the next definition, $C_{\mathcal{T}}^*(\mathcal{A})$ is the consistent closure of the ABox w.r.t. the TBox, which is used to define the closed repairs on which the CAR semantics is based. Closed repairs can be seen as maximally ‘completing’ the standard repairs with additional facts from $C_{\mathcal{T}}^*(\mathcal{A})$.

**Definition 5.1 (Repairs).** Let $\mathcal{K} = \langle \mathcal{T}, \mathcal{A} \rangle$ and define

$$C_{\mathcal{T}}^*(\mathcal{A}) = \{ \phi \mid \phi \text{ is an assertion such that } \langle \mathcal{T}, \mathcal{A}' \rangle \models \phi \text{ for some } \mathcal{T}\text{-consistent } \mathcal{A}' \subseteq \mathcal{A} \}$$

A repair of $\mathcal{K}$ is a maximal $\mathcal{T}$-consistent subset of $\mathcal{A}$. A closed repair of $\mathcal{K}$ is a $\mathcal{T}$-consistent $\mathcal{R} \subseteq C_{\mathcal{T}}^*(\mathcal{A})$ for which there is no $\mathcal{T}$-consistent $\mathcal{R}' \subseteq C_{\mathcal{T}}^*(\mathcal{A})$ such that either (1) $\mathcal{R} \cap \mathcal{A} \subseteq \mathcal{R}' \cap \mathcal{A}$ or (2) $\mathcal{R} \cap \mathcal{A} = \mathcal{R}' \cap \mathcal{A}$ and $\mathcal{R} \subseteq \mathcal{R}'$. We denote the set of all repairs (resp. closed repairs) of $\mathcal{K}$ with $\text{Rep}(\mathcal{K})$ (resp. $\text{CRep}(\mathcal{K})$).

**Definition 5.2 (Repair semantics).** Let $\mathcal{q}$ be a Boolean CQ.

* $\mathcal{K} \models_{\text{AR}} \mathcal{q}$ if $\langle \mathcal{T}, \mathcal{A}' \rangle \models \mathcal{q}$ for every $\mathcal{A}' \in \text{Rep}(\mathcal{K})$.

* $\mathcal{K} \models_{\text{brave}} \mathcal{q}$ if $\langle \mathcal{T}, \mathcal{A}' \rangle \models \mathcal{q}$ for some $\mathcal{A}' \in \text{Rep}(\mathcal{K})$.

* $\mathcal{K} \models_{\text{IAR}} \mathcal{q}$ if $\left( \mathcal{T}, \bigcap_{\mathcal{A}' \in \text{Rep}(\mathcal{K})} \mathcal{A}' \right) \models \mathcal{q}$.

* $\mathcal{K} \models_{\text{CAR}} \mathcal{q}$ if $\langle \mathcal{T}, \mathcal{R} \rangle \models \mathcal{q}$ for every $\mathcal{R} \in \text{CRep}(\mathcal{K})$.

We recall the relations that hold between these semantics.

$$\mathcal{K} \models_{\text{IAR}} \mathcal{q} \implies \mathcal{K} \models_{\text{AR}} \mathcal{q} \iff \mathcal{K} \models_{\text{brave}} \mathcal{q} \\ \mathcal{K} \models_{\text{CAR}} \mathcal{q}$$

We start by remarking that $\models_{\text{4}}$ over-approximates $\models_{\text{brave}}$ in Horn DLs.

**THEOREM 5.3.** If $\mathcal{K}$ is an $\mathcal{ELHI}_-$ KB and $\mathcal{q}$ is a BCQ, then $\mathcal{K} \models_{\text{brave}} \mathcal{q}$ implies $\mathcal{K} \models_{\text{4}} \mathcal{q}$.

**PROOF.** Assume that $\mathcal{K} \models_{\text{brave}} \mathcal{q}$: there is a classically consistent subset $\mathcal{K}' \subseteq \mathcal{K}$ such that $\mathcal{K}' \models \mathcal{q}$. By Proposition 3.10, $\mathcal{K}' \models_{\text{4}} \mathcal{q}$ because $\mathcal{q}$ does not contain any value operator. It follows that $\mathcal{K} \models_{\text{4}} \mathcal{q}$. Indeed, every 4-model of $\mathcal{K}$ is a 4-model of $\mathcal{K}'$ and since $\mathcal{q}$ does not contain any value operator, item 2 of Definition 3.6 is vacuously true. $\square$

Note that Theorem 5.3 and Proposition 3.2 are a way to see that in Horn DLs, dropping the negative inclusions $A \sqsubseteq \neg B$ provides an over-approximation of brave. However, we cannot generalise Theorem 5.3 beyond Horn DLs. Indeed, recall that $\models_{\text{4}}$ and $\models$ differ on consistent KBs (cf. Example 3.11) for languages with $\sqcup$, while all repair-based semantics coincide with $\models$ on consistent KBs.

Theorem 5.3 indicates that if we consider CQs without values, in line with the prior work of (Nguyen and Szałas 2012; Zhou et al. 2012), then the four-valued semantics ($\models_{\text{4}}$) is more permissive than brave. Thus, a natural idea for bringing closer paraconsistent reasoning and repair-based reasoning is to add T on query atoms to strengthen the requirements on answers. We quickly observe that in this case, $\models_{\text{4}}$ no longer over-approximates (in contrast with Theorem 5.3) even the ‘safest’ semantics IAR, while it does not under-approximate the ‘loosest’ semantics brave and CAR. For example, consider the following knowledge base: $\mathcal{K}_{\text{ic}} = \{ \langle C \sqsubseteq A, C \sqsubseteq \neg A, C \sqsubseteq \neg B \rangle, \{C(a), B(a)\} \}$. The only (closed) repair of $\mathcal{K}_{\text{ic}}$ is $\{B(a)\}$ so $\mathcal{K}_{\text{ic}} \models_{\text{IAR}} B(a)$ while $\mathcal{K}_{\text{ic}} \not\models_{\text{brave}} C(a)$ and $\mathcal{K}_{\text{ic}} \not\models_{\text{CAR}} C(a)$. On the other hand, $\mathcal{K}_{\text{ic}} \not\models_{\text{4}} T(B(a))$ while $\mathcal{K}_{\text{ic}} \models_{\text{4}} T(C(a))$. However, this example relies on the use of a concept name unsatisfiable w.r.t. the TBox, which may be not so common in practice. We thus next investigate the case of coherent KBs, i.e., KBs where all concept names are satisfiable w.r.t. the TBox.

We show that even for coherent KBs, answering CQs under repair-based semantics and answering CQVs over paraconsistent DL KBs are incomparable. Moreover, we show this not only for the paraconsistent DLs we study
in this paper but for a wider class of such logics. The following definition, inspired by Gottwald (2001, Chapter 3) and Skurt (2020, §1.5.2), will allow us to state our incomparability results in a general setting, by abstracting from the way extensions (and especially negative extensions) of complex concepts are defined.

**Definition 5.4.** For a concept C and a 4-interpretation *I*, let $C^I_T = C^I_p \setminus C^I_n$ and $C^I_F = C^I_n \setminus C^I_p$. We say that

* a unary connective $\neg$ is

- NEG-normal if $x \in C^I_T$ implies $x \in (-C)^{I_F}$ and $x \in C^I_F$ implies $x \in (-C)^{I_T}$;

- NEG-standard if $(-C)^{I_p} = \Delta^I \setminus C^{I_p}$;

- self-dual if $(-C)^{I_p} = C^{I_n}$ and $(-C)^{I_n} = C^{I_p}$;

* a binary connective $\oplus$ is

- AND-normal if $x \in C^I_T \cap D^{I_T}$ implies $x \in (C \oplus D)^{I_T}$ and $x \in C^I_F \cup D^{I_F}$ implies $x \in (C \oplus D)^{I_F}$;

- AND-standard if $(C \oplus D)^{I_p} = C^{I_p} \cap D^{I_p}$;

- OR-normal if $x \in C^I_T \cup D^{I_T}$ implies $x \in (C \oplus D)^{I_T}$ and $x \in C^I_F \cap D^{I_F}$ implies $x \in (C \oplus D)^{I_F}$;

- OR-standard if $(C \oplus D)^{I_p} = C^{I_p} \cup D^{I_p}$;

* a quantifier $\heartsuit_S$ is

- ALL-normal if $\forall y((x, y) \in S^I \Rightarrow y \in C^I_T)$ implies $x \in (\heartsuit_S C)^{I_T}$ and $\exists y((x, y) \in S^I \& y \in C^I_F)$ implies $x \in (\heartsuit_S C)^{I_F}$;

- ALL-standard if $(\heartsuit_S C)^{I_p} = \{x \mid \forall y : (x, y) \in S^I \Rightarrow y \in C^{I_p}\}$;

- EX-normal if $\exists y((x, y) \in S^I \& y \in C^I_T)$ implies $x \in (\heartsuit_S C)^{I_T}$ and $\forall y((x, y) \in S^I \Rightarrow y \in C^{I_F})$ implies $x \in (\heartsuit_S C)^{I_F}$;

- EX-standard if $(\heartsuit_S C)^{I_p} = \{x \mid \exists y : (x, y) \in S^I \& y \in C^{I_p}\}$.

Considering $\mathcal{A}LCHI_\Delta^4$ connectives, we can observe that: $\neg$, $\sqcap$, $\sqcup$, $\exists$, $\forall$ are NEG-, AND-, OR-, EX- and ALL-normal respectively, while $\sqcap$, $\sqcup$, $\exists$, $\forall$ are AND-, OR-, EX- and ALL-standard respectively, and $\neg$ is not NEG-standard but is self-dual. Note that normality and standardness do not imply one another: the strong interpretation of disjunction used by Zhang, Xiao, et al. (2014) is OR-normal but not OR-standard, while $\oplus$ defined by Omori and Sano (2015) is AND-standard but not AND-normal.

The next theorem states our incomparability result when value operators are allowed in queries: even for atomic concept queries over coherent Horn DL KBs, when we put T on top of the query atom, $\models_4$ does not over-approximate IAR, nor does it under-approximate brave and CAR.

**Definition 5.5.** Given a set of connectives $\mathcal{C} = \{-, \otimes, \oplus, \boxdot, \diamond_S\}$ and an $\mathcal{A}LCHI$ concept C, we denote by $C^\mathcal{C}$ the concept obtained from C by replacing $\neg$ with $-$, $\sqcap$ with $\otimes$, $\sqcup$ with $\oplus$, $\forall$S with $\boxdot_S$, and $\exists$S with $\diamond_S$. We say that a query entailment relation $\models_Y$ T-over-approximates (resp. T-under-approximates) $\models_X$ under $\mathcal{C}$ if $\mathcal{K} \models_X A(a)$ implies $\mathcal{K}^\mathcal{C} \models_Y T(A(a))$ (resp. $\mathcal{K}^\mathcal{C} \models_Y T(A(a))$ implies $\mathcal{K} \models_X A(a)$) for any KB $\mathcal{K}$ and Boolean atomic concept query $A(a)$, where $\mathcal{K}^\mathcal{C}$ is obtained from $\mathcal{K}$ by replacing every concept C by $C^\mathcal{C}$.

**THEOREM 5.6.** It holds that:

* $\models_4$ does not T-over-approximate $\models_{IAR}$, and

* $\models_4$ does not T-under-approximate $\models_{brave}$ and $\models_{CAR}$

under $\mathcal{C}$ when $\sqsubseteq$ is the internal inclusion and for

(1) coherent DL-Lite$_{core}$ ontologies if $-$ is self-dual and $\diamond_S$ is EX-normal or EX-standard,

(2) coherent propositional Horn ontologies if $-$ is self-dual and $\otimes$ is AND-standard.

This holds even if the ontologies are required to be closed under contraposition, that is, if $C \sqsubseteq \neg D \in \mathcal{T}$ implies that $D \sqsubseteq \neg C \in \mathcal{T}$.

**PROOF.** To show that $\models_4$ does not T-under-approximate $\models_{CAR}$ (in both cases (1) and (2) of the theorem), consider $\mathcal{K} = \langle \mathcal{T}, \mathcal{A} \rangle$ defined by $\mathcal{T} = \{A \sqsubseteq C, B \sqsubseteq \neg C, C \sqsubseteq \neg B\}$ and $\mathcal{A} = \{A(a), B(a)\}$. Since $C^*_{\mathcal{T}}(\mathcal{A}) =$
`{A(a), B(a), C(a)}, K has two closed repairs: {A(a), C(a)} and {B(a)}. Hence K ≠<sub>CAR</sub> A(a). However, we can show that K<sup>C</sup> =<sub>4</sub> T(A(a)). Indeed, for every 4-model I of K<sup>C</sup>, a<sup>I</sup> ∈ A<sup>I<sub>p</sub></sup> and the following 4-model J of K<sup>C</sup> is such that a<sup>J</sup> ∉ A<sup>J<sub>n</sub></sup>: A<sup>J<sub>n</sub></sup> = ∅ and A<sup>J<sub>p</sub></sup> = B<sup>J<sub>p</sub></sup> = C<sup>J<sub>p</sub></sup> = B<sup>J<sub>n</sub></sup> = C<sup>J<sub>n</sub></sup> = {a<sup>J</sup>}.`

To show that $|\equiv_4$ does not T-under-approximate $|\equiv_{\text{brave}}$ in case (1), consider the DL-Lite<sub>core</sub> knowledge base $\mathcal{K}_1 = \langle \mathcal{T}_1, \mathcal{A}_1 \rangle$ defined as follows (note that all concepts that occur in $\mathcal{T}_1$ are satisfiable w.r.t. $\mathcal{T}_1$):

$$ \mathcal{T}_1 = \{\exists R. T \sqsubseteq B, \exists R'. T \sqsubseteq C, B \sqsubseteq A, B \sqsubseteq \neg C, C \sqsubseteq \neg B\} $$

$$ \mathcal{A}_1 = \{R(a, a)\} $$

It is easy to check that the only repair of $\mathcal{K}_1$ is the empty set, so $\mathcal{K}_1 \not\equiv_{\text{brave}} A(a)$. However, we can show that $\mathcal{K}_1^C = |\equiv_4 T(A(a))$. Indeed, for every 4-model $\mathcal{I}$ of $\mathcal{K}_1^C$, since $(a^I, a^J) \in R^I$, by ex-standardness or normality of ♦<sub>R</sub>, $a^I \in (\diamond_R T)^{I_p}$ so $a^I \in B^{I_p}$ and $a^I \in A^{I_p}$. Moreover, the following 4-model $\mathcal{J}$ of $\mathcal{K}_1^C$ is such that $a^J \notin A^{J_n}$: $R^J = \{(a^J, a^I)\}, A^{J_p} = \{a^J\}, B^{J_p} = B^{J_n} = C^{J_p} = C^{J_n} = \{a^J\}$.

To show that $|\equiv_4$ does not T-over-approximate $|\equiv_{\text{IAR}}$ in case (1), consider $\mathcal{K}'_1 = \langle \mathcal{T}'_1, \mathcal{A}'_1 \rangle$ with $\mathcal{T}'_1 = \mathcal{T}_1 \cup \{A \sqsubseteq \neg G, G \sqsubseteq \neg A\}$ and $\mathcal{A}'_1 = \mathcal{A}_1 \cup \{G(a)\}$. The only repair is $\{G(a)\}$ so $\mathcal{K}'_1 |\equiv_{\text{IAR}} G(a)$. However, we can show that $\mathcal{K}'_1^C \not= |\equiv_4 T(G(a))$. Indeed, for every 4-model $\mathcal{I}$ of $\mathcal{K}'_1^C$, we obtain as above that $a^I \in A^{I_p}$ so by self-duality of $-$, $a^I \in G^{I_n}$.

To show that $|\equiv_4$ does not T-under-approximate $|\equiv_{\text{brave}}$ in case (2), consider the propositional Horn knowledge base $\mathcal{K}_2 = \langle \mathcal{T}_2, \mathcal{A}_2 \rangle$ defined as follows (note that all concepts that occur in $\mathcal{T}_2$ are satisfiable w.r.t. $\mathcal{T}_2$):

$$ \mathcal{T}_2 = \{D \sqsubseteq B, E \sqsubseteq C, B \sqcap C \sqsubseteq A, D \sqsubseteq \neg E, E \sqsubseteq \neg D\} $$

$$ \mathcal{A}_2 = \{D(a), E(a)\} $$

It is easy to check that $\mathcal{K}_2$ has two repairs, $\{D(a)\}$ and $\{E(a)\}$, so $\mathcal{K}_2 \not\equiv_{\text{brave}} A(a)$. However, we can show that $\mathcal{K}_2^C = |\equiv_4 T(A(a))$. Indeed, for every 4-model $\mathcal{I}$ of $\mathcal{K}_2^C$, $a^I$ belongs to $D^{I_p}$ so to $B^{I_p}$ and to $E^{I_p}$ so to $C^{I_p}$. Hence, $a^I \in B^{I_p} \cap C^{I_p}$ so by and-standardness of ⊗, $a^I \in (B \otimes C)^{I_p}$. It follows that $a^I \in A^{I_p}$. Moreover, the following 4-model $\mathcal{J}$ of $\mathcal{K}_2^C$ is such that $a^J \notin A^{J_n}$: $A^{J_n} = B^{J_n} = C^{J_n} = D^{J_n} = E^{J_n} = \{a^J\}$, $A^{J_n} = B^{J_n} = C^{J_n} = \emptyset$ and $D^{J_n} = E^{J_n} = \{a^J\}$

To show that $|\equiv_4$ does not T-over-approximate $|\equiv_{\text{IAR}}$ in case (2), consider $\mathcal{K}'_2 = \langle \mathcal{T}'_2, \mathcal{A}'_2 \rangle$ with $\mathcal{T}'_2 = \mathcal{T}_2 \cup \{A \sqsubseteq \neg G, G \sqsubseteq \neg A\}$ and $\mathcal{A}'_2 = \mathcal{A}_2 \cup \{G(a)\}$. There are two repairs, $\{D(a), G(a)\}$ and $\{E(a), G(a)\}$, so $\mathcal{K}'_2 |\equiv_{\text{IAR}} G(a)$. However, we can show that $\mathcal{K}'_2^C \not= |\equiv_4 T(G(a))$. Indeed, for every 4-model $\mathcal{I}$ of $\mathcal{K}'_2^C$, we obtain as above that $a^I \in A^{I_p}$ so by self-duality of $-$, $a^I \in G^{I_n}$. □

The preceding incomparability result holds even for quite inexpressive description logics. We observe however that by restricting to an even simpler ontology language we can identify a case where $|\equiv_4$ is a T-over- and T-under-approximation of known repair semantics.

**PROPOSITION 5.7.** Let $\mathcal{K} = \langle \mathcal{T}, \mathcal{A} \rangle$ be such that $\mathcal{T}$ is coherent and consists of concept inclusions of the form $A \sqsubseteq B$ or $A \sqsubseteq \neg B$ with $A, B \in \mathbb{C}N$. Then the following relation holds:

$$ \mathcal{K} |\equiv_{\text{AR}} A(a) \implies \mathcal{K} |\equiv_4 T(A(a)) \implies \mathcal{K} |\equiv_{\text{brave}} A(a) $$

**PROOF.** Given a KB $\mathcal{K} = \langle \mathcal{T}, \mathcal{A} \rangle$ of the stated form, define a 'canonical' 4-interpretation $\mathcal{I}_{\min} = \langle \Delta^{\mathcal{I}_{\min}}, \cdot^{\mathcal{I}_{\min}}, \cdot^{\mathcal{I}_{\min}} \rangle$ as follows:

* $\Delta^{\mathcal{I}_{\min}} = \mathbb{N} \text{ and } a^{\mathcal{I}_{\min}} = a^{\mathcal{I}_{\min}} = a \text{ for all } a \in \mathbb{N}.$

* $A^{\mathcal{I}_{\min}} = \{a \mid \text{ there exists } B(a) \in \mathcal{A} \text{ such that } \mathcal{T} \models B \sqsubseteq A\}$

* $A^{\mathcal{I}_{\min}} = \{a \mid \text{ there exists } B(a) \in \mathcal{A} \text{ such that } \mathcal{T} \models B \sqsubseteq \neg A\}$
It is easy to see that $I_{\min}$ is a 4-model of $\mathcal{K}$.

To prove the first implication, let us suppose that $\mathcal{K} \not\models_4 T(A(a))$ and further that $\mathcal{K} \models_{\text{brave}} A(a)$ (since if $\mathcal{K} \not\models_{\text{brave}} A(a)$, then we trivially have $\mathcal{K} \not\models_{\text{AR}} A(a)$). We can infer from $\mathcal{K} \not\models_4 T(A(a))$ and $\mathcal{K} \models_{\text{brave}} A(a)$ (which implies $\mathcal{K} \models_4 A(a)$ by Theorem 5.3) that $\mathcal{K} \models_4 \neg A(a)$. Moreover, due to $\mathcal{K} \models_4 \neg A(a)$ and the definition of the 4-model $I_{\min}$, there must exist some assertion $B(a) \in \mathcal{A}$ such that $\mathcal{T} \models B \sqsubseteq \neg A$. However, due to the coherence of $\mathcal{T}$, we know that $\{B(a)\}$ is classically consistent with $\mathcal{T}$, hence there exists a repair $\mathcal{R}$ that contains $B(a)$, and hence is such that $\langle \mathcal{T}, \mathcal{R} \rangle \not\models A(a)$. We thus obtain $\mathcal{K} \not\models_{\text{AR}} A(a)$.

For the second implication, suppose that $\mathcal{K} \models_4 T(A(a))$. In particular, this means that $a \in A^{I_{\min}}$ in the 4-model $I_{\min}$. Hence, there exists $B(a) \in \mathcal{A}$ such that $\mathcal{T} \models B \sqsubseteq A$. Again using the coherence of $\mathcal{T}$, we can show that there is a repair $\mathcal{R}$ that contains $B(a)$, from which we can infer $\mathcal{K} \models_{\text{brave}} A(a)$. □

One could, of course, wonder what happens if we use value operators other than T in queries. However, note that $N(A(a))$ and $F(A(a))$ require that $a^I \notin A^{I_p}$ in all 4-models, so intuitively that $A(a)$ cannot be derived, while queries under repair-based semantics only look for answers that can be derived in some way. Regarding $B$, we can see that for $\mathcal{K}_1$ defined in the proof of Theorem 5.6, $\mathcal{K}_1^\mathcal{C} \models_4 B(B(a))$ while $\mathcal{K}_1 \not\models_X B(a)$ with $X \in \{\text{brave}, \text{CAR}\}$, and that if we let $\mathcal{K}_3 = \langle \emptyset, \{D(a)\} \rangle$, $\mathcal{K}_3 \models_{\text{IAR}} D(a)$ while $\mathcal{K}_3^\mathcal{C} \not\models_4 B(D(a))$.

We conclude this section by recalling the computational advantages of paraconsistent reasoning over repair-based semantics: BCQ entailment under brave (resp. AR and IAR) is $\Sigma_2^P$-hard (resp. $\Pi_2^P$-hard) in $\mathcal{A}LC$ and NP-hard (resp. coNP-hard) in $\mathcal{EL}_\perp$ w.r.t. data complexity (cf. Table 3). It is also worth noting that paraconsistent reasoning does not need to assume that the TBox is satisfiable (while the AR semantics has been generalised to repairs that remove TBox axioms as well (Eiter et al. 2016), the complexity of generalised AR semantics is at least as high as that of (plain) AR semantics).

# 6 Paraconsistent DLs With Four-Valued Roles

Let us now show how our results can be transferred to description logics, where both concepts and roles can be four-valued. Formally, this means that we allow 4-interpretations such that $R^{I_p} \neq R^{I_n}$ for some $R \in \text{RN}$.

In this section, we will consider $\mathcal{A}LC\mathcal{H}\mathcal{I}_\Delta^4$ KBs, which are defined like $\mathcal{A}LC\mathcal{H}\mathcal{I}_\Delta^4$ KBs but may additionally include negative role inclusion axioms of the form $S \sqsubseteq \neg S'$. Such negative role inclusion axioms are in particular allowed in DL-Lite$_R$, which extends DL-Lite$_{core}$ with role inclusions of the form $S \sqsubseteq S'$ or $S \sqsubseteq \neg S'$. Given a 4-interpretation $\mathcal{I} = \langle \Delta^I, \cdot^{I_p}, \cdot^{I_n} \rangle$, the semantics of $\neg S$ is defined as expected:

$$ (\neg S)^{I_p} = S^{I_n} \qquad (\neg S)^{I_n} = S^{I_p} \qquad (S \in \text{RN}^\pm) $$

Just like four-valued concepts (recall Example 2.1), four-valued roles can be used to discern between different types of contradictions occurring in the knowledge base. We illustrate this in the following example.

**Example 6.1.** Assume that the university regulations prohibit an advisor from being a member of the thesis committee of their student. Initially, Ann was assigned as Claire's supervisor, but then resigned, and Diane took over the supervision. When Claire's thesis committee was being formed, Ann was included in it. The knowledge base, however, was not duly updated, and Ann is still mentioned as Claire's supervisor:

$$ \begin{array}{l} \mathcal{T} = \{\text{supervise} \sqsubseteq \neg \text{inCommittee}\} \\ \mathcal{A} = \left\{ \begin{array}{ll} \text{supervise}(\text{ann}, \text{claire}), & \text{supervise}(\text{diane}, \text{claire}), \\ \text{inCommittee}(\text{ann}, \text{claire}), & \text{inCommittee}(\text{brittney}, \text{claire}) \end{array} \right\} \end{array} $$

It is clear that $\mathcal{K} = \langle \mathcal{T}, \mathcal{A} \rangle$ does not have classical models. In fact, it does not have even 4-models if all roles are two-valued (i.e., if $\neg$ is treated as role complement). On the other hand, if the roles are four-valued, then we have that $\langle \text{ann}^I, \text{claire}^I \rangle \in \text{inCommittee}^{I_p} \cap \text{inCommittee}^{I_n}$ indicating an irregularity of the records.
The remainder of the section is structured as follows. First, we formally introduce and compare several different ways of interpreting quantified concepts (i.e., concepts of the form ∃S.C or ∀S.C) using four-valued roles. This allows us to select the most satisfactory semantics of quantified concepts with four-valued roles. Adopting this semantics for quantified concepts, we then expand the query language from Section 3 with value operators for role atoms and show how the results from Section 4 can be extended to this language.

## 6.1 Semantics of Concepts With Four-Valued Roles

To the best of our knowledge, there are three different interpretations of quantified concepts ∃R.C or ∀R.C with four-valued roles that have been considered for paraconsistent DLs. These semantics were proposed by Patel-Schneider (1989), Meghini and Straccia (1996) and Kamide (2013). Hence, we start by formally introducing these interpretations of quantified concepts using four-valued roles and investigating their properties.

Before defining the semantics, let us first discuss several desirable properties. We single out two desiderata for a semantics $\mathcal{S}$ with four-valued roles. Given a concept C and a 4-interpretation $\mathcal{I} = (\Delta, \cdot^{I_p}, \cdot^{I_n})$, we use $C_{\mathcal{S}}^{I_p}$ and $C_{\mathcal{S}}^{I_n}$ for the positive and negative extensions of C w.r.t. $\mathcal{S}$, and write $\mathcal{I} \models_S^S \phi$ to denote that $\mathcal{I}$ satisfies the statement $\phi$ under $\mathcal{S}$. Similarly, we write $\mathcal{K} \models_S^S \phi$ to denote that the KB $\mathcal{K}$ entails statement $\phi$ under $\mathcal{S}$.

*   **$\forall\exists$-interdefinability** Given an $\exists$-free concept C, there is a $\forall$-free concept $C^\forall$ such that $(\forall S.C)^{I_p}_S = (C^\forall)^{I_p}_S$ and $(\forall S.C)^{I_n}_S = (C^\forall)^{I_n}_S$ for every 4-interpretation $\mathcal{I}$. Dually, given a $\forall$-free concept D, there is an $\exists$-free concept $D^\exists$ such that $(\exists S.D)^{I_p}_S = (D^\exists)^{I_p}_S$ and $(\exists S.D)^{I_n}_S = (D^\exists)^{I_n}_S$ for every 4-interpretation $\mathcal{I}$.

*   **$\mathcal{I}_p$-classicality** Given a $\neg$-free KB $\mathcal{K}$ and a $\neg$-free concept inclusion, role inclusion, or assertion $\phi$, it holds that $\mathcal{K} \models^S \phi$ iff $\mathcal{K} \models^S_4 \phi$.

**Remark 3 (Naming of semantics).** There is a considerable confusion in the literature considering names of different semantics for four-valued roles. In particular, Straccia (1997) calls the semantics by Meghini and Straccia (1996) and Patel-Schneider (1989) ‘Type A’ and ‘Type B’, respectively. The Type A semantics is called ‘weak quasi-classical’ by Zhang and Lin (2008), Zhang, Qi, et al. (2009), and Zhang, Xiao, et al. (2014). On the other hand, Kamide (2013) uses ‘quasi-classical’ (without a qualifier ‘weak’) to denote a different (third) semantics.

Hence, in this section, we will use our own (informative) names for different semantics with four-valued roles. We give names to semantics based on how they use the positive and negative interpretations of the roles.

### 6.1.1 One-Sided Semantics
We begin with the more traditional semantics proposed by Meghini and Straccia (1996). The semantics was later adopted by Maier et al. (2013), Zhang and Lin (2008), Zhang, Qi, et al. (2009), and Zhang, Xiao, et al. (2014). As it uses positive extensions of roles to define both positive and negative extensions of quantified concepts, we will call it one-sided in this paper.

**Definition 6.2 (One-sided semantics).** Given a concept C and a 4-interpretation $\mathcal{I} = (\Delta, \cdot^{I_p}, \cdot^{I_n})$, we use $C_1^{I_p}$ and $C_1^{I_n}$ for the positive and negative extensions of C w.r.t. one-sided semantics. The positive and negative extensions of quantified concepts are as follows:

$$ (\forall S.C)^{I_p}_1 = \{x \mid \forall y : (x, y) \in S^{I_p} \Rightarrow y \in C_1^{I_p}\} \qquad (\forall S.C)^{I_n}_1 = \{x \mid \exists y : (x, y) \in S^{I_p} \& y \in C_1^{I_n}\} $$

$$ (\exists S.C)^{I_p}_1 = \{x \mid \exists y : (x, y) \in S^{I_p} \& y \in C_1^{I_p}\} \qquad (\exists S.C)^{I_n}_1 = \{x \mid \forall y : (x, y) \in S^{I_p} \Rightarrow y \in C_1^{I_n}\} $$

Given a KB $\mathcal{K}$ and a statement $\phi$, we use $\mathcal{K} \models^S_4 \phi$ to denote that $\mathcal{K}$ entails $\phi$ w.r.t. one-sided semantics.

We can easily observe that one-sided semantics satisfies the $\forall\exists$-interdefinability property since it preserves the usual connection between quantifiers: $(\forall S.C)^{I_p}_1 = (\neg\exists S.\neg C)^{I_p}_1$ and $(\forall S.C)^{I_n}_1 = (\neg\exists S.\neg C)^{I_n}_1$ hold in all 4-interpretations, as well as $(\exists S.D)^{I_p}_1 = (\neg\forall S.\neg D)^{I_p}_1$ and $(\exists S.D)^{I_n}_1 = (\neg\forall S.\neg D)^{I_n}_1$.
One can also show that one-sided semantics satisfies $I_p$-classicality. In fact, it validates the following even stronger property.

**Conservativity** Given a KB $\mathcal{K}$ that does not contain negated roles and a concept inclusion, role inclusion, or assertion $\phi$, it holds that $\mathcal{K} \models_I \phi$ iff $\mathcal{K} \models_I \neg \phi$.

**PROPOSITION 6.3.** *One-sided semantics satisfies the conservativity property.*

**PROOF.** The proof is straightforward, and we only provide a sketch thereof. It is clear that $\mathcal{K} \nvDash_I \phi$ entails $\mathcal{K} \nvDash_I \neg \phi$. For the converse direction, let $\mathcal{I} = \langle \Delta^I, \cdot I_p, \cdot I_n \rangle$ be a 4-interpretation that witnesses $\mathcal{K} \nvDash_I \phi$. We construct a 4-interpretation with two-valued roles that witnesses $\mathcal{K} \nvDash_I \phi$ as follows. We set $\mathcal{I}' = \langle \Delta^{\prime I}, \cdot I'_{p}, \cdot I'_{n} \rangle$ with $A^{\prime I'_{p}} = A^{\prime I_{p}}$ and $A^{\prime I'_{n}} = A^{\prime I_{n}}$ for each $A \in CN$, $c^{\prime I'} = c^{\prime I}$ for each $c \in IN$, and $R^{\prime I'} = R^{\prime I'_{p}} = R^{\prime I'_{n}} = R^{\prime I_{p}}$ for every $R \in RN$. It is clear that if $\phi$ is an assertion, $\mathcal{I} \nvDash_I \neg \phi$ implies $\mathcal{I}' \nvDash_I \neg \phi$. It is then easy to check by induction on concepts that $C^{\prime I'_{p}} = C^{\prime I_{p}}$ and $C^{\prime I'_{n}} = C^{\prime I_{n}}$ for every $\mathcal{A}LCH\mathcal{I}^4_\Delta$ concept. Hence, the statement holds for $\phi$ being a concept inclusion. To see that the statement holds for the case of $\phi$ being a role inclusion, recall that role inclusions only use their *positive* extensions, and $\mathcal{K}$ does not contain negated roles. The result now follows. $\square$

We finish the discussion of the one-sided semantics with a couple of remarks on its other useful properties. First, since $\forall$ and $\exists$ are interdefinable in a standard way, one-sided semantics allows for negation normal form. Second, KBs interpreted in one-sided semantics can also be translated into the two-variable fragment of $BD_\Delta^{\forall,\exists}$ – the first-order Belnap–Dunn logic introduced by Anderson and Belnap (1963) (cf. a modern presentation by Priest (2008, Chapter 22)) with $\Delta$ and Avron’s internal implication $\supset^4$ proposed by Sano and Omori (2014). As one can see, this translation coincides with the embedding of classical KBs into the two-variable fragment of classical first-order logic.

$$
\begin{array}{l@{\qquad}l@{\qquad}l}
\tau(C) \rightsquigarrow \tau_x(C) & & \tau(A(a)) \rightsquigarrow A(a) & (a \in \mathbf{IN}) \\
\tau_x(A) \rightsquigarrow A(x) & (A \in \mathbf{CN}) & \tau(S(a, b)) \rightsquigarrow S(a, b) & (a, b \in \mathbf{IN}) \\
\tau_x(\#C) \rightsquigarrow \#\tau_x(C) & (\# \in \{\neg, \Delta\}) & \tau(C \sqsubseteq D) \rightsquigarrow \forall x(\tau_x(C) \supset \tau_x(D)) \\
\tau_x(C \circ D) \rightsquigarrow \tau_x(C) \circ \tau_x(D) & (\circ \in \{\sqcap, \sqcup\}) & \tau(S \sqsubseteq S') \rightsquigarrow \forall x \forall y(S(x, y) \supset S'(x, y)) \\
\tau_x(\forall S.C) \rightsquigarrow \forall y(S(x, y) \supset \tau_y(C)) & & \tau(S \sqsubseteq \neg S') \rightsquigarrow \forall x \forall y(S(x, y) \supset \neg S'(x, y)) \\
\tau_x(\exists S.C) \rightsquigarrow \exists y(S(x, y) \wedge \tau_y(C)) & & &
\end{array}
$$

It is easy to see that $\mathcal{I} \nvDash_I \neg \phi$ iff $\mathcal{I} \nvDash_{BD_\Delta^{\forall,\exists}} \tau(\phi)$ for a role inclusion, a concept inclusion, or an assertion $\phi$.

**6.1.2** *Split Semantics.* Even if the one-sided semantics satisfies desirable properties, it may seem counterintuitive that the negative role extensions are not used at all to interpret the quantified concepts, and alternative semantics that do take them into account have been proposed in the literature. In the ‘quasi-classical’ semantics given by Kamide (2013), the negative extensions of quantified concepts use the negative extensions of roles. In this text, we will refer to it as the *split* semantics, referring to the fact that the positive and negative interpretations are ‘split’ in the sense that there is no interaction between them. This semantics has received some attention in modal logic. In fact, it was originally introduced by Sherkhonov (2008) in the context of paraconsistent constructive modal logics and then further studied by Gao et al. (2026). It was then applied to the formalisation of beliefs in the presence of inconsistent information by Bílková et al. (2025, 2023).

**Definition 6.4 (Split semantics).** Given a concept C and a 4-interpretation $\mathcal{I} = \langle \Delta, \cdot I_p, \cdot I_n \rangle$, we denote the positive and negative extensions of C w.r.t. split semantics with $C^I_p$ and $C^I_n$. The positive and negative extensions of

<footnote n="4">⁴Observe that $\phi \supset \chi$ can be defined as $\neg \Delta \phi \lor \chi$ (Omori and Sano 2015).</footnote>
quantified concepts are as follows:

$$ (\forall S.C)_V^{I_p} = \{x \mid \forall y : (x, y) \in S^{I_p} \Rightarrow y \in C_V^{I_p}\} \qquad (\forall S.C)_V^{I_n} = \{x \mid \exists y : (x, y) \in S^{I_n} \& y \in C_V^{I_n}\} $$

$$ (\exists S.C)_V^{I_p} = \{x \mid \exists y : (x, y) \in S^{I_p} \& y \in C_V^{I_p}\} \qquad (\exists S.C)_V^{I_n} = \{x \mid \forall y : (x, y) \in S^{I_n} \Rightarrow y \in C_V^{I_n}\} $$

Given a KB $\mathcal{K}$ and a statement $\phi$, we use $\mathcal{K} \models_4^\gamma \phi$ to denote that $\mathcal{K}$ entails $\phi$ w.r.t. split semantics.

As one can see from the definition above, the split semantics satisfies $I_p$-classicality. On the other hand, one can show that quantifiers *are not interdefinable* w.r.t. split semantics.

**PROPOSITION 6.5.** *Split semantics does not satisfy the $\forall \exists$-interdefinability property.*

**PROOF.** We consider the following interpretations $I$ and $J$.

$$ \bullet \Delta^I = \{a, b\}, A^{I_p} = \{b\}, A^{I_n} = \emptyset, R^{I_p} = \{(a, b)\}, R^{I_n} = \emptyset. $$

$$ \bullet \Delta^J = \{a', b'\}, A^{J_p} = \{a'\}, A^{J_n} = \{a'\}, R^{J_p} = \{(a', b')\}, R^{J_n} = \emptyset. $$

We have that $a \in (\exists R.A)_V^{I_p} \cap (\exists R.A)_V^{I_n}$, and further, that $a' \notin (\forall R.A)_V^{J_p} \cup (\forall R.A)_V^{J_n}$. If $CN = \{A\}$ and $RN = \{R\}$, one can show the two following statements, from which it follows that (1) $\exists R.A$ is not definable by an $\exists$-free concept and (2) $\forall R.A$ is not definable by a $\forall$-free concept.

(1) There is no $\exists$-free $\mathcal{A}LCHI_\Delta^4$ concept C such that $a \in C_V^{I_p} \cap C_V^{I_n}$.

(2) There is no $\forall$-free $\mathcal{A}LCHI_\Delta^4$ concept D such that $a' \notin D_V^{J_p} \cup D_V^{J_n}$.

We only show (1) as (2) can be obtained in a dual manner. We proceed by induction on $\mathcal{A}LCHI_\Delta^4$ concepts. The base case is evident from the definition of $I$. The cases of propositional connectives are also easy to obtain since $(\Delta C)_V^{I_p} \cap (\Delta C)_V^{I_n} = \emptyset$ in every 4-interpretation and the cases $a \in (-C)_V^{I_p} \cap (-C)_V^{I_n}$, $a \in (C \sqcap C')_V^{I_p} \cap (C \sqcap C')_V^{I_n}$, and $a \in (C \sqcup C')_V^{I_p} \cap (C \sqcup C')_V^{I_n}$ all imply that $a \in C_V^{I_p} \cap C_V^{I_n}$ or $a \in C'_V^{I_p} \cap C'_V^{I_n}$ which is impossible by the induction hypothesis. Finally, to see that $a \notin (\forall R.C)_V^{I_p} \cap (\forall R.C)_V^{I_n}$, observe that $R^{I_n} = \emptyset$. Hence, $(\forall R.C)_V^{I_n} = \emptyset$. $\square$

Moreover, note that even though split semantics validates $I_p$-classicality, the conservativity property fails. That is, the analogue of Proposition 6.3 does not hold for it. To see this, let $\mathcal{K} = \langle \mathcal{T}, \mathcal{A} \rangle$ with $\mathcal{T} = \{B \sqsubseteq \neg A, \neg \forall R.A \sqsubseteq C\}$ and $\mathcal{A} = \{R(a, b), B(b)\}$. It holds that $\mathcal{K}$ does not contain negated roles and $\mathcal{K} \models_4 C(a)$, but one can show that $\mathcal{K} \models_4^\gamma C(a)$. Indeed, the following 4-interpretation $I$ is such that $I \models_4^\gamma \mathcal{K}: a^I = a, b^I = b, R^{I_p} = \{(a, b)\}, R^{I_n} = \emptyset, A^{I_p} = \emptyset, A^{I_n} = \{b\}, B^{I_p} = \{b\}, B^{I_n} = \emptyset$ and $C^{I_p} = C^{I_n} = \emptyset$.

### 6.1.3 Non-Refuting Semantics.
The third alternative is the semantics proposed by Patel-Schneider (1989). The idea here is to redefine the universal quantifier as follows: to verify whether $\forall S.C$ is true of $a$, one checks the individuals $b$ for which $S(a, b)$ is not false, i.e., those that do not refute the relation $S$. Hence, we will call this semantics *positive non-refuting*.

**Definition 6.6 (Positive non-refuting semantics).** For a concept C and a 4-interpretation $I = \langle \Delta, \cdot^{I_p}, \cdot^{I_n} \rangle$, we denote the positive and negative extensions of C w.r.t. positive non-refuting semantics with $C_{pnr}^{I_p}$ and $C_{pnr}^{I_n}$. The positive and negative extensions of quantified concepts are as follows:

$$ (\forall S.C)_{pnr}^{I_p} = \{x \mid \forall y : (x, y) \notin S^{I_n} \Rightarrow y \in C_{pnr}^{I_p}\} \qquad (\forall S.C)_{pnr}^{I_n} = \{x \mid \exists y : (x, y) \in S^{I_p} \& y \in C_{pnr}^{I_n}\} $$

$$ (\exists S.C)_{pnr}^{I_p} = \{x \mid \exists y : (x, y) \in S^{I_p} \& y \in C_{pnr}^{I_p}\} \qquad (\exists S.C)_{pnr}^{I_n} = \{x \mid \forall y : (x, y) \notin S^{I_n} \Rightarrow y \in C_{pnr}^{I_n}\} $$

Given a KB $\mathcal{K}$ and a statement $\phi$, we use $\mathcal{K} \models_4^{pnr} \phi$ to denote that $\mathcal{K}$ entails $\phi$ w.r.t. positive non-refuting semantics.
As one can immediately see from Definition 6.6, $\forall$ and $\exists$ are interdefinable via an expected duality: $(\forall S.C)_{\text{pnr}}^{I_p} = (\neg\exists S.\neg C)_{\text{pnr}}^{I_p}$ and $(\forall S.C)_{\text{pnr}}^{I_n} = (\neg\exists S.\neg C)_{\text{pnr}}^{I_n}$ hold in all 4-interpretations, as well as $(\exists S.D)_{\text{pnr}}^{I_p} = (\neg\forall S.\neg D)_{\text{pnr}}^{I_p}$ and $(\exists S.D)_{\text{pnr}}^{I_n} = (\neg\forall S.\neg D)_{\text{pnr}}^{I_n}$. On the other hand, $I_p$-classicality is not satisfied. To see that, consider the following KB: $\mathcal{K} = \langle\mathcal{T}, \mathcal{A}\rangle$ with $\mathcal{A} = \{A(a), R(a, b)\}$ and $\mathcal{T} = \{A \sqsubseteq \forall R.C\}$. Observe that $\mathcal{K} \models_4^{\text{pnr}} C(b)$ because $\langle a^I, b^I \rangle \notin R^{I_n}$ does not follow from $\mathcal{K}$.

To remedy the failure of the $I_p$-classicality in positive non-refuting semantics, we can change the definition of $\forall$. Namely, we switch conditions $(x, y) \notin S^{I_n}$ and $(x, y) \in S^{I_p}$. In other words, we will use standard truth conditions for $\forall$ and $\exists$ and retain the falsity condition for $\exists$ from Definition 6.6; on the other hand, to check whether $\forall S.C$ is false w.r.t. $a$, we will check individuals $b$ for which $S(a, b)$ is not false. We call this semantics negative non-refuting since we consider individuals that do not refute $S$ to define the negative extensions of concepts.

**Definition 6.7 (Negative non-refuting semantics).** For a concept C and a 4-interpretation $\mathcal{I} = \langle\Delta, \cdot I_p, \cdot I_n\rangle$, we denote the positive and negative extensions of C w.r.t. negative non-refuting semantics with $C_{\text{nnr}}^{I_p}$ and $C_{\text{nnr}}^{I_n}$. The positive and negative extensions of quantified concepts are as follows:

$$ (\forall S.C)_{\text{nnr}}^{I_p} = \{x \mid \forall y : (x, y) \in S^{I_p} \Rightarrow y \in C_{\text{nnr}}^{I_p}\} \qquad (\forall S.C)_{\text{nnr}}^{I_n} = \{x \mid \exists y : (x, y) \notin S^{I_n} \ \& \ y \in C_{\text{nnr}}^{I_n}\} $$

$$ (\exists S.C)_{\text{nnr}}^{I_p} = \{x \mid \exists y : (x, y) \in S^{I_p} \ \& \ y \in C_{\text{nnr}}^{I_p}\} \qquad (\exists S.C)_{\text{nnr}}^{I_n} = \{x \mid \forall y : (x, y) \notin S^{I_n} \Rightarrow y \in C_{\text{nnr}}^{I_n}\} $$

Given a KB $\mathcal{K}$ and a statement $\phi$, we use $\mathcal{K} \models_4^{\text{pnr}} \phi$ to denote that $\mathcal{K}$ entails $\phi$ w.r.t. negative non-refuting semantics.

It is clear that negative non-refuting semantics satisfies the $I_p$-classicality property. Unfortunately, as was the case with the split semantics, quantifiers are not interdefinable. Namely, consider the following 4-interpretation $\mathcal{I}: \Delta^I = \{a, b\}, A^{I_p} = \{a\}, A^{I_n} = \emptyset, R^{I_p} = \{(a, a), (a, b)\}, R^{I_n} = \Delta^I \times \Delta^I$. Using the same argument as in Proposition 6.5, it is easy to see that there is no $\forall$-free $\mathcal{A}LCHI_\Delta^4$-concept C such that $a \notin C_{\text{nnr}}^{I_p} \cup C_{\text{nnr}}^{I_n}$. Likewise, there is no $\exists$-free concept D such that $a \in D_{\text{nnr}}^{I_p} \cap D_{\text{nnr}}^{I_n}$. On the other hand, $a \notin (\forall R.A)_{\text{nnr}}^{I_p} \cup (\forall R.A)_{\text{nnr}}^{I_n}$ and $a \in (\exists R.A)_{\text{nnr}}^{I_p} \cap (\exists R.A)_{\text{nnr}}^{I_n}$.

The analogue of Proposition 6.3 does not hold either. To see this, consider $\mathcal{K} = \langle\mathcal{T}, \mathcal{A}\rangle$ with $\mathcal{T} = \{B \sqsubseteq \neg A, \neg\forall R.A \sqsubseteq C\}$ and $\mathcal{A} = \{R(a, b), B(b)\}$. One can verify that $\mathcal{K} \models_4 C(a)$ and $\mathcal{K} \models_4^{\text{pnr}} C(a)$. Indeed, the latter non-entailment can be shown by considering the 4-interpretation $\mathcal{I}$ with domain $\Delta^I = \{a, b\}$ such that $\mathcal{I} \models_4^{\text{pnr}} \mathcal{K}: a^I = a, b^I = b, R^{I_p} = \{(a, b)\}, R^{I_n} = \{(a, b)\}, A^{I_p} = \emptyset, A^{I_n} = \{b\}, B^{I_p} = \{b\}, B^{I_n} = \emptyset, C^{I_p} = \{b\}$ and $C^{I_n} = \emptyset$.

From the preceding discussion and examples, we can see that, although somewhat counterintuitive, it is important to use the positive extensions of roles to define both positive and negative extensions of quantified concepts if we want to preserve intuitive inferences. This is why, in what follows, we will restrict our attention to the one-sided semantics. In particular, we will write $\models_4$ for $\models_4^1$.

## 6.2 Queries With Value Operators for Role Atoms

We begin with the definition of the query language, which expands the language from Definition 3.3 by allowing value operators on role atoms.

**Definition 6.8 (Queries with valued relations).** A conjunctive query with valued relations (CQVR) is a CQV (recall Definition 3.3) that can additionally have atoms of the form $X(R(t, t'))$ with $X \in \{\mathbf{T}, \mathbf{B}, \mathbf{N}, \mathbf{F}\}$. A Boolean CQVR (BCQVR) has no free variables, and as before, we use terms($\mathbf{q}$) for the terms of a CQVR.

The definition of atom sets and query semantics are extended to CQVRs as expected.
**Definition 6.9 (Atom sets in CQVRs).** Let atoms(q) be the set of all atoms occurring in a CQVR q and X, Y ∈ {T, B, N, F}. We define:

$$
\begin{align*}
\text{atoms}^{\text{X}}(\mathbf{q}) &= \{A(t) \mid X(A(t)) \in \text{atoms}(\mathbf{q})\} \cup \{R(t, t') \mid X(R(t, t')) \in \text{atoms}(\mathbf{q})\} \\
\text{atoms}^{\text{XY}}(\mathbf{q}) &= \text{atoms}^{\text{X}}(\mathbf{q}) \cup \text{atoms}^{\text{Y}}(\mathbf{q}) \\
\text{atoms}^{+}(\mathbf{q}) &= \{A(t) \mid A(t) \in \text{atoms}(\mathbf{q})\} \cup \{R(t, t') \mid R(t, t') \in \text{atoms}(\mathbf{q})\} \cup \text{atoms}^{\text{TB}}(\mathbf{q})
\end{align*}
$$

**Definition 6.10 (CQVR answers).** A KB K 4-entails a BCQVR q (K |=₄ q) if the following conditions hold.

(1) For every 4-model I = ⟨Δ<sup>I</sup>, .I<sub>p</sub>, .I<sub>n</sub>⟩ of K, there is a match π : terms(q) ↦→ Δ<sup>I</sup> such that for every c ∈ IN, π(c) = c<sup>I</sup>, and

• (π(t₁), π(t₂)) ∈ R<sup>I<sub>p</sub></sup> for every R(t₁, t₂) ∈ atoms<sup>+</sup>(q);

• (π(t₁), π(t₂)) ∈ R<sup>I<sub>n</sub></sup> for every R(t₁, t₂) ∈ atoms<sup>BF</sup>(q);

• π(t) ∈ A<sup>I<sub>p</sub></sup> for every A(t) ∈ atoms<sup>+</sup>(q);

• π(t) ∈ A<sup>I<sub>n</sub></sup> for every A(t) ∈ atoms<sup>BF</sup>(q).

(2) There exists a 4-model I = ⟨Δ<sup>I</sup>, .I<sub>p</sub>, .I<sub>n</sub>⟩ of K and a match π as required above which is additionally such that

• π(t) ∉ A<sup>I<sub>n</sub></sup> for every A(t) ∈ atoms<sup>TN</sup>(q);

• (π(t₁), π(t₂)) ∉ R<sup>I<sub>n</sub></sup> for every R(t₁, t₂) ∈ atoms<sup>TN</sup>(q);

• π(t) ∉ A<sup>I<sub>p</sub></sup> for every A(t) ∈ atoms<sup>FN</sup>(q);

• (π(t₁), π(t₂)) ∉ R<sup>I<sub>p</sub></sup> for every R(t₁, t₂) ∈ atoms<sup>FN</sup>(q).

We say that $\vec{a}$ is a *four-valued paraconsistent answer* to a CQVR $\mathbf{q}(\vec{x})$ with free variables $\vec{x}$ over $\mathcal{K}$ ($\vec{a} \in \text{ans}_4(\mathbf{q}(\vec{x}), \mathcal{K})$) if $\mathcal{K} \models_4 \mathbf{q}(\vec{a})$ where $\mathbf{q}(\vec{a})$ is the Boolean query obtained by replacing the variables from $\vec{x}$ with the constants from $\vec{a}$.

Note that we expanded the interpretation of value operators to role atoms as well. The following example illustrates this use of value operators.

**Example 6.11.** Recall the knowledge base in Example 6.1, and let K' be its expansion with the following axioms and assertions:

$$
\mathcal{T}' = \{ \text{Full} \sqsubseteq \neg \text{Asc}, \text{Asc} \sqsubseteq \neg \text{Full}, \text{coAuthor} \sqsubseteq \neg \text{inCommittee} \}
$$

$$
\mathcal{A}' = \{ \text{Full}(\text{ann}), \text{Full}(\text{brittney}), \text{Full}(\text{diane}), \text{coAuthor}(\text{eva}), \text{claire}) \}
$$

Assume that another defence has been scheduled during the deliberation on Claire's thesis, and the other committee is understaffed. Thus, the administration is looking for a full professor who is *guaranteed to not partake in the deliberation*. This can be represented via the query below:

$$
\mathbf{q} := \mathbf{T}(\mathbf{Full}(x)) \wedge \mathbf{F}(\mathbf{inCommittee}(x, \mathbf{claire}))
$$

One can see that there are three full professors (Ann, Brittney, and Diane). Ann is still listed as Claire's supervisor by mistake, whence $\mathcal{K}' \models_4 \neg \text{inCommittee}(\text{ann, claire})$. However, she is also correctly listed as a member of her committee, so $\mathcal{K}' \models_4 \text{inCommittee}(\text{ann, claire})$. Thus, $\text{ann} \notin \text{ans}_4(\mathbf{q}(x), \mathcal{K}')$. Brittney is also listed as a member of Claire's committee, hence *brittney* $\notin \text{ans}_4(\mathbf{q}(x), \mathcal{K}')$ either. On the other hand, Diane is Claire's supervisor (whence, not in her committee: $\mathcal{K}' \models_4 \neg \text{inCommittee}(\text{diane, claire})$) and $\mathcal{K}' \not\models_4 \text{inCommittee}(\text{diane, claire})$. Thus, $\text{diane} \in \text{ans}_4(\mathbf{q}(x), \mathcal{K}')$. Finally, Eva is also not on the committee because she is a co-author of Claire. However, as the knowledge base does not contain any mention of her position, $\mathcal{K}' \not\models_4 \text{Full}(\text{eva})$, whence, $\text{eva} \notin \text{ans}_4(\mathbf{q}(x), \mathcal{K}')$.
Let us now extend the results of Section 4 to CQVRs. We observe first that since every (Boolean) CQV is a (Boolean) CQVR, all of the lower bounds from Table 2 hold for the latter queries as well. To show that the upper bounds are preserved, we can adapt the proof of Theorem 4.2.

First, we modify the definition of classical counterparts (cf. Definition 2.6) following the approach of Maier et al. (2013). Now every $R \in \mathbb{R}N$ occurring in $\mathcal{K}$ corresponds to two role names in $\mathcal{K}^{\text{cl}}$: $R_p$ and $R_n$ that will stand for $R$ and $\neg R$, respectively. More formally, we modify the definition of classical counterparts as follows:

$$ (S \sqsubseteq S')^{\text{cl}} = S_p \sqsubseteq S'_p \qquad (S \sqsubseteq \neg S')^{\text{cl}} = S_p \sqsubseteq S'_n \qquad (QS.C)^{\text{cl}} = QS_p.C^{\text{cl}} \qquad (R(a, b))^{\text{cl}} = R_p(a, b) $$

Note that if $\mathcal{K}$ is an $\mathcal{A}LCHI_{\Delta}^{4R}$ knowledge base, then $\mathcal{K}^{\text{cl}}$ is still an $\mathcal{A}LCHI$ KB and does not use negative role inclusions.

Second, we modify the query embedding from Definition 4.1 so that now both concept and role atoms with values are treated in the same manner. For a Boolean CQVR $q = \exists \vec{y} : \phi$, we thus define:

$$ q_4^+ := \exists \vec{y} : \bigwedge_{R(t,t') \in \text{atoms}^+(q)} R_p(t,t') \wedge \bigwedge_{R(t,t') \in \text{atoms}^{\text{BF}}(q)} R_n(t,t') \wedge \bigwedge_{A(t) \in \text{atoms}^+(q)} A^+(t) \wedge \bigwedge_{A(t) \in \text{atoms}^{\text{BF}}(q)} A^-(t) $$

$$ q_4^{\text{ctr}} := \bigvee_{A(t) \in \text{atoms}^{\text{TN}}(q)} A^{-}(c_t) \vee \bigvee_{A(t) \in \text{atoms}^{\text{FN}}(q)} A^{+}(c_t) \vee \bigvee_{R(t,t') \in \text{atoms}^{\text{TN}}(q)} R_n(c_t, c_{t'}) \vee \bigvee_{R(t,t') \in \text{atoms}^{\text{FN}}(q)} R_p(c_t, c_{t'}) $$

$$ \begin{aligned} \mathcal{A}_{q_4} := & \{R_p(c_t, c_{t'}) | R_p(t, t') \in \text{atoms}(q^+)\} \cup \{R_n(c_t, c_{t'}) | R_n(t, t') \in \text{atoms}(q^+)\} \cup \\ & \{A^+(c_t) | A^+(t) \in \text{atoms}(q^+)\} \cup \{A^-(c_t) | A^-(t) \in \text{atoms}(q^+)\} \end{aligned} $$

Now we can prove the following statement in the same way as Theorem 4.2.

**THEOREM 6.12.** Let $\mathcal{K}$ be an $\mathcal{A}LCHI_{\Delta}^{4R}$ KB and $q$ be a BCQVR.

$$ \mathcal{K} \models_4 q \text{ iff } \mathcal{K}^{\text{cl}} \models q_4^+ \text{ and } \mathcal{K}^{\text{cl}} \cup \mathcal{A}_{q_4} \nvDash q_4^{\text{ctr}} $$

The next theorem is now immediate (in the case of DL-Lite<sub>R</sub>, the complexity of assertion entailment is the same as in DL-Lite<sub>core</sub> so the upper bound is preserved).

**THEOREM 6.13.** The results of Table 2 hold for BCQVR entailment even if the DL languages are extended with negative role inclusions (and positive role inclusions in the case of DL-Lite<sub>core</sub>, i.e., for DL-Lite<sub>R</sub>).

# 7 Conclusion

In this paper, we presented a new approach to querying inconsistent DL KBs based upon paraconsistent logic, which we show to be incomparable to repair-based semantics. Differently from existing paraconsistent OMQA approaches, our query language enables us to take full advantage of the four-valued semantics, making it possible to differentiate between *exactly true* and *at least true* instances of a concept. We proved that our approach is computationally well-behaved (cf. Table 2): in Horn KBs, the combined and data complexity of paraconsistent query answering coincides with that of the classical certain answers semantics; in expressive DLs, data complexity of paraconsistent BCQV entailment remains lower than in repair-based semantics. Moreover, we have shown (cf. Section 6.2) that our query-answering semantics can be naturally extended to the case of paraconsistent DLs with *four-valued roles* and that moving from two- to four-valued roles can be done without impacting the complexity of query answering when using the only semantics for four-valued roles that satisfies the desiderata put forth in Section 6.1. Notably, our complexity results for both two- and four-valued roles rely on a simple reduction of CQV(R) answering to OMQA, providing a way to readily implement CQV(R) answering. We also expect that the technique based on translation we provide can be adapted to more expressive DLs (the translation given by Maier et al. (2013) that we adapted was for SROIQ).
The paraconsistent DLs considered in this work assign truth values to concept and role assertions and are, in this regard, close to *fuzzy DLs*, in which concept memberships and relatedness by roles are evaluated using *degrees*. In particular, it is natural to wonder whether there is a relationship between our work and *lattice-based fuzzy DLs* that allow for incomparable membership degrees (Borgwardt and Peñaloza 2014). If we consider fuzzy DLs based on a lattice formed by Belnapian values (be it the lattice with T as the supremum and F as the infimum or the one with B as the supremum and N as the infimum) and queries that allow one to ask that a concept holds to at least some degree, then one can capture the semantics of CQs (without value operators) in paraconsistent DLs (Definition 3.1). However, it would not be possible to capture CQVs under the semantics we introduced. For example, considering the lattice with B as supremum, in our semantics $T(A(a))$ would mean that $A(a)$ has degree at least T in all models and that *there exists a model such that A(a) has not degree at least F*, which is not directly expressible in fuzzy DLs.

Following this idea of queries requiring that an atom has “degree at least X”, note that CQV atoms of the form $A(t)$ can be seen as two-valued atoms “T or B” (at least positive evidence). We could extend the definition of CQVs to allow for multi-valued atoms and would easily treat the case “F or B” (at least negative evidence) by extending $q^+$ (Definition 4.1) with $A^-(t)$ for such atoms and not taking them into account in $q^{\text{ctr}}$. However, allowing multi-valued query atoms in general would affect the results. For example, the cases “N or F” (no positive evidence) or “N or T” (no negative evidence) would be equivalent to having a (classical) negation in the query (we would need atoms of the form $\neg A^+(t)$ or $\neg A^-(t)$ in $q^+$) so we would need to reduce queries with such atoms to queries with negative atoms in classical DLs, which are known to be much harder to handle and will lead to higher complexity results.

## Acknowledgments

This work was supported by the ANR AI Chair INTENDED (ANR-19-CHIA-0014). We would like to thank the reviewers for their comments that helped enhance the quality of the paper.

## References

A. R. Anderson and N. D. Belnap. 1963. "First-Degree Entailments." *Mathematische Annalen*, 149, 302–319.

M. Arenas, L. Bertossi, and J. Chomicki. 1999. "Consistent Query Answers in Inconsistent Databases." In: *Proceedings of the 18th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS-1999)*. doi:10.1145/303976.303983.

O. Arieli and A. Avron. 1996. "Reasoning With Logical Bilattices." *Journal of Logic, Language and Information*, 5, 1, 25–63. doi:10.1007/BF00215626.

O. Arieli and A. Avron. 1998. "The Value of the Four Values." *Artificial Intelligence*, 102, 1, 97–141. doi:10.1016/S0004-3702(98)00032-0.

F. Baader, S. Brandt, and C. Lutz. 2005. "Pushing the *EL* Envelope." In: *Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI-05)*. doi:10.5555/1642293.1642351.

F. Baader, I. Horrocks, C. Lutz, and U. Sattler. 2017. *An Introduction to Description Logic*. Cambridge University Press, Cambridge, England. doi:10.1017/9781139025355.

N. D. Belnap. 1977a. "A Useful Four-Valued Logic." In: *Modern Uses of Multiple-Valued Logic*. Springer Netherlands, Dordrecht, 5–37. ISBN: 978-94-010-1161-7. doi:10.1007/978-94-010-1161-7_2.

N. D. Belnap. 1977b. "How a Computer Should Think." In: *Contemporary Aspects of Philosophy*. Oriel Press.

M. Bienvenu. 2020. "A Short Survey on Inconsistency Handling in Ontology-Mediated Query Answering." *Künstliche Intelligenz*, 34, 4, 443–451. doi:10.1007/s13218-020-00680-9.

M. Bienvenu and C. Bourgaux. 2016. "Inconsistency-Tolerant Querying of Description Logic Knowledge Bases." In: *Reasoning Web: Logical Foundation of Knowledge Graph Construction and Query Answering* (Lecture Notes in Computer Science). Vol. 9885. Springer, 156–202. doi:10.1007/978-3-319-49493-7_5.

M. Bienvenu, C. Bourgaux, and D. Kozhemiachenko. 2024. "Queries With Exact Truth Values in Paraconsistent Description Logics." In: *Proceedings of the Twenty-First International Conference on Principles of Knowledge Representation and Reasoning (KR-2024)*. International Joint Conferences on Artificial Intelligence Organization, Hanoi, Vietnam, 145–155. doi:10.24963/kr.2024/14.

M. Bienvenu and M. Ortiz. 2015. "Ontology-Mediated Query Answering With Data-Tractable Description Logics." In: *Reasoning Web. Web Logic Rules* (Lecture Notes in Computer Science). Vol. 9203. Springer, 218–307. doi:10.1007/978-3-319-21768-0_9.
M. Bienvenu and R. Rosati. 2013. "Tractable Approximations of Consistent Query Answering for Robust Ontology-based Data Access." In: *Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI-2013)*.

M. Bilková, S. Frittella, and D. Kozhemiachenko. 2025. "Fuzzy bi-Gödel modal logic and its paraconsistent relatives." *Journal of Logic and Computation*, 35, 2. doi:10.1093/logcom/exae011.

M. Bilková, S. Frittella, and D. Kozhemiachenko. 2023. "Non-standard Modalities in Paraconsistent Gödel Logic." In: *Logics in Artificial Intelligence. Lecture Notes in Artificial Intelligence*. Ed. by S. Gaggl, M. V. Martinez, and M. Ortiz. Springer Nature Switzerland, Cham, 420–436. doi:10.1007/978-3-031-43619-2_29.

S. Borgwardt and R. Peñaloza. 2014. "Consistency Reasoning in Lattice-Based Fuzzy Description Logics." *International Journal of Approximate Reasoning*, 55, 9, 1917–1938. doi:10.1016/J.IJAR.2013.07.006.

D. Calvanese, G. D. Giacomo, D. Lembo, M. Lenzerini, and R. Rosati. 2007. "Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-Lite Family." *Journal of Automated Reasoning*, 39, 3, 385–429. doi:10.1007/s10817-007-9078-x.

J. M. Dunn. 1976. "Intuitive Semantics for First-Degree Entailments and 'Coupled Trees'." *Philosophical Studies*, 29, 3, 149–168.

T. Eiter, T. Łukasiewicz, and L. Predoiu. 2016. "Generalized Consistent Query Answering under Existential Rules." In: *Proceedings of Principles of Knowledge Representation and Reasoning (KR-2016)*. AAAI Press, 359–368. doi:10.5555/3032027.3032070.

H. Gao, D. Kozhemiachenko, and N. Olivetti. 2026. "Paraconsistent constructive modal logic." In: *Logic, Language, Information, and Computation*. Lecture Notes in Computer Science. Vol. 15942. Ed. by D. Kozen and R. d. Queiroz. Springer Nature Switzerland, Cham, 71–88. doi:10.1007/978-3-031-99536-1_5.

S. Gottwald. 2001. *A Treatise on Many-Valued Logics*. Studies in Logic and Computation. Vol. 3. Research studies press.

N. Kamide. 2013. "A Comparison of Paraconsistent Description Logics." *International Journal of Intelligence Science*, 03, 02, 99–109. doi:10.4236/ijis.2013.32011.

T. Kaminski, M. Knorr, and J. Leite. 2015. "Efficient Paraconsistent Reasoning With Ontologies and Rules." In: *Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI-2015)*. AAAI, 3098–3105. doi:10.5555/2832581.2832681.

D. Lembo, M. Lenzerini, R. Rosati, M. Ruzzi, and D. F. Savo. 2010. "Inconsistency-Tolerant Semantics for Description Logics." In: *Web Reasoning and Rule Systems (RR-2010)* (Lecture Notes in Computer Science). Vol. 6333. Springer, Berlin, Heidelberg, 103–117. doi:10.1007/978-3-642-15918-3_9.

Y. Ma and P. Hitzler. 2009. "Paraconsistent Reasoning for OWL 2." In: *Web Reasoning and Rule Systems (RR-2009)*. Lecture Notes in Computer Science. Vol. 5837. Springer Berlin Heidelberg, Berlin, Heidelberg, 197–211. doi:10.1007/978-3-642-05082-4_14.

Y. Ma, P. Hitzler, and Z. Lin. 2007. "Algorithms for Paraconsistent Reasoning With OWL." In: *The Semantic Web: Research and Applications. (ESWC-2007)*. Lecture Notes in Computer Science. Vol. 4519. Springer Berlin Heidelberg, Berlin, Heidelberg, 399–413. doi:10.1007/978-3-642-29356-6_2.

Y. Ma, Z. Lin, and Z. Lin. 2006. "Inferring With Inconsistent OWL DL Ontology: A Multi-Valued Logic Approach." In: *Current Trends in Database Technology (EDBT-2006)*. Lecture notes in computer science. Vol. 4254. Springer Berlin Heidelberg, Berlin, Heidelberg, 535–553. doi:10.1007/11896548_40.

F. Maier. 2010. "Extending Paraconsistent SROIQ." In: *Web Reasoning and Rule Systems (RR-2010)*. Lecture Notes in Computer Science. Vol. 6333. Springer Berlin Heidelberg, Berlin, Heidelberg, 118–132. doi:10.1007/978-3-642-15918-3_10.

F. Maier, Y. Ma, and P. Hitzler. 2013. "Paraconsistent OWL and Related Logics." *Semantic Web Journal*, 4, 4, 395–427. doi:10.3233/SW-2012-0066.

C. Meghini and U. Straccia. 1996. "A relevance terminological logic for information retrieval." In: *Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval*. ACM Press, Zurich, Switzerland. doi:10.1145/243199.243267.

L. A. Nguyen and A. Szalas. 2012. "Paraconsistent Reasoning for Semantic Web Agents." In: *Proceedings of Transactions on Computational Collective Intelligence VI*. Lecture Notes in Computer Science. Vol. 7190. Springer Berlin Heidelberg, Berlin, Heidelberg, 36–55. doi:10.1007/978-3-642-29356-6_2.

S. Odintsov and H. Wansing. 2003. "Inconsistency-Tolerant Description Logic: Motivation and Basic Systems." *Studia Logica*, 31, 301–335. doi:10.1007/978-94-017-3598-8_11.

H. Omori and K. Sano. 2015. "Generalizing Functional Completeness in Belnap-Dunn Logic." *Studia Logica*, 103, 5, 883–917. doi:10.1007/s11225-014-9597-5.

M. Ortiz and M. Šimkus. 2012. "Reasoning and Query Answering in Description Logics." In: *Reasoning Web. Semantic Technologies for Advanced Query Answering* (Lecture Notes in Computer Science). Vol. 7487. Springer, 1–53. doi:10.1007/978-3-642-33158-9_1.

P. F. Patel-Schneider. 1989. "A Four-Valued Semantics for Terminological Logics." *Artificial Intelligence*, 38, 3, 319–351. doi:10.1016/0004-3702(89)90036-2.

A. Poggi, D. Lembo, D. Calvanese, G. De Giacomo, M. Lenzerini, and R. Rosati. 2008. "Linking Data to Ontologies." *Journal of Data Semantics*, 10, 133–173. doi:10.1007/978-3-540-77688-8_5.

G. Priest. 2008. *An Introduction to Non-Classical Logic. From If to Is*. (2nd ed.). Cambridge University Press. 613+xxxii. ISBN: 978-0-521-85433-7.

R. Rosati. 2011. "On the Complexity of Dealing with Inconsistency in Description Logic Ontologies." In: *IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence*. Ed. by T. Walsh. IJCAI/AAAI, 1057–1062. doi:10.5591/978-1-57735-516-8/IJCAI11-181.

K. Sano and H. Omori. 2014. "An Expansion of First-Order Belnap-Dunn Logic." *Logic Journal of IGPL*, 22, 3, 458–481. doi:10.1093/jigpal/jzt044.
A. Schaerf. 1993. "On the Complexity of the Instance Checking Problem in Concept Languages With Existential Quantification." *Journal of Intelligent Information Systems*, 2, 3, 265–278. doi:10.1007/BF00962071.

E. Y. Sherkhonov. 2008. "Modal operators over constructive logic." *Journal of Logic Computation*, 18, 6, 815–829. doi:10.1093/logcom/exn016.

D. Skurt. 2020. *Mehrwertige Aussagenlogik*. Ruhr-Universität Bochum.

U. Straccia. 1997. "A Sequent Calculus for Reasoning in Four-Valued Description Logics." In: *Automated Reasoning with Analytic Tableaux and Related Methods* (Lecture Notes in Artificial Intelligence). Ed. by D. Galmiche. Vol. 1227. Springer, 343–357. doi:10.1007/BFB0027425.

S. Tobies. 2001. "Complexity Results and Practical Algorithms for Logics in Knowledge Representation." Ph.D. Dissertation. RWTH Aachen University, Germany.

G. Xiao, D. Calvanese, R. Kontchakov, D. Lembo, A. Poggi, R. Rosati, and M. Zakharyaschev. 2018. "Ontology-Based Data Access: A Survey." In: *Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI-2018)*, 5511–5519. doi:10.24963/ijcai.2018/777.

X. Zhang and Z. Lin. 2008. "Paraconsistent reasoning with quasi-classical semantic in *ALC*." In: *Web Reasoning and Rule Systems*. Lecture Notes in Computer Science. Springer Berlin Heidelberg, Berlin, Heidelberg, 222–229. doi:10.1007/978-3-540-88737-9_18.

X. Zhang, Z. Lin, and K. Wang. 2010. "Towards a Paradoxical Description Logic for the Semantic Web." In: *Foundations of Information and Knowledge Systems* (Lecture Notes in Computer Science). Vol. 5956. Springer Berlin Heidelberg, Berlin, Heidelberg, 306–325. doi:10.1007/978-3-642-11829-6_20.

X. Zhang, G. Qi, Y. Ma, and Z. Lin. 2009. "Quasi-Classical Semantics for Expressive Description Logics." In: *Proceedings of the 22nd International Workshop on Description Logic (CEUR Workshop Proceedings)*. Vol. 477. Aachen.

X. Zhang, G. Xiao, Z. Lin, and J. v. Bussche. 2014. "Inconsistency-Tolerant Reasoning With OWL DL." *International Journal of Approximate Reasoning*, 55, 2, 557–584. doi:10.1016/j.ijar.2013.09.005.

L. Zhou, H. Huang, G. Qi, Y. Ma, Z. Huang, and Y. Qu. 2012. "Paraconsistent Query Answering Over DL-Lite Ontologies." *Web Intelligence and Agent Systems: An International Journal*, 10, 1, 19–31. doi:10.3233/WIA-2012-0228.

Received 15 April 2025; accepted 29 January 2026