Inconsistency-Tolerant Query Answering: Rationality Properties and Computational Complexity Analysis

Abstract

Generalising the state of the art, an inconsistency-tolerant semantics can be seen as a couple composed of a modifier operator and an inference strategy. In this paper we deepen the analysis of such general setting and focus on two aspects. First, we investigate the rationality properties of such semantics for existential rule knowledge bases. Second, we unfold the broad landscape of complexity results of inconsistency-tolerant semantics under a specific (yet expressive) subclass of existential rules.

1 Introduction

Within the Ontology-Based Data Access [17, 18] setting, this paper addresses the problem of query answering when the assertional base (which stores data) is inconsistent with the ontology (which represents generic knowledge about a domain). Recently, a general framework for inconsistency-tolerant semantics was proposed in [2]. This framework considers two key notions: modifiers and inference strategies. Inconsistency-tolerant query answering is seen as made out of a modifier, which transforms the original ABox into a so-called MBox, which is a set of consistent ABoxes (w.r.t. the TBox), and an inference strategy, which evaluates queries against this MBox knowledge base. Interestingly enough, such setting unifies main existing work and captures various semantics in the literature (see e.g., [1, 6, 16]). The obtained semantics were compared with respect to the productivity of their inference.

This paper goes one step further in the characterization of these inconsistency-tolerant semantics by carrying out an analysis in terms of rationality properties and data complexity. The rationality properties are considered for existential rule knowledge bases [3, 9] (a prominent ontology language that generalizes lightweight description logics). On the one hand we study basic properties of semantics such as their behaviour with respect to the conjunction and consistency of inferred conclusions. On the other hand, starting from the obvious observation that inconsistency-tolerant semantics are inherently nonmonotonic, we investigate their behaviour with respect to properties introduced for nonmonotonic inference [14] that we rephrase in our framework. Entailment with general existential rules being undecidable, complexity is studied for a specific (yet expressive) subclass of existential rules known as Finite Unification Sets (FUS) [3], which in particular generalizes the description logic DL-Lite$_\mathcal {R}$ dedicated to query answering [10] (see also the OWL2-QL profile).

Before presenting our contributions, we provide some preliminaries on the logical setting and briefly recall the unified framework for inconsistency-tolerant semantics.

2 Preliminaries

We consider first-order logical languages without function symbols, hence a term is a variable or a constant. An atom is of the form $p(t_1,\ldots ,t_k)$ where p is a predicate name of arity k, and the $t_i$ are terms. A (factual) assertion is an atom without variables (also named a ground atom). A Boolean conjunctive query ¹ (and simply query in the following) is an existentially closed conjunction of atoms, that we will consider as a set of atoms, leaving quantifiers implicit. Given a set of assertions ${\mathcal {A}}$ and a query q, the answer to q over ${\mathcal {A}}$ is yes iff ${\mathcal {A}}\models q$, where $\models$ denotes the standard logical consequence. Given two sets of atoms $S_1$ and $S_2$ (with disjoint sets of variables), a homomorphism h from $S_1$ to $S_2$ is a substitution of the variables in $S_1$ by the terms in $S_2$ such that $h(S_1) \subseteq S_2$ (where $h(S_1)$ is obtained from $S_1$ by substituting each variable according to h). It is well-known that, given two existentially closed conjunctions of atoms $f_1$ and $f_2$ (for instance queries and conjunctions of factual assertions), $f_1 \models f_2$ iff there is a homomorphism from the set of atoms in $f_2$ to the set of atoms in $f_1$.

A knowledge base can be seen as a database enhanced with an ontological component. Since inconsistency-tolerant query answering has been mostly studied in the context of description logics (DLs), and especially DL-Lite, we will use some DL vocabulary, like ABox for the data and TBox for the ontology. However, our framework is not restricted to DLs, hence we define TBoxes and ABoxes in terms of first-order logic (and more precisely in the existential rule framework). We assume the reader familiar with the basics of DLs and their logical translation.

An ABox is a set of factual assertions. As a special case we have DL assertions restricted to unary and binary predicates. A positive axiom is of the form $\forall \mathbf {x} \forall \mathbf {y}(B[\mathbf {x},\mathbf {y}] \rightarrow \exists \mathbf {z}~H[\mathbf {y},\mathbf {z}])$ where B and H are conjunctions of atoms; in other words, it is a positive existential rule. As a special case, we have for instance concept and role inclusions in DL-Lite$_{\mathcal R}$, which are respectively of the form $B_1 \sqsubseteq B_2$ and $S_1 \sqsubseteq S_2$, where $B_i := A~| ~\exists S$ and $S_i := P ~| ~P^-$ (with A an atomic concept, P an atomic role and $P^{-}$ the inverse of an atomic role). A negative axiom is of the form $\forall \mathbf {x} (B[\mathbf {x}] \rightarrow \bot )$ where B is a conjunction of atoms; in other words, it is a negative constraint. As a special case, we have for instance disjointness axioms in DL-Lite$_{\mathcal R}$, which are inclusions of the form $B_1\sqsubseteq \lnot B_2$ and $S_1 \sqsubseteq \lnot S_2$, or equivalently $B_1\sqcap B_2 \sqsubseteq \bot$ and $S_1\sqcap S_2 \sqsubseteq \bot$.

A TBox ${\mathcal {T}}= {\mathcal {T}}_p \cup {\mathcal {T}}_n$ is partitioned into a set ${\mathcal {T}}_p$ of positive axioms and a set ${\mathcal {T}}_n$ of negative axioms. Finally, a knowledge base (KB) is of the form ${\mathcal {K}}{=}\langle {\mathcal {T}},{\mathcal {A}}\rangle$ where ${\mathcal {A}}$ is an ABox and ${\mathcal {T}}$ is a TBox. Such a KB is logically interpreted as the conjunction of its elements. ${\mathcal {K}}$ is said to be consistent if ${\mathcal {T}}\cup {\mathcal {A}}$ is satisfiable, otherwise it is said to be inconsistent. We also say that ${\mathcal {A}}$ is consistent (or inconsistent) with ${\mathcal {T}}$, which reflects the assumption that the TBox is reliable while the ABox may not. The answer to a query q over a consistent KB ${\mathcal {K}}$ is yes iff $\langle {\mathcal {T}},{\mathcal {A}}\rangle \models q$. When ${\mathcal {K}}$ is inconsistent, standard consequence is not appropriate since all queries would be positively answered.

The notion of a (virtual) repair is a key notion in inconsistency-tolerant query answering. A repair is a subset of the ABox consistent with the TBox and inclusion-maximal for this property: ${\mathcal {R}}\subseteq {\mathcal {A}}$ is a repair of ${\mathcal {A}}$ w.r.t. ${\mathcal {T}}$ if (i) $\langle {\mathcal {T}},{\mathcal {R}}\rangle$ is consistent, and (ii) $\forall {\mathcal {R}}' \subseteq \mathcal A$, if ${\mathcal {R}}\varsubsetneq {\mathcal {R}}'$ (${\mathcal {R}}$ is strictly included in ${\mathcal {R}}'$) then $\langle {\mathcal {T}},{\mathcal {R}}'\rangle$ is inconsistent. We denote by ${\mathcal {R}}({\mathcal {A}})$ the set of ${\mathcal {A}}$’s repairs (for easier reading, we often leave $\mathcal T$ implicit in our notations). Note that ${\mathcal {R}}({\mathcal {A}}){=}\{\mathcal A\}$ iff $\mathcal A$ is consistent. The most commonly considered semantics for inconsistency-tolerant query answering, inspired from previous works in databases, is the following: q is said to be a consistent consequence of ${\mathcal {K}}$ if it is a standard consequence of each repair of ${\mathcal {A}}$ [1]. Several variants of this semantics have been proposed, which differ in their behaviour (cautiousness w.r.t. inconsistencies) and their computational complexity, see in particular [1, 6, 16].

3 A Unified Framework for Inconsistency-Tolerant Query Answering

In this section we recall the framework introduced in [2] for the study of inconsistency-tolerant query answering semantics. In this framework, semantics are defined by two components: a modifier and an inference strategy, applied on MBox knowledge bases. An MBox KB is simply a KB with multiple ABoxes of the form ${\mathcal {K}}_{\mathcal {M}}{=}\langle {\mathcal {T}},{\mathcal {M}}\rangle$ where ${\mathcal {T}}{=} {\mathcal {T}}_p \cup {\mathcal {T}}_n$ is a TBox and ${\mathcal {M}}{=}\{{\mathcal {A}}_1,\ldots ,{\mathcal {A}}_m\}$ is a set of ABoxes, called an MBox. A standard KB will be seen as an MBox with $m = 1$. An MBox KB ${\mathcal {K}}_{\mathcal {M}}$ is said to be consistent, or ${\mathcal {M}}$ is said to be consistent (with ${\mathcal {T}}$), if each ${\mathcal {A}}_i$ in ${\mathcal {M}}$ is consistent (with ${\mathcal {T}}$). A modifier transforms a possibly inconsistent MBox KB into an MBox KB such that, when the latter is consistent, it can be provided as input to the inference strategy that determines if the query is entailed.

A (composite) modifier is a finite combination of elementary modifiers. In [2] the three following kinds of elementary modifiers are introduced:

• Expansion modifiers, which expand an MBox by explicitly adding some inferred assertions to its ABoxes. A natural expansion modifier is the ground positive closure of an MBox, which computes the closure of each ABox with respect to the positive axioms of the TBox, keeping only ground atoms: $\circ _{cl}({\mathcal {M}})=\{\textit{Cl}({\mathcal {A}}_i) | {\mathcal {A}}_i \in {\mathcal {M}}\}$, where $\textit{Cl}({\mathcal {A}}_i) = \{$ground atom $a ~| \langle {\mathcal {T}}_p,{\mathcal {A}}_i\rangle \models a \}$.

• Splitting modifiers, which replace each ${\mathcal {A}}_i$ of an MBox by one or several of its maximally consistent subsets (hence, they always produce consistent MBoxes). A natural splitting modifier splits each ABox into the set of its repairs: $\circ _{rep}({\mathcal {M}})=\bigcup _{{\mathcal {A}}_i\in {\mathcal {M}}}\{{\mathcal {R}}({\mathcal {A}}_i)\}.$

• Selection modifiers, which select some elements of an MBox. A natural selection modifier is the cardinality-based selection modifier, which selects the largest ABoxes of an MBox: $\circ _{card}({\mathcal {M}})=\{{\mathcal {A}}_i \in {\mathcal {M}}|\forall {\mathcal {A}}_j \in {\mathcal {M}}, |{\mathcal {A}}_j|\le |{\mathcal {A}}_i|\}.$

Note that the cardinality-based selection function fully makes sense when inconsistency is due to the presence of multiple sources. Other selection functions, such as the ones based on rational closure or System Z [11] may be used, especially when inconsistency reflects the presence of exceptions in axioms of the TBox.

Many composite modifiers can be potentially defined using the three above “natural” modifiers, however this number is considerably reduced if we focus on non-equivalent modifiers: indeed, any composite modifier that produces a consistent MBox from a standard ABox, and obtained by combining the elementary modifiers $\circ _{rep}$, $\circ _{card}$ and $\circ _{cl}$, is equivalent to one of the eight modifiers listed in Table 1. To ease reading, these modifiers are also denoted by abbreviations reflecting the order in which the elementary modifiers are applied, and using the following letters: $\mathsf {R}$ for $\circ _{rep}$, $\mathsf {C}$ for $\circ _{cl}$ and $\mathsf {M}$ for $\circ _{card}$. Different kinds of inclusion relations hold between modifiers (see [2] for details).

Example 1

Let ${\mathcal {K}}_{\mathcal {M}}=\langle {\mathcal {T}},{\mathcal {M}}\rangle$ be an MBox KB where ${\mathcal {T}}$=$\{A(x){\wedge }B(x){\rightarrow \bot }$, $A(x)\wedge C(x){\rightarrow \bot }$, $B(x){\wedge }C(x){\rightarrow \bot }$, $A(x){\rightarrow }D(x)$, $B(x){\rightarrow }D(x)$, $C(x){\rightarrow }D(x)$, $B(x){\rightarrow }E(x)$, $C (x){\rightarrow }E(x)\}$ and ${\mathcal {M}}{=}\{\{A(a),B(a),C(a),A(b)\}\}$. With $\mathsf {R}$, we get $\circ _1({\mathcal {M}}){=}\{\{A(a)$, $A(b)\}$,$\{B(a),A(b)\}$,$\{C(a),A(b)\}\}$. With $\mathsf {CR}$: $\circ _5({\mathcal {M}}){=}\{\{A(a),D(a),A(b),D(b)\}$, $\{B(a),D(a),E(a)$, A(b),$D(b)\}$, $\{C(a),D(a),E(a),A(b)$, $D(b)\}\}$. With $\mathsf {MCR}$: $\circ _6({\mathcal {M}})$ = $\{\{B(a),D(a),E(a),A(b),D(b)\},\{C(a),D(a)$, E(a), A(b), $D(b)\}\}$.

An inference strategy takes as input a consistent MBox KB ${\mathcal {K}}_{\mathcal {M}}$=$\langle {\mathcal {T}},{\mathcal {M}}\rangle$ and a query q and determines if q is entailed from ${\mathcal {K}}_{\mathcal {M}}$. Four main inference strategies are considered, namely universal (also known as skeptical), safe, majority-based and existential (also called brave). They are formally defined as follows:

Table 1. The eight composite modifiers for an MBox ${\mathcal {K}}_{\mathcal {M}}$=$\langle {\mathcal {T}},{\mathcal {M}}=\{{\mathcal {A}}\}\rangle$

• universal consequence: ${\mathcal {K}}_{\mathcal {M}}\models _{\forall } q$ if $\forall {\mathcal {A}}_i \in {\mathcal {M}}$,$\langle {\mathcal {T}},{\mathcal {A}}_i\rangle \models q$.

• safe consequence: ${\mathcal {K}}_{\mathcal {M}}\models _{\cap } q$ if $\langle {\mathcal {T}},\bigcap _{{\mathcal {A}}_i\in {\mathcal {M}}}{\mathcal {A}}_i\rangle \models q$.

• majority-based consequence: ${\mathcal {K}}_{\mathcal {M}}\models _{maj} q$ if $\left. \frac{|{\mathcal {A}}_i: {\mathcal {A}}_i \in {\mathcal {M}},\langle {\mathcal {T}},{\mathcal {A}}_i\rangle \models q|}{|{\mathcal {M}}|} \right. > 1/2$.

• existential consequence: ${\mathcal {K}}_{\mathcal {M}}\models _{\exists } q$ if $\exists {\mathcal {A}}_i \in {\mathcal {M}}$, $\langle {\mathcal {T}},{\mathcal {A}}_i\rangle \models q$.

Given two inference strategies $s_i$ and $s_j$, $s_i$ is said to be more cautious than $s_j$, denoted $s_i \le s_j$, if for any consistent MBox ${\mathcal {K}}_{\mathcal {M}}$ and any query q, if ${\mathcal {K}}_{\mathcal {M}}\models _{s_i} q$ then ${\mathcal {K}}_{\mathcal {M}}\models _{s_j} q$. The considered inference strategies are totally ordered by $\le$ as follows: $\cap \le \forall \le maj \le \exists$.

Fig. 1.

Productivity of inconsistency-tolerant semantics where $X{\longrightarrow }Y$ means that Y is strictly more productive than X.

An inconsistency-tolerant query answering semantics is then defined by a composite modifier and an inference strategy.

Definition 1

Let ${\mathcal {K}}{=}\langle {\mathcal {T}},{\mathcal {A}}\rangle$ be a standard KB, $\circ _i$ be a composite modifier and $s_j$ be an inference strategy. A query q is said to be an $\langle \circ _i,s_j\rangle$ -consequence of ${\mathcal {K}}$, denoted by ${\mathcal {K}}$ $\models _{\langle \circ _i, s_j \rangle } q$, if it is entailed from the MBox KB $\langle {\mathcal {T}},\circ _i(\{{\mathcal {A}}\})\rangle$ by the strategy $s_j$.

Note that the main semantics from the literature [1, 6, 16] are covered by this definition: AR, IAR and ICR semantics respectively correspond to $\langle \mathsf {R},\forall \rangle$, $\langle \mathsf {R},\cap \rangle$, and $\langle \mathsf {CR}, \cap \rangle$.²

Example 2

Consider the input KB ${\mathcal {K}}_{\mathcal {M}}{=}\langle {\mathcal {T}},{\mathcal {M}}\rangle$ from Example 1. $\circ _1({\mathcal {M}}) = {\mathcal {M}}_1 = \{\{A(a),A(b)\},\{B(a),A(b)\}$,$\{C(a),A(b)\}\}$. Since $A(b) \in \bigcap _{{\mathcal {A}}{_i}_\in {\mathcal {M}}_1}$ and $A(x){\rightarrow }D(x)$, ${\mathcal {K}}\models _{\langle \circ _1, \cap \rangle }D(b)$ holds. Hence, we also have ${\mathcal {K}}\models _{\langle \circ _1, \forall \rangle }D(b)$. Furthermore ${\mathcal {K}}\models _{\langle \circ _1, \forall \rangle }D(a)$. By $\langle \circ _1,maj\rangle$, E(a) is furthermore entailed. Indeed, $\langle {\mathcal {T}},\{B(a),A(b)\}\rangle \models E(a)$ and $\langle {\mathcal {T}},\{C(a),A(b)\}\rangle \models E(a)$ and $|{\mathcal {M}}_1|$=3. By $\langle \circ _1,\exists \rangle$, A(a) is also entailed. Let $q = \exists x D(x) \wedge E(x)$. Then q is a consequence of $\langle \circ _1,maj\rangle$ and $\langle \circ _1,\exists \rangle$.

The obtained semantics have been compared from a productivity point of view. Formally, a semantics $\langle \circ _i,s_k\rangle$ is less productive than a semantics $\langle \circ _j,s_l\rangle$ if, for any KB ${\mathcal {K}}{=}\langle {\mathcal {T}},{\mathcal {A}}\rangle$ and any query q, if ${\mathcal {K}}\models _{\langle \circ _i, s_k \rangle } q$ then ${\mathcal {K}}\models _{\langle \circ _j, s_l \rangle } q$. This productivity relation is a preorder, which can be established by considering on the one hand the inclusion relations between composite modifiers and on the other hand the cautiousness total order on inference, as detailed below. Figure 1 depicts the results about semantics defined with the same inference strategy (note that transitivity edges are not drawn and no other edges hold). Then Theorem 1 extends these results to semantics possibly based on different inference strategies. In particular, if $s_k<s_l$ then, for all modifiers $\circ _i$ and $\circ _j$, $\langle \circ _i, s_k \rangle$ is strictly less productive than $\langle \circ _i, s_l \rangle$, and $\langle \circ _j,s_l\rangle$ is at least as productive as $\langle \circ _i,s_k\rangle$.

Theorem 1

(Productivity of semantics [2]). The inclusion relation $\sqsubseteq$ is the smallest relation that contains the inclusions $\langle \circ _i,s_k \rangle \sqsubseteq \langle \circ _j , s_k\rangle$ defined by the inclusions in Fig. 1a to d and satisfying the two following conditions: (1) for all $s_j$, $s_p$ and $o_i$, if $s_j \le s_p$ then $\langle \circ _i , s_j \rangle \sqsubseteq \langle \circ _i, s_p \rangle$; (2) it is transitive.

It follows from Theorem 1 that 26 different semantics are obtained (out of the possible 32 inference relations used in Fig. 1). We point out that this result holds even when KBs are restricted to DL-Lite$_\mathcal R$ TBoxes. Finally, note that when the initial KB is consistent, all semantics correspond to standard entailment, i.e., given a consistent standard KB ${\mathcal {K}}$ and a query q, ${\mathcal {K}}\models _{\langle \circ _i, s \rangle }q$ iff ${\mathcal {K}}\models q$, for all $1 \le i\le 8$ and $s\in \{\cap$,$\forall$,$\exists$,$maj\}$.

4 Rationality Properties of Inconsistency-Tolerant Semantics

This section is dedicated to the logical properties of inconsistency-tolerant semantics. We first analyze the behaviour of these semantics w.r.t the conjunction (or set union) and the consistency of inferred conclusions for a fixed KB. We then turn our attention to the fact that these semantics are inherently nonmonotonic. Indeed, if some query q is entailed from a KB using a semantics $\langle \circ _i,s_j\rangle$, then q may be questionable in the light of new factual assertions. We will assume that these new factual assertions are sure (and will speak of conditional inference, opposed to unconditional inference when the KB is fixed). Hence, we also analyze inconsistency-tolerant semantics w.r.t rationality properties introduced for nonmonotonic inference that we recast in our framework.

4.1 Properties of Unconditional Inference

Let ${\mathcal {K}}_{\mathcal {M}}$=$\langle {\mathcal {T}},\{{\mathcal {A}}\}\rangle$ be a possibly inconsistent KB and $\langle o_i, s \rangle$ denote any semantics with $\circ _i\in \{ \mathsf {R}$, $\mathsf {MR}$, $\mathsf {CMR}$, $\mathsf {MCMR}$, $\mathsf {CR}$,$\mathsf {MCR}$, $\mathsf {RC}$, $\mathsf {MRC}\}$ and $s \in \{\forall , \cap , \exists , maj \}$. We define the following desirable properties:  

QCE:

(Query Conjunction Elimination) For any KB ${\mathcal {K}}_{\mathcal {M}}$ and any queries $q_1$ and $q_2$, if ${\mathcal {K}}_{\mathcal {M}}\models _{\langle \circ _i, s \rangle } q_1\wedge q_2$ then ${\mathcal {K}}_{\mathcal {M}}\models _{\langle \circ _i, s \rangle } q_1$ and ${\mathcal {K}}_{\mathcal {M}}\models _{\langle \circ _i, s \rangle } q_2$.

QCI:

(Query Conjunction Introduction) For any KB ${\mathcal {K}}_{\mathcal {M}}$ and any queries $q_1$ and $q_2$, if ${\mathcal {K}}_{\mathcal {M}}\models _{\langle \circ _i, s \rangle } q_1$ and ${\mathcal {K}}_{\mathcal {M}}\models _{\langle \circ _i, s \rangle } q_2$ then ${\mathcal {K}}_{\mathcal {M}}\models _{\langle \circ _i, s \rangle }q_1\wedge q_2$.

Cons:

(Consistency) For any set of assertions $\mathcal A'$, if ${\mathcal {K}}_{\mathcal {M}}\models _{\langle \circ _i, s \rangle }{\mathcal {A}}'$ then $\langle {\mathcal {T}},{\mathcal {A}}'\rangle$ is consistent.

ConsC:

(Consistency of Conjunction) For any set of assertions ${\mathcal {A}}$, if for all $f\in {\mathcal {A}}$, ${\mathcal {K}}_{\mathcal {M}}\models _{\langle \circ _i, s \rangle } f$ then $\langle {\mathcal {T}},{\mathcal {A}}\rangle$ is consistent.

ConsS:

(Consistency of Support) For any set of assertions ${\mathcal {A}}'$, if ${\mathcal {K}}_{\mathcal {M}}\models _{\langle \circ _i, s \rangle } {\mathcal {A}}'$ then there is $R \in \mathcal R(\mathcal A)$, such that $\langle {\mathcal {T}},R\rangle \models {\mathcal {A}}'$.

 

Note that in the three last properties, the sets of assertions could be extended to queries with a more complex formulation. We first remind that, when $\mathcal K_{\mathcal {M}}$ is consistent, all semantics correspond to standard entailment, hence ${\mathcal {K}}_{\mathcal {M}}\models _{\langle \circ _i, s \rangle }q_1\wedge q_2$ iff ${\mathcal {K}}_{\mathcal {M}}\models _{\langle \circ _i, s \rangle } q_1$ and ${\mathcal {K}}_{\mathcal {M}}\models _{\langle \circ _i, s \rangle } q_2$. When ${\mathcal {K}}_{\mathcal {M}}$ is inconsistent, one direction is still true for all semantics, namely Property QCE, which relies on the consistency of a repair. The converse direction, namely Property QCI, is obviously satisfied by universal and safe semantics but not by brave and majority-based semantics, even when $q_1$ and $q_2$ are ground atoms and the TBox contains only disjointness inclusions as shown by the next examples.

Example 3

(Majority-based semantics does not satisfy QCI ). ³ Let ${\mathcal {T}}$=$\{B \sqcap C \sqsubseteq \bot$, $A \sqcap D\sqsubseteq$ $\bot$, $C\sqcap D\sqsubseteq \bot \}$ and ${\mathcal {A}}$=$\{A(a),B(a),C(a),D(a)\}$. The repairs are $\{A(a)$,$B(a)\}$, $\{A(a)$, $C(a)\}$ and $\{B(a)$,$D(a)\}$. All modifiers give the same MBox since $\mathcal T_p$=$\emptyset$ and the repairs have the same size. A(a) and B(a) are each entailed by a majority of repairs but their conjunction is not.

Example 4

(Brave semantics does not satisfy properties QCI and ConsC ). Let ${\mathcal {T}}$=$\{A\sqcap$ B $\sqsubseteq \bot \}$ and ${\mathcal {A}}$=$\{A(a)$,$B(a)\}$. The repairs are $\{A(a)\}$ and $\{B(a)\}$. All modifiers lead to the same MBox since $\mathcal T_p$=$\emptyset$ and the repairs have the same size. A(a) and B(a) are both brave consequences but their conjunction is not. Besides ConsC is not satisfied since $\langle {\mathcal {T}}, \{A(a)$, $B(a)\}\rangle$ is inconsistent.

Property Cons is true for any semantics (again by the consistency of a repair). Property ConsC holds for universal and safe semantics, and is false for any brave semantics, even for $|A_j|$=$|A_k|$=1 and DL-Lite TBoxes restricted to disjointness inclusions (see Example 3). Majority-based semantics are an interesting case, since the expressivity of the ontological language plays a role: Property ConsC is satisfied by all majority-based semantics when the language is restricted to DL-Lite$_{\mathcal R}$ and not satisfied as soon as we allow concept inclusions of the form $A \sqcap B\sqsubseteq C$ or ternary disjointness axioms of the form $A\sqcap B \sqcap C\sqsubseteq \bot$, even with ground queries (see Example 6). The fundamental reason why majority-based semantics satisfy Property ConsC over DL-Lite$_{\mathcal R}$ KBs is that, in these KBs, conflicts (i.e., minimal inconsistent subsets of the ABox) are necessarily of size two. When two ground atoms $a_1$ and $a_2$ are inferred with a majority-based strategy, at least one of element of the considered (consistent) MBox classically entails both $a_1$ and $a_2$, hence $a_1\wedge a_2$ is consistent; when conflicts are of size two, pairwise consistency entails global consistency. Note that this property still holds if we extend DL-Lite$_{\mathcal R}$ to n-ary predicates.

Example 5

(Majority-based semantics does not satisfy Property ConsC for slight generalizations of DL-Lite $_{\mathcal R}$ ). Let ${\mathcal {T}}$=$\{A \sqcap B\sqcap C\sqsubseteq \bot \}$ and ${\mathcal {A}}$=$\{A(a),B(a),$ $C(a)\}$. The repairs are $\{A(a), B(a)\}$, $\{A(a), C(a)\}$ and $\{B(a), C(a)\}$. All modifiers give the same MBox since ${\mathcal {T}}_p$=$\emptyset$ and all the repairs have the same size. Each atom from ${\mathcal {A}}$ is entailed (by 2 / 3 repairs), however ${\mathcal {A}}$ itself is not.

Finally, Property ConsS, which expresses that every conclusion has a consistent support in the ABox, is satisfied by all semantics except those involving modifiers $\mathsf {RC}$ and $\mathsf {MRC}$ (as illustrated by the next example).

Example 6

( $\mathsf {(M)RC}$ -based semantics do not satisfy Property ConsS ). ⁴ Let ${\mathcal {T}}{=}\{A\sqcap B\sqsubseteq$ $\bot$, $A\sqsubseteq C_1, B \sqsubseteq C_2 \}$ and ${\mathcal {A}}{=}\{A(a),B(a)\}$. The (maximal) repairs of the ABox’ closure are $\{A(a), C_1(a), C_2(a)\}$ and $\{B(a), C_1(a), C_2(a)\}$. The set of atoms $A_j = \{C_1(a), C_2(a)\}$ is entailed by all semantics based on RC and MRC, however no consistent subset of $\mathcal A$ allows to entail $A_j$ using $\mathcal T$.

Proposition 1

(Properties of unconditional inference). The behaviour of semantics $\langle \circ _i,s\rangle$, with $\circ _i\in \{\mathsf {R}$, $\mathsf {MR}$,$\mathsf {CMR}$,$\mathsf {MCMR}$, $\mathsf {CR}$, $\mathsf {MCR}$, $\mathsf {RC}$, $\mathsf {MRC}\}$ and $s \in \{\cap , \forall , maj, \exists \}$, with respect to Properties QCE, QCI, Cons, ConsC and ConsS, is stated in Table 2.

Table 2. Properties of unconditional inferences.

4.2 Properties of Conditional Inferences

We now analyze more finely the inconsistency-tolerant semantics by considering their properties in terms of nonmonotonic inference. Within propositional logic setting, several approaches have been proposed for nonmonotonic inference (e.g. [5, 12, 14]). In such approaches nonmonotonicity is essentially caused by the fact that initial knowledge used for inference process is incomplete, and thus, later information may come to enrich them, which generally leads to revise some of the a priori considered hypotheses.

Let ${\mathcal {K}}_{\mathcal {M}}{=}\langle {\mathcal {T}},\{{\mathcal {A}}\}\rangle$ be a possibly inconsistent KB and ${\mathcal {A}}_{\alpha }$, ${\mathcal {A}}_{\beta }$ be two sets of assertions such that $\langle {\mathcal {T}},{\mathcal {A}}_{\alpha }\rangle$ and $\langle {\mathcal {T}},{\mathcal {A}}_{\beta }\rangle$ are consistent. Assume that ${\mathcal {A}}_{\alpha }$ is the newly added knowledge. Since ${\mathcal {A}}_{\alpha }$ is considered as more reliable than the assertions in the KB, we have to keep ${\mathcal {A}}_\alpha$ in every selected repair of the KB. For the sake of simplicity, we define the notion of the set of repairs of ${\mathcal {K}}_{\mathcal {M}}$ in presence of a new consistent set of assertions ${\mathcal {A}}_{\alpha }$ with respect to a modifier $\circ _i$: ${{\mathcal {M}}}_i^{\alpha }{=}\{R{:}R \in \circ _i(\{{\mathcal {A}}\cup {\mathcal {A}}_{\alpha }\}) \,$and$\, {\mathcal {A}}_{\alpha } \subseteq R\}$. Now, we say that ${\mathcal {A}}_{\beta }$ is a nonmonotonic consequence of ${\mathcal {A}}_{\alpha }$ w.r.t. ${\mathcal {K}}_{\mathcal {M}}$, denoted by ${\mathcal {A}}_{\alpha }|\!\!\!\sim _{\circ _i, s}{\mathcal {A}}_{\beta }$, if $\langle {\mathcal {T}},{{\mathcal {M}}}_i^{\alpha }\rangle \models _s {\mathcal {A}}_{\beta }$.

In this study, we focus on the situation where the considered conclusions are sets of assertions, which can also be seen as conjunctions of ground queries. We first rephrase within our framework some KLM rationality properties [14]. Let ${\mathcal {A}}_{\alpha }$, ${\mathcal {A}}_{\beta }$ and ${\mathcal {A}}_{\gamma }$ be consistent sets of assertions w.r.t ${\mathcal {T}}$ and ${|\!\!\!\sim }$ be an inference relation, the KLM logical properties that we consider are the following⁵.

 

R :

(Reflexivity)  ${\mathcal {A}}_{\alpha }{|\!\!\!\sim }{\mathcal {A}}_{\alpha }$.

LLE :

(Left Logical Equivalence) If $\langle {\mathcal {T}},{\mathcal {A}}_{\alpha }\rangle \equiv \langle {\mathcal {T}},{\mathcal {A}}_{\beta }\rangle$ and ${\mathcal {A}}_{\alpha } {|\!\!\!\sim }{\mathcal {A}}_{\gamma }$ then ${\mathcal {A}}_{\beta }{|\!\!\!\sim }{\mathcal {A}}_{\gamma }$.

RW :

(Right Weakening)   If $\langle {\mathcal {T}},{\mathcal {A}}_{\alpha }\rangle \models \langle {\mathcal {T}},{\mathcal {A}}_{\beta }\rangle$ and ${\mathcal {A}}_{\gamma }{|\!\!\!\sim }{\mathcal {A}}_{\alpha }$ then ${\mathcal {A}}_{\gamma }{|\!\!\!\sim }{\mathcal {A}}_{\beta }$.

Cut :

 If ${\mathcal {A}}_{\alpha }{|\!\!\!\sim }{\mathcal {A}}_{\beta }$ and ${\mathcal {A}}_{\alpha }\cup {\mathcal {A}}_{\beta }{|\!\!\!\sim }{\mathcal {A}}_{\gamma }$ then ${\mathcal {A}}_{\alpha }{|\!\!\!\sim }{\mathcal {A}}_{\gamma }$.

CM :

(Cautious Monotony)  If ${\mathcal {A}}_{\alpha }{|\!\!\!\sim }{\mathcal {A}}_{\beta }$ and ${\mathcal {A}}_{ \alpha }{|\!\!\!\sim }{\mathcal {A}}_{\gamma }$ then ${\mathcal {A}}_{\alpha }\cup {\mathcal {A}}_{\beta }{|\!\!\!\sim }{\mathcal {A}}_{\gamma }$.

And :

 If ${\mathcal {A}}_{\alpha }{|\!\!\!\sim }{\mathcal {A}}_{\beta }$ and ${\mathcal {A}}_{\alpha }{|\!\!\!\sim }{\mathcal {A}}_{\gamma }$ then ${\mathcal {A}}_{\alpha }{|\!\!\!\sim }{\mathcal {A}}_{\beta }\cup {\mathcal {A}}_{\gamma }$.

 

R means that the additional assertions have to be a consequence of the inference relation. LLE expresses the fact that two equivalent sets of assertions have the same consequences. RW says that consequences of the plausible assertions are plausible assertions too. Cut expresses the fact that if a plausible consequence is as secure as the assumptions it is based on, then it may be added into the assumptions. CM expresses that learning new assertions that could be plausibly inferred should not invalidate previous consequences. And expresses that the conjunction of two plausible consequences is a plausible consequence. The first five properties correspond to the system C [14] while the And property is derived from the previous ones. Clearly the $\mathbf{And}$ property is closely related to the QCI property given in Sect. 4.2. Indeed when ${\mathcal {A}}_{\alpha }$=$\emptyset$ (empty set, no additional information) and if $q_1$ and $q_2$ used in CQI are sets of assertions then And is equivalent to CQI. We now give the properties of the inference relations.

Proposition 2

(Properties of conditional inference). The behaviour of inference relations $|\!\!\!\sim _{\circ _i, s}$, with $\circ _i\in \{\mathsf {R}$, $\mathsf {MR}$,$\mathsf {CMR}$,$\mathsf {MCMR}$, $\mathsf {CR}$, $\mathsf {MCR}$, $\mathsf {RC}$, $\mathsf {MRC}\}$ and $s \in \{\cap , \forall$, maj, $\exists \}$, with respect to Properties R, LLE, RW, Cut, CM, And, is given in Table 3.

Table 3. Properties of conditional inferences.

Proof: [Sketch of proof]. Properties R, LLE and RW follow from the definition of ${{\mathcal {M}}}_i^{\alpha }$. For $s\in \{\forall , \cap , \exists \}$ and for $\circ _i\in \{ \mathsf {R}, \mathsf {MR} \}$ the satisfaction of Properties Cut and CM stems from the fact that $\forall R'\in {{\mathcal {M}}}_i^{\alpha \cup \beta }$ we have $R'$=$R\cup {\mathcal {A}}_{\beta }$ with $R\in {{\mathcal {M}}}_i^{\alpha }$. Moreover, for $\circ _i\in \{\mathsf {CMR},\mathsf {CR}, \mathsf {RC}, \mathsf {MRC}\}$ the satisfaction of Properties Cut and CM holds due the fact that $\forall R'\in {{\mathcal {M}}}_i^{\alpha \cup \beta }$ we have $R'$=$R\cup \textit{Cl}({\mathcal {A}}_{\beta })$ with $R\in {{\mathcal {M}}}_i^{\alpha }$. The following counter-examples show the non-satisfaction cases.    $\square$

Example 7

( $|\!\!\!\sim _{\circ _i, s}$ with $\circ _i\in \{\mathsf {MCMR}, \mathsf {MCR}\}$ and $s\in \{\forall ,\exists ,\cap \}$ does not satisfy Cut ). For $\mathsf {MCMR}$: Let ${\mathcal {T}}$=$\{A\sqsubseteq \lnot B$, $A\sqsubseteq \lnot G$, $F\sqsubseteq \lnot B$, $B\sqsubseteq C$, $C\sqsubseteq D$, $A \sqsubseteq E\}$, and ${\mathcal {A}}$=$\{A(a)$,B(a), F(a), $G(a)\}$, ${\mathcal {A}}_{\alpha }$=$\emptyset$, ${\mathcal {A}}_{\beta }$=$\{C(a),D(a)\}$, ${\mathcal {A}}_{\gamma }$=$\{A(a)\}$. We have ${{\mathcal {M}}}_4^{\alpha }$=$\{\{B(a)$,G(a), C(a),$D(a)\}\}$ and ${{\mathcal {M}}}_4^{\alpha \cup \beta }$=$\{\{A(a),F(a),C(a),D(a),E(a)\}\}$. Thus $\langle {\mathcal {T}},{{\mathcal {M}}}_4^{\alpha }\rangle$ $\models _{\forall }{\mathcal {A}}_{\beta }$ and $\langle {\mathcal {T}},{{\mathcal {M}}}_4^{\alpha \cup \beta }\rangle \models _{\forall }$ ${\mathcal {A}}_{\gamma }$ but $\langle {\mathcal {T}},{{\mathcal {M}}}_4^{\alpha }\rangle$ $\not \models _{\forall }$ ${\mathcal {A}}_{\gamma }$. Cut is not satisfied even for $s \in \{\exists ,\cap \}$.

$\mathsf {MCR}$: Let ${\mathcal {T}}$ =$\{A \sqsubseteq \lnot B$, $F \sqsubseteq \lnot B$, $B \sqsubseteq C$, $C \sqsubseteq D\}$, ${\mathcal {A}}$ = $\{A(a),B(a),F(a) \}$, ${\mathcal {A}}_{\alpha }$=$\emptyset$, ${\mathcal {A}}_{\beta }$=$\{C(a),D(a)\}$, ${\mathcal {A}}_{\gamma }$ = $\{A(a) \}$. We have ${{\mathcal {M}}}_6^{\alpha }$=$\{\{B(a),C(a),D(a)\}\}$, ${{\mathcal {M}}}_6^{\alpha \cup \beta }$=$\{\{$ $A(a),F(a),C(a),D(a) \}\}$. Thus $\langle {\mathcal {T}},{{\mathcal {M}}}_6^{\alpha }\rangle \models _{\forall }{\mathcal {A}}_{\beta }$ and $\langle {\mathcal {T}},{{\mathcal {M}}}_6^{\alpha \cup \beta }\rangle \models _{\forall }{\mathcal {A}}_{\gamma }$ but $\langle {\mathcal {T}},{{\mathcal {M}}}_6^{\alpha }\rangle$ $\not \models _{\forall }$ ${\mathcal {A}}_{\gamma }$. Cut is not satisfied either for $s\in \{\exists , \cap \}$.

Example 8

( $|\!\!\!\sim _{\circ _i, s}$ with $\circ _i \in \{\mathsf {MCMR}, \mathsf {MCR}\}$ and $s\in \{\forall ,\cap \}$ does not satisfy CM ). Let ${\mathcal {T}}$=$\{A\sqsubseteq \lnot B$, $B\sqsubseteq C\}$, and ${\mathcal {A}}$=$\{A(a),B(a)\}$, ${\mathcal {A}}_{\alpha }$=$\emptyset$, ${\mathcal {A}}_{\beta }$=$\{ C(a)\}$, ${\mathcal {A}}_{\gamma }$=$\{B(a) \}$. We have ${{\mathcal {M}}}_4^{\alpha }$=${{\mathcal {M}}}_6^{\alpha }$=$\{\{B(a),C(a)\}\}$, ${{\mathcal {M}}}_4^{\alpha \cup \beta }$=${{\mathcal {M}}}_6^{\alpha \cup \beta }$=$\{\{A(a),C(a)\}$,$\{B(a)$,$C(a)\}\}$. Thus $\langle {\mathcal {T}},{{\mathcal {M}}}_4^{\alpha }\rangle \models _{\forall } {\mathcal {A}}_{\beta }$ and $\langle {\mathcal {T}},{{\mathcal {M}}}_4^{\alpha }\rangle \models _{\forall }{\mathcal {A}}_{\gamma }$ but $\langle {\mathcal {T}}, {{\mathcal {M}}}_4^{\alpha \cup \beta }\rangle \not \models _{\forall }{\mathcal {A}}_{\gamma }$. Moreover, $\langle {\mathcal {T}},{{\mathcal {M}}}_6^{\alpha }\rangle \models _{\forall }$ ${\mathcal {A}}_{\beta }$ and $\langle {\mathcal {T}},{{\mathcal {M}}}_6^{\alpha }\rangle \models _{\forall } {\mathcal {A}}_{\gamma }$ but $\langle {\mathcal {T}},{{\mathcal {M}}}_6^{\alpha \cup \beta }\rangle \not \models _{\forall } {\mathcal {A}}_{\gamma }$. CM is not satisfied even for s=$\cap$.

Example 9

( $|\!\!\!\sim _{\circ _i, maj}$ with any $\circ _i$ does not satisfy Cut ). For $i = 1$ ($\mathsf {R}$), let ${\mathcal {T}}$=$\{A\sqsubseteq \lnot B$, $A\sqsubseteq \lnot C$, $A\sqsubseteq \lnot D$, $B\sqsubseteq \lnot D$, $C\sqsubseteq \lnot D$, $A\sqsubseteq E$, $B \sqsubseteq E$, $C\sqsubseteq E$, $D \sqsubseteq \lnot E$, $A \sqsubseteq G$, $B \sqsubseteq G\}$, and ${\mathcal {A}}$=$\{A(a)$,B(a),C(a),$D(a)\}$, ${\mathcal {A}}_{\alpha }$=$\{ F(a) \}$, ${\mathcal {A}}_{\beta }$=$\{E(a)\}$, ${\mathcal {A}}_{\gamma }$= $\{G(a) \}$. We have ${{\mathcal {M}}}_1^{\alpha }=\{\{A(a)$,$F(a)\}$,$\{B(a)$,$F(a)\}$,$\{C(a)$,$F(a)\}$,$\{D(a)$,$F(a)\} \}$, thus $\langle {\mathcal {T}},{{\mathcal {M}}}_1^{\alpha } \rangle$ $\models _{maj}$ ${\mathcal {A}}_{\beta }$. Moreover, ${{\mathcal {M}}}_1^{\alpha \cup \beta }$=$\{\{ A(a)$,F(a),$E(a)\}$,$\{ B(a),F(a),E(a)\}$, $\{C(a),F(a),E(a)\}\}$ and $\langle {\mathcal {T}}, {\mathcal {M}}_1^{\alpha \cup \beta }\rangle \models _{maj}{\mathcal {A}}_{\gamma }$, however $\langle {\mathcal {T}},{{\mathcal {M}}}_1^{\alpha } \rangle \not \models _{maj}{\mathcal {A}}_{\gamma }$. Cut is not satisfied for any other $\circ _i$.

Example 10

( $|\!\!\!\sim _{\circ _i, \exists }$ with any $\circ _i$ does not satisfy CM ). For i=1 ($\mathsf {R}$): Let ${\mathcal {T}}=\{A \sqsubseteq \lnot C, A \sqsubseteq B, C \sqsubseteq B, A \sqsubseteq D, C \sqsubseteq E, D \sqsubseteq \lnot C, E \sqsubseteq \lnot A \}$, and ${\mathcal {A}}= \{A(a),C(a)\}$, ${\mathcal {A}}_{\alpha }=\{ B(a) \}$, ${\mathcal {A}}_{\beta }=\{ D(a)\}$, ${\mathcal {A}}_{\gamma }=\{E(a) \}$. We have ${{\mathcal {M}}}_1^{\alpha }=\{\{ A(a), B(a)\}, \{ C(a)$, $B(a)\}\}$, thus $\langle {\mathcal {T}},{{\mathcal {M}}}_1^{\alpha }\rangle \models _{\exists }$ ${\mathcal {A}}_{\beta }$ and $\langle {\mathcal {T}},{{\mathcal {M}}}_1^{\alpha } \rangle \models _{\exists }{\mathcal {A}}_{\gamma }$. Moreover ${{\mathcal {M}}}_i^{\alpha \cup \beta }$=$\{\{A(a),B(a)$, $D(a)\}\}$ and $\langle {\mathcal {T}},{{\mathcal {M}}}_1^{\alpha \cup \beta }\rangle \not \models _{\exists }{\mathcal {A}}_{\gamma }$. CM is not satisfied for any other $\circ _i$.

Example 11

( $|\!\!\!\sim _{\circ _i, maj}$ with any $\circ _i$ does not satisfy CM ). For i=1 ($\mathsf {R}$): Let ${\mathcal {T}}$=$\{A\sqsubseteq \lnot B$, $A\sqsubseteq \lnot C$, $B\sqsubseteq \lnot C$, $A\sqsubseteq D$, $B \sqsubseteq D, C \sqsubseteq D, A \sqsubseteq E, B \sqsubseteq E, C \sqsubseteq F, B \sqsubseteq F, A \sqsubseteq \lnot F \}$, and ${\mathcal {A}}= \{A(a), B(a), C(a) \}$, ${\mathcal {A}}_{\alpha } = \{ D(a) \}$, ${\mathcal {A}}_{\beta } = \{ E(a)\}$, ${\mathcal {A}}_{\gamma } = \{F(a) \}$. We have ${{\mathcal {M}}}_1^{\alpha } =\{\{ A(a), D(a)\}, \{ B(a), D(a)\}, R_3 =\{ C(a), D(a)\}\}$, thus $\langle {\mathcal {T}},{{\mathcal {M}}}_1^{\alpha } \rangle \models _{maj}{\mathcal {A}}_{\beta }$. Moreover $\langle {\mathcal {T}},{{\mathcal {M}}}_1^{\alpha } \rangle \models _{maj} {\mathcal {A}}_{\gamma }$. We have ${{\mathcal {M}}}_1^{\alpha \cup \beta }$=$\{\{ A(a),D(a)$, $E(a)\},\{ B(a), D(a)$, $E(a)\} \}$, thus $\langle {\mathcal {T}},{{\mathcal {M}}}_1^{\alpha \cup \beta }\rangle \not \models _{maj} {\mathcal {A}}_{\gamma }$. CM is not satisfied for any other $\circ _i$.

Example 12

( $|\!\!\!\sim _{\circ _i, s}$ with any $\circ _i$ and $s\in \{\exists , maj \}$ does not satisfy And ). For $i = 1$ and $s= \exists$ ($\mathsf {R}$): Let ${\mathcal {T}}$ and ${\mathcal {A}}$ from Example 10. $\langle {\mathcal {T}},{{\mathcal {M}}}_1^{\alpha } \rangle \models _{\exists } {\mathcal {A}}_{\beta }$ and $\langle {\mathcal {T}},{{\mathcal {M}}}_1^{\alpha } \rangle \models _{\exists } {\mathcal {A}}_{\gamma }$ but $\langle {\mathcal {T}},{{\mathcal {M}}}_1^{\alpha } \rangle \not \models _{\exists } {\mathcal {A}}_{\beta } \cup {\mathcal {A}}_{\gamma }$. And is not satisfied for any other $\circ _i$. For $i = 1$ and $s= maj$ ($\mathsf {R}$): Let ${\mathcal {T}}$ and ${\mathcal {A}}$ from Example 11. $\langle {\mathcal {T}},{{\mathcal {M}}}_i^{\alpha } \rangle \models _{maj} {\mathcal {A}}_{\beta }$ and $\langle {\mathcal {T}},{{\mathcal {M}}}_i^{\alpha } \rangle \models _{maj} {\mathcal {A}}_{\gamma }$. but $\langle {\mathcal {T}},{{\mathcal {M}}}_i^{\alpha } \rangle \not \models _{maj} {\mathcal {A}}_{\beta } \cup {\mathcal {A}}_{\gamma }$. And is not satisfied for any other $\circ _i$.

From Table 3, one can see that, for the composite modifiers $\circ _i\in \{\mathsf {R}$,$\mathsf {MR}$,$\mathsf {CMR}$,$\mathsf {CR}$,$\mathsf {RC}$, $\mathsf {MRC}\}$, the semantics based on universal and safe consequence satisfy all the properties of the system C. In LLE ${\mathcal {A}}_{\gamma }$ can be replaced by a Conjunctive Query (CQ), in RW ${\mathcal {A}}_{\alpha }$ (resp. ${\mathcal {A}}_{\beta }$) can be replaced by CQ and And ${\mathcal {A}}_{\gamma }$ (resp. ${\mathcal {A}}_{\beta }$) can be replaced by a CQ.

5 Complexity of Inconsistency-Tolerant Query Answering

In this section we study the data complexity⁶ of CQ entailment under the various semantics for classes of TBoxes ${\mathcal {T}}$=${\mathcal {T}}_p \cup {\mathcal {T}}_n$ that fulfill the following property: ${\mathcal {T}}_p$ is a Finite Unification Set (FUS) of existential rules [3], while ${\mathcal {T}}_n$ remains any set of negative constraints. A set of rules ${\mathcal {T}}_p$ fulfills the FUS property when, for any CQ q, there exists a finite set of CQs $\mathcal Q$ (called the set of rewritings of q) such that for any ABox ${\mathcal {A}}$, $\langle {\mathcal {T}}_p, {\mathcal {A}}\rangle \models q$ iff $\exists q_i\in \mathcal Q\,\text{ such } \text{ that }\,{\mathcal {A}}\models q_i$; in other words, q can be rewritten into a union of CQs $\mathcal Q$, which allows to forget the rules. Since query rewriting does not depend on any ABox, CQ entailment has the same data complexity as the classical database problem, which is in the low complexity class AC$_0$. Note also that when ${\mathcal {T}}_p$ satisfies the FUS property, the consistency of a standard KB can be checked by rewriting the query $\bot$ with ${\mathcal {T}}$ (or equivalently, rewriting each body of a negative constraint with ${\mathcal {T}}_p$) and checking if one of the obtained rewritings is entailed by ${\mathcal {A}}$. Such TBoxes encompass DL-Lite$_{\mathcal R}$ TBoxes as well as more expressive classes of existential rules, e.g., linear and sticky [8, 9]. All the following membership results apply to FUS rules, while all hardness results hold as soon as DL-Lite$_{\mathcal R}$ TBoxes are considered.

We first briefly recall the definition of the complexity classes that we use. The class $\varDelta _2^P = P^{NP}$ refers to problems solvable in polynomial time by a deterministic Turing Machine provided with an NP oracle, and its subclass $\varTheta ^P_2$=$\varDelta _2^P[O(log~n)]$ is allowed to make only logarithmically many calls to an NP oracle. A Probabilistic Turing Machine (PTM) is a non-deterministic TM allowed to “toss coins” to make decisions: we will use the Probabilistic Polynomial-time (PP) class that contains the problems solvable in polynomial time with probability strictly greater than $\frac{1}{2}$ by a PTM [13].⁷ We also recall that $\varDelta _2^P$, $\varTheta _2^P$ and PP are all closed under complement. CQ entailment with DL-Lite$_{\mathcal R}$ TBoxes is coNP-complete under $\langle \mathsf {R},\forall \rangle$ and $\langle \mathsf {RC},\forall \rangle$ semantics, and in $AC_0$ under $\langle \mathsf {R},\cap \rangle$ and $\langle \mathsf {RC},\cap \rangle$ semantics (semantics respectively known as AR, CAR, IAR and ICAR [16]). It is coNP-complete under $\langle \mathsf {CR},\cap \rangle$ semantics (known as ICR [6]), and $\varTheta _2^P$-complete under $\langle \mathsf {MR},\forall \rangle$ and $\langle \mathsf {MR},\cap \rangle$ semantics [7]. We first show that these complexity results also hold for FUS existential rules.

Proposition 3

If CQ-entailment under $\langle \mathsf {R}/\mathsf {RC}/\mathsf {MR},\forall \rangle$ and $\langle \mathsf {R}/\mathsf {RC}/\mathsf {CR},\cap \rangle$ belongs to some complexity class $\mathcal C$ for DL-Lite$_{\mathcal R}$ TBoxes, then CQ-entailment remains in the same complexity class $\mathcal C$ for the more general FUS existential rules.

Proof: [Sketch] Let us first consider $\langle \mathsf {R}/\mathsf {RC},\forall \rangle$. One can obviously guess a repair ${\mathcal {R}}$ and check in polynomial time (actually in $AC_0$) if $\langle {\mathcal {T}},{\mathcal {R}}\rangle \models \bot$ (by rewriting all negative constraints and looking for a homomorphism from one of those rewritings into ${\mathcal {R}}$), and if $\langle {\mathcal {T}}$,${\mathcal {R}}\rangle \not \models q$ via rewriting methods as well. Concerning $\langle \mathsf {MR},\forall \rangle$, the membership holds for any FUS rules for similar reasons, and by observing that one can compute the maximum size of a repair through logarithmically many calls to an NP oracle. For $\langle \mathsf {R}/\mathsf {MRC},\cap \rangle$ the technique from [16] still holds; whereas for $\langle \mathsf {CR}$,$\cap \rangle$, we guess a set of repairs $\mathcal R$=$\{\mathcal R_1,...,\mathcal R_k \}$, with k polynomially bounded by the number of homomorphisms from rewritings of the query q to $Cl({\mathcal {A}})$, such that: for any homomorphism h from a rewriting $q'$ of q to $Cl({\mathcal {A}})$ there is $\mathcal R_i\in \mathcal R$ with $h(q')\not \subseteq \mathcal R_i$. There is a polynomial number of rewritings (for data complexity), hence a polynomial number of homomorphisms from these rewritings to the $Cl({\mathcal {A}})$.   $\square$

The previous observations explain the complexity results written in black font without star in Table 4. We now provide some new complexity results for other universal-based and existential-based semantics.

Table 4. Complexity: tight complexity results are in black font (completely new results marked by a star, the other being generalizations of known results to FUS). Membership results are in gray font.

Proposition 4

CQ entailment under $\langle \mathsf {R}, \exists \rangle$ (hence $\langle \mathsf {CR}, \exists \rangle$) is in $AC_0$.

Proof: [Sketch] We first compute a set ${\mathcal Q}$ that contains all the rewritings of q with the rules from ${\mathcal {T}}_p$, as well as all their specialisations according to all possible partitions on terms. We also rewrite $\bot$ (i.e., all negative constraints) into the set ${\mathcal N}$. We remove from ${\mathcal Q}$ all rewritings $q'$ such that an element of ${\mathcal N}$ maps to $q'$ by homomorphism. Finally, we add to each remaining rewriting $q'' \in {\mathcal Q}$ all inequalities between its terms, which yields ${\mathcal Q}'$. ${\mathcal Q}'$ can be seen as a union of CQs with inequality predicates, hence a first-order query. We have that ${\mathcal {K}}\models _{\langle \mathsf {R},\exists \rangle } q$ iff ${\mathcal {A}}\models {\mathcal Q}'$. Therefore q is first-order rewritable w.r.t.  ${\mathcal {T}}$, under $\langle \mathsf {R}, \exists \rangle$ semantics.    $\square$

Proposition 5

For $\circ _i\in \{\mathsf {CMR}$, $\mathsf {MCMR}$, $\mathsf {MCR}$, $\mathsf {MRC}\}$, CQ entailment under $\langle \circ _i,\forall \rangle$ and $\langle \circ _i, \exists \rangle$ semantics is in $\varTheta ^P_2$.

Proof: [Sketch] Notice that we can compute the maximum size of a repair and the maximum size of the ground positive closure of a maximum-sized repair through logarithmically many calls to an NP oracle. Then with one more call to this oracle, we can check whether there is a repair ${\mathcal {R}}$ that satisfies the cardinality constraints and such that $\langle {\mathcal {T}}, {\mathcal {R}}\rangle \not \models q$ (resp. $\langle {\mathcal {T}}, {\mathcal {R}}\rangle \models q$). Therefore, $\langle \circ _i,\forall \rangle$ (resp. $\langle \circ _i,\exists \rangle$) is in $\varTheta ^P_2$.    $\square$

Proposition 6

For $\circ _i\in \{\mathsf {CMR}$, $\mathsf {MCMR}$, $\mathsf {MCR}$, $\mathsf {MRC}\}$, CQ entailment under $\langle \circ _i,\forall \rangle$ semantics is $\varTheta ^P_2$-hard.

Proof: We adapt the reduction from the problem ParitySAT built in [7] (which is a reduction to $\langle \mathsf {MR}, \forall \rangle$ with an instance query). We “tweak” the query and the TBox so that the positive part of the TBox is empty; this ensures that $(\circ _i,\forall ) = (\circ _j,\forall )$ for any $\circ _i,\circ _j \in \{{\mathsf {MR}},$ ${\mathsf {CMR}},$ ${\mathsf {MCMR}},$ ${\mathsf {MCR}},$ ${\mathsf {MRC}}\}$.    $\square$

For majority-based semantics, we rely on probabilistic algorithms and provide two completeness results, as stated by the next proposition.

Proposition 7

Conjunctive Query entailment under $\langle \mathsf {R}, Maj \rangle$ and $\langle \mathsf {CR}, Maj \rangle$ semantics is $PP$-$complete$.

Proof: [Sketch] Membership: We use the following algorithm: first choose a subset S of atoms from ${\mathcal {A}}$ randomly, then if S is not a repair of ${\mathcal {K}}$, output no with probability $\frac{1}{2}$. Otherwise (S is a repair), if $({\mathcal {T}}, S) \models q$, output no with probability $\frac{1}{2^{n+1}}$; else ($({\mathcal {T}}, S) \not \models q$), output no with probability 1. This procedure obviously runs in polynomial time and the idea is that each repair has the same probability of being selected in the first step ($\frac{1}{2^n}$), and by answering no a few times when $({\mathcal {T}}, S) \models q$ we ensure that the algorithm will give the right answer with probability strictly greater than $\frac{1}{2}$.

Hardness: We consider the following problem coMajSAT: given a Boolean SAT formula, is the number of unsatisfying affectations strictly greater than half of all possible affectations? We recall that PP is closed under complement. We notice that the reduction from SAT to $\langle S$,$\forall \rangle$ built in [15], ensures that each repair corresponds exactly to an affectation of the SAT formula, and the obtained query q is evaluated to true iff there is at least one invalid affectation. Hence, the majority of affectations are invalid iff q is entailed by the majority of the repairs. Hence, this transformation yields a reduction from coMajSAT to $\langle \mathsf {R},Maj \rangle$. Since $\langle \mathsf {R}, Maj \rangle {=}\langle \mathsf {CR},Maj \rangle$, the result also holds for $\langle \mathsf {CR}, Maj \rangle$.    $\square$

To further clarify the complexity picture, we give some complexity class membership results for the remaining semantics (Table 4, in gray font). CQ entailment under $\langle \mathsf {RC}, \exists \rangle$ semantics is clearly in P since we can first compute the ground positive closure of the ABox in polynomial time and $\langle \mathsf {R}, \exists \rangle$ is in $AC_0$. For $\langle \mathsf {MRC}, Maj\rangle$ semantics, the membership proof from Proposition 7 holds as soon as we have observed that we could first compute the ground positive closure of the ABox. For the remaining majority-based semantics, we use an argument similar to the one in Proposition 5 to show membership to $PP^{NP[O(log~n)]}$: we only need logarithmically many calls to an NP oracle to get the maximum cardinality of a repair. Concerning the remaining intersection-based semantics $\langle \circ _i,\cap \rangle$, we observe that by calling independently the corresponding universal problem $(\circ _i,\forall )$ on each atom from the ABox, we can build the intersection of all repairs, hence the $\varTheta _2^P$ membership. Finally, an interesting question is to what extent preprocessing the data, independently from any query, can reduce the complexity of query entailment. It seems reasonable to require that the result of this preprocessing step takes space at most linear in the size of the data. For instance, let us consider $\langle \mathsf {MR},\forall \rangle$: if we precompute the maximum cardinality of a repair (stored in $log_2(|{\mathcal {A}}|)$ space), the complexity of CQ entailment drops from $\varTheta ^P_2$-c to coNP-c, i.e., the complexity of $\langle \mathsf {R},\forall \rangle$.

6 Concluding Remarks

The framework for inconsistency-tolerant query answering recently proposed in [2] covers some well-known semantics and introduces new ones. These semantics were compared with respect to productivity. We broaden the analysis by considering two other points of view. First, we initiate a study of rationality properties of inconsistency-tolerant semantics. Second, we complement known complexity results, on the one hand by extending them to the more general case of FUS existential rules, and on the other hand by providing tight complexity results on some newly considered semantics (computation of repairs or closed repairs with majority-based or brave inference, as well several cardinality-based modifiers with universal inference).

The most efficiently computable semantics are $\langle \mathsf {R},\cap \rangle$ and $\langle \mathsf {R},\exists \rangle$ (equal to $\langle \mathsf {CR},\exists \rangle$). The $\langle \mathsf {R},\cap \rangle$ semantics is the least productive semantics in the framework. However, if one considers the closure of the repairs to increase the productivity of $\langle \mathsf {R},\cap \rangle$, i.e., $\langle \mathsf {CR},\cap \rangle$, one obtains a semantics that computationally costs as the “natural” semantics $\langle \mathsf {R},\forall \rangle$. At the opposite, $\langle \mathsf {R},\exists \rangle$ may be considered as too adventurous and does not behave well from a rationality point of view since it produces conclusions that may be inconsistent with the ontology. More generally, universal and safe semantics satisfy the rationality properties for most modifiers, which is not the case of majority-based and existential semantics. In addition, for all semantics, $\mathsf {RC}$ and $\mathsf {MRC}$, which compute the closure of an inconsistent ABox, may lead to consider as plausible a conclusion with a contestable support, and since they do not seem to bring any advantage compared to other semantics, they should be discarded. Despite majority-based semantics do not fulfil some desirable logical properties, they remain interesting for several reasons: they are only slightly more complex to compute than universal semantics (w.r.t. the same modifier) while being more productive, without being as adventurous as existential semantics. Hence, they may be considered as a good tradeoff between both semantics when the universal semantics appear to be insufficiently productive. We also recall that majority-based semantics behave better from a logical viewpoint when they are restricted to DL-Lite$_{\mathcal R}$ (and more generally, when the ontological language ensures that the size of the conflicts is at most two). Regarding the use of cardinality, cardinality-based modifiers can be used to counteract troublesome assertions that conflict with many others, however they behave strangely when the cardinality criterion is applied to closed repairs.

In summary, no semantics appears to outperform all the others in all of the considered criteria. Selecting a semantics means selecting a suitable tradeoff between productivity (or, inversely, cautiousness), satisfaction of rationality properties and computational complexity. We believe that this choice depends on the applicative context.

In a future work, new semantics could be considered within the unified framework, like no-objection semantics [4]. Besides, the study of rationality properties could be extended to other properties, and the exact complexity of several semantics remains an open issue.