# Inconsistency-Tolerant Semantics Based on (Preferred) Repairs

Camille Bourgaux

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

## To cite this version:

Camille Bourgaux. Inconsistency-Tolerant Semantics Based on (Preferred) Repairs. Reasoning Web Summer School (RW 2025), Sep 2025, Istanbul, Turkey. 10.4230/OASIcs.RW.2024/2025.5. hal-05291421v2

HAL Id: hal-05291421

https://inria.hal.science/hal-05291421v2

Submitted on 7 Nov 2025

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_2.png" /></figure>
# Inconsistency-Tolerant Semantics Based on (Preferred) Repairs

Camille Bourgaux

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

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

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

DI ENS, ENS, CNRS, PSL University & Inria, Paris, France

## Abstract

Real-world datasets are plagued by data quality issues which may render the data inconsistent w.r.t. a set of constraints, be they given by database integrity constraints or ontologies. A prominent way to handle such inconsistent data is to use inconsistency-tolerant semantics to obtain meaningful answers to queries. Most of these semantics are based on some notion of repairs, which represent ways of restoring the data consistency. The most basic kind of repairs is that of subset repairs, which are maximal consistent subsets of the dataset. However, in many scenarios, one can define preferred repairs based on some preference information. These lecture notes present inconsistency-tolerant semantics, focusing on the repair-based ones, then review different kinds of preferred repairs that have been considered in the literature. We present in particular the relationships between different kinds of preferred repairs and other notions related to inconsistency handling, the computational complexity of reasoning with (preferred) repairs, and some implementations.

**2012 ACM Subject Classification** Theory of computation → Automated reasoning; Computing methodologies → Description logics; Computing methodologies → Nonmonotonic, default reasoning and belief revision; Computing methodologies → Reasoning about belief and knowledge; Information systems → Data cleaning

**Keywords and phrases** Knowledge bases, databases, inconsistency handling, repairs, preferences

**Digital Object Identifier** 10.4230/OASICS.RW.2024/2025.5

**Category** Invited paper

**Funding** This lecture was supported by the ANR AI Chair INTENDED (ANR-19-CHIA-0014).

**Acknowledgements** I am grateful to the RW 2025 organizers for the invitation to give this lecture. Several sections of these lecture notes are based on some work on priority-based repairs that I co-authored with Meghyn Bienvenu.

## 1 Introduction

Many relational datasets are associated with either some integrity constraints, which aim at preventing errors by expressing properties expected from the stored data [1], or with an ontology, which expresses knowledge on the domain of interest and allows a user to formulate queries in familiar terms and obtain more complete answers through logical reasoning [124, 136, 40]. Integrity constraints and ontologies both consist of logical formulas that can be written as first-order logic sentences. In particular, ontologies are typically expressed in some description logics [14] or extensions of Datalog [20, 56]. The main difference between the database setting, which considers a dataset equipped with a set of integrity constraints, and the knowledge base setting, where a dataset is enriched with an ontology, is that the former uses the logical formulas to check whether the data complies with some rules it is expected to follow while the latter uses them to infer implicit information from the explicitly stored data. However, the question of how to handle the case where the dataset is inconsistent w.r.t. the background knowledge is crucial in both settings. Indeed, it is widely acknowledged that real-world datasets are plagued by data quality issues, and it is not always possible to

<figure><img src="image_6.png" /></figure>
restore consistency since it may be difficult to identify the erroneous parts of the data, and
removing all potentially erroneous facts may lead to unacceptable loss of information.

A prominent way to tackle this issue is to use some inconsistency-tolerant semantics.
Such a semantics was first proposed in the database area under the name of consistent query
answering, with the goal of obtaining query answers that would be consistent w.r.t. the
database constraints even though the database itself was not [8, 25]. In a nutshell, a query
answer is consistent if it can be obtained from all repairs of the database, where a repair is a
dataset consistent w.r.t. the constraints which minimally differs from the original dataset.
As the inconsistency issue is even more problematic for knowledge bases, since everything is
entailed by an inconsistent knowledge base under the classical semantics, consistent query
answering was adapted to knowledge bases under the name of AR semantics (AR standing for
ABox Repair, as a dataset is called an ABox in description logic parlance) [98, 99]. While this
semantics remains the most studied and well-established, many other inconsistency-tolerant
semantics have been proposed, e.g., to address the intractability of consistent query answering
via approximations, or to get a finer classification of the reliability of query answers. A
great deal of research effort has been put into exploring the problem of querying inconsistent
databases and knowledge bases under these semantics, in particular on the theoretical side,
with extensive studies of the computational complexity of this problem in various settings,
but also with more practically-oriented research aiming at developing and implementing
efficient algorithms for this problem (see surveys [25, 26, 29, 28]).

The notion of repair is at the basis of most of inconsistency-tolerant semantics. However, in many scenarios, one can define preferred repairs based on some preference information, and use these preferred repairs instead of standard ones when querying inconsistent databases or knowledge bases to obtain more accurate answers. For example, optimal repairs based on weights associated to the dataset facts, on a priority relation between facts, or on preference rules have been considered [102, 129, 73, 33, 30, 100, 122, 50, 107, 32].

The goal of these lecture notes is to provide an overview of inconsistency handling based
on database or knowledge base (preferred) repairs. After some preliminaries, we introduce
the basic notion of a repair in Section 3 and present some characterizations of repairs, based
on the concept of conflict hypergraph and argumentation frameworks. In Section 4, we briefly
present existing inconsistency-tolerant semantics, focusing on the repair-based ones. We then
review the different kinds of preferred repairs that have been considered in the literature in
Section 5, focusing on their properties and relationships, and presenting known links to other
frameworks for inconsistency handling. We also expand the focus to consider related work on
other ways of defining optimal consistent datasets that are not repairs per se. In Section 6,
we present some results on the computational complexity of deciding whether a dataset is a
repair and of reasoning under repair-based semantics, then on the impact of using preferred
repairs instead of standard ones, focusing in particular on data complexity. In Section 7, we
give a concise overview of systems that have been implemented for querying inconsistent
databases and knowledge bases under (preferred) repair-based semantics and illustrate some
prominent practical approaches. We conclude with a discussion of recent related work and
research directions in Section 8.
Contents

<table><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>1 Introduction</td><td>1</td></tr><tr><td>2 Preliminaries</td><td>3</td></tr><tr><td>2.1 Databases, knowledge bases, queries</td><td>4</td></tr><tr><td>2.2 Computational complexity</td><td>10</td></tr><tr><td>3 Dataset repairs of inconsistent databases or knowledge bases</td><td>12</td></tr><tr><td>3.1 Definition</td><td>12</td></tr><tr><td>3.2 Repair characterization via the conflict hypergraph</td><td>14</td></tr><tr><td>3.3 Connections with abstract argumentation</td><td>15</td></tr><tr><td>4 Inconsistency-tolerant semantics</td><td>17</td></tr><tr><td>4.1 Repair-based semantics</td><td>17</td></tr><tr><td>4.2 Related work: Semantics that are not based on dataset repairs</td><td>20</td></tr><tr><td>5 Preferred repairs</td><td>22</td></tr><tr><td>5.1 Preferred repairs based on a preorder over datasets (≤, ≤<sub>w</sub>, ⊑<sub>P</sub>, ≤<sub>P</sub>)</td><td>23</td></tr><tr><td>5.2 Optimal repairs based on a priority relation</td><td>26</td></tr><tr><td>5.2.1 Pareto-, globally- and completion-optimal repairs</td><td>27</td></tr><tr><td>5.2.2 Links with abstract argumentation and active integrity constraints</td><td>30</td></tr><tr><td>5.3 Preferred repairs based on preference rules</td><td>33</td></tr><tr><td>5.4 Related work: “Optimal repairs” that are not dataset repairs</td><td>36</td></tr><tr><td>5.4.1 Repairs based on non strictly ⊑-monotone weight-based preorders</td><td>36</td></tr><tr><td>5.4.2 Selecting a single T-consistent dataset from a prioritized dataset</td><td>36</td></tr><tr><td>5.4.3 Soft repairs for weighted constraints</td><td>38</td></tr><tr><td>6 Computational complexity of reasoning with (preferred) repairs</td><td>39</td></tr><tr><td>6.1 The case of standard repairs</td><td>39</td></tr><tr><td>6.1.1 Repair checking</td><td>39</td></tr><tr><td>6.1.2 BCQ entailment under CQA, intersection, and brave semantics</td><td>42</td></tr><tr><td>6.2 Reasoning with preferred repairs</td><td>46</td></tr><tr><td>6.2.1 Repair checking</td><td>46</td></tr><tr><td>6.2.2 BCQ entailment under CQA, intersection, and brave semantics</td><td>49</td></tr><tr><td>6.2.3 Comments and additional results</td><td>53</td></tr><tr><td>7 Implementations of (preferred) repair-based semantics</td><td>54</td></tr><tr><td>7.1 Examples of encodings for CQA</td><td>56</td></tr><tr><td>7.2 Tractable semantics and approximations</td><td>58</td></tr><tr><td>8 Summary and outlook</td><td>58</td></tr></tbody></table>

2 Preliminaries

In this section, we introduce the database and knowledge base settings we will consider throughout this chapter and recall some relevant results on their computational complexity. We assume a basic knowledge of first-order logic (FO) syntax and semantics.
## 2.1 Databases, knowledge bases, queries

Let P, C, and V be three disjoint countable sets of predicates, constants and variables respectively. Each predicate is associated with an arity, i.e., a non-negative integer. A term is a constant or a variable and a (relational) atom has form $P(t_1, ..., t_n)$ where P is a predicate of arity n and $t_1, ..., t_n$ are terms. A fact is a ground atom, i.e., an atom that does not contain any variable. A dataset is a finite set of facts. We consider pairs $K = \langle D, T \rangle$ where D is a dataset and T is a logical theory, i.e., a finite set of logical formulas, which is interpreted either as a set of integrity constraints, or as an ontology. In the former case, we call K a database, and in the latter, a knowledge base (KB). As ontology languages, we consider description logics and Datalog$^{\pm}$ (a.k.a. existential rules with negative constraints). We use interpretations to define the semantics of databases and KBs. An interpretation $I = (\Delta^I, \cdot_I)$ consists of a domain $\Delta^I$ and an interpretation function $\cdot_I$, which maps each constant $c \in C$ to some domain element $c^I \in \Delta^I$ and each n-ary predicate $P \in P$ to a set of n-tuples $P^I \subseteq (\Delta^I)^n$. Given an interpretation $I$ and an FO sentence $\phi$, we write $I \models \phi$ to denote that $I$ satisfies $\phi$ under the standard FO semantics. Given a dataset $D$, we define the interpretation corresponding to $D$ as follows: $I_D = (C, \cdot_I)$ and $\cdot_I$ interprets each constant by itself and each predicate $P$ by the set of tuples $\{(c_1, ..., c_n) | P(c_1, ..., c_n) \in D\}$.

**Database integrity constraints.** An integrity constraint (IC) is simply an FO sentence. A dataset $D$ satisfies an IC $\phi$ iff $I_D \models \phi$. If $D$ does not satisfy $\phi$, we also say that $D$ violates $\phi$. A database $K = \langle D, T \rangle$ is consistent if $D$ satisfies all ICs in $T$, inconsistent otherwise (written $K \models \perp$). The dataset $D$ is $T$-(in)consistent if $\langle D, T \rangle$ is (in)consistent. Most studied IC languages can be written as disjunctive rules of the form:

$$ \forall \vec{x} (\beta[\vec{x}] \wedge \epsilon[\vec{x}] \rightarrow \bigvee_{i=1}^{k} \exists \vec{y}_i \eta_i[\vec{x}, \vec{y}_i]) \qquad (1) $$

where $\beta[\vec{x}]$ and $\eta_i[\vec{x}, \vec{y}_i]$ (for $1 \le i \le k$) are conjunctions of relational atoms whose terms are in $\vec{x}$ and $\vec{x} \cup \vec{y}_i$, respectively, and $\epsilon[\vec{x}]$ is a conjunction of inequality atoms whose terms are in $\vec{x}$. Moreover, every variable in $\vec{x}$ is required to occur in $\beta[\vec{x}]$ to ensure safety. We often omit the universal quantifier and write $\beta[\vec{x}] \wedge \epsilon[\vec{x}] \rightarrow \bigvee_{i=1}^{k} \exists \vec{y}_i \eta_i[\vec{x}, \vec{y}_i]$. The left-hand side $\beta[\vec{x}] \wedge \epsilon[\vec{x}]$ is called the body of the rule and the right-hand side $\bigvee_{i=1}^{k} \exists \vec{y}_i \eta_i[\vec{x}, \vec{y}_i]$ its head. Figure 1 (left) shows a hierarchy of IC languages [11] (in this picture, FO stands for domain independent FO sentences).

- A universal constraint (UC) is a rule of form (1) without existential quantifiers. Any UC can be written as a set of rules of form $\beta[\vec{x}] \wedge \nu[\vec{x}] \wedge \epsilon[\vec{x}] \rightarrow \perp$, where $\nu[\vec{x}]$ is a conjunction of negated relational atoms (e.g., $P(x, y) \rightarrow Q(x) \lor (R(x, y) \wedge S(y))$) can be written as two rules $P(x, y) \wedge \neg Q(x) \wedge \neg R(x, y) \rightarrow \perp$ and $P(x, y) \wedge \neg Q(x) \wedge \neg S(y) \rightarrow \perp$).

- A denial constraint (DC) is a rule of form (1) with an empty head: $\beta[\vec{x}] \wedge \epsilon[\vec{x}] \rightarrow \perp$.

- An equality-generating dependency (EGD) is a DC where $\epsilon[\vec{x}]$ is a single inequality and is often written as $\beta[\vec{x}] \rightarrow x_i = x_j$.

- Given a predicate $P$ of arity $n$, a functional dependency (FD) over $P$ is of the form $P(x_1, ..., x_n) \wedge P(y_1, ..., y_n) \wedge \bigwedge_{i \in I} x_i = y_i \rightarrow \bigwedge_{j \in J} x_j = y_j$ for two disjoint sets of indexes $I, J \subseteq \{1, ..., n\}$. Any FD can be written as a set of EGDs (e.g., $P(x_1, x_2, x_3) \wedge P(y_1, y_2, y_3) \wedge x_1 = y_1 \rightarrow x_2 = y_2 \wedge x_3 = y_3$ can be written as two EGDs $P(x_1, x_2, x_3) \wedge P(x_1, y_2, y_3) \rightarrow x_i = y_i$ for $i \in \{2, 3\}$).

- A key constraint is an FD such that $I \cup J = \{1, ..., n\}$.

- A disjunctive tuple-generating dependency ($\vee$-TGD) is a rule of form (1) with an empty $\epsilon[\vec{x}]$, i.e., no inequalities.
- A tuple-generating dependency (TGD) is a ∨-TGD without disjunction (i.e., where k = 1).

- A local-as-view TGD (lav TGD) is a TGD where the body $\beta[\vec{x}]$ is a single atom.

- An inclusion dependency (ID) is a lav TGD where the head $\eta[\vec{x}, \vec{y}]$ is also a single atom.

- A full ($\vee$-)TGD is a ($\vee$-)TGD that does not contain any existential quantifier.

DCs (hence all ICs encompassed by DCs) are anti-monotone constraints: if a dataset $\mathcal{D}$ satisfies a DC $\phi$, then every $\mathcal{D}' \subseteq \mathcal{D}$ also satisfies $\phi$.

**► Example 1.** Consider the following university database $\langle \mathcal{D}_{\text{DB}}, \mathcal{T}_{\text{DB}} \rangle$. The predicate Student is used to register students with their identifiers, first names and last names, TakeCourse associates students and courses they are enrolled in, and GradCourse and UndergradCourse list the graduate and undergraduate courses, respectively. There are five ICs: (IC₁) is a key constraint that states that the identifier determines the student name; (IC₂) is a TGD that states that every student must be enrolled in some course; (IC₃) is a full ∨-TGD that states that every course must be registered as a graduate or undergraduate course; (IC₄) is a DC that ensures that no student identifier occurs in the second position of TakeCourse, which is intended for course identifiers; (IC₅) is a DC that states that graduate and undergraduate courses are disjoint. The database $\langle \mathcal{D}_{\text{DB}}, \mathcal{T}_{\text{DB}} \rangle$ is inconsistent: it violates (IC₁) because of the two first facts, (IC₃) because 456 is not registered as a graduate nor an undergraduate course while it occurs in second position in TakeCourse(123, 456), (IC₄) because of Student(456, Bea, Blue) and TakeCourse(123, 456), and (IC₅) because of the last two facts. Note that if we remove TakeCourse(123, 456) from $\mathcal{D}_{\text{DB}}$, (IC₃) and (IC₄) will be satisfied, but (IC₂) will become violated since TakeCourse(123, 456) is the only fact that associates some course to 123.

$$ \mathcal{T}_{\text{DB}} = \{ \text{Student}(x, y, z) \wedge \text{Student}(x', y', z') \wedge x = x' \rightarrow y = y' \wedge z = z', \quad (\text{IC}_1) $$

$$ \text{Student}(x, y, z) \rightarrow \exists v \text{TakeCourse}(x, v), \quad (\text{IC}_2) $$

$$ \text{TakeCourse}(x, y) \rightarrow \text{GradCourse}(y) \lor \text{UndergradCourse}(y), \quad (\text{IC}_3) $$

$$ \text{Student}(x, y, z) \wedge \text{TakeCourse}(v, x) \rightarrow \bot, \quad (\text{IC}_4) $$

$$ \text{GradCourse}(x) \wedge \text{UndergradCourse}(x) \rightarrow \bot \quad (\text{IC}_5) $$

$$ \mathcal{D}_{\text{DB}} = \{ \text{Student}(123, \text{Ana}, \text{Azure}), \text{Student}(123, \text{Ann}, \text{Azure}), \text{Student}(456, \text{Bea}, \text{Blue}), \\ \text{TakeCourse}(123, 456), \text{TakeCourse}(456, \text{CS1}), \\ \text{GradCourse}(\text{CS1}), \text{UndergradCourse}(\text{CS1}) \} $$

**Datalog$^{\pm}$.** A Datalog$^{\pm}$ ontology, or Datalog$^{\pm}$ program, is a finite set of rules of two kinds:

- TGDs (also called existential rules), i.e., rules of the form $\beta[\vec{x}] \rightarrow \exists \vec{y} \eta[\vec{x}, \vec{y}]$, and

- negative constraints (NCs), which are rules of the form $\beta[\vec{x}] \rightarrow \bot$ where $\beta[\vec{x}]$ is a conjunction of relational atoms with variables $\vec{x}$ (and may contain constants) [104].

However, the semantics of Datalog$^{\pm}$ is different from that of database integrity constraints. Indeed, while databases are interpreted under the closed world assumption, KBs are interpreted under the open world assumption, so that facts that do not belong to the dataset are not deemed to be false. Hence, instead of evaluating rules on the interpretation corresponding to the dataset as in the database setting, one reasons over the set of all models of the KB. A model of a Datalog$^{\pm}$ KB $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$ is an interpretation $\mathcal{I} = (\Delta^{\mathcal{I}}, \mathcal{I}^*)$ such that

- $\Delta^{\mathcal{I}}$ contains all constants from $\mathcal{D}$ and $\mathcal{I}^* = \mathcal{C}$ for each constant $\mathcal{C}$ that occurs in $\mathcal{D}$ (standard name assumption),

- $\mathcal{I} \models P(c_1, \dots, c_n)$, i.e., $(c_1, \dots, c_n) \in \mathcal{P}^{\mathcal{I}}$, for every $P(c_1, \dots, c_n) \in \mathcal{D}$, and

- $\mathcal{I} \models \phi$ for every $\phi \in \mathcal{T}$.
5:6 Inconsistency-Tolerant Semantics Based on (Preferred) Repairs

<figure><img src="image_7.png" /><figcaption>Figure 1 Hierarchies of database integrity constraint languages (left) [11, Fig. 1] and of some ontology languages (right). There is a downward path from $\mathcal{L}_1$ to $\mathcal{L}_2$ if any set of ICs (resp. any ontology) in $\mathcal{L}_2$ can be rewritten into an equivalent set of ICs (resp. ontology) in $\mathcal{L}_1$.</figcaption></figure>

A KB is *consistent*, or satisfiable, if it has a model, inconsistent otherwise ($\mathcal{K} \models \perp$). Again, $\mathcal{D}$ is $\mathcal{T}$-(in)consistent if $\langle \mathcal{D}, \mathcal{T} \rangle$ is (in)consistent. A KB *entails* an FO sentence $\phi$, written $\mathcal{K} \models \phi$, if $\mathcal{I} \models \phi$ for every model $\mathcal{I}$ of $\mathcal{K}$. To illustrate the difference between TGDs used as ICs or as ontology language, consider $\mathcal{D} = \{P(c)\}$ and $\mathcal{T} = \{P(x) \to Q(x)\}$. The database $\langle \mathcal{D}, \mathcal{T} \rangle$ is inconsistent while the KB $\langle \mathcal{D}, \mathcal{T} \rangle$ is not (and entails $Q(c)$). Since query answering in Datalog<sup>±</sup> is undecidable (this is already the case for existential rules, without NCs), a wealth of decidable fragments have been designed. Some of the most studied are as follows [104].

- Recall that a TGD is called *full* if it does not have any existential quantifier. We denote by $F$ the ontology language of full TGDs, also known as *Datalog*.

- A set of TGDs is *acyclic* if its predicate graph, defined as the directed graph with vertices **P** and an edge from **P** to **Q** iff there is a rule whose body contains **P** and whose head contains **Q**, is acyclic. We denote by **A** the language of acyclic sets of TGDs.

- A TGD is *guarded* if its body has an atom (called a guard) that contains all variables occurring in the body. We denote by **G** the language of guarded TGDs.

- A TGD is *linear* if its body contains a single atom. We denote by **L** the language of linear TGDs.

- A set of TGDs is *sticky* if it respects a syntactic condition which ensures that terms that unify with variables that appear more than once in the body of some rule are always propagated by the rules. We denote by **S** the language of sets of sticky TGDs.

- A, **G** and **S** come with their respective “weak” versions which restrict the acyclicity, guardedness and stickiness syntactic conditions to take into account only potentially “harmful” variables: weakly acyclic (**WA**), weakly guarded (**WG**) and weakly sticky (**WS**). For every TGD language **X**, we denote by **X**<sub>⊥</sub> its extension with NCs. Figure 1 (right) shows a hierarchy of ontology languages, including these Datalog<sup>±</sup> fragments.

**Example 2.** Consider the KB $\langle \mathcal{D}_{\mathcal{K}\mathcal{B}}, \mathcal{T}_{\mathcal{K}\mathcal{B}} \rangle$ obtained from the database of Example 1 by dropping $(\mathcal{I}\mathcal{C}_1)$ and $(\mathcal{I}\mathcal{C}_3)$ (since key constraints and disjunctive TGDs are not supported by Datalog<sup>±</sup>), which belongs to all the Datalog<sup>±</sup> fragments of Figure 1 except $F_{\perp}$.
$$ \mathcal{T}_{\text{KB}} = \{\text{Student}(x, y, z) \to \exists v \text{TakeCourse}(x, v), \qquad (\text{TGD}) $$

$$ \text{Student}(x, y, z) \land \text{TakeCourse}(v, x) \to \perp, \qquad (\text{NC}_1) $$

$$ \text{GradCourse}(x) \land \text{UndergradCourse}(x) \to \perp \} \qquad (\text{NC}_2) $$

$$ \mathcal{D}_{\text{KB}} = \{ \text{Student}(123, \text{Ana}, \text{Azure}), \text{Student}(123, \text{Ann}, \text{Azure}), \text{Student}(456, \text{Bea}, \text{Blue}), \\ \text{TakeCourse}(123, 456), \text{TakeCourse}(456, \text{CS1}), \\ \text{GradCourse}(\text{CS1}), \text{UndergradCourse}(\text{CS1}) \} $$

$\langle \mathcal{D}_{\text{KB}}, \mathcal{T}_{\text{KB}} \rangle$ is inconsistent since for every interpretation $\mathcal{I}$, if $\mathcal{I} \models \text{Student}(456, \text{Bea}, \text{Blue})$ and $\mathcal{I} \models \text{TakeCourse}(123, 456)$, then $\mathcal{I}$ does not satisfy $(\text{NC}_1)$, and similarly, every interpretation that satisfies the two last facts violates $(\text{NC}_2)$. However, in contrast with the database setting, removing the facts $\text{TakeCourse}(123, 456)$ and, e.g., $\text{GradCourse}(\text{CS1})$ from $\mathcal{D}_{\text{KB}}$ yields a consistent KB. For example, the interpretation $\mathcal{I} = (\mathbf{C}, \mathcal{I})$ below is a model of $\langle \mathcal{D}_{\text{KB}} \setminus \{\text{TakeCourse}(123, 456), \text{GradCourse}(\text{CS1})\}, \mathcal{T}_{\text{KB}} \rangle$. Note that $\mathcal{I}$ uses a fresh element $n$ to witness a course taken by 123 and satisfy the TGD.

$$ c^{\mathcal{I}} = c \text{ for every } c \in \mathbf{C} $$

$$ \text{Student}^{\mathcal{I}} = \{(123, \text{Ana}, \text{Azure}), (123, \text{Ann}, \text{Azure}), (456, \text{Bea}, \text{Blue})\} $$

$$ \text{TakeCourse}^{\mathcal{I}} = \{(123, n), (456, \text{CS1})\} $$

$$ \text{UndergradCourse}^{\mathcal{I}} = \{\text{CS1}\} $$

$$ \text{GradCourse}^{\mathcal{I}} = \emptyset $$

<table><caption>■ **Table 1** Syntax and semantics of DL concept and role constructors and TBox axioms: *a* denotes an individual name, *C*, *C*₁ and *C*₂ concepts (concept names or complex concepts), *R* and *S* role names or inverse roles, and *n* a natural number.</caption><thead><tr><th>Name</th><th>Syntax</th><th>Semantics</th></tr></thead><tbody><tr><td>Top concept</td><td>⊤</td><td>Δ<sup>I</sup></td></tr><tr><td>Bottom concept</td><td>⊥</td><td>∅</td></tr><tr><td>Nominal</td><td>{a}</td><td>{a<sup>I</sup>}</td></tr><tr><td>Negation</td><td>¬C</td><td>Δ<sup>I</sup> \ C<sup>I</sup></td></tr><tr><td>Conjunction</td><td>C<sub>1</sub> &cap; C<sub>2</sub></td><td>C<sub>1</sub><sup>I</sup> &cap; C<sub>2</sub><sup>I</sup></td></tr><tr><td>Disjunction</td><td>C<sub>1</sub> &cup; C<sub>2</sub></td><td>C<sub>1</sub><sup>I</sup> &cup; C<sub>2</sub><sup>I</sup></td></tr><tr><td>Existential restriction</td><td>∃R</td><td>{d<sub>1</sub> | there exists (d<sub>1</sub>, d<sub>2</sub>) ∈ R<sup>I</sup>}</td></tr><tr><td>Qualified existential restriction</td><td>∃R.C</td><td>{d<sub>1</sub> | there exists (d<sub>1</sub>, d<sub>2</sub>) ∈ R<sup>I</sup> with d<sub>2</sub> ∈ C<sup>I</sup>}</td></tr><tr><td>Qualified universal restriction</td><td>∀R.C</td><td>{d<sub>1</sub> | d<sub>2</sub> ∈ C<sup>I</sup> for all (d<sub>1</sub>, d<sub>2</sub>) ∈ R<sup>I</sup>}</td></tr><tr><td rowspan="2">Qualified cardinality restrictions</td><td>≥ nR.C</td><td>{d<sub>1</sub> | |{d<sub>2</sub> | (d<sub>1</sub>, d<sub>2</sub>) ∈ R<sup>I</sup> and d<sub>2</sub> ∈ C<sup>I</sup>}| ≥ n}</td></tr><tr><td>≤ nR.C</td><td>{d<sub>1</sub> | |{d<sub>2</sub> | (d<sub>1</sub>, d<sub>2</sub>) ∈ R<sup>I</sup> and d<sub>2</sub> ∈ C<sup>I</sup>}| ≤ n}</td></tr><tr><td>Inverse role</td><td>R<sup>-</sup></td><td>{(d<sub>2</sub>, d<sub>1</sub>) | (d<sub>1</sub>, d<sub>2</sub>) ∈ R<sup>I</sup>}</td></tr><tr><td>Concept inclusion</td><td>C<sub>1</sub> &sqsubseteq; C<sub>2</sub></td><td>C<sub>1</sub><sup>I</sup> &sqsubseteq; C<sub>2</sub><sup>I</sup></td></tr><tr><td>Role inclusion</td><td>R &sqsubseteq; S</td><td>R<sup>I</sup> &sqsubseteq; S<sup>I</sup></td></tr><tr><td>Complex role inclusion</td><td>R<sub>1</sub> &circ; &hellip; &circ; R<sub>n</sub> &sqsubseteq; S</td><td>R<sub>1</sub><sup>I</sup> &circ; &hellip; &circ; R<sub>n</sub><sup>I</sup> &sqsubseteq; S<sup>I</sup></td></tr><tr><td>Role disjointness</td><td>R &sqsubseteq; ¬S</td><td>R<sup>I</sup> &cap; S<sup>I</sup> = ∅</td></tr><tr><td>Transitivity axiom</td><td>(trans R)</td><td>R<sup>I</sup> &circ; R<sup>I</sup> &sqsubseteq; R<sup>I</sup></td></tr></tbody></table>
5:8 Inconsistency-Tolerant Semantics Based on (Preferred) Repairs

**Description logics.** Description logics (DLs) form a family of ontology languages that are incomparable with Datalog$^{±}$: on the one hand the DL syntax restricts a lot what can be expressed in TGD-like rules, but on the other hand some DL languages allow for features not available in Datalog$^{±}$ TGDs, such as disjunction in the head, use of constants, or cardinality restrictions. DL predicates can only have arity 1 or 2, and are called concept and role names, respectively. Note that in DL parlance, constants are called individual names, facts are called assertions, datasets are called ABoxes, and ontologies TBoxes. Moreover, the ontology axioms are not written as FO sentences but in a concise syntax, which enforces restrictions on the language expressivity. Table 1 gives the syntax and semantics of the most common DL axioms and we list below a few examples among the many DL languages.

■ ALC is the prototypical DL and allows for concept inclusions (and no other kind of axiom) using the constructors $⊤, ⊥, ¬C, C_1 ∩ C_2, C_1 ∪ C_2, ∃R.C, ∀R.C$.

■ The expressive SHIQ extends ALC with role inclusions, transitivity axioms, inverse roles, and qualified cardinality restrictions, with the restriction that roles that occur in qualified cardinality restrictions are required to be simple, meaning that they should not have any transitive subrole (i.e., R is simple if $T ≡ S ⊑ R$ implies (trans S) $\notin T$).

■ One can further extend SHIQ with nominals, complex role inclusions, role disjointness axioms, a universal role and a Self concept, with again some restrictions on the use of complex roles to ensure decidability. The resulting language, called SROIQ, is closely related to OWL, the ontology language standard for the Semantic Web [121].

■ The lightweight DL $EL_⊥$ is the fragment of ALC that only allows for $⊤, ⊥, C_1 ∩ C_2, ∃R.C$.

■ Another family of lightweight DLs is the DL-Lite family. In particular:

- DL-Lite$_{core}$ TBox consists of concept inclusions of the form $B ⊑ C$ where $B := A | ∃R$ with A a concept name and R a role name or inverse role, and $C := B | ¬B$.

- DL-Lite$_R$ extends DL-Lite$_{core}$ with role inclusions and role disjointness axioms.

- DL-Lite$_{R,∩}^1$ extends DL-Lite$_R$ with concept inclusions of the form $A_1 ∩ ... ∩ A_n ⊑ A$.

An interpretation $I = (Δ^I, ♦^I)$ is a model of a DL KB $K = ⟨D, T⟩$ if

■ $I$ satisfies all facts in $D$ (i.e., $a^I ∈ A^I$ and $(a^I, b^I) ∈ R^I$ for all concept and role assertions $A(a)$ and $R(a, b)$ in $D$) and

■ $I$ satisfies all axioms in $T$ as explained in Table 1.

The only difference with the semantics of Datalog$^{±}$ KBs is that we do not need to make the standard name assumption, nor the unique name assumption (even though these assumptions are sometimes made): in general, two different constants from $D$ can be interpreted by the same element of $Δ^I$.

► **Example 3.** The database of Example 1 can be “translated” into the SHIQ KB $⟨D_{DL}, T_{DL}⟩$. Since predicates of arity greater than 2 are not allowed, the ternary predicate Student is replaced by a concept Student that stores the student identifiers and two roles FirstName and LastName that associate identifiers with first and last names. $(ax_1)-(ax_2)$ state that students have at most one first name and one last name, $(ax_3)$ that every student takes some course, $(ax_4)$ that everything in the range of TakeCourse is a graduate course or an undergraduate course, $(ax_5)$ that the concept Student and the range of TakeCourse are disjoint, and $(ax_6)$ that GradCourse and UndergradCourse are disjoint.

<footnote n="1">¹ DL-Lite<sub>Horn</sub> [12], the variant of DL-Lite<sub>R,∩</sub> [58] without role disjointness axioms, may be more common. However, both languages have the same computational behavior [12].</footnote>
$$
\begin{align*}
\mathcal{T}_{\text{DL}} = & \{ \text{Student} \sqsubseteq \text{1 student}, \text{ First Name}, \text{ T}, \text{ Student} \sqsubseteq \text{1 student}, \text{ Last Name}, \text{ T}, \quad (\text{ax}_1)-(\text{ax}_2) \\
& \text{Student} \sqsubseteq \exists \text{Take Course}, \text{ T}, \quad (\text{ax}_3) \\
& \exists \text{Take Course}, \text{ T} \sqsubseteq \text{Grad Course} \sqcup \text{Undergrad Course}, \quad (\text{ax}_4) \\
& \text{Student} \sqcap \exists \text{Take Course}, \text{ T} \sqsubseteq \perp, \quad (\text{ax}_5) \\
& \text{Grad Course} \sqcap \text{Undergrad Course} \sqsubseteq \perp \} \quad (\text{ax}_6)
\end{align*}
$$

$$
\mathcal{D}_{\text{DL}} = \{ \text{Student}(123), \text{Student}(456), \text{Last Name}(123, \text{Azure}), \text{Last Name}(456, \text{Blue}), \\
\text{ student}(123, \text{Ana}), \text{ student}(123, \text{Ann}), \text{ student}(456, \text{Bea}), \\
\text{Take Course}(123, 456), \text{Take Course}(456, \text{CS1}), \\
\text{Grad Course}(\text{CS1}), \text{Undergrad Course}(\text{CS1}) \}
$$

As in Example 2, the KB is inconsistent but removing the facts TakeCourse(123, 456) and GradCourse(CS1) makes it consistent, when interpreted without the unique name assumption: a model of ⟨D<sub>DL</sub> \ {TakeCourse(123, 456), GradCourse(CS1)}, T<sub>DL</sub>⟩ simply interprets Ann and Ana by the same domain element (however, if interpreted under the unique name assumption, the KB would be inconsistent).

**Queries.** An FO query is simply an FO formula, whose free variables are called the *answer variables*. A tuple $\vec{a} = (a_1, \dots, a_n)$ is a (certain) *answer* to a query $q(\vec{x})$ with answer variables $\vec{x} = (x_1, \dots, x_n)$ over a KB $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$ if $\mathcal{K} \models q(\vec{a})$, where $q(\vec{a})$ is the FO sentence obtained by replacing each $x_i$ by $a_i$ in $q(\vec{x})$. For a database $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$, we simply define $\mathcal{K} \models q(\vec{a})$ by $\mathcal{I}_{\mathcal{D}} \models q(\vec{a})$. A conjunctive query (CQ) is an FO query of the form $q(\vec{x}) = \exists \vec{y} \varphi(\vec{x}, \vec{y})$ where $\varphi(\vec{x}, \vec{y})$ is a conjunction of relational atoms. A union of conjunctive queries (UCQ) has form $q(\vec{x}) = \bigvee_{i=1}^n q_i(\vec{x})$ where each $q_i(\vec{x})$ is a CQ. We often see a UCQ as a finite set of CQs. A query that has no answer variable is called a *Boolean query* (BCQ, BUCQ).

► **Example 4.** Consider the dataset $\mathcal{D}'_{\text{DL}} = \{\text{Student}(123), \text{TakeCourse}(456, \text{CS1})\}$ and the ontology $\mathcal{T}_{\text{DL}}$ from Example 3. The CQ $q(x) = \exists y \text{TakeCourse}(x, y)$ has two certain answers over $\langle \mathcal{D}'_{\text{DL}}, \mathcal{T}_{\text{DL}} \rangle$: (123) and (456).

**FO- and UCQ-rewritability.** We say that CQ answering under an ontology language $\mathcal{L}$ is UCQ-rewritable (resp. FO-rewritable) if for every BCQ $q$ and ontology $\mathcal{T}$ in $\mathcal{L}$, there exists a BUCQ (resp. an FO query) $q_r$ such that for every dataset $\mathcal{D}$, $\langle \mathcal{D}, \mathcal{T} \rangle \models q$ iff $\mathcal{I}_{\mathcal{D}} \models q_r$. In the BUCQ case, we denote the set of BCQs in $q_r$ by $\text{Rew}(q, \mathcal{T})$.

► **Fact 5.** CQ answering under L, A and S is UCQ-rewritable (cf. [131, Def. 2.19 and Properties 4, 5, 6], and [104, Sec. 3.2.1]), as well as under DL-Lite<sub>R,∩</sub> and its sub-languages [58].

► **Example 6.** Given the DL-Lite<sub>core</sub> ontology $\mathcal{T} = \{\text{Student} \sqsubseteq \exists \text{TakeCourse}\}$ and BCQ $q = \exists y \text{TakeCourse}(123, y)$, $\text{Rew}(q, \mathcal{T}) = \{q, q'\}$ with $q' = \text{Student}(123)$.

► **Proposition 7 (Consistency checking via UCQ-rewritability).** For every Datalog<sup>±</sup> fragment X, if CQ answering under X is UCQ-rewritable, then for every ontology T in X<sub>⊥</sub>, there exists a BUCQ q<sub>⊥</sub><sup>T</sup> such that for every dataset D, ⟨D, T⟩ ⊧ ⊥ iff I<sub>D</sub> ⊧ q<sub>⊥</sub><sup>T</sup>.

**Proof.** For every Datalog<sup>±</sup> KB ⟨D, T⟩, ⟨D, T⟩ ⊧ ⊥ iff there exists $\beta[\vec{x}] \to \in \mathcal{T}$ such that ⟨D, T<sup>+</sup>⟩ ⊧ ∃$\vec{x}\beta[\vec{x}]$, where T<sup>+</sup> is the set of TGDs in T, so if T<sup>+</sup> is in X and CQ answering under X is UCQ-rewritable, ⟨D, T⟩ ⊧ ⊥ iff $\mathcal{I}_D \models q'$ for some $q' \in \bigcup_{\beta[\vec{x}] \to \perp \in \mathcal{T}} \text{Rew}(\exists \vec{x} \beta[\vec{x}], T^+)$. ◀
5:10 Inconsistency-Tolerant Semantics Based on (Preferred) Repairs

## 2.2 Computational complexity

We consider two ways of measuring the computational complexity of decision problems: the *data complexity* is measured w.r.t. the size of the dataset $\mathcal{D}$ while the *combined complexity* takes into account the size of the whole input.

**Complexity classes.** We will refer to the following complexity classes:

$$AC^0 \subseteq L \subseteq NL \subseteq P \stackrel{\text{NP}}{\subseteq} \stackrel{\text{coNP}}{\subseteq} DP \subseteq \Theta_2^P \subseteq \Delta_2^P \stackrel{\Sigma_2^P}{\subseteq} \stackrel{\text{coNP}}{\subseteq} \Pi_2^P \stackrel{\text{NEXP}}{\subseteq} \stackrel{\text{coNEXP}}{\subseteq} DEXP \subseteq \dots \subseteq 2EXP$$

■ Below P:

- $AC^0$: problems solvable by a family of circuits of constant depth and polynomial size w.r.t. the size of the input, with unbounded-fanin AND and OR gates.

- L: problems solvable in logarithmic space w.r.t. the size of the input.

- NL: problems solvable in non-deterministic logarithmic space. These are problems for which there exists a certificate of polynomial size which can be verified by a deterministic logarithmic-space bounded Turing machine that has an additional read-only read-once input tape. It is known (by Immerman-Szelepcsényi theorem) that $NL = coNL$.

- The polynomial hierarchy and other classes between P and PSPACE:

- $P = \Sigma_0^P$: problems which are solvable in polynomial time w.r.t. the size of the input.

- $NP = \Sigma_1^P$: problems which are solvable in non-deterministic polynomial time. These are problems for which there exists a certificate of polynomial size which can be verified by a deterministic polynomial-time Turing machine.

- $coNP = \Pi_1^P$: problems whose complement is in NP.

- In general, for $i \ge 0$, $\Delta_{i+1}^P = P^{\Sigma_i^P}$ is the class of problems solvable in polynomial time with access to a $\Sigma_i^P$ oracle, $\Sigma_{i+1}^P = NP^{\Sigma_i^P}$, and $\Pi_{i+1}^P = coNP^{\Sigma_i^P}$.

- $\Theta_{i+1}^P$ is the class of problems solvable in polynomial time with at most logarithmically many calls to a $\Sigma_i^P$ oracle. It is known that these are problems solvable by polynomially many *independent* (parallel) calls to a $\Sigma_i^P$ oracle [47].

- DP: problems that are the intersection of a problem in NP and a problem in coNP.

- PSPACE: problems which are solvable in polynomial space. It is known (by Savitch's theorem) that $PSPACE = NPSPACE$.

- The (weak) exponential hierarchy and other classes between EXP and 2EXP:

- $EXP = \Sigma_0^{EXP}$: problems which are solvable in exponential time, i.e., in $O(2^{p(n)})$ where $p$ is a polynomial function and $n$ is the input size.

- $NEXP = \Sigma_1^{EXP}$: problems which are solvable in non-deterministic exponential time.

- $coNEXP = \Pi_1^{EXP}$: problems whose complement is in NEXP.

- In general, for $i \ge 0$, $\Delta_{i+1}^{EXP} = EXP^{\Sigma_i^P}$ is the class of problems solvable in exponential time with access to a $\Sigma_i^P$ oracle, $\Sigma_{i+1}^{EXP} = NEXP^{\Sigma_i^P}$, and $\Pi_{i+1}^{EXP} = coNEXP^{\Sigma_i^P}$.

- DEXP: problems that are the intersection of a problem in NEXP and one in coNEXP.

- $P^{NEXP}$: problems that are solvable in polynomial time with an NEXP oracle. It is known (since the strong exponential hierarchy collapses [89]) that $NP^{NEXP} = P^{NEXP}$.

- 2EXP: problems which are solvable in double-exponential time.
<table><caption>**Table 2** Complexity of BCQ entailment. All non-“in” entries are completeness results. For Datalog<sup>±</sup> fragments, references are given for X rather than X<sub>⊥</sub>, cf. Remark 9.</caption><thead><tr><th></th><th></th><th>Data complexity</th><th></th><th>Combined complexity</th></tr></thead><tbody><tr><td rowspan="5">DLs</td><td>DL-Lite<sub>R</sub></td><td>in AC<sup>0</sup></td><td rowspan="2">[12, Th. 8.9]</td><td>NP</td><td rowspan="2">[58, Th. 44]</td></tr><tr><td>DL-Lite<sub>R,∩</sub></td><td>in AC<sup>0</sup></td><td>NP</td></tr><tr><td>E<sub>L</sub><sub>⊥</sub></td><td>P</td><td>[125, Th. 2]</td><td>NP</td><td>[125, Th. 2]</td></tr><tr><td>A<sub>L</sub><sub>C</sub></td><td>coNP</td><td>[120, Th. 4.6]</td><td>EXP</td><td>[110, Th. 4]</td></tr><tr><td>S<sub>H</sub><sub>I</sub><sub>Q</sub></td><td>coNP</td><td>[84, Cor. 36]</td><td>2EXP</td><td>[84, Cor. 33]</td></tr><tr><td rowspan="5">Datalog<sup>±</sup></td><td>L<sub>⊥</sub></td><td>in AC<sup>0</sup></td><td>[56, Cor. 10]</td><td>PSPACE</td><td>[55, Th. 12.7]</td></tr><tr><td>A<sub>⊥</sub></td><td>in AC<sup>0</sup></td><td>[104, Pr. 3.3]</td><td>NEXP</td><td>[104, Pr. 3.3]</td></tr><tr><td>G<sub>⊥</sub></td><td>P</td><td>[54, Th. 6.1]</td><td>2EXP</td><td>[54, Th. 6.1]</td></tr><tr><td>S<sub>⊥</sub></td><td>in AC<sup>0</sup></td><td>[57, Th. 3.5]</td><td>EXP</td><td>[57, Th. 3.3 & 3.4]</td></tr><tr><td>F<sub>⊥</sub></td><td>P</td><td>[70, Th. 4.4]</td><td>EXP</td><td>[70, Th. 4.5]</td></tr><tr><td>Database</td><td></td><td>in AC<sup>0</sup></td><td>[135, Tab. 1]</td><td>NP</td><td>[63, Th. 7]</td></tr></tbody></table>

**Complexity of BCQ entailment and consistency checking.** We illustrate the computational complexity of the decision problems we consider on a few selected languages from Figure 1. Table 2 shows the data and combined complexity of *BCQ entailment*, the decision problem which takes as input a database or KB $\mathcal{K} = \langle D, \mathcal{T} \rangle$ and a Boolean conjunctive query $q$ and outputs “yes” if $\mathcal{K} \models q$, and “no” otherwise. Table 3 shows the data and combined complexity of *consistency checking*, the decision problem which takes as input a database or KB $\mathcal{K} = \langle D, \mathcal{T} \rangle$ and outputs “yes” if $\mathcal{K}$ is consistent, and “no” otherwise.

**Remark 8 (Database setting).** In the database setting, ICs do not play any role in BCQ evaluation, so we do not distinguish between the different IC languages in Table 2. Regarding consistency checking, $\langle D, \mathcal{T} \rangle \models \perp$ iff $\mathcal{I}_D \models \bigvee_{\phi \in \mathcal{T}} \neg \phi$. This straightforwardly yields the AC<sup>0</sup> data complexity upper bounds and the coNP upper bounds for the IC languages such that the $\neg \phi$ are BCQs with safe negation and inequalities (i.e., for universal constraints).

**Remark 9 (Datalog<sup>±</sup>: X versus X<sub>⊥</sub>).** For Datalog<sup>±</sup> fragments, most complexity results have actually been shown for BCQ entailment in X rather than in X<sub>⊥</sub>, but they extend to both *inconsistency checking* and BCQ entailment in X<sub>⊥</sub>:

- Lower bounds: If $\mathcal{T}$ contains only TGDs, for any BCQ $q$, $\langle D, \mathcal{T} \rangle \models q$ iff $\langle D, \mathcal{T} \cup \{q \to \perp\} \rangle \models \perp$, hence inconsistency checking in X<sub>⊥</sub> is at least as hard as BCQ entailment in X.

- Combined complexity and P data complexity upper bounds: Recall that (i) $\langle D, \mathcal{T} \rangle \models \perp$ iff there exists $\beta[\vec{x}] \to \perp \in \mathcal{T}$ such that $\langle D, \mathcal{T}^+ \rangle \models \exists \vec{x} \beta[\vec{x}]$, where $\mathcal{T}^+$ is the set of TGDs in $\mathcal{T}$ (meaning that $\mathcal{T}^+$ is in X if $\mathcal{T}$ is in X<sub>⊥</sub>), and (ii) for every BCQ $q$, $\langle D, \mathcal{T} \rangle \models q$ iff either $\langle D, \mathcal{T}^+ \rangle \models q$ or $\langle D, \mathcal{T} \rangle \models \perp$ (since an inconsistent KB entails every query).

- We thus only need a linear number of checks of BCQ entailment under X to decide (in)consistency checking and BCQ entailment under X<sub>⊥</sub>. This yields the P data complexity upper bounds and the EXP and 2EXP combined complexity upper bounds.

- For the PSPACE upper bound for L<sub>⊥</sub>, guess an NC $\beta[\vec{x}] \to \perp \in \mathcal{T}$ (or q in the BCQ entailment case) and check in PSPACE that $\langle D, \mathcal{T}^+ \rangle \models \exists \vec{x} \beta[\vec{x}]$ (or $\langle D, \mathcal{T}^+ \rangle \models q$). The result follows from the fact that NPSPACE = PSPACE.

- For the NEXP/coNEXP upper bounds for A<sub>⊥</sub>, proceed as above, but guess the BCQ $\exists \vec{x} \beta[\vec{x}]$ (or q) together with the certificate that shows that it is entailed by $\langle D, \mathcal{T}^+ \rangle$, which can be verified in exponential time since BCQ entailment in A is in NEXP.
5:12 Inconsistency-Tolerant Semantics Based on (Preferred) Repairs

<table><caption>Table 3 Complexity of consistency checking. All non-"in" entries are completeness results.</caption><thead><tr><th></th><th></th><th>Data complexity</th><th>Combined complexity</th></tr></thead><tbody><tr><td rowspan="4">DLs</td><td>DL-Lite<sub>R</sub></td><td>in AC<sup>0</sup></td><td>NL</td><td rowspan="4">[12, Th. 8.2]</td></tr><tr><td>DL-Lite<sub>R,∩</sub></td><td>in AC<sup>0</sup></td><td>P</td></tr><tr><td>E<sub>L</sub></td><td>P</td><td>[13, Th. 4][59, Th. 7]</td></tr><tr><td>ALC</td><td>NP</td><td>P</td></tr><tr><td></td><td>SHIQ</td><td>NP</td><td>[90, Th. 2]</td><td>[13, Th. 4][59, Th. 7]</td></tr><tr><td rowspan="5">Datalog<sup>±</sup></td><td>L<sub>⊥</sub></td><td>in AC<sup>0</sup></td><td>PSPACE</td><td rowspan="5">[132, Cor. 3.1]</td></tr><tr><td>A<sub>⊥</sub></td><td>in AC<sup>0</sup></td><td>coNEXP</td></tr><tr><td>G<sub>⊥</sub></td><td>P</td><td>2EXP</td></tr><tr><td>S<sub>⊥</sub></td><td>in AC<sup>0</sup></td><td>EXP</td></tr><tr><td>F<sub>⊥</sub></td><td>P</td><td>EXP</td></tr><tr><td rowspan="5">ICs</td><td>FD</td><td>in AC<sup>0</sup></td><td>in L</td><td rowspan="5">folklore (e.g., [11])</td></tr><tr><td>DC</td><td>in AC<sup>0</sup></td><td>coNP</td></tr><tr><td>full TGD</td><td>in AC<sup>0</sup></td><td>coNP</td></tr><tr><td>UC</td><td>in AC<sup>0</sup></td><td>coNP</td></tr><tr><td>TGD</td><td>in AC<sup>0</sup></td><td>Π<sub>2</sub><sup>P</sup></td></tr><tr><td></td><td></td><td></td><td></td><td>BCQ eval. [63, Th. 7]</td></tr><tr><td></td><td></td><td></td><td></td><td>extend. to BCQ with safe ¬ and ≠</td></tr><tr><td></td><td></td><td></td><td></td><td>[123, Th. 3.1]</td></tr></tbody></table>

AC⁰ upper bounds: If $X_⊥ \in \{L_⊥, A_⊥, S_⊥\}$, since CQ answering under $X$ is UCQ-rewritable (Fact 5), by Proposition 7, for every ontology $T$ in $X_⊥$, there exists a BUCQ $q_⊥^T$ such that for every dataset $D$, $\langle D, T \rangle \models \perp$ iff $\mathcal{I}_D \models q_⊥^T$. Moreover, for every BCQ $q$, $\langle D, T \rangle \models q$ iff $\mathcal{I}_D \models q_⊥^T \lor \bigvee_{q' \in \text{Rev}(q, T^+)} q'$ where $T^+$ is the set of TGDs in $T$. This yields the AC⁰ data complexity upper bound for consistency checking and BCQ entailment in $X_⊥$.

3 Dataset repairs of inconsistent databases or knowledge bases

In this section, we define the central notion of a (dataset) repair then present some characterizations of repairs based on the conflict hypergraph of a database or KB and on abstract argumentation frameworks.

3.1 Definition

We assume that all logical theories (sets of ICs or ontologies) we consider are satisfiable and reliable, so that if a database or KB $K = \langle D, T \rangle$ is inconsistent, the problem stems from the dataset $D$. In this context, it makes sense to define (dataset) repairs of $K$ as consistent datasets that minimally differ from $D$. In the database setting, one can restore consistency by deleting and/or adding facts to $D$ (if $D = \{P(c)\}$ and $T = \{P(x) \to Q(x)\}$), we can obtain a consistent database by removing $P(c)$ or by adding $Q(c)$ to $D$), except for anti-monotone constraints for which only deleting facts can solve a constraint violation. In the KB setting, because of the open world assumption, repairs can only be obtained by removing facts.

► **Definition 10 (Dataset repairs).** A symmetric difference repair, or $\Delta$-repair, of $D$ w.r.t. $T$ is a $T$-consistent dataset $R$ such that there is no $T$-consistent $R'$ such that $R' \Delta D \subseteq R \Delta D$, where $\Delta$ is the symmetric difference operator: $S_1 \Delta S_2 = (S_1 \setminus S_2) \cup (S_2 \setminus S_1)$.

A subset repair (resp. superset repair), or $\subseteq$-repair (resp. $\supseteq$-repair), of $D$ w.r.t. $T$ is a $T$-consistent dataset $R$ such that $R \subseteq D$ (resp. $R \supseteq D$) and there is no $T$-consistent $R'$ such that $R \subsetneq R' \subseteq D$ (resp. $R \supsetneq R' \supseteq D$).
For $K = \langle D, T \rangle$ and $x \in \{\Delta, \subseteq, \supset\}$, we use $S-Rep_x(K)$ or $S-Rep_x(D, T)$ to denote the set of all $x$-repairs of $K$, i.e., $x$-repairs of $D$ w.r.t. $T$. When $K$ is a KB or a database with anti-monotone ICs, $S-Rep_\Delta(K) = S-Rep_\subseteq(K)$ and $S-Rep_\supseteq(K) = \emptyset$ if $K$ is inconsistent, so we can simply write $S-Rep(K)$ for $S-Rep_\subseteq(K)$ and talk about “repairs” instead of $\subseteq$-repairs.

In the above definition, the “S” in $S-Rep_x(K)$ can be understood as “standard” or “set-inclusion-based”, in contrast with the optimal repairs that we consider in Section 5 and which compare datasets using other criteria than set-inclusion. It follows from the definition that $S-Rep_\subseteq(K) \subseteq S-Rep_\Delta(K)$ and $S-Rep_\supseteq(K) \subseteq S-Rep_\Delta(K)$.

**► Example 11.** Recall $\langle D_{\mathcal{DB}}, T_{\mathcal{DB}} \rangle$ from Example 1. The $\Delta$-repairs of $D_{\mathcal{DB}}$ w.r.t. $T_{\mathcal{DB}}$ are as follows, among which only $R_1$ and $R'_1$ are $\subseteq$-repairs:

$$R_1 = \{\text{Student}(456, \text{Bea}, \text{Blue}), \text{TakeCourse}(456, \text{CS1}), \text{UndergradCourse}(\text{CS1})\}$$

$$R'_1 = \{\text{Student}(456, \text{Bea}, \text{Blue}), \text{TakeCourse}(456, \text{CS1}), \text{GradCourse}(\text{CS1})\}$$

$$R_2 = \{\text{Student}(123, \text{Ana}, \text{Azure}), \text{TakeCourse}(123, 456), \text{GradCourse}(456), \text{TakeCourse}(456, \text{CS1}), \text{UndergradCourse}(\text{CS1})\}$$

$$R'_2 = \{\text{Student}(123, \text{Ana}, \text{Azure}), \text{TakeCourse}(123, 456), \text{GradCourse}(456), \text{TakeCourse}(456, \text{CS1}), \text{GradCourse}(\text{CS1})\}$$

$$R_3 = \{\text{Student}(123, \text{Ana}, \text{Azure}), \text{TakeCourse}(123, 456), \text{UndergradCourse}(456), \text{TakeCourse}(456, \text{CS1}), \text{UndergradCourse}(\text{CS1})\}$$

$$R'_3 = \{\text{Student}(123, \text{Ana}, \text{Azure}), \text{TakeCourse}(123, 456), \text{UndergradCourse}(456), \text{TakeCourse}(456, \text{CS1}), \text{GradCourse}(\text{CS1})\}$$

$$R_4^c = \{\text{Student}(123, \text{Ana}, \text{Azure}), \text{Student}(456, \text{Bea}, \text{Blue}), \text{TakeCourse}(123, c), \text{GradCourse}(c), \text{TakeCourse}(456, \text{CS1}), \text{UndergradCourse}(\text{CS1})\} \text{ for } c \in \mathbf{C}$$

$$R'_4^c = \{\text{Student}(123, \text{Ana}, \text{Azure}), \text{Student}(456, \text{Bea}, \text{Blue}), \text{TakeCourse}(123, c), \text{GradCourse}(c), \text{TakeCourse}(456, \text{CS1}), \text{GradCourse}(\text{CS1})\} \text{ for } c \in \mathbf{C}$$

$$R_5^c = \{\text{Student}(123, \text{Ana}, \text{Azure}), \text{Student}(456, \text{Bea}, \text{Blue}), \text{TakeCourse}(123, c), \text{UndergradCourse}(c), \text{TakeCourse}(456, \text{CS1}), \text{UndergradCourse}(\text{CS1})\} \text{ for } c \in \mathbf{C}$$

$$R'_5^c = \{\text{Student}(123, \text{Ana}, \text{Azure}), \text{Student}(456, \text{Bea}, \text{Blue}), \text{TakeCourse}(123, c), \text{UndergradCourse}(c), \text{TakeCourse}(456, \text{CS1}), \text{GradCourse}(\text{CS1})\} \text{ for } c \in \mathbf{C}$$

plus for each repair that contains $\text{Student}(123, \text{Ana}, \text{Azure})$, the repair obtained by replacing this fact by $\text{Student}(123, \text{Ann}, \text{Azure})$. Note that there are infinitely many repairs since $c$ can be any constant.

Now recall $\langle D_{\mathcal{DL}}, T_{\mathcal{DL}} \rangle$ from Example 3. The repairs of $D_{\mathcal{DL}}$ w.r.t. $T_{\mathcal{DL}}$ are as follows:

$$R_1 = \mathcal{B} \cup \{\text{Student}(456), \text{UndergradCourse}(\text{CS1})\}$$

$$R_2 = \mathcal{B} \cup \{\text{Student}(456), \text{GradCourse}(\text{CS1})\}$$

$$R_3 = \mathcal{B} \cup \{\text{TakeCourse}(123, 456), \text{UndergradCourse}(\text{CS1})\}$$

$$R_4 = \mathcal{B} \cup \{\text{TakeCourse}(123, 456), \text{GradCourse}(\text{CS1})\}$$

with

$$\mathcal{B} = \{\text{Student}(123), \text{LastName}(123, \text{Azure}), \text{LastName}(456, \text{Blue}), \text{IFA}(123, \text{Ana}), \text{IFA}(123, \text{Ann}), \text{IFA}(456, \text{Bea}), \text{TakeCourse}(456, \text{CS1})\}$$
5:14 Inconsistency-Tolerant Semantics Based on (Preferred) Repairs

Note that if we made the unique name assumption, we would obtain eight repairs {$\mathcal{R}'_i, \mathcal{R}''_i$ | $1 \le i \le 4$} with $\mathcal{R}'_i = \mathcal{R}_i \setminus \{\text{FirstName}(123, Ana)\}$ and $\mathcal{R}''_i = \mathcal{R}_i \setminus \{\text{FirstName}(123, Ann)\}$.

► **Remark 12 (KBs with closed predicates).** KBs with closed predicates, in which some predicates are interpreted under the closed world assumption, have also been studied (e.g., [111, 119, 39]). In this context, it makes sense to consider Δ-repairs also for KBs. However, the investigation of inconsistency handling for such KBs has just started, and focused on ⊑-repairs [116].

3.2 Repair characterization via the conflict hypergraph

If $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$ is a KB or a database with anti-monotone ICs (hence for which $\Delta$-repairs and $\subseteq$-repairs coincide), it is well known that the (subset) repairs of $\mathcal{D}$ w.r.t. $\mathcal{T}$ are the maximal independent sets of the conflict hypergraph whose vertices are the facts in $\mathcal{D}$ and whose hyperedges are the conflicts of $\mathcal{K}$:

► **Definition 13 (Conflicts of a KB or database with anti-monotone constraints).** Let $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$ be a KB or a database with anti-monotone ICs. A conflict of $\mathcal{K}$ is a $\subseteq$-minimal $\mathcal{T}$-inconsistent subset of $\mathcal{D}$. We denote by $\text{Conf}(\mathcal{K})$ or $\text{Conf}(\mathcal{D}, \mathcal{T})$ the set of all conflicts of $\mathcal{K}$.

► **Proposition 14.** Let $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$ be a KB or a database with anti-monotone ICs and $\mathcal{R} \subseteq \mathcal{D}$. Then $\mathcal{R} \in \mathcal{S-Rep}(\mathcal{K})$ iff $\mathcal{R}$ is a maximal independent set of $\mathcal{G} = (\mathcal{D}, \text{Conf}(\mathcal{K}))$.

► **Example 15.** Let $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$ with $\mathcal{D} = \{A(a), B(a), C(a), D(a), E(a)\}$ and

$$ \mathcal{T} = \{A \sqcap B \sqcap C \sqsubseteq \perp, A \sqcap D \sqsubseteq \perp, C \sqcap E \sqsubseteq \perp, D \sqcap E \sqsubseteq \perp\}. $$

The conflict hypergraph $\mathcal{G} = (\mathcal{D}, \text{Conf}(\mathcal{K}))$ is pictured below, and the repairs of $\mathcal{K}$ are its three maximal independent sets.

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

Maximal independent sets of $\mathcal{G}$:

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

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

$$ \mathcal{R}_3 = \{B(a), C(a), D(a)\} $$

For databases with constraints which are not anti-monotone, which may be violated because of the absence of some fact, the notion of conflict hypergraph is less direct. However, for universal constraints (which have no existential quantifier in the head), we can define a conflict hypergraph whose vertices are literals (i.e., facts or negated facts) that express whether a fact belongs to the dataset or not [32]. Conflicts can then be defined as minimal sets of literals that necessarily lead to a constraint violation.

► **Definition 16 (Conflicts of a database with universal constraints).** Let $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$ be a database such that $\mathcal{T}$ is a set of UCs. Let $\text{Facts}_\mathcal{D}^T$ be the union of $\mathcal{D}$ and facts of the form $P(c_1, \dots, c_n)$ where $P$ is a predicate that occurs in $\mathcal{T}$, and $c_1, \dots, c_n$ are constants that occur in $\mathcal{D}$, and let $\text{Lits}_\mathcal{D}^T = \mathcal{D} \cup \{\neg \alpha \mid \alpha \in \text{Facts}_\mathcal{D}^T \setminus \mathcal{D}\}$ be the set of literals of $\mathcal{D}$. A conflict of $\mathcal{K}$ is a $\subseteq$-minimal set $C \subseteq \text{Lits}_\mathcal{D}^T$ such that for every interpretation $\mathcal{I}$, if $\mathcal{I} \models C$, then $\mathcal{I} \not\models \mathcal{T}$.
**► Proposition 17** ([32, Prop. 2]). Let $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$ be a database such that $\mathcal{T}$ is a set of UCs and $\mathcal{R} \subseteq \text{Facts}_{\mathcal{D}}^{\mathcal{T}}$. Let $\text{Int}_{\mathcal{D}}(\mathcal{R}) = (\mathcal{R} \cap \mathcal{D}) \cup \{\neg \alpha \mid \alpha \in \text{Facts}_{\mathcal{D}}^{\mathcal{T}} \setminus (\mathcal{R} \cup \mathcal{D})\}$ be the set of literals upon which $\mathcal{R}$ and $\mathcal{D}$ agree. Then $\mathcal{R} \in \text{S-Rep}_{\Delta}(\mathcal{K})$ iff $\text{Int}_{\mathcal{D}}(\mathcal{R})$ is a maximal independent set of $\mathcal{G} = (\text{Lits}_{\mathcal{D}}^{\mathcal{T}}, \text{Conf}(\mathcal{K}))$. ▶

**► Example 18** ([32]). Let $\mathcal{D} = \{A(a), B(a)\}$ and $\mathcal{T}$ be the following set of UCs:

$$ \mathcal{T} = \{A(x) \to C(x), B(x) \to D(x), C(x) \wedge D(x) \to \bot\} $$

The conflicts, conflict graph (binary conflicts) and $\Delta$-repairs of $\mathcal{D}$ w.r.t. $\mathcal{T}$ are as follows:

$$ \begin{array}{l} \text{Conf}(\mathcal{D}, \mathcal{T}) = \{\{A(a), \neg C(a)\}, \{B(a), \neg D(a)\}, \{A(a), B(a)\}\} \qquad \begin{array}{l} A(a) \dashv \neg C(a) \\ \mid \\ B(a) \dashv \neg D(a) \end{array} \\ \text{S-Rep}_{\Delta}(\mathcal{D}, \mathcal{T}) = \{\emptyset, \{A(a), C(a)\}, \{B(a), D(a)\}\} \end{array} $$

The first (resp. second) conflict directly violates the first (resp. second) IC. To see why $\{A(a), B(a)\}$ is also a conflict, consider any interpretation $\mathcal{I}$ such that $\mathcal{I} \models \{A(a), B(a)\}$. Then if $\mathcal{I} \nvDash C(a)$ or $\mathcal{I} \nvDash D(a)$, $\mathcal{I}$ violates the first or second constraint, respectively, and if $\mathcal{I} \models C(a)$ and $\mathcal{I} \models D(a)$, it violates the third constraint.

We can obtain, e.g., the second repair, $\{A(a), C(a)\}$ by considering the maximal independent set of the conflict hypergraph $\{A(a), \neg D(a)\}$, which gives the literals upon which the repair and $\mathcal{D}$ agree (so implicitly also those on which they disagree: $B(a)$ and $\neg C(a)$, which have to be “flipped” to obtain the repair $\{A(a), C(a)\}$).

### 3.3 Connections with abstract argumentation

A long line of work connects inconsistent KBs and argumentation frameworks, a formalism that aims at representing and reasoning with contradictory information [7, 85, 67, 10]. We present here some very simple reductions from inconsistent KBs or databases to abstract argumentation frameworks, which will also serve as a basis when we discuss the relationships between more involved notions of preferred repair and abstract argumentation in Section 5.

**Background on abstract argumentation.** We start by introducing the basics of abstract argumentation frameworks [76] and their extension with collective attacks [81].

**► Definition 19** (Argumentation framework). An argumentation framework (AF) is a pair $(\text{Args}, \rightsquigarrow)$ where *Args* is a finite set of arguments and $\rightsquigarrow \subseteq \text{Args} \times \text{Args}$ is the attack relation. When $(\alpha, \beta) \in \rightsquigarrow$, we say that $\alpha$ attacks $\beta$, alternatively denoted by $\alpha \rightsquigarrow \beta$.

**► Definition 20** (Set-based argumentation framework). A set-based AF (SETAF) is a pair $(\text{Args}, \rightsquigarrow)$ where *Args* is a finite set of arguments and $\rightsquigarrow \subseteq (2^{\text{Args}} \setminus \{\emptyset\}) \times \text{Args}$ is the attack relation. We say that $S$ attacks $\alpha$, and write $S \rightsquigarrow \alpha$, to mean $(S, \alpha) \in \rightsquigarrow$.

Given an AF $(\text{Args}, \rightsquigarrow)$ and some $A \subseteq \text{Args}$, let $A^+ = \{\beta \mid \alpha \rightsquigarrow \beta$ for some $\alpha \in A\}$ be the set of arguments attacked by arguments from $A$. A set $A \subseteq \text{Args}$ *defends* $\gamma \in \text{Args}$ iff $\{\beta \mid \beta \rightsquigarrow \gamma\} \subseteq A^+$. If $(\text{Args}, \rightsquigarrow)$ is a SETAF, these definitions are adapted as expected: $A^+ = \{\beta \mid S \rightsquigarrow \beta$ for some $S \subseteq A\}$ and $A$ *defends* $\beta$ iff $A^+ \cap S \neq \emptyset$ whenever $S \rightsquigarrow \beta$.

Given a (SET)AF $F = (\text{Args}, \rightsquigarrow)$, a set $A \subseteq \text{Args}$ is conflict-free if $A \cap A^+ = \emptyset$. The characteristic function $\Gamma_F: 2^{\text{Args}} \mapsto 2^{\text{Args}}$ of F is defined as follows: $\Gamma_F(A) = \{\alpha \mid \alpha$ is defended by $A\}$. A set $A \subseteq \text{Args}$ is admissible if it is conflict-free and defends itself: $A \subseteq \Gamma_F(A)$. (SET)AF semantics are based upon sets of arguments called *extensions*.
5:16 Inconsistency-Tolerant Semantics Based on (Preferred) Repairs

► **Definition 21 (Extensions).** Let $F = (Args, ↦)$ be a (SET)AF. Then $E \subseteq Claims$ is a:

■ naive extension iff $E$ is a $\subseteq$-maximal conflict-free subset of $Claims$;

■ preferred extension iff $E$ is a $\subseteq$-maximal admissible set;

■ stable extension iff $E^+ = Claims \setminus E$.

Stable extensions are preferred extensions but the converse does not hold in general [76].

► **Example 22.** The AF depicted below has the following extensions.

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

**From KB and database repairs to (SET)AF extensions.** Let $K = \langle D, T \rangle$ be a KB or a database with anti-monotone ICs and assume that $D$ does not contain any self-conflicting fact (i.e., there is no fact $\alpha \in D$ such that $\langle \{\alpha\}, T \rangle \models \perp$). The SETAF associated to $K$ is $F_K = (D, ↦_K)$, where $ ↦_K = \{ (C \setminus \{\alpha\}, \alpha) \mid C \in Conf(K), \alpha \in C \}$ [30]. This SETAF is strongly symmetric, which implies that preferred and stable extensions coincide [30].

► **Proposition 23 ([30]).** Let $K = \langle D, T \rangle$ be a KB or a database with anti-monotone ICs without self-conflicting facts, $F_K = (D, ↦_K)$ be its associated SETAF and $R \subseteq D$.

■ $R \in S-Rep(K)$ iff $R$ is a naive extension of $F_K$.

■ $R \in S-Rep(K)$ iff $R$ is a preferred extension of $F_K$.

■ $R \in S-Rep(K)$ iff $R$ is a stable extension of $F_K$.

► **Example 24.** Consider $K = \langle D, T \rangle$ defined in Example 15. The SETAF associated to $K$ is $F_K = (\{A(a), B(a), C(a), D(a), E(a)\}, ↦_K)$ where $ ↦_K$ is as follows.

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

Since this reduction relies entirely on the relationship between repairs and conflicts, it is not difficult to extend it to handle the case of Δ-repairs of database with UCs, using literals instead of facts as the set of arguments. We did however not define conflicts for a database whose ICs have existential quantifiers in the head so we cannot easily extend the preceding reduction to such databases. However, there is also a connection between $\subseteq$-repairs of databases with inclusion dependencies (of the form $P(\vec{x}) \rightarrow \exists \vec{y} Q[\vec{x}, \vec{y}]$) and functional dependencies (of the form $P(\vec{x}) \land P(\vec{y}) \land \bigwedge_{i \in I} x_i = y_i \rightarrow \bigwedge_{j \in J} x_j = y_j$) and AF extensions [113]. Let $K = \langle D, T \rangle$ be a database such that $T$ is a set of IDs and FDs. The AF associated to $K$ is $F_K = (Args_K, ↦_K)$, where $Args_K = D \cup \{\alpha_\tau \mid \alpha \in D, \tau \in T, \alpha = P(\vec{c}), \tau = P(\vec{x}) \rightarrow \exists \vec{y} Q[\vec{x}, \vec{y}]\}$ and

$$ \begin{align*} ↦_K &= \{(\alpha, \beta), (\beta, \alpha) \mid \exists \tau \in T, \tau \text{ FD}, \langle\{\alpha, \beta\}, \{\tau\}\rangle \models \perp\} \cup \\ & \quad \{(\alpha_\tau, \alpha), (\alpha_\tau, \alpha_\tau) \mid \alpha_\tau \in \text{Args}_K\} \cup \\ & \quad \{(\beta, \alpha_\tau) \mid \alpha_\tau \in \text{Args}_K, \alpha = P(\vec{c}), \tau = P(\vec{x}) \rightarrow \exists \vec{y} Q[\vec{x}, \vec{y}], \beta \in D, \beta = Q[\vec{c}, \vec{d}]\}. \end{align*} $$

The first line corresponds to the attack relation of the (SET)AF associated to $\langle D, T_{FD} \rangle$, where $T_{FD}$ is the set of FDs in $T$, as defined before, while the second and third lines deal with the IDs: each $\alpha_\tau$ attacks $\alpha \in D$ that requires the presence of some fact to satisfy $\tau$ and is attacked by such facts $\beta$ that are in $D$.
**Proposition 25** ([113]). Let $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$ with $\mathcal{T}$ a set of IDs and FDs, $F_{\mathcal{K}} = (\mathrm{Args}_{\mathcal{K}}, \rightsquigarrow_{\mathcal{K}})$ be its associated AF and $\mathcal{R} \subseteq \mathcal{D}$. Then $\mathcal{R} \in \mathrm{S-Rep}_{\subseteq}(\mathcal{K})$ iff $\mathcal{R}$ is a preferred extension of $F_{\mathcal{K}}$.

Naive, stable and preferred extensions may not coincide in this case, as illustrated below.

**Example 26.** Let $\mathcal{D} = \{\alpha, \beta, \gamma, \delta\}$ with $\alpha = P(c), \beta = P(d), \gamma = Q(d, e)$, and $\delta = Q(d, f)$ and $\mathcal{T}$ consists of the ID $\tau = P(x) \to \exists y Q(x, y)$ and the FD $Q(x, y) \land Q(x, z) \to y = z$. The AF associated with $\mathcal{K}$ is such that $\mathrm{Args}_{\mathcal{K}} = \{\alpha, \beta, \gamma, \delta, \alpha_{\tau}, \beta_{\tau}\}$, and $\rightsquigarrow_{\mathcal{K}}$ is as follows.

$$ \gamma \rightsquigarrow_{\mathcal{K}} \delta \quad \delta \rightsquigarrow_{\mathcal{K}} \gamma \quad \alpha_{\tau} \rightsquigarrow_{\mathcal{K}} \alpha \quad \alpha_{\tau} \rightsquigarrow_{\mathcal{K}} \alpha_{\tau} \quad \beta_{\tau} \rightsquigarrow_{\mathcal{K}} \beta \quad \beta_{\tau} \rightsquigarrow_{\mathcal{K}} \beta_{\tau} \quad \gamma \rightsquigarrow_{\mathcal{K}} \beta_{\tau} \quad \delta \rightsquigarrow_{\mathcal{K}} \beta_{\tau} $$

The naive extensions of $F_{\mathcal{K}} = (\mathrm{Args}_{\mathcal{K}}, \rightsquigarrow_{\mathcal{K}})$ are $\{\alpha, \beta, \gamma\}$ and $\{\alpha, \beta, \delta\}$. Its preferred extensions are $\{\beta, \gamma\}$ and $\{\beta, \delta\}$ (since $\alpha$ is not defended against $\alpha_{\tau}$), which are also the two $\subseteq$-repairs of $\mathcal{K}$. However, there is no stable extension (since for every $E \subseteq \mathrm{Args}_{\mathcal{K}}$, either $\alpha_{\tau} \in E$ so that $\alpha_{\tau} \in E^{+}$ while $\alpha_{\tau} \notin \mathrm{Args}_{\mathcal{K}} \setminus E$, or $\alpha_{\tau} \notin E$ so that $\alpha_{\tau} \notin E^{+}$ while $\alpha_{\tau} \in \mathrm{Args}_{\mathcal{K}} \setminus E$).

**From AF extensions to database repairs.** Interestingly, it was recently shown that in the other direction, every AF can be encoded as an inconsistent database (using IDs and FDs) whose $\subseteq$-repairs correspond to the preferred extensions of the AF [112].

# 4 Inconsistency-tolerant semantics

In this section, we briefly review the inconsistency-tolerant semantics that have been proposed in the literature, with a focus on those based on dataset repairs. For more details and examples, we refer to previous chapter and survey on inconsistency handling in DL KBs [29, 28].

## 4.1 Repair-based semantics

In the following definitions we use the notation $S-Rep(\mathcal{K})$ even when $\mathcal{K}$ is a database with general ICs, meaning that we can choose between $S-Rep_{\Delta}(\mathcal{K})$, $S-Rep_{\subseteq}(\mathcal{K})$ or $S-Rep_{\supseteq}(\mathcal{K})$ when relevant to get three variants of each semantics. The relationships between the semantics and their properties are summarized in Figure 2, and Example 36 illustrates them.

**Consistent query answering (CQA), a.k.a. AR semantics.** The most studied and well-established inconsistency-tolerant semantics, called *consistent query answering (CQA)* in the database community [8, 25] and *AR (ABox Repair)* semantics in the DL community [98, 99], considers that a query answer holds if it holds in every repair. This mode of reasoning is also known as *cautious reasoning*, e.g., in the area of abstract argumentation.

**Definition 27 (CQA semantics).** A tuple $\vec{a}$ is an answer to the query $q(\vec{x})$ over $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$ under the CQA semantics iff $\langle \mathcal{R}, \mathcal{T} \rangle \models q(\vec{a})$ for every $\mathcal{R} \in S-Rep(\mathcal{K})$.

**Under-approximations of CQA.** Several semantics that under-approximate CQA, in the sense that they provide a subset of the consistent query answers, have been considered, either with the goal of achieving a lower computational complexity of reasoning or to obtain answers that are even more “sure” than the consistent query answers. The first one, introduced under the name of *IAR (Intersection of ABox Repairs)* semantics [98, 99] and sometimes called *intersection semantics*, evaluates the queries over the intersection of the repairs.

**Definition 28 (Intersection semantics).** A tuple $\vec{a}$ is an answer to the query $q(\vec{x})$ over $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$ under the intersection semantics iff $\langle \mathcal{R} \cap \mathcal{T}, \mathcal{T} \rangle \models q(\vec{a})$ where $\mathcal{R} \cap \mathcal{T} = \bigcap_{\mathcal{R} \in S-Rep(\mathcal{K})} \mathcal{R}$.
5:18 Inconsistency-Tolerant Semantics Based on (Preferred) Repairs

The ICR (Intersection of Closed Repairs) semantics achieves a finer approximation of CQA than the intersection semantics by logically closing repairs with respect to the ontology before intersecting them [27]. Given a *T*-consistent dataset *B*, the closure of *B* w.r.t. *T*, denoted cl<sub>*T*</sub>(*B*), is the set of all facts entailed by ⟨*B*, *T*⟩.

**Definition 29 (ICR semantics).** A tuple $\vec{a}$ is an answer to the query $q(\vec{x})$ over $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$
under the ICR semantics iff $\langle \mathcal{R}_{\cap}^{cl}, \mathcal{T} \rangle \models q(\vec{a})$ where $\mathcal{R}_{\cap}^{cl} = \bigcap_{\mathcal{R} \in \mathcal{S-Rep}(\mathcal{K})} \mathrm{cl}_{\mathcal{T}}(\mathcal{R})$.

► **Remark 30.** If $\mathcal{K}$ is a database, $\mathrm{cl}_{\mathcal{T}}(\mathcal{B}) = \mathcal{B}$ so the ICR and intersection semantics coincide.

The family of *k*-support semantics was introduced to generalize the intersection semantics and obtain more fine-grained under-approximations of CQA, such that increasing the value of *k* yields a closer approximation [41]. A *support* of a Boolean query *q* in $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$ is a *T*-consistent subset $\mathcal{S} \subseteq \mathcal{D}$ such that $\langle \mathcal{S}, \mathcal{T} \rangle \models q$.

**Definition 31 (k-support semantics).** A tuple $\vec{a}$ is an answer to the query $q(\vec{x})$ over $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$ under the k-support semantics iff there exist $k$ (not necessarily distinct) supports $S_1, \dots, S_k$ of $q(\vec{a})$ in $\mathcal{K}$ such that for every $\mathcal{R} \in \mathcal{S-Rep}(\mathcal{K})$, there is some $S_i \subseteq \mathcal{R}$.

**Over-approximations of CQA.** Instead of approximating CQA from below, we can over-approximate it, by computing a super-set of the consistent query answers. The *brave* semantics considers all answers that hold in some repair [41].

**Definition 32 (Brave semantics).** A tuple $\vec{a}$ is an answer to the query $q(\vec{x})$ over $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$
under the brave semantics iff $\langle \mathcal{R}, \mathcal{T} \rangle \models q(\vec{a})$ for some $\mathcal{R} \in \mathcal{S-Rep}(\mathcal{K})$.

The *non-objection* semantics refines the brave semantics by retaining only the brave query answers that are consistent with all repairs [23].

**Definition 33 (Non-objection semantics).** A tuple $\vec{a}$ is an answer to the query $q(\vec{x})$ over $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$ under the non-objection semantics iff (i) $\langle \mathcal{R}, \mathcal{T} \rangle \models q(\vec{a})$ for some $\mathcal{R} \in \mathcal{S-Rep}(\mathcal{K})$ and (ii) for every $\mathcal{R}' \in \mathcal{S-Rep}(\mathcal{K})$, there is a model $\mathcal{I}$ of $\langle \mathcal{R}', \mathcal{T} \rangle$ such that $\mathcal{I} \models q(\vec{a})$.

The majority-based semantics is another refinement of brave that requires that the answer
holds in more than half of the repairs [19]. This semantics can be adapted to use any
threshold instead of $\frac{1}{2}$ and is closely related to the semantics that associates to each brave
query answer the percentage (or number) of repairs in which it holds, which attracted quite
a lot of attention in the database setting, with theoretical results on the precise complexity
of the counting problem depending on the classes of constraints and queries [118, 48, 52] as
well as approximation schemes [49].

**Definition 34 (Majority-based semantics).** A tuple $\vec{a}$ is an answer to the query $q(\vec{x})$ over $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$ under the majority-based semantics iff $\frac{|\mathcal{R}|\mathcal{R} \in \mathcal{S-Rep}(\mathcal{K}), \langle \mathcal{R}, \mathcal{T} \rangle = q(\vec{a})|}{|\mathcal{S-Rep}(\mathcal{K})|} > \frac{1}{2}$.

Finally, the family of *k-defeater* semantics provides fine-grained over-approximations of CQA, where increasing the value of *k* yields a closer approximation [41] (note that even if the following definition does not mention a repair, the set *B* is a subset of a repair that does not entail the query, so we consider this semantics as “repair-based”).

**Definition 35 (k-defeater semantics).** A tuple $\vec{a}$ is an answer to the query $q(\vec{x})$ over $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$ under the k-defeater semantics iff there does not exist a T-consistent subset $\mathcal{B}$ of $\mathcal{D}$ with $|\mathcal{B}| \le k$ such that $\langle \mathcal{B} \cup \mathcal{S}, \mathcal{T} \rangle \models \perp$ for every minimal support $\mathcal{S}$ of $q(\vec{a})$ in $\mathcal{K}$.
<figure><img src="image_11.png" /></figure>

<table><thead><tr><th></th><th>Semantics with the property</th></tr></thead><tbody><tr><td>CONSISTENT SUPPORT</td><td>all</td></tr><tr><td>CONSISTENT RESULTS</td><td>intersection, ICR, k-support, CQA, non-objection</td></tr><tr><td>UNIQUE BASE</td><td>intersection, ICR</td></tr></tbody></table>

- CONSISTENT SUPPORT: for every $\langle D, T \rangle$, $q(\vec{x})$ and $\vec{a}$, if $\vec{a}$ is an answer to $q(\vec{x})$ over $\langle D, T \rangle$ under Sem, then there exists a $T$-consistent subset $S$ of $D$ such that $\langle S, T \rangle \models q(\vec{a})$.

- CONSISTENT RESULTS: for every $\langle D, T \rangle$, there exists a model $\mathcal{I}$ of $T$ such that for every $q(\vec{x})$ and $\vec{a}$, if $\vec{a}$ is an answer to $q(\vec{x})$ over $\langle D, T \rangle$ under Sem, then $\mathcal{I} \models q(\vec{a})$.

- UNIQUE BASE: for every $\langle D, T \rangle$, there exists a $T$-consistent dataset $D'$ such that for every $q(\vec{x})$ and $\vec{a}$, $\vec{a}$ is an answer to $q(\vec{x})$ over $\langle D, T \rangle$ under Sem iff $\langle D', T \rangle \models q(\vec{a})$.

■ **Figure 2** (left) Relationships between repair-based semantics (adapted from [28, Fig. 1]). An arrow Sem $\rightarrow$ Sem' means that if $\vec{a}$ is an answer to $q(\vec{x})$ over $\mathcal{K}$ under Sem, then it is also an answer under Sem'. (right) Properties of repair-based semantics (adapted from [28, Fig. 2]).

**Properties and relationships between repair-based semantics.** Figure 2 (left) shows the relationships between the repair-based inconsistency-tolerant semantics. Following [29, 28], we also recall in Figure 2 (right) which desirable properties these semantics have (note that all repair-based semantics have the CONSISTENT SUPPORT property, contrary to some non repair-based inconsistency-tolerant semantics, cf. Section 4.2). We conclude with an example to illustrate the differences between these semantics.

► **Example 36.** Consider the following DL-Lite<sub>core</sub> KB. The ontology expresses that associate and full professors are professors, professors and postdoctoral fellows are PhD holders and belong to some department, postdoctoral fellows have some supervisor, that one cannot be both an associate and a full professor or a postdoctoral fellow and a professor, and that the range of the roles Chair and Teach are disjoint.

$$ T = \{\text{AssociateProf} \sqsubseteq \text{Prof}, \text{FullProf} \sqsubseteq \text{Prof}, \text{Prof} \sqsubseteq \text{Phd}, \text{Postdoc} \sqsubseteq \text{Phd}, \\ \text{Prof} \sqsubseteq \exists \text{Department}, \text{Postoc} \sqsubseteq \exists \text{Department}, \text{Postdoc} \sqsubseteq \exists \text{Supervisor}, \\ \text{AssociateProf} \sqsubseteq \neg \text{FullProf}, \text{Postdoc} \sqsubseteq \neg \text{Prof}, \exists \text{Chair} \sqsubseteq \neg \exists \text{Teach} \} $$

$$ D = \{\text{AssociateProf}(\mathit{Carol}), \text{FullProf}(\mathit{Carol}), \text{Postdoc}(\mathit{Carol}), \\ \text{Teach}(\mathit{Carol}, \mathit{Algo}), \text{Teach}(\mathit{Carol}, \mathit{DB}), \text{Teach}(\mathit{Carol}, \mathit{KR}), \\ \text{Chair}(\mathit{Carol}, \mathit{DB}), \text{Chair}(\mathit{Carol}, \mathit{KR})\} $$

The repairs of $\langle D, T \rangle$ are as follows:

$$ \mathcal{R}_1 = \{\text{AssociateProf}(\mathit{Carol}), \text{Teach}(\mathit{Carol}, \mathit{Algo}), \text{Teach}(\mathit{Carol}, \mathit{DB}), \text{Teach}(\mathit{Carol}, \mathit{KR})\} $$

$$ \mathcal{R}_2 = \{\text{AssociateProf}(\mathit{Carol}), \text{Teach}(\mathit{Carol}, \mathit{Algo}), \text{Chair}(\mathit{Carol}, \mathit{DB}), \text{Chair}(\mathit{Carol}, \mathit{KR})\} $$

$$ \mathcal{R}_3 = \{\text{AssociateProf}(\mathit{Carol}), \text{Teach}(\mathit{Carol}, \mathit{Algo}), \text{Teach}(\mathit{Carol}, \mathit{DB}), \text{Chair}(\mathit{Carol}, \mathit{KR})\} $$
5:20 Inconsistency-Tolerant Semantics Based on (Preferred) Repairs

$$
\mathcal{R}_4 = \{\text{AssociateProf}(\mathcal{Carol}), \text{Teach}(\mathcal{Carol}, \text{Algo}), \text{Teach}(\mathcal{Carol}, \text{KR}), \text{Chair}(\mathcal{Carol}, \text{DB})\}
$$

$$
\mathcal{R}_5 = \{\text{FullProf}(\mathcal{Carol}), \text{Teach}(\mathcal{Carol}, \text{Algo}), \text{Teach}(\mathcal{Carol}, \text{DB}), \text{Teach}(\mathcal{Carol}, \text{KR})\}
$$

$$
\mathcal{R}_6 = \{\text{FullProf}(\mathcal{Carol}), \text{Teach}(\mathcal{Carol}, \text{Algo}), \text{Chair}(\mathcal{Carol}, \text{DB}), \text{Chair}(\mathcal{Carol}, \text{KR})\}
$$

$$
\mathcal{R}_7 = \{\text{FullProf}(\mathcal{Carol}), \text{Teach}(\mathcal{Carol}, \text{Algo}), \text{Teach}(\mathcal{Carol}, \text{DB}), \text{Chair}(\mathcal{Carol}, \text{KR})\}
$$

$$
\mathcal{R}_8 = \{\text{FullProf}(\mathcal{Carol}), \text{Teach}(\mathcal{Carol}, \text{Algo}), \text{Teach}(\mathcal{Carol}, \text{KR}), \text{Chair}(\mathcal{Carol}, \text{DB})\}
$$

$$
\mathcal{R}_9 = \{\text{Postdoc}(\mathcal{Carol}), \text{Teach}(\mathcal{Carol}, \text{Algo}), \text{Teach}(\mathcal{Carol}, \text{DB}), \text{Teach}(\mathcal{Carol}, \text{KR})\}
$$

$$
\mathcal{R}_{10} = \{\text{Postdoc}(\mathcal{Carol}), \text{Teach}(\mathcal{Carol}, \text{Algo}), \text{Chair}(\mathcal{Carol}, \text{DB}), \text{Chair}(\mathcal{Carol}, \text{KR})\}
$$

$$
\mathcal{R}_{11} = \{\text{Postdoc}(\mathcal{Carol}), \text{Teach}(\mathcal{Carol}, \text{Algo}), \text{Teach}(\mathcal{Carol}, \text{DB}), \text{Chair}(\mathcal{Carol}, \text{KR})\}
$$

$$
\mathcal{R}_{12} = \{\text{Postdoc}(\mathcal{Carol}), \text{Teach}(\mathcal{Carol}, \text{Algo}), \text{Teach}(\mathcal{Carol}, \text{KR}), \text{Chair}(\mathcal{Carol}, \text{DB})\}
$$

The KB $\langle \mathcal{D}, \mathcal{T} \rangle$ entails the BCQ:

- Teach(*Carol*, *Algo*) under the intersection semantics, since $\bigcap_{i=1}^{12} \mathcal{R}_i$ = 
  {Teach(*Carol*, *Algo*)};

- Phd(*Carol*) under

- the ICR semantics, since $\bigcap_{i=1}^{12} cl_T(\mathcal{R}_i) = \{\text{Teach}(\mathcal{Carol}, \text{Algo}), \text{Phd}(\mathcal{Carol})\}$,

- the 3-support semantics, since the three supports {$\text{AssociateProf}(\mathcal{Carol})$}, 
  {$\text{FullProf}(\mathcal{Carol})$} and {$\text{Postdoc}(\mathcal{Carol})$} cover all repairs,
  but not under the intersection semantics nor under the 2-support semantics;

- ∃yDepartment(*Carol*, y) under the CQA semantics, since it is entailed by every repair,
  but not under the ICR semantics;

- Prof(*Carol*) under the majority semantics (it holds in $\frac{2}{3}$ of the repairs), but not under

- the CQA semantics, since it does not hold in $\mathcal{R}_9 - \mathcal{R}_{12}$,

- the non-objection semantics, since for $i \in \{9, 12\}$, $\langle \mathcal{R}_i \cup \{\text{Prof}(\mathcal{Carol})\}, \mathcal{T} \rangle \models \perp$,

- the 1-defeater semantics, since one fact (*Postdoc*(Carol)) is sufficient to contradict the
  two minimal supports of *Prof*(Carol) ({*AssociateProf*(Carol)} and {*FullProf*(Carol)});

- ∃ySupervisor(*Carol*, y) under the non-objection semantics since it holds in repairs $\mathcal{R}_9 - \mathcal{R}_{12}$
  and is consistent with all repairs, but not under

- the CQA semantics, since it does not hold in $\mathcal{R}_1 - \mathcal{R}_8$,

- the majority semantics, since it holds only in $\frac{1}{3}$ of the repairs,

- the 1-defeater semantics, since one fact (e.g., FullProf(*Carol*)) is sufficient to contradict
  the only minimal support of ∃ySupervisor(*Carol*, y) ({Postdoc(*Carol*)});

- ∃yChair(*Carol*, y) under the 1-defeater semantics, since we need two facts
  (Teach(*Carol*, DB) and Teach(*Carol*, KR)) to contradict the minimal supports
  {*Chair*(*Carol*, *DB*)} and {*Chair*(*Carol*, *KR*)}, but not under the CQA semantics (cf. $\mathcal{R}_1$,
  $\mathcal{R}_5$ and $\mathcal{R}_9$);

- AssociateProf(*Carol*) under the brave semantics but not under the non-objection, majority
  or 1-defeater semantics.

4.2 Related work: Semantics that are not based on dataset repairs

Not all inconsistency-tolerant semantics that have been proposed for KBs or databases are
based on dataset repairs. We review them only briefly since they are not the main focus of
this chapter and received comparatively less attention than the main repair-based semantics.
**T**-consistent subsets of some closure of *D*. In the KB context, several semantics based on repairs of some closure of the original dataset w.r.t. the ontology were proposed, with the motivation of retaining more consequences and being independent from the KB syntax. The first ones, called the *CAR (Closed ABox Repair)* and *ICAR (Intersection of Closed ABox Repairs)* semantics, are the counterparts of the *AR (CQA)* and *IAR (intersection)* semantics that use closed repairs defined below instead of dataset repairs [98]. The *consistent closure* of *D* w.r.t. *T*, denoted **conscl**<sub>*T*</sub>(*D*), is the set of facts entailed by *T*-consistent subsets of *D*.

**► Definition 37 (Closed repairs).** A closed repair of $\langle D, T \rangle$ is a $T$-consistent $R' \subseteq \text{conscl}_T(D)$ for which there is no $T$-consistent $R' \subseteq \text{conscl}_T(D)$ such that either (i) $R \cap D \subseteq R' \cap D$ or (ii) $R \cap D = R' \cap D$ and $R \supseteq R'$.

The closed repairs of $\langle D, T \rangle$ may differ from the (dataset) repairs of $\text{conscl}_T(D)$ (see [29, Example 13] for an example) so we get different semantics by using the latter. Another notion of closure of the original dataset was proposed in the context of Datalog<sup>±</sup> KBs: the *positive closure* of *D* w.r.t. *T*, denoted $\text{poscl}_T(D)$, is the set of facts entailed by $\langle D, T^+ \rangle$ where $T^+$ is the set of TGDs in *T* [19]. This yields yet another family of semantics based on the repairs of $\text{poscl}_T(D)$. However, it is not clear how to define positive closure for expressive DLs such as *ALC* and *SHIQ*, since they cannot be written as Datalog<sup>±</sup> rules.

Note that in contrast with the repair-based semantics, these semantics do not satisfy the CONSISTENT SUPPORT property (cf. [29, Example 15]).

**T**-consistent quantified datasets. A long line of work in DL is concerned by modifying a (consistent) KB so that some unwanted consequences do not hold anymore, while preserving as much as possible the other consequences. Some recent work targets in particular dataset modifications, using *quantified ABoxes*, which allow variables to be used in facts [16, 15]. By identifying sets of atoms with their conjunctions, we can view such a quantified ABox *D* as a BCQ $\exists \vec{y} D$ where $\exists \vec{y}$ contains all variables in *D*. The extension of this framework to *inconsistent* KBs gives rise to an alternative notion of syntax-independent, consequence-preserving, repairs [17, 18]. These repairs have been defined for *Horn-DL ontologies*, which are such that *T* can be split into a “positive part” $T^+$, which is such that any dataset is $T^+$-consistent, and a “negative part” $T^\perp$ which contains only concept inclusions of the form $C \sqsubseteq \perp$. Intuitively, a repair of a dataset *D* w.r.t. an ontology *T* is a quantified ABox $\exists \vec{y} R$ such that $\langle D, T^+ \rangle \models \exists \vec{y} R$, $\langle \exists \vec{y} R, T^+ \rangle \nvDash \exists x C(x)$ for every $C \sqsubseteq \perp \in T^\perp$ (and $\langle \exists \vec{y} R, T^+ \rangle \nvDash q$ for other unwanted consequences *q*, if any). An optimal consequence-preserving repair is then a repair $\exists \vec{y} R$ such that there is no repair $\exists \vec{z} R'$ such that $\langle \exists \vec{z} R', T^+ \rangle \models \exists \vec{y} R$ but $\langle \exists \vec{y} R, T^+ \rangle \nvDash \exists \vec{z} R'$. We omit the formal definitions and details on this framework and simply illustrate how it can be applied in our context.

**► Example 38.** Let $\langle D, T \rangle$ be as follows. $T^+$ contains the two first axioms, $T^\perp$ the last one.

$$ 
\begin{aligned}
T &= \{\exists \text{Teach} \sqsubseteq \text{Person}, \exists \text{Teach}^- \sqsubseteq \text{Course}, \text{Person} \sqcap \text{Course} \sqsubseteq \perp\} \\
D &= \{\text{Teach}(\text{Dan}, \text{DB}), \text{Teach}(\text{Dan}, \text{KR}), \text{Teach}(\text{Algo}, \text{Dan})\}
\end{aligned}
$$

It holds that the quantified ABoxes $\exists x \{\text{Teach}(\text{Dan}, \text{DB}), \text{Teach}(\text{Dan}, \text{KR}), \text{Teach}(\text{Algo}, x)\}$ and $\exists x \{\text{Teach}(x, \text{DB}), \text{Teach}(x, \text{KR}), \text{Teach}(\text{Algo}, \text{Dan})\}$ are optimal consequence-preserving repairs of *D* w.r.t. *T*, as well as all those obtained by adding some consequences w.r.t. $T^+$, such as $\exists x \{\text{Teach}(\text{Dan}, \text{DB}), \text{Teach}(\text{Dan}, \text{KR}), \text{Teach}(\text{Algo}, x), \text{Person}(\text{Dan}), \text{Course}(\text{DB})\}$. Indeed, two equivalent (quantified) datasets are both optimal repairs or not. Using such repairs allows us to keep the information that *KR* and *DB* courses are taught by the same person, so
that $∃xTeach(x, DB) ∧ Teach(x, KR)$ is entailed under the CQA semantics based on this kind of repair. We also obtain that $∃xyTeach(x, KR) ∧ Teach(Algo, y)$ holds under CQA based on such repairs, which shows that the CONSISTENT SUPPORT property is not satisfied.

**T-consistent subsets of D that may not besubseteq-maximal.** Some semantics relax the notion of repairs by allowing “too many” facts to be removed to restore consistency. Motivated by computational complexity considerations, the family of *k*-lazy semantics restores consistency in each connected component of the conflict hypergraph by either removing at most *k* facts, or by removing the whole connected component if removing *k* facts is not sufficient to achieve consistency [109]. To get a database counterpart of conflict-free sets of arguments considered in the context of abstract argumentation, a recent work defines “repairs” as *T*-consistent subsets of *D*, calling “maximal repairs” the standardsubseteq-repairs [112]. This very relaxed notion of repairs is the basis of the definition of *maximally covering* (resp. *fully covering*) repairs which are *T*-consistent subsets of *D* that retain as much as possible (resp. all) the constants occurring in *D* at some predicate positions.

**Repairs modifying T.** While most inconsistency-tolerant semantics consider that the logical theory is reliable and repair only the dataset, *generalized repairs* allow to modify *T* as well as *D* to restore consistency [78]. The definition also allows for splitting *T* and *D* into a hard and a soft part, so that only the soft parts can be modified by a repair.

**Attribute-based repairs.** In the database area, *attribute-based repairs*, which modify the tuples instead of removing them, have been proposed. Many different kinds of attribute-based repairs have been considered: the attribute values can be taken from a database-independent domain, the database domain, or be “nulls” with a specific semantics, and minimality of change can be measured by a numerical aggregation function over differences of attribute values, or set-minimality of the sequence of updates yielding the repair [43, 102, 88, 26].

**Operational repairs.** Also in the database area, *operational repairs* have been defined as the result of applying a repairing sequence of update operations that has to fulfill some conditions [51, 53]. This kind of repair also allows for taking into account the probability of the updates, hence of the repairs and query answers.

## 5 Preferred repairs

In many scenarios, one can define preferred repairs based on some preference information, such as the relative or absolute reliability of the facts, or some rules modeling the user preferences. In this section, we present the different kinds of preferred (dataset) repair that have been proposed in the literature, their properties, relationships and links with other formalisms for inconsistency handling. Preferred repairs have mostly been defined forsubseteq-repairs, since it is less natural to consider, e.g., the reliability of some missing facts, but we also consider preferred *Δ*-repairs when they have been studied. As in Section 4, we conclude with a brief overview of other notions of “optimal repairs” which are not dataset repairs.

Before delving into the specific preferred repair definitions, we start with two general observations on the impact of using preferred (dataset) repairs on repair-based semantics: (1) it increases the number of query answers under CQA and intersection semantics while it decreases the number of answers under brave semantics, and (2) it preserves the relationships between the semantics presented in Figure 2.
**Proposition 39.** Let X-CQA, X-intersection and X-brave be the counterparts of the CQA, intersection and brave semantics that use preferred repairs from some X-Rep($K$) $\subseteq S$-Rep($K$) instead of standard ($\subseteq$- or $\Delta$-)repairs. If $q$ is entailed by $K$ under:

- CQA (resp. intersection), then it is also entailed under X-CQA (resp. X-intersection);

- X-brave, then it is also entailed under brave.

Moreover, if $q$ is entailed by $K$ under:

- X-intersection, then it is entailed under X-CQA;

- X-CQA, then it is entailed under X-brave.

## 5.1 Preferred repairs based on a preorder over datasets ($\leq, \leq_w, \subseteq_P, \leq_P$)

The first category of preferred repairs is based on a generalization of the definition of dataset repairs (cf. Definition 10) using a preorder (i.e., a reflexive and transitive binary relation) $\preceq$ over datasets instead of set-inclusion. We write $B \prec B'$ to indicate that $B \preceq B'$ and $B' \nsim B$.

**Definition 40** (Strictly $\subseteq$-monotone preorder). A preorder $\preceq$ over datasets is strictly $\subseteq$-monotone iff $B \subset B'$ implies $B \prec B'$.

**Definition 41** ($\preceq$-optimal repairs). Let $\preceq$ be a strictly $\subseteq$-monotone preorder over datasets.

- A $\preceq$-optimal $\subseteq$-repair of $D$ w.r.t. $T$ is a $T$-consistent dataset $R \subseteq D$ such that there is no $T$-consistent $R' \subseteq D$ such that $R \prec R'$.

- A $\preceq$-optimal $\Delta$-repair of $D$ w.r.t. $T$ is a $T$-consistent dataset $R$ such that there is no $T$-consistent $R'$ such that $R'\Delta D \prec R\Delta D$.

We write $\preceq$-Rep($K$) (resp. $\preceq$-Rep$_{\subseteq}$(K), $\preceq$-Rep$_{\Delta}$(K)) to denote the set of $\preceq$-optimal (resp. $\subseteq$-, $\Delta$-) repairs of $K$.

**Remark 42.** The condition that $\preceq$ is strictly $\subseteq$-monotone implies that $\preceq$-optimal $\subseteq$-repairs are indeed $\subseteq$-repairs, and $\preceq$-optimal $\Delta$-repairs are $\Delta$-repairs (i.e., $\preceq$-Rep$_{\subseteq}$(K) $\subseteq S$-Rep$_{\subseteq}$(K) and $\preceq$-Rep$_{\Delta}$(K) $\subseteq S$-Rep$_{\Delta}$(K)). Hence Proposition 39 applies.

We next introduce the four types of $\preceq$-optimal repairs that received the most attention. Their properties and relationships as well as examples are given at the end of this section.

**Cardinality ($\leq$).** Cardinality-based repairs use the preorder $\leq$ that compares datasets based on their cardinality:

$$B \preceq B' \text{ iff } |B| \leq |B'|.$$

The $\preceq$-optimal $\Delta$-repairs are those that make the fewest updates. In particular, $\preceq$-optimal $\subseteq$-repairs drop the fewest facts, and are thus more appropriate when it is believed that all the facts in the dataset have the same (small) probability of being erroneous. Cardinality-based repairs have been studied for DL and Datalog$^{\pm}$ KBs [33, 108] as well as for both $\Delta$-repairs and $\subseteq$-repairs in the database setting [9, 102, 4, 74].

**Weight ($\leq_w$).** Weight-based repairs require a function $w$ that assigns a (positive) weight to each fact and induces a preorder $\leq_w$ over datasets:

$$B \leq_w B' \text{ iff } \Sigma_{\alpha \in B} w(\alpha) \leq \Sigma_{\alpha \in B'} w(\alpha).$$

Weights can be used to model the reliability of different facts in $D$ (e.g., if it is built using information extraction techniques, the weights may be derived from the confidence levels output by the extraction tool). In the case of $\Delta$-repairs, one needs to assign a weight to all
possible facts (since $\leq_w$-optimal $\Delta$-repairs minimize the weight of the symmetric difference between $\mathcal{D}$ and the repair). This can be done, e.g., by assigning the same weight to all facts that do not belong to $\mathcal{D}$, to penalize every addition in the same way while taking into account different reliability levels for facts from $\mathcal{D}$. This kind of repair has been studied for DL and Datalog$^{\pm}$ KBs [73, 33, 107] and for databases [102, 100, 122].

**Prioritized set inclusion ($\subseteq_P$).** Repairs based on priority levels and set-inclusion require that the dataset $\mathcal{D}$ is partitioned into priority levels: a prioritization of $\mathcal{D}$ is a tuple $P = \langle \mathcal{P}_1, \dots, \mathcal{P}_n \rangle$ of disjoint datasets such that $\mathcal{D} = \bigcup_{i=1}^n \mathcal{P}_i$. Facts in $\mathcal{P}_1$ are considered the most reliable and those in $\mathcal{P}_n$ the least reliable. A prioritization $P = \langle \mathcal{P}_1, \dots, \mathcal{P}_n \rangle$ induces a set-inclusion-based preorder $\subseteq_P$:

$$ \mathcal{B} \subseteq_P \mathcal{B}' \text{ iff either } \mathcal{B} \cap \mathcal{P}_i = \mathcal{B}' \cap \mathcal{P}_i \text{ for every } 1 \le i \le n, \\ \text{or there is some } 1 \le i \le n \text{ such that} \\ \mathcal{B} \cap \mathcal{P}_i \subseteq \mathcal{B}' \cap \mathcal{P}_i \text{ and } \mathcal{B} \cap \mathcal{P}_j = \mathcal{B}' \cap \mathcal{P}_j \text{ for } 1 \le j < i. $$

Prioritizations are a natural way to distinguish facts coming from different sources, separate a part of the dataset that has already been validated from recent additions, or to take into account that some predicates are known to be more reliable than others. $\subseteq_P$-optimal repairs have been mostly studied for DL and Datalog$^{\pm}$ KBs [33, 107] but also extended to $\Delta$-repairs of databases with universal constraints [32]. In this case, we consider a prioritization $P = \langle \mathcal{P}_1, \dots, \mathcal{P}_n \rangle$ of the set of relevant literals $\mathit{Lits}_\mathcal{D}^T$ (cf. Definition 16) so that we keep the intuition that the more reliable a literal $\lambda$ (which expresses whether a fact is true or false w.r.t. $\mathcal{D}$), the smaller the index of $\mathcal{P}_i$ that contains $\lambda$. We then simply drop the negation in literals to get the corresponding prioritization of all relevant facts $\mathit{Facts}_\mathcal{D}^T$, $P' = \langle \mathcal{P}'_1, \dots, \mathcal{P}'_n \rangle$ with $\mathcal{P}'_i = (\mathcal{P}_i \cap \mathcal{D}) \cup \{\alpha \mid \neg \alpha \in \mathcal{P}_i\}$, and use $P'$ instead of $P$ in the definition of $\subseteq_P$ (additionally setting $\mathcal{B} \subseteq_P \mathcal{B}'$ for every $\mathcal{B} \subseteq \mathit{Facts}_\mathcal{D}^T$ and $\mathcal{B}' \not\subseteq \mathit{Facts}_\mathcal{D}^T$). We can show that the definition of $\subseteq_P$-optimal $\Delta$-repairs given in [32] is indeed equivalent to that of Definition 41 using this preorder by observing that for all $\mathcal{R}, \mathcal{R}' \subseteq \mathit{Facts}_\mathcal{D}^T$, $\mathcal{R}'\Delta\mathcal{D} \subseteq_P \mathcal{R}\Delta\mathcal{D}$ iff there is some $1 \le i \le n$ such that

- $\mathit{Int}_\mathcal{D}(\mathcal{R}) \cap \mathcal{P}_i \subseteq \mathit{Int}_\mathcal{D}(\mathcal{R}') \cap \mathcal{P}_i$ (recall from Proposition 17 that $\mathit{Int}_\mathcal{D}(\mathcal{B}) = (\mathcal{B} \cap \mathcal{D}) \cup \{\neg \alpha \mid \alpha \in \mathit{Facts}_\mathcal{D}^T \setminus (\mathcal{B} \cup \mathcal{D})\}$ is the set of literals upon which $\mathcal{B}$ and $\mathcal{D}$ agree) and

- $\mathit{Int}_\mathcal{D}(\mathcal{R}) \cap \mathcal{P}_j = \mathit{Int}_\mathcal{D}(\mathcal{R}') \cap \mathcal{P}_j$ for $1 \le j < i$.

**Prioritized cardinality ($\leq_P$).** A prioritization $P = \langle \mathcal{P}_1, \dots, \mathcal{P}_n \rangle$ also induces a cardinality-based preorder $\leq_P$:

$$ \mathcal{B} \leq_P \mathcal{B}' \text{ iff either } |\mathcal{B} \cap \mathcal{P}_i| = |\mathcal{B}' \cap \mathcal{P}_i| \text{ for every } 1 \le i \le n, \\ \text{or there is some } 1 \le i \le n \text{ such that} \\ |\mathcal{B} \cap \mathcal{P}_i| < |\mathcal{B}' \cap \mathcal{P}_i| \text{ and } |\mathcal{B} \cap \mathcal{P}_j| = |\mathcal{B}' \cap \mathcal{P}_j| \text{ for } 1 \le j < i. $$

$\leq_P$-optimal repairs have been studied for DL and Datalog$^{\pm}$ KBs [33, 107] but we can extend their definition to $\Delta$-repairs of databases with universal constraints in the same way as for $\subseteq_P$-optimal repairs. Note that with $\leq_P$ and $\subseteq_P$, a single fact on level $\mathcal{P}_i$ is preferred to any number of facts from $\mathcal{P}_{i+1}$. This makes these preorders best suited for cases in which there is a significant difference in the perceived reliability of adjacent priority levels.

**Properties and relationships.** In this paragraph, we use $\leq_-\mathit{Rep}(\mathcal{K})$ ($\leq \in \{\leq, \leq_w, \subseteq_P, \leq_P\}$) and $\mathit{S-Rep}(\mathcal{K})$ to denote the ($\leq$-optimal) $\subseteq$- or $\Delta$-repairs of a KB or database $\mathcal{K}$.
■ If w assigns the same weight to every fact, then $\le_w$-Rep($\mathcal{K}$) and $\le$-Rep($\mathcal{K}$) coincide, i.e., weight-based repairs generalize cardinality-based repairs.

■ Given a prioritization $P = \langle \mathcal{P}_1, \dots, \mathcal{P}_n \rangle$, let $u = (\max_{i=1}^n |\mathcal{P}_i|) + 1$, and let $w$ be defined by $w(\alpha) = u^{n-i}$ for $\alpha \in \mathcal{P}_i$ (or in case of $\Delta$-repairs, $w(\alpha) = u^{n-i}$ for $\alpha \in \mathcal{P}_i$ or $\neg \alpha \in \mathcal{P}_i$). Then for every $\mathcal{T}$, $\le_P$-Rep($\mathcal{T}$, $\mathcal{T}$) and $\le_w$-Rep($\mathcal{T}$, $\mathcal{T}$) coincide [44, Lemma 6.2.5]. Hence weight-based repairs also generalize repairs based on prioritized cardinality.

■ If a prioritization assigns all facts (or literals) to the same priority level, then $\subseteq_P$-Rep($\mathcal{K}$) and $\subseteq$-Rep($\mathcal{K}$) coincide, and $\le_P$-Rep($\mathcal{K}$) and $\le$-Rep($\mathcal{K}$) coincide.

**Examples.** Examples 43 and 44 illustrate the four kinds of $\le$-optimal repair, for KBs and $\Delta$-repairs of databases with UCs, respectively.

► **Example 43** ([44]). Consider the DL-Lite<sub>core</sub> KB $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$ defined as follows.

$$ \mathcal{T} = \{ \text{Student} \sqsubseteq \text{Person}, \text{Prof} \sqsubseteq \text{Person}, \text{Student} \sqsubseteq \neg \text{Prof}, \\ \phantom{\mathcal{T} = \{ } \exists \text{Teach} \sqsubseteq \text{Prof}, \exists \text{Teach} \neg \sqsubseteq \text{Course}, \text{Course} \sqsubseteq \neg \text{Person} \} $$

$$ \mathcal{D} = \{ \text{Student}(Ann), \text{Teach}(Ann, DB), \text{Teach}(Ann, KR), \\ \phantom{\mathcal{D} = \{ } \text{Student}(Bob), \text{Prof}(Bob), \text{Teach}(KR, Bob), \text{Teach}(Bob, Algo) \} $$

The set of repairs $\mathcal{S}$-$\text{Rep}(\mathcal{K})$ contains:

$$ \mathcal{R}_1 = \{ \text{Student}(Ann), \text{Student}(Bob) \} $$

$$ \mathcal{R}_2 = \{ \text{Teach}(Ann, DB), \text{Teach}(Ann, KR), \text{Student}(Bob) \} $$

$$ \mathcal{R}_3 = \{ \text{Student}(Ann), \text{Prof}(Bob), \text{Teach}(Bob, Algo) \} $$

$$ \mathcal{R}_4 = \{ \text{Teach}(Ann, DB), \text{Teach}(Ann, KR), \text{Prof}(Bob), \text{Teach}(Bob, Algo) \} $$

$$ \mathcal{R}_5 = \{ \text{Student}(Ann), \text{Teach}(KR, Bob) \} $$

$$ \mathcal{R}_6 = \{ \text{Teach}(Ann, DB), \text{Teach}(KR, Bob) \} $$

Observe that $\text{Person}(Ann)$ is entailed under CQA semantics, but not under intersection semantics, as the intersection of the repairs is empty. On the other hand, every fact from $\mathcal{D}$ is entailed under brave. By using $\le$-optimal repairs, we can obtain further answers under $\le$-CQA and $\le$-intersection semantics, and eliminate some answers under $\le$-brave semantics.

■ We have $\le$-Rep($\mathcal{K}$) = {$\mathcal{R}_4$}, so $\text{Prof}(Ann)$ and $\text{Prof}(Bob)$ are entailed under $\le$-intersection, while they were not entailed under (plain) CQA semantics. On the other hand, using $\le$-optimal repairs rules out $\text{Student}(Ann)$, $\text{Student}(Bob)$ and $\text{Teach}(KR, Bob)$, which do not hold under the $\le$-brave semantics.

■ Suppose we have the prioritization $P = \langle \mathcal{P}_1, \mathcal{P}_2 \rangle$, based on the reliability of the predicates:

$$ \mathcal{P}_1 = \{ \text{Student}(Ann), \text{Student}(Bob), \text{Prof}(Bob) \} $$

$$ \mathcal{P}_2 = \{ \text{Teach}(Ann, DB), \text{Teach}(Ann, KR), \text{Teach}(KR, Bob), \text{Teach}(Bob, Algo) \} $$

We obtain $\subseteq_P$-Rep($\mathcal{K}$) = {$\mathcal{R}_1, \mathcal{R}_3$} and $\le_P$-Rep($\mathcal{K}$) = {$\mathcal{R}_3$}. Now $\text{Student}(Ann)$ is entailed under the $\subseteq_P$-intersection and $\le_P$-intersection semantics, whereas it was not entailed under (plain) CQA semantics, and it conflicts with a fact entailed under the $\le$-intersection semantics. Note that $\text{Prof}(Bob)$ is entailed under $\le_P$-intersection semantics, but only the less specific $\text{Person}(Bob)$ is entailed under $\subseteq_P$-CQA semantics.

■ If we assign facts in $\mathcal{P}_1$ a weight of 2, and facts of $\mathcal{P}_2$ a weight of 1, $\le_w$-Rep($\mathcal{K}$) = {$\mathcal{R}_3, \mathcal{R}_4$}. Under $\le_w$-CQA semantics, neither $\text{Prof}(Ann)$ nor $\text{Student}(Ann)$ is entailed, but only $\text{Person}(Ann)$. Under $\le_w$-intersection semantics, $\text{Prof}(Bob)$ is entailed.
**► Example 44.** Consider the database (with UCs) $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$ defined as follows.

$$ 
\begin{aligned}
\mathcal{T} &= \{ \text{Name}(x, y) \rightarrow \text{Person}(x), \text{Teach}(x, y) \rightarrow \text{Person}(x), \\
&\phantom{=} \text{Teach}(x, y) \rightarrow \text{Course}(y), \text{Course}(x) \wedge \text{Person}(x) \rightarrow \bot \} \\
\mathcal{D} &= \{ \text{Name}(123, Ann), \text{Teach}(Bob, 123) \}
\end{aligned}
$$

The set of $\Delta$-repairs $S-Rep_\Delta(\mathcal{K})$ contains:

$$ 
\begin{aligned}
\mathcal{R}_1 &= \{ \text{Name}(123, Ann), \text{Person}(123) \} \\
&\qquad \text{i.e., } \mathcal{R}_1\Delta\mathcal{D} = \{ \text{Teach}(Bob, 123), \text{Person}(123) \} \\
\mathcal{R}_2 &= \{ \text{Teach}(Bob, 123), \text{Person}(Bob), \text{Course}(123) \} \\
&\qquad \text{i.e., } \mathcal{R}_2\Delta\mathcal{D} = \{ \text{Name}(123, Ann), \text{Person}(Bob), \text{Course}(123) \} \\
\mathcal{R}_3 &= \emptyset \\
&\qquad \text{i.e., } \mathcal{R}_3\Delta\mathcal{D} = \{ \text{Name}(123, Ann), \text{Teach}(Bob, 123) \}
\end{aligned}
$$

- $\leq_{Rep_\Delta}(\mathcal{K}) = \{\mathcal{R}_1, \mathcal{R}_3\}$ since $\mathcal{R}_1$ and $\mathcal{R}_3$ have the smallest symmetric differences with $\mathcal{D}$.

- If we take the prioritization $P = \langle P_1, P_2 \rangle$ where $P_1$ contains $\text{Teach}(Bob, 123)$ and all negative literals (to strongly penalize fact additions) and $P_2 = \{\text{Name}(123, Ann)\}$, then $\subseteq_P-Rep_\Delta(\mathcal{K}) = \{\mathcal{R}_2, \mathcal{R}_3\}$ and $\leq_P-Rep_\Delta(\mathcal{K}) = \{\mathcal{R}_3\}$. Indeed, $\mathcal{R}_3\Delta\mathcal{D} \subseteq_P \mathcal{R}_1\Delta\mathcal{D}$ while $\mathcal{R}_2\Delta\mathcal{D}$ and $\mathcal{R}_3\Delta\mathcal{D}$ are incomparable w.r.t. $\subseteq_P$. However, $\mathcal{R}_3\Delta\mathcal{D} <_P \mathcal{R}_2\Delta\mathcal{D}$ since $\mathcal{R}_2\Delta\mathcal{D}$ contains two facts of level 1 while $\mathcal{R}_3\Delta\mathcal{D}$ only one.

- If we assign to literals in $P_1$ a weight of 2, and to those in $P_2$ a weight of 1, we obtain that $\leq_w-Rep_\Delta(\mathcal{D}, \mathcal{T}) = \{\mathcal{R}_3\}$ since $\mathcal{R}_3\Delta\mathcal{D}$ has weight 3, $\mathcal{R}_1\Delta\mathcal{D}$ 4 and $\mathcal{R}_2\Delta\mathcal{D}$ 5.

## 5.2 Optimal repairs based on a priority relation

The second category of preferred repairs we consider is based on a *priority relation* defined over conflicting facts (or literals in the case of $\Delta$-repairs of databases with UCs, even if most work on these kinds of repairs has focused on databases with anti-monotone ICs and KBs).

**► Definition 45 (Priority relation [129]).** A priority relation $\succ$ for a dataset $\mathcal{D}$ w.r.t. an ontology or set of anti-monotone ICs (resp. UCs) $\mathcal{T}$ is an acyclic binary relation over the facts (resp. literals) of $\text{Conf}(\mathcal{D}, \mathcal{T})$ such that if $\alpha \succ \beta$, there is $C \in \text{Conf}(\mathcal{D}, \mathcal{T})$ s.t. $\{\alpha, \beta\} \subseteq C$.

We say that $\succ$ is total if for every pair $\alpha \neq \beta$ such that $\{\alpha, \beta\} \subseteq C$ for some $C \in \text{Conf}(\mathcal{D}, \mathcal{T})$, either $\alpha \succ \beta$ or $\beta \succ \alpha$. A completion of $\succ$ is a total priority relation $\succ' \supseteq \succ$.

A priority relation $\succ$ is score-structured if there is a function $s: \bigcup_{C \in \text{Conf}(\mathcal{D}, \mathcal{T})} C \to \mathbb{N}$ such that for every $\{\alpha, \beta\} \subseteq C$ with $C \in \text{Conf}(\mathcal{D}, \mathcal{T})$, $\alpha \succ \beta$ iff $s(\alpha) > s(\beta)$.

**► Definition 46 (Prioritized KB/database).** A prioritized KB (resp. database) $\mathcal{K} \succ = (\mathcal{K}, \succ)$ consists of a KB (resp. database) $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$ and a priority relation $\succ$ for $\mathcal{D}$ w.r.t. $\mathcal{T}$.

**Specifying the priority relation.** Before defining the optimal repairs based on a priority relation, let us start by briefly explaining how one can specify such a relation, since it is not realistic to expect users to manually input a binary relation between facts or literals. This question has been recently tackled by a rule-based approach to specifying preferences over conflicting facts [37]. In a nutshell, the idea is that the user defines a few rules that are evaluated on $\mathcal{D}$, possibly taking into account $\mathcal{T}$ and/or some metadata (such as the sources of the facts or the dates they have been added to the dataset) to produce preference statements over facts (using fact identifiers). If these statements yield a cyclic relation,
cycle removal techniques are used to obtain a proper priority relation (possibly taking into account a stratification of the preference rules into more or less important ones). While this framework has been defined for KBs, we can in principle extend preference rules to specify a priority relation over literals in the case of databases with UCs.

**► Example 47 (Adapted from [37]).** The following preference rules express that (i) more recently added facts are preferred, (ii) if $\mathcal{D}$ contains both $\text{FullProf}(c)$ and $\text{AssociateProf}(c)$ for some $c$, then the former is preferred, and (iii) if a person is declared to belong to Student and to a subclass $Y$ of Prof, but there is no Teach-fact about this person in $\mathcal{D}$, then the Student-fact is deemed more reliable.

$$ (i) \qquad \text{Date}(x_1, y_1) \wedge \text{Date}(x_2, y_2) \wedge y_2 < y_1 \rightarrow \text{pref}(x_1, x_2) $$

$$ (ii) \qquad x_1 = \text{id}(\text{FullProf}(y)) \wedge x_2 = \text{id}(\text{AssociateProf}(y)) \rightarrow \text{pref}(x_1, x_2) $$

$$ (iii) \quad Y \sqsubseteq \text{Prof} \wedge x_1 = \text{id}(\text{Student}(y)) \wedge x_2 = \text{id}(Y(y)) \wedge \neg(\exists z \text{Teach}(y, z)) \rightarrow \text{pref}(x_1, x_2) $$

Assume that

$$ \mathcal{T} = \{\text{AssociateProf} \sqsubseteq \text{Prof}, \text{FullProf} \sqsubseteq \text{Prof}, \text{AssociateProf} \sqsubseteq \neg\text{FullProf}, \text{Prof} \sqsubseteq \neg\text{Student}\} $$

$$ \mathcal{D} = \{\text{Student}(a), \text{AssociateProf}(a), \text{FullProf}(a)\} $$

and that $\text{AssociateProf}(a)$ is associated to a more recent date than $\text{FullProf}(a)$. The rules yield the following preference statements: (i) $\text{AssociateProf}(a)$ is preferred to $\text{FullProf}(a)$, (ii) $\text{FullProf}(a)$ is preferred to $\text{AssociateProf}(a)$, and (iii) $\text{Student}(a)$ is preferred to the two other facts. Since there is a cycle in the preference statements, we need to either remove the whole cycle, which produces the priority relation $\succ$ $\text{AssociateProf}(a)$, $\succ$ $\text{Student}(a)$ $\succ$ $\text{FullProf}(a)$, or to rely on some information on the relative importance of the rules. For example, if rule (ii) has priority over (i), we additionally obtain $\succ$ $\text{FullProf}(a)$ $\succ$ $\text{AssociateProf}(a)$.

### 5.2.1 Pareto-, globally- and completion-optimal repairs

We now present the three kinds of optimal repair for a prioritized database or KB [129, 30, 32].

**► Definition 48 (Optimal repairs of a KB or database with anti-monotone constraints).** Consider a prioritized KB or database with anti-monotone ICs $K_{\succ} = (K, \succ)$ with $K = (\mathcal{D}, \mathcal{T})$, and let $\mathcal{R} \in \text{S-Rep}(K)$.

- A Pareto improvement of $\mathcal{R}$ (w.r.t. $\succ$) is a $\mathcal{T}$-consistent $\mathcal{B} \subseteq \mathcal{D}$ such that there exists $\beta \in \mathcal{B} \setminus \mathcal{R}$ such that $\beta \succ \alpha$ for every $\alpha \in \mathcal{R} \setminus \mathcal{B}$.

- A global improvement of $\mathcal{R}$ (w.r.t. $\succ$) is a $\mathcal{T}$-consistent $\mathcal{B} \subseteq \mathcal{D}$ such that $\mathcal{B} \neq \mathcal{R}$ and for every $\alpha \in \mathcal{R} \setminus \mathcal{B}$, there exists $\beta \in \mathcal{B} \setminus \mathcal{R}$ such that $\beta \succ \alpha$.

The repair $\mathcal{R}$ is a:

- Pareto-optimal repair of $K_{\succ}$ if there is no Pareto improvement of $\mathcal{R}$ w.r.t. $\succ$.

- Globally-optimal repair of $K_{\succ}$ if there is no global improvement of $\mathcal{R}$ w.r.t. $\succ$.

- Completion-optimal repair of $K_{\succ}$ if $\mathcal{R}$ is a globally-optimal repair of $K_{\succ'}$, for some completion $\succ'$ of $\succ$.

We denote by $\text{P-Rep}(K_{\succ})$, $\text{G-Rep}(K_{\succ})$, and $\text{C-Rep}(K_{\succ})$ the sets of Pareto-, globally-, and completion-optimal repairs.

For $\Delta$-repairs, recall from Section 3.2 that $\text{Int}_{\mathcal{D}}(\mathcal{B}) = (\mathcal{B} \cap \mathcal{D}) \cup \{\neg\alpha \mid \alpha \in \text{Facts}_{\mathcal{D}}^{\mathcal{T}} \setminus (\mathcal{B} \cup \mathcal{D})\}$ is the set of literals upon which $\mathcal{B}$ and $\mathcal{D}$ agree.
**► Definition 49** (Optimal repairs of a database with universal constraints). *Consider a prioritized database $K_\succ = (K, \succ)$ with $K = \langle D, T \rangle$ where $T$ is a set of UCs, and let $\mathcal{R} \in S-\text{Rep}_\Delta(K)$.*

■ A Pareto improvement of $\mathcal{R}$ (w.r.t. $\succ$) is a $\mathcal{T}$-consistent dataset $\mathcal{B}$ such that there is $\mu \in \text{Int}_{\mathcal{D}}(\mathcal{B}) \setminus \text{Int}_{\mathcal{D}}(\mathcal{R})$ such that $\mu \succ \lambda$ for every $\lambda \in \text{Int}_{\mathcal{D}}(\mathcal{R}) \setminus \text{Int}_{\mathcal{D}}(\mathcal{B})$.

■ A global improvement of $\mathcal{R}$ (w.r.t. $\succ$) is a $\mathcal{T}$-consistent dataset $\mathcal{B}$ s.t. $\text{Int}_{\mathcal{D}}(\mathcal{B}) \neq \text{Int}_{\mathcal{D}}(\mathcal{R})$ and for every $\lambda \in \text{Int}_{\mathcal{D}}(\mathcal{R}) \setminus \text{Int}_{\mathcal{D}}(\mathcal{B})$, there exists $\mu \in \text{Int}_{\mathcal{D}}(\mathcal{B}) \setminus \text{Int}_{\mathcal{D}}(\mathcal{R})$ such that $\mu \succ \lambda$. The Pareto-, globally-, and completion-optimal $\Delta$-repairs of $K_\succ$ ($\text{P-Rep}_\Delta(K_\succ)$, $\text{G-Rep}_\Delta(K_\succ)$ and $\text{C-Rep}_\Delta(K_\succ)$) are then defined as in Definition 48.

A Pareto improvement is a global improvement, and a global improvement w.r.t. $\succ$ is a global improvement w.r.t. any completion $\succ'$ of $\succ$, so optimal repairs are related as follows.

**► Proposition 50** ([129, 32]). For every prioritized KB or database $K_\succ$, it holds that

$$C-\text{Rep}(K_\succ) \subseteq \text{G-Rep}(K_\succ) \subseteq \text{P-Rep}(K_\succ) \subseteq \text{S-Rep}(K),$$

and similarly for $X-\text{Rep}_\Delta(K_\succ)$ in the case of $\Delta$-repairs.

Examples 51 and 52 illustrate the three kinds of optimal repair for prioritized KBs and $\Delta$-repairs of prioritized databases with UCs, respectively.

**► Example 51.** Consider the KB $\mathcal{K}$ from Example 15, whose conflict hypergraph and repairs are recalled below, and assume that $E(a) \succ C(a)$, $C(a) \succ A(a)$ and $A(a) \succ D(a)$.

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

$S-\text{Rep}(\mathcal{K}) = \{\mathcal{R}_1, \mathcal{R}_2, \mathcal{R}_3\}$ with:

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

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

$$\mathcal{R}_3 = \{B(a), C(a), D(a)\}$$

We show that $C-\text{Rep}(K_\succ) = \text{G-Rep}(K_\succ) = \{\mathcal{R}_1\}$ and $\text{P-Rep}(K_\succ) = \{\mathcal{R}_1, \mathcal{R}_3\}$.

■ $\mathcal{R}_2$ is not Pareto-optimal (hence not globally- nor completion-optimal) because $\{A(a), E(a)\}$ is a Pareto improvement of $\mathcal{R}_2$ (since $E(a) \succ C(a)$).

■ $\mathcal{R}_3$ is not globally-optimal (hence not completion-optimal) since $\{B(a), E(a), A(a)\}$ is a global improvement of $\mathcal{R}_3$ (since $E(a) \succ C(a)$ and $A(a) \succ D(a)$). However, it is Pareto-optimal, since replacing only $C(a)$ by $E(a)$ leads to a contradiction between $D(a)$ and $E(a)$, and similarly replacing only $D(a)$ with $A(a)$ leads to a conflict $\{A(a), B(a), C(a)\}$.

■ $\mathcal{R}_1$ is completion-optimal (hence globally- and Pareto-optimal), since every completion $\succ'$ of $\succ$ is such that $E(a) \succ' D(a)$ (to avoid cycle $E(a) \succ' C(a) \succ' A(a) \succ' D(a) \succ' E(a)$). Indeed, this implies that for every completion $\succ'$, a globally-optimal repair $\mathcal{R}$ of $K_\succ'$ must contain $E(a)$ (otherwise $\mathcal{R} \setminus \{C(a), D(a)\} \cup \{E(a)\}$ would be a global improvement of $\mathcal{R}$ w.r.t. $\succ'$), hence does not contain $C(a)$ nor $D(a)$, so that $\mathcal{R} = \mathcal{R}_1$.

**► Example 52** ([32]). Let $\mathcal{D} = \{S(a, b), S(a, c), R(d, b), R(d, c)\}$ and $\mathcal{T}$ contains the UCs:

$$S(x, y) \land S(x, z) \land y \neq z \rightarrow \bot$$

$$S(x, y) \rightarrow A(x)$$

$$R(y, x) \land S(z, x) \rightarrow \bot$$

$$R(x, y) \land R(x, z) \land y \neq z \rightarrow \bot$$

$$S(x, y) \rightarrow B(x)$$

The conflicts are all binary, so the conflict hypergraph is a graph, whose edges are pictured below. Assume that $R(d, b) \succ S(a, b)$, $S(a, b) \succ \neg A(a)$, $S(a, c) \succ R(d, c)$, $S(a, c) \succ \neg B(a)$. We use an arrow $\lambda \rightarrow \mu$ when $\lambda \succ \mu$ and plain lines for conflicting literals with no priority.
<figure><img src="image_13.png" /></figure>

It can be verified that the optimal repairs are as follows:

$$
\begin{align*}
C-\text{Rep}_{\Delta}(K_{\succ}) &= \{\{R(d, b), S(a, c), A(a), B(a)\}\} \\
G-\text{Rep}_{\Delta}(K_{\succ}) &= C-\text{Rep}_{\Delta}(K_{\succ}) \cup \{\{R(d, b)\}, \{R(d, c)\}\} \\
P-\text{Rep}_{\Delta}(K_{\succ}) &= G-\text{Rep}_{\Delta}(K_{\succ}) \cup \{\{R(d, c), S(a, b), A(a), B(a)\}\}
\end{align*}
$$

and that $S-\text{Rep}_\Delta(K) = P-\text{Rep}_\Delta(K_\succ)$.

There always exists at least one completion-(hence Pareto- and globally-)optimal repair, which can be obtained by the following greedy procedure: while some fact of $\mathcal{D}$ (or literal from $\text{Lits}_D^T$) has not been considered, pick one that is maximal w.r.t. $\succ$ among the facts (or literals) not yet considered (i.e., pick some $\alpha$ such that there is no $\beta \succ \alpha$), and add it to the current set if it does not lead to a contradiction [129, 32].

► **Remark 53** ([129, 32]). When $\succ$ is total, $|P-\text{Rep}(K_\succ)| = 1$ (hence $C-\text{Rep}(K_\succ) = G-\text{Rep}(K_\succ) = P-\text{Rep}(K_\succ)$). It follows that we may replace “globally-optimal” by “Pareto-optimal” in the definition of completion-optimal repairs.

The following example shows that the binary relation $\preceq_{P-\text{imp}}$ between datasets defined by “$\mathcal{B} \preceq_{P-\text{imp}} \mathcal{B}'$ iff $\mathcal{B} = \mathcal{B}'$ or $\mathcal{B}'$ is a Pareto improvement of $\mathcal{B}$” is not a preorder over datasets, so that we cannot recast Pareto-optimal repairs in the terms of Section 5.1 in this way, and similarly for globally-optimal repairs.

► **Example 54.** Let $\mathcal{D} = \{\alpha, \beta, \gamma, \delta\}$ and assume that $\mathcal{T}$ is such that $\text{Conf}(\mathcal{D}, \mathcal{T}) = \{\{\alpha, \beta\}, \{\alpha, \gamma\}, \{\delta, \beta\}, \{\delta, \gamma\}, \{\beta, \gamma\}\}$. Let $\beta \succ \alpha$, $\beta \succ \delta$ and $\gamma \succ \beta$. There are three repairs: $\mathcal{R}_1 = \{\alpha, \delta\}$, $\mathcal{R}_2 = \{\beta\}$, and $\mathcal{R}_3 = \{\gamma\}$. $\mathcal{R}_2$ is a Pareto improvement of $\mathcal{R}_1$ and $\mathcal{R}_3$ is a Pareto improvement of $\mathcal{R}_2$, but $\mathcal{R}_3$ is a not a Pareto improvement of $\mathcal{R}_1$: the relation “is a Pareto improvement of” is not transitive, so $\preceq_{P-\text{imp}}$ is not a preorder. This example also shows that the relation “is a global improvement of” is not transitive.

**The case of score-structured priority relations.** When $\succ$ is score-structured with scoring function $s: \bigcup_{C \in \text{Conf}(\mathcal{D}, \mathcal{T})} C \to \mathbb{N}$, the corresponding prioritization of $\bigcup_{C \in \text{Conf}(\mathcal{D}, \mathcal{T})} C$ is $P = \langle P_1, \dots, P_n \rangle$ such that for every $1 \le i \le n$, there exists $m \in \mathbb{N}$ such that $P_i = \{\alpha \mid s(\alpha) = m\}$, $P_i \ne \emptyset$, and for every $\alpha_i \in P_i$, $\alpha_j \in P_j$, $i < j$ iff $s(\alpha_i) > s(\alpha_j)$. The corresponding prioritization of the whole dataset $\mathcal{D}$ (or set of literals $\text{Lits}_D^T$ in the case of $\Delta$-repairs of databases with UCs) is obtained by adding the facts from $\mathcal{D} \setminus \bigcup_{C \in \text{Conf}(\mathcal{D}, \mathcal{T})} C$ (or literals from $\text{Lits}_D^T \setminus \bigcup_{C \in \text{Conf}(\mathcal{D}, \mathcal{T})} C$) to $P_1$ (this is an arbitrary choice as we could add them to any of the priority levels and obtain the following result). In this case, all three notions of optimal repairs coincide with $\subseteq_P$-optimal repairs.

► **Proposition 55** ([44, Prop. 6.1.14] and [32, Prop. 5]). If $K_\succ$ is a prioritized KB or database with a score-structured priority relation $\succ$, and $P$ is the corresponding prioritization, then

$$
C-\text{Rep}(K_{\succ}) = G-\text{Rep}(K_{\succ}) = P-\text{Rep}(K_{\succ}) = \subseteq_P -\text{Rep}(K),
$$

and similarly for $X-\text{Rep}_\Delta(K_\succ)$ in the case of $\Delta$-repairs.
## 5.2.2 Links with abstract argumentation and active integrity constraints

We now present some correspondences between Pareto-optimal repairs and other notions defined in frameworks that deal with inconsistent information, which speaks in favor of the naturalness of Pareto-optimal repairs.

### 5.2.2.1 Abstract argumentation

Recall from Section 3.3 that given a KB (or database with anti-monotone ICs) $K = \langle D, T \rangle$, its associated SETAF $F_K = (D, \rightsquigarrow_K)$, with $\rightsquigarrow_K = \{(C \setminus \{\alpha\}, \alpha) \mid C \in Conf(K), \alpha \in C\}$, is such that $R \in S-Rep(K)$ iff $R$ is a naive/stable/preferred extension of $F_K$. To capture prioritized KBs (or databases), we need to use preference-based SETAFs (PSETFs) [30].

**Definition 56 (Preference-based set-based argumentation framework).** A PSETF is a triple $(\mathit{Args}, \rightsquigarrow, \succ)$, where $(\mathit{Args}, \rightsquigarrow)$ is a SETAF, and $\succ$ is an acyclic binary relation over $\mathit{Args}$ called the preference relation.

The semantics of PSETFs is given by a reduction to SETAFs:

**Definition 57 (PSETF extensions).** Given a PSETF $(\mathit{Args}, \rightsquigarrow, \succ)$, its corresponding SETAF is $(\mathit{Args}, \rightsquigarrow)$, where the relation $\rightsquigarrow \subseteq (2^{\mathit{Args}} \setminus \{\emptyset\}) \times \mathit{Args}$ is defined as follows: $S \rightsquigarrow \alpha$ iff $S \rightsquigarrow \alpha$ and $\alpha \not\supseteq \beta$ for every $\beta \in S$. A subset $E \subseteq \mathit{Args}$ is a stable (resp. preferred) extension of a PSETF $(\mathit{Args}, \rightsquigarrow, \succ)$ iff it is a stable (resp. preferred) extension of the corresponding SETAF.

**From Pareto-optimal repairs to PSETF extensions.** Let $K_{\succ}$ be a prioritized KB (or database with anti-monotone ICs) such that $K = \langle D, T \rangle$ and $D$ does not contain any self-conflicting fact. The PSETF $F_{K, \succ}$ associated to $K_{\succ}$ is obtained from the SETAF associated to $K$ by using the priority relation $\succ$ as the preference relation, i.e., $F_{K, \succ} = (D, \rightsquigarrow_K, \succ)$ [30].

**Proposition 58 ([30, Th. 35, 36 and 37]).** Let $K_{\succ} = (K, \succ)$ be a prioritized KB (or database with anti-monotone ICs) such that $K = \langle D, T \rangle$ and $D$ does not contain any self-conflicting fact, $F_{K, \succ} = (D, \rightsquigarrow_K, \succ)$ be its associated PSETF, and $R \subseteq D$.

* $R \in P-Rep(K_{\succ})$ iff $R$ is a stable extension of $F_{K, \succ}$.

* If $\succ$ is transitive, then $R \in P-Rep(K_{\succ})$ iff $R$ is a preferred extension of $F_{K, \succ}$.

* If every $C \in Conf(K)$ is such that $|C| = 2$, then $R \in P-Rep(K_{\succ})$ iff $R$ is a preferred extension of $F_{K, \succ}$.

Note that it follows that globally-optimal and completion-optimal repairs correspond to proper subsets of the stable extensions of $F_{K, \succ}$, but they do not at present have any analogue in the argumentation setting.

**Example 59.** Consider again the prioritized KB $K_{\succ}$ of Example 51. The PSETF associated to $K_{\succ}$ is $F_{K, \succ} = (D, \rightsquigarrow_K, \succ)$ where $\rightsquigarrow_K$ is the attack relation defined in Example 24. The SETAF corresponding to the PSETF $F_{K, \succ}$ is $(\{A(a), B(a), C(a), D(a), E(a)\}, \rightsquigarrow)$ where $\rightsquigarrow$ is as follows.

$$ \begin{array}{l@{\qquad}l} \{A(a), C(a)\} & \rightsquigarrow B(a) & \{B(a), C(a)\} \rightsquigarrow A(a) \\ \{A(a)\} & \rightsquigarrow D(a) & \\ \{E(a)\} & \rightsquigarrow C(a) & \\ \{D(a)\} & \rightsquigarrow E(a) & \{E(a)\} \rightsquigarrow D(a) \end{array} $$

As in the case of standard repairs, it is not difficult to extend this reduction to the case of Pareto-optimal $\Delta$-repairs of databases with UCs.
### 5.2.2.2 Active integrity constraints

Active integrity constraints (AICs) provide a framework in which universal constraints are enriched with information on what are the allowed update actions (fact deletions or additions) to resolve a given constraint violation [80, 61, 42].

**Background on AICs.** In this section, we consider that UCs are written in the form $\beta[\vec{x}] \land \nu[\vec{x}] \land \epsilon[\vec{x}] \rightarrow \perp$, with $\beta[\vec{x}]$ a conjunction of relational atoms, $\nu[\vec{x}]$ a conjunction of negated relational atoms and $\epsilon[\vec{x}]$ a conjunction of inequalities (cf. Section 2.1).

**► Definition 60 (Update actions).** An update atom is of the form $+P(\vec{x})$ or $-P(\vec{x})$ where $P(\vec{x})$ is a relational atom. We use a function fix to map relational literals to the corresponding update atoms: fix($P(\vec{x})$) = $-P(\vec{x})$ and fix($\neg P(\vec{x})$) = $+P(\vec{x})$. An update action is a ground update atom, i.e., is of the form $-\alpha$ or $+\alpha$ with $\alpha$ a fact. A set of update actions $\mathcal{U}$ is consistent if $\mathcal{U}$ does not contain both $-\alpha$ and $+\alpha$ for some fact $\alpha$. The result of applying a consistent set of update actions $\mathcal{U}$ on a dataset $\mathcal{D}$ is $\mathcal{D} \circ \mathcal{U} := \mathcal{D} \setminus \{\alpha \mid -\alpha \in \mathcal{U}\} \cup \{\alpha \mid +\alpha \in \mathcal{U}\}$.

**► Definition 61 (Active integrity constraints).** An active integrity constraint takes the form $r = \ell_1 \wedge \dots \wedge \ell_n \rightarrow \{A_1, \dots, A_k\}$, where $\tau_r := \ell_1 \wedge \dots \wedge \ell_n \rightarrow \perp$ is a UC, and $\{A_1, \dots, A_k\}$ is a non-empty set of update atoms such that each $A_j$ is equal to fix($\ell_i$) for some $\ell_i$. A literal $\ell$ of $r$ is non-updatable if fix($\ell$) $\notin$ $\{A_1, \dots, A_k\}$. A dataset $\mathcal{D}$ satisfies $r$ ($\mathcal{D} \models r$) if it satisfies $\tau_r$.

A ground AIC is an AIC that contains no variables. The set $gr_{\mathcal{D}}(r)$ contains all ground AICs obtained from $r$ by (i) replacing variables by constants that occur in $\mathcal{D}$, (ii) removing all true $c \neq d$ atoms, and (iii) removing all ground AICs with an atom $c \neq c$. We let $gr_{\mathcal{D}}(\eta) := \cup_{r \in \eta} gr_{\mathcal{D}}(r)$, and observe that $\mathcal{D} \models r$ iff $\mathcal{D} \models r_g$ for every $r_g \in gr_{\mathcal{D}}(r)$.

An AIC is called normal if its head contains a single update atom. The normalization of $r = \ell_1 \wedge \dots \wedge \ell_n \rightarrow \{A_1, \dots, A_k\}$ is the set $N(r) = \{\ell_1 \wedge \dots \wedge \ell_n \rightarrow \{A_i\} \mid 1 \le i \le k\}$. The normalization of a set of AICs $\eta$ is $N(\eta) = \cup_{r \in \eta} N(r)$.

**► Definition 62 (Repair updates).** A repair update<fnref n="2" /> of a dataset $\mathcal{D}$ w.r.t. a set of AICs $\eta$ is a consistent $\subseteq$-minimal set of update actions $\mathcal{U}$ such that $\mathcal{D} \circ \mathcal{U}$ satisfies all AICs in $\eta$. We denote the set of repair updates of $\mathcal{D}$ w.r.t. $\eta$ by $Up(\mathcal{D}, \eta)$.

It is easy to check that $\{\mathcal{D} \circ \mathcal{U} \mid \mathcal{U} \in Up(\mathcal{D}, \eta)\} = S-\text{Rep}_{\Delta}(\mathcal{D}, \mathcal{T}_{\eta})$ where $\mathcal{T}_{\eta}$ is the set of UCs that correspond to AICs in $\eta$. To take into account the restrictions on the possible update actions expressed by the AICs, several classes of repair updates have been defined.

**► Definition 63 (Founded, well-founded, grounded and justified repair updates).** A repair update $\mathcal{U}$ of $\mathcal{D}$ w.r.t. $\eta$ is:

- Founded if for every $A \in \mathcal{U}$, there exists $r \in gr_{\mathcal{D}}(\eta)$ such that $A$ is an update action of $r$ and $\mathcal{D} \circ \mathcal{U} \setminus \{A\} \nvDash r$.

- Well-founded if there is a sequence of actions $A_1, \dots, A_n$ such that $\mathcal{U} = \{A_1, \dots, A_n\}$, and for each $1 \le i \le n$, there exists $r_i \in gr_{\mathcal{D}}(\eta)$ such that $A_i$ is an update action of $r_i$ and $\mathcal{D} \circ \{A_1, \dots, A_{i-1}\} \nvDash r_i$.

- Grounded if for every $\mathcal{V} \subsetneq \mathcal{U}$, there is $r \in gr_{\mathcal{D}}(N(\eta))$ such that $\mathcal{D} \circ \mathcal{V} \nvDash r$ and the (only) update action of $r$ is in $\mathcal{U} \setminus \mathcal{V}$ (recall that $N(\eta)$ is the normalization of $\eta$).

- Justified if $ne(\mathcal{D}, \mathcal{D} \circ \mathcal{U}) \cup \mathcal{U}$ is a minimal set of update actions closed under $\eta$ that contains the set of no-effect actions $ne(\mathcal{D}, \mathcal{D} \circ \mathcal{U})$ where

- $ne(\mathcal{D}, \mathcal{D} \circ \mathcal{U}) = \{+\alpha \mid \alpha \in \mathcal{D} \cap (\mathcal{D} \circ \mathcal{U})\} \cup \{-\alpha \mid \alpha \notin \mathcal{D} \cup (\mathcal{D} \circ \mathcal{U}), \alpha \in \text{Facts}_{\mathcal{D}}^{\mathcal{T}}\}$

- $\mathcal{V}$ is closed under $\eta$ if for every $r \in gr_{\mathcal{D}}(\eta)$, if $\mathcal{V}$ satisfies all the non-updatable literals of $r$, then $\mathcal{V}$ contains an update action of $r$.

<footnote n="2">² Repair updates are usually called repairs in the AIC literature, we use this term to avoid confusion.</footnote>
We denote the sets of Δ-repairs obtained by applying some founded, well-founded, grounded or justified repair update of D w.r.t. η by Found-Rep<sub>Δ</sub>(D, η), WellFound-Rep<sub>Δ</sub>(D, η), Ground-Rep<sub>Δ</sub>(D, η) and Just-Rep<sub>Δ</sub>(D, η), respectively.

The relationships between the various kinds of repairs are represented below, where a plain arrow from X to Y means X ⊆ Y and the dotted arrow represents an inclusion that only holds when η is a set of normal AICs. All inclusions may be strict [62, 69, 68].

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

**From Pareto-optimal repairs to repairs w.r.t. AICs.** Given a prioritized database $K_>$ where $K = \langle D, T \rangle$ with $T$ a set of UCs, its corresponding set of ground AICs [32] is

$$ \eta_{>}^{T} = \{r_C \mid C \in \text{Conf}(K)\} \text{ where } r_C := \bigwedge_{\lambda \in C} \lambda \rightarrow \{\text{fix}(\lambda) \mid \lambda \in C, \forall \mu \in C, \lambda \not\supseteq \mu\}. $$

Intuitively, $\eta_{>}^T$ expresses that conflicts of $K$ should be fixed by modifying their least preferred literals according to $>$. The Pareto-optimal repairs of $K_>$ coincide with several kinds of repairs of $D$ w.r.t. $\eta_{>}^T$.

**Proposition 64** ([32, Prop. 7]). Let $K_> = (\langle D, T \rangle, >)$ be a prioritized database such that $T$ is a set of UCs, and $\eta_{>}^T$ be its corresponding set of ground AICs.

$$ P-\text{Rep}_{\Delta}(K_>) = \text{Just-Rep}_{\Delta}(D, \eta_{>}^{T}) = \text{Ground-Rep}_{\Delta}(D, \eta_{>}^{T}) = \text{Found-Rep}_{\Delta}(D, \eta_{>}^{T}) \\ \subseteq \text{WellFound-Rep}_{\Delta}(D, \eta_{>}^{T}) $$

**Example 65.** We modify slightly the UCs of Example 52 so that some Δ-repares are not Pareto-optimal. Let $D = \{S(a, b), S(a, c), R(d, b), R(d, c)\}$ and $T$ contains the UCs:

$$ \begin{array}{l@{\qquad}l} S(x, y) \wedge S(x, z) \wedge y \neq z \rightarrow \bot & S(x, y) \rightarrow A(y) \\ R(x, y) \wedge R(x, z) \wedge y \neq z \rightarrow \bot & R(y, x) \wedge S(z, x) \rightarrow \bot \end{array} $$

The edges of the conflict graph and the optimal repairs are shown below, assuming that $R(d, b) > S(a, b)$, $S(a, b) > \neg A(b)$, $S(a, c) > R(d, c)$, $S(a, c) > \neg A(c)$.

$$ \begin{array}{l@{\qquad}l} R(d, b) \rightarrow S(a, b) \rightarrow \neg A(b) & C-\text{Rep}_{\Delta}(K_>) = G-\text{Rep}_{\Delta}(K_>) = \{\{R(d, b), S(a, c), A(c)\}\} \\ | & P-\text{Rep}_{\Delta}(K_>) = G-\text{Rep}_{\Delta}(K_>) \cup \{\{R(d, c), S(a, b), A(b)\}\} \\ R(d, c) \leftarrow S(a, c) \rightarrow \neg A(c) & S-\text{Rep}_{\Delta}(K_>) = P-\text{Rep}_{\Delta}(K_>) \cup \{\{R(d, b)\}, \{R(d, c)\}\} \end{array} $$

The set of ground AICs $\eta_{>}^T$ corresponding to $K_>$ contains the following AICs:

$$ r_1 : R(d, b) \wedge S(a, b) \rightarrow \{-S(a, b)\} \qquad r_4 : S(a, b) \wedge S(a, c) \rightarrow \{-S(a, b), -S(a, c)\} $$

$$ r_2 : R(d, c) \wedge S(a, c) \rightarrow \{-R(d, c)\} \qquad r_5 : R(d, b) \wedge R(d, c) \rightarrow \{-R(d, b), -R(d, c)\} $$

$$ r_3 : S(a, b) \wedge \neg A(b) \rightarrow \{+A(b)\} \qquad r_6 : S(a, c) \wedge \neg A(c) \rightarrow \{+A(c)\} $$

We can check that the two Pareto-optimal Δ-repares correspond exactly to the justified, grounded and founded repair updates:
- $U_1 = \{-S(a,b), -S(a,c), -R(d,c)\}$ and $U_2 = \{-S(a,b), -S(a,c), -R(d,b)\}$, which correspond respectively to the $\Delta$-repairs $R_1 = \{R(d,b)\}$ and $R_2 = \{R(d,c)\}$, are not founded (hence not grounded nor justified). Indeed, $-S(a,c) \in U_1$ while the only AIC with $-S(a,c)$ in the head ($r_4$) is satisfied by $R_1 \cup \{S(a,c)\}$. Regarding $U_2$, $-S(a,b) \in U_2$ and the two AICs with $-S(a,b)$ in the head ($r_1$ and $r_4$) are satisfied by $R_2 \cup \{S(a,b)\}$.

- The repair update $U_3 = \{-R(d,b), -S(a,c), +A(b)\}$, which corresponds to the Pareto-optimal $\Delta$-repair $R_3 = \{R(d,c), S(a,b), A(b)\}$ is grounded (hence founded) and justified. Indeed, (1) for every $V \subsetneq U_3$, there is $r$ in the normalization $N(\eta_T)$ of $\eta_T$ such that $D \circ V \neq r$ and the only update action of $r$ is in $U_3 \setminus V$, so $U_3$ is grounded, and (2) $ne(D, D \circ U_3) \cup U_3 = \{+R(d,c), +S(a,b), -A(c), -R(d,b), -S(a,c), +A(b)\}$ is a minimal set of update actions closed under $\eta_T$ that contains $ne(D, D \circ U_3) = \{+R(d,c), +S(a,b), -A(c)\}$ (since this set of update actions satisfies all the non-updatable literals of $r_3$, $r_4$ and $r_5$).

- The repair update $U_4 = \{-R(d,c), -S(a,b), +A(c)\}$, which corresponds to the Pareto-optimal $\Delta$-repair $R_4 = \{R(d,b), S(a,c), A(c)\}$ is also grounded, founded and justified.

The above reduction is data-dependent and requires us to create potentially exponentially many ground AICs (one for every conflict). In the case of *denial constraints*, however, there exists an alternative data-independent reduction, provided that the priority relation $>_{\prec}$ is specified in the dataset [32]. It assumes the existence of a predicate $P_{>_{\prec}} \in \mathbf{P}$, that the first attribute of each relation in $\mathbf{P} \setminus \{P_{>_{\prec}}\}$ stores a unique fact identifier, and that $P_{>_{\prec}}$ stores pairs of such identifiers. Then given a set of DCs $\mathcal{T}$ over $\mathbf{P} \setminus \{P_{>_{\prec}}\}$, $\min(\mathcal{T})$ is the set of DCs that is equivalent to $\mathcal{T}$ but has the property that for every dataset $D$, the conflicts of $D$ w.r.t. $\mathcal{T}$ are precisely the images of constraint bodies of $\min(\mathcal{T})$ on $D$. This can be achieved by replacing each $\varphi \to \perp \in \mathcal{T}$ with all refinements obtained by (dis)equating variables in $\varphi$ with each other, then removing any subsumed constraints. For example, if $\mathcal{T} = \{R(x,x) \to \perp, R(x,y) \wedge S(y) \to \perp\}$, then $\min(\mathcal{T})$ contains $R(x,x) \to \perp$ and $R(x,y) \wedge S(y) \wedge x \neq y \to \perp$, so $\{R(a,a), S(a)\}$ is no longer an image of a constraint body. The set of AICs corresponding to $\mathcal{T}$, $\eta^T$, contains all AICs

$$ (\ell_1 \wedge \dots \wedge \ell_n \wedge \varepsilon \wedge \bigwedge_{\substack{j \in \{1, \dots, n\}, \\ j \neq i}} \neg P_{>_{\prec}}(id_i, id_j)) \to \{-\ell_i\} $$

such that $\ell_1 \wedge \dots \wedge \ell_n \wedge \varepsilon \to \perp \in \min(\mathcal{T})$, $i \in \{1, \dots, n\}$, and for every $1 \le k \le n$, $\ell_k = R(id_k, \vec{t})$ for some $R, \vec{t}$.

**Proposition 66** ([32, Prop. 8]). Let $K_{>_{\prec}} = (\langle D, \mathcal{T} \rangle, >_{\prec})$ be a prioritized database such that $\mathcal{T}$ is a set of DCs, and $\eta^T$ be the set of AICs corresponding to $\mathcal{T}$.

$$ \begin{aligned} P-\text{Rep}(K_{>_{\prec}}) &= \text{Just-Rep}_{\Delta}(D, \eta^T) = \text{Ground-Rep}_{\Delta}(D, \eta^T) = \text{Found-Rep}_{\Delta}(D, \eta^T) \\ &\subseteq \text{WellFound-Rep}_{\Delta}(D, \eta^T) \end{aligned} $$

**From repairs w.r.t. AICs to Pareto-optimal repairs.** Interestingly, certain “well-behaved” sets of AICs, for which, in particular, justified, grounded and founded repairs coincide, can be translated into prioritized databases whose Pareto-optimal repairs coincide with these repairs [32]. The conditions on the AICs are quite involved though.

## 5.3 Preferred repairs based on preference rules

The last category of preferred repairs we consider is inspired by work in logic programming [46] and uses *preference rules* to express context-dependent preferences. Preferred repairs are then those that maximally (w.r.t. some preorder) satisfy these preference rules [50].
**► Definition 67** (Preference program [50]). A preference rule $\rho$ is an expression of the form

$$P[\vec{x}] \succ Q[\vec{y}] \leftarrow \exists \vec{z} \varphi[\vec{z}, \vec{w}],$$

where $P[\vec{x}]$ and $Q[\vec{y}]$ are two relational atoms whose variables are $\vec{x}$ and $\vec{y}$ respectively (and may contain constants), $\vec{x} \cap \vec{z} = \vec{y} \cap \vec{z} = \emptyset$, and $\varphi[\vec{z}, \vec{w}]$ is a (possibly empty) conjunction of relational atoms with variables $\vec{z} \cup \vec{w}$. A set of preference rules is called a preference program.

**► Definition 68** (Preference program-based prioritized KB or database [50]). A (preference program-based) prioritized KB or database $K_\Pi = (K, \Pi)$ consists of a KB (or database with anti-monotone ICs) $K = \langle D, T \rangle$ and a preference program $\Pi$.

A ground instance of a preference rule $\rho$ (w.r.t. $K$ and $\Pi$) is a preference rule obtained from $\rho$ by replacing all its free variables by constants that occur in $K$ or $\Pi$. The set of all ground instances of all rules in $\Pi$ is denoted by $\text{grnd}_K(\Pi)$.

A $T$-consistent dataset $B$ satisfies a ground instance $P(\vec{a}) \succ Q(\vec{b}) \leftarrow \exists \vec{z} \varphi[\vec{z}, \vec{c}]$ (w.r.t. $K$) if $\langle B, T \rangle \models \exists \vec{z} \varphi[\vec{z}, \vec{c}]$ implies that $\langle B, T \rangle \not\models Q(\vec{b})$ or $\langle B, T \rangle \models P(\vec{a})$, i.e., if the following holds:

$$\langle B, T \rangle \models \exists \vec{z} \varphi[\vec{z}, \vec{c}] \Rightarrow (\langle B, T \rangle \models Q(\vec{b}) \Rightarrow \langle B, T \rangle \models P(\vec{a}))$$

The set of preference rules from $\text{grnd}_K(\Pi)$ satisfied by $B$ is denoted by $\text{GrSat}(B, K_\Pi)$.

**► Definition 69** (Preference program-based preferred repairs [50]). Let $K_\Pi = (K, \Pi)$ be a (preference program-based) prioritized KB (or database) and $\leq$ be a preorder on the subsets of $\text{grnd}_K(\Pi)$. A repair $\mathcal{R}$ of $K$ is $\Pi$-preferred iff there is no repair $\mathcal{R}'$ of $K$ such that $\text{GrSat}(\mathcal{R}, K_\Pi) \triangleleft \text{GrSat}(\mathcal{R}', K_\Pi)$. We denote by $\text{Pr}_\leq$-Rep($K_\Pi$) the set of $\Pi$-preferred repairs.

Note that even if the binary relation over datasets $\leq_{\Pi}$ defined by $B \preceq_{\Pi} B'$ iff $\text{GrSat}(B, K_\Pi) \leq \text{GrSat}(B', K_\Pi)$ is a preorder, we cannot recast $\Pi$-preferred repairs in the terms of Section 5.1. Indeed, $\leq_{\Pi}$ is not strictly $\subseteq$-monotone, since the empty set trivially satisfies every preference rule ground instance, hence is $\leq_{\Pi}$-maximal.

**► Example 70.** Consider the KB $K = \langle D, T \rangle$, where $T$ expresses that computer science (CS), economics (Eco) and literature (Lit) courses and professors, respectively, are disjoint.

$$T = \{ \text{CSCourse} \sqsubseteq \neg \text{EcoCourse}, \text{CSCourse} \sqsubseteq \neg \text{LitCourse}, \text{LitCourse} \sqsubseteq \neg \text{EcoCourse}, \\ \text{CSPr} \sqsubseteq \neg \text{EcoPr}, \text{CSPr} \sqsubseteq \neg \text{LitPr}, \text{LitPr} \sqsubseteq \neg \text{EcoPr} \}$$

$$D = \{ \text{CSCourse}(c), \text{EcoCourse}(c), \text{LitCourse}(c), \text{CSPr}(p), \text{EcoPr}(p), \text{Teach}(p, c) \}$$

There are six repairs:

$$\mathcal{R}_1 = \{ \text{CSCourse}(c), \text{CSPr}(p), \text{Teach}(p, c) \} \qquad \mathcal{R}_2 = \{ \text{CSCourse}(c), \text{EcoPr}(p), \text{Teach}(p, c) \}$$

$$\mathcal{R}_3 = \{ \text{EcoCourse}(c), \text{CSPr}(p), \text{Teach}(p, c) \} \qquad \mathcal{R}_4 = \{ \text{EcoCourse}(c), \text{EcoPr}(p), \text{Teach}(p, c) \}$$

$$\mathcal{R}_5 = \{ \text{LitCourse}(c), \text{CSPr}(p), \text{Teach}(p, c) \} \qquad \mathcal{R}_6 = \{ \text{LitCourse}(c), \text{EcoPr}(p), \text{Teach}(p, c) \}$$

Assume that $\Pi$ contains the following preference rules, which express that when a course is taught by a professor in a given subject, we prefer the fact that states that this course is on that subject to facts that state it is on another subject:

$$\rho_1 : \quad \text{CSCourse}(x) \succ \text{EcoCourse}(x) \leftarrow \exists y \text{Teach}(y, x) \wedge \text{CSPr}(y)$$

$$\rho_2 : \quad \text{EcoCourse}(x) \succ \text{CSCourse}(x) \leftarrow \exists y \text{Teach}(y, x) \wedge \text{EcoPr}(y)$$

$$\rho_3 : \quad \text{CSCourse}(x) \succ \text{LitCourse}(x) \leftarrow \exists y \text{Teach}(y, x) \wedge \text{CSPr}(y)$$

$$\rho_4 : \quad \text{LitCourse}(x) \succ \text{CSCourse}(x) \leftarrow \exists y \text{Teach}(y, x) \wedge \text{LitPr}(y)$$

$$\rho_5 : \quad \text{EcoCourse}(x) \succ \text{LitCourse}(x) \leftarrow \exists y \text{Teach}(y, x) \wedge \text{EcoPr}(y)$$

$$\rho_6 : \quad \text{LitCourse}(x) \succ \text{EcoCourse}(x) \leftarrow \exists y \text{Teach}(y, x) \wedge \text{LitPr}(y)$$
Since all repairs trivially satisfy the ground instances obtained by replacing $x$ by $p$, we identify each $\rho_i$ with its ground instance obtained by replacing $x$ by $c$ in what follows.

- $\mathcal{R}_1$ and $\mathcal{R}_4$ satisfy all rules. For example, $\mathcal{R}_1$ satisfies $\rho_1$ because $\langle \mathcal{R}_1, \mathcal{T} \rangle \models \text{CSCourse}(c)$, and $\rho_2$ because $\langle \mathcal{R}_1, \mathcal{T} \rangle \not\models \exists y \text{Teach}(y, c) \wedge \text{EcoPr}(y)$.

- $\mathcal{R}_2$ satisfies all rules but $\rho_2$: $\langle \mathcal{R}_2, \mathcal{T} \rangle \models \exists y \text{Teach}(y, c) \wedge \text{EcoPr}(y)$ and $\langle \mathcal{R}_2, \mathcal{T} \rangle \models \text{CSCourse}(c)$ while $\langle \mathcal{R}_2, \mathcal{T} \rangle \not\models \text{EcoCourse}(c)$. Note that it satisfies $\rho_5$ because $\langle \mathcal{R}_2, \mathcal{T} \rangle \not\models \text{LitCourse}(c)$.

- $\mathcal{R}_3$ satisfies all rules but $\rho_1$; $\mathcal{R}_5$ satisfies all rules but $\rho_3$; and $\mathcal{R}_6$ satisfies all rules but $\rho_5$. Hence, for $\sqsubseteq \in \{\subseteq, \leq\}$, $\text{Pr}_{\sqsubseteq}\text{-Rep}(\mathcal{K}_{\sqsubseteq}) = \{\mathcal{R}_1, \mathcal{R}_4\}$, which correspond to the two ways of repairing $\mathcal{D}$ by selecting a pair of a course and a professor with matching subject.

To illustrate how choosing $\subseteq$ or $\leq$ may lead to different $\Pi_{\sqsubseteq}$-preferred repairs, consider $\mathcal{K}' = \langle \mathcal{D}, \mathcal{T}' \rangle$ where $\mathcal{T}'$ keeps only the three first axioms of $\mathcal{T}$ (i.e., a course has only one subject but professors can teach several subjects). There are three repairs of $\mathcal{K}'$:

$$ \mathcal{R}'_1 = \{\text{CSCourse}(c), \text{CSPr}(p), \text{EcoPr}(p), \text{Teach}(p, c)\} $$

$$ \mathcal{R}'_2 = \{\text{EcoCourse}(c), \text{CSPr}(p), \text{EcoPr}(p), \text{Teach}(p, c)\} $$

$$ \mathcal{R}'_3 = \{\text{LitCourse}(c), \text{CSPr}(p), \text{EcoPr}(p), \text{Teach}(p, c)\} $$

We obtain $\text{Pr}_{\sqsubseteq}\text{-Rep}(\mathcal{K}'_{\sqsubseteq}) = \{\mathcal{R}'_1, \mathcal{R}'_2, \mathcal{R}'_3\}$ while $\text{Pr}_{\leq}\text{-Rep}(\mathcal{K}'_{\leq}) = \{\mathcal{R}'_1, \mathcal{R}'_2\}$. Indeed $\mathcal{R}'_1$ satisfies all rules but $\rho_2$; $\mathcal{R}'_2$ satisfies all rules but $\rho_1$; and $\mathcal{R}'_3$ satisfies $\rho_1, \rho_2, \rho_4$, and $\rho_6$.

While the preference rules used to define a priority relation among conflicting facts in Section 5.2 (cf. Example 47) are quite similar to the ones considered here from a syntactic point of view, they have a different semantics: the former aim at defining a priority relation between conflicting facts globally, taking into account the whole dataset $\mathcal{D}$, while the latter aim at defining directly a preference relation between repairs, so that the relation $\succ$ between facts is specific to each repair. If we consider the counterparts of the preference rules of Example 70 that specify a priority relation as in Example 47 and evaluate them over $\mathcal{D}$, we obtain that $\text{CSCourse}(c)$ is preferred to $\text{EcoCourse}(c)$ (counterpart of $\rho_1$), $\text{EcoCourse}(c)$ is preferred to $\text{CSCourse}(c)$ (counterpart of $\rho_2$), $\text{CSCourse}(c)$ is preferred to $\text{LitCourse}(c)$ (counterpart of $\rho_3$), and $\text{EcoCourse}(c)$ is preferred to $\text{LitCourse}(c)$ (counterpart of $\rho_5$), which yields (assuming that all rules are equally important) the priority relation $\text{CSCourse}(c) \succ \text{LitCourse}(c)$, $\text{EcoCourse}(c) \succ \text{LitCourse}(c)$. The optimal repairs w.r.t. this priority relation are $\{\mathcal{R}_1, \mathcal{R}_2, \mathcal{R}_3, \mathcal{R}_4\}$ for $\mathcal{K}' \succ$ and $\{\mathcal{R}'_1, \mathcal{R}'_2\}$ for $\mathcal{K}' \prec$.

**Capturing $\leq$-optimal repairs for $\leq \in \{\leq, \leq_w, \subseteq_P, \leq_P\}$**. Given $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$ and a preorder $\leq \in \{\leq, \leq_w, \subseteq_P, \leq_P\}$ over the subsets of $\mathcal{D}$, it is possible to define a preference program $\Pi$, a fact $\alpha$ and a preorder $\sqsubseteq$ on the subsets of $\text{grnd}_{\mathcal{K}}(\Pi)$ such that there is a one-to-one correspondence between $\leq$-optimal repairs of $\mathcal{K}$ and $\Pi_{\leq}$-preferred repairs of $\mathcal{K}' = \langle \mathcal{D} \cup \{\alpha\}, \mathcal{T} \rangle$. More precisely:

$$ \text{Pr}_{\leq}\text{-Rep}(\mathcal{K}'_{\leq}) = \{\mathcal{R} \cup \{\alpha\} \mid \mathcal{R} \in \leq\text{-Rep}(\mathcal{K})\}. $$

The idea is simply to encode the preorder over the subsets of $\mathcal{D}$ in $\Pi$: take $\alpha = A(a)$ such that $A$ and $a$ do not occur in $\mathcal{K}$, $\Pi = \{\beta \succ \alpha \leftarrow | \beta \in \mathcal{D}\}$, and for all subsets $S$ and $S'$ of $\text{grnd}_{\mathcal{K}}(\Pi)$ (which is equal to $\Pi$ in this case) let $S \sqsubseteq S'$ iff $\{\beta | \beta \succ \alpha \leftarrow \in S\} \subseteq \{\beta | \beta \succ \alpha \leftarrow \in S'\}$. Then for all $\mathcal{T}$-consistent $B$ and $B'$ subsets of $\mathcal{D}$, $B \preceq B'$ iff $\text{GrSat}(B \cup \{\alpha\}, \mathcal{K}'_{\Pi}) \sqsubseteq \text{GrSat}(B' \cup \{\alpha\}, \mathcal{K}'_{\Pi})$. Since all repairs of $\mathcal{K}'$ contain $\alpha$ (so that subsets of $\mathcal{D}$, which trivially satisfy all rules from $\Pi$, are not repairs of $\mathcal{K}'$, hence not $\Pi_{\leq}$-preferred repairs), it follows that $\mathcal{R}$ is a $\leq$-optimal repair of $\mathcal{K}$ iff $\mathcal{R} \cup \{\alpha\}$ is a $\Pi_{\leq}$-preferred repair of $\mathcal{K}'$. In the case of $\leq$, this reduction can be adapted into a data-independent one [50, Prop. 42].
**Comparison with optimal repairs based on a priority relation.** Given a prioritized KB or database $\mathcal{K}_{\succ}$, we can consider the preference program $\Pi = \{\alpha \succ \beta \leftarrow | \alpha \succ \beta\}$. However, the $\Pi_{\sqsubseteq}$-preferred repairs of $\mathcal{K}_{\Pi}$ are incomparable with the optimal repairs of $\mathcal{K}_{\succ}$ [50]. For example, assume that $\mathcal{D} = \{\alpha, \beta, \gamma\}$, $\text{Conf}(\mathcal{D}, \mathcal{T}) = \{\{\alpha, \beta\}, \{\alpha, \gamma\}\}$ and $\alpha \succ \beta$. There are two repairs, $\{\alpha\}$ and $\{\beta, \gamma\}$. The priority relation $\succ$ is score-structured so Pareto-, globally-, completion- and $\subseteq_P$-optimal repairs coincide and both $\{\alpha\}$ and $\{\beta, \gamma\}$ are optimal. However, only $\{\alpha\}$ is a $\Pi_{\sqsubseteq}$-preferred (resp. $\Pi_{\leq}$-preferred) repair. For an example where there are more $\Pi_{\sqsubseteq}$-preferred repairs, consider $\mathcal{D} = \{\alpha, \beta, \gamma\}$, $\text{Conf}(\mathcal{D}, \mathcal{T}) = \{\{\alpha, \beta\}, \{\beta, \gamma\}\}$ and $\alpha \succ \beta$, $\beta \succ \gamma$. Again $\succ$ is score-structured, and the only optimal repair of $\mathcal{K}_{\succ}$ is $\{\alpha, \gamma\}$. However both $\{\alpha, \gamma\}$ and $\{\beta\}$ are $\Pi_{\sqsubseteq}$-preferred repairs of $\mathcal{K}_{\Pi}$ because $\{\beta\}$ satisfies $\beta \succ \gamma \leftarrow$ while $\{\alpha, \gamma\}$ does not. More examples and discussion can be found in [50, Sec. 6].

## 5.4 Related work: “Optimal repairs” that are not dataset repairs

We conclude this section with a brief presentation of other notions of “optimal repairs” which are not dataset repairs (i.e., do not form a subset of $\text{S-Rep}(\mathcal{K})$).

### 5.4.1 Repairs based on non strictly $\subseteq$-monotone weight-based preorders

A generalization of $\leq_w$-optimal repairs based on aggregation functions has been defined for databases with anti-monotone ICs [122]. An aggregation function $g$ maps every dataset $\mathcal{B}$ (associated with a weight function $w$) to a non-negative rational number $g(\mathcal{B})$ (cf. [122] for the precise definition). Prominent examples of such functions are $\Sigma(\mathcal{B}) = \sum_{\alpha \in \mathcal{B}} w(\alpha)$ (which yields $\leq_w$-optimal repairs), $\max(\mathcal{B}) = \max_{\alpha \in \mathcal{B}} w(\alpha)$, or $\text{average}(\mathcal{B}) = \frac{\sum_{\alpha \in \mathcal{B}} w(\alpha)}{|\mathcal{B}|}$.

**► Definition 71 (Aggregation-based repairs).** Given an aggregation function $g$ and a KB (or database with anti-monotone ICs) $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$ with a weight function $w$, a *g-repair* of $\mathcal{K}$ is a *T-consistent* $\mathcal{R} \subseteq \mathcal{D}$ such that (i) there is no *T-consistent* $\mathcal{R}' \subseteq \mathcal{D}$ with $g(\mathcal{R}) < g(\mathcal{R}')$ and (ii) for every *T-consistent* $\mathcal{R}' \subseteq \mathcal{D}$, if $g(\mathcal{R}') = g(\mathcal{R})$ and $\mathcal{R} \subseteq \mathcal{R}'$, then $\mathcal{R} = \mathcal{R}'$.

Note that if we define the preorder corresponding to an aggregation function $g$ as $\mathcal{B} \preceq_g \mathcal{B}'$ iff $g(\mathcal{B}) \leq g(\mathcal{B}')$, condition (i) of Definition 71 can be written as “there is no $\mathcal{T}$-consistent $\mathcal{R}' \subseteq \mathcal{D}$ with $\mathcal{R} \prec_g \mathcal{R}'$”. This definition thus modifies Definition 41 by (1) dropping the condition that the preorder is strictly $\subseteq$-monotone and (2) partially compensating the effects of dropping this requirement with condition (ii), which expresses that a *g-repair* needs to be $\subseteq$-maximal among the $\preceq_g$-maximal $\mathcal{T}$-consistent subsets of $\mathcal{D}$. The following example shows that this is not sufficient to ensure that *g-repairs* are dataset repairs.

**► Example 72 ([122]).** Let $\mathcal{D} = \{\beta, \gamma\}$ be such that $\mathcal{D}$ is $\mathcal{T}$-consistent, so that $\text{S-Rep}(\mathcal{D}, \mathcal{T}) = \{\mathcal{D}\}$, and assume that $w(\beta) = 1$ and $w(\gamma) = 2$. Consider the aggregation function min defined by $\min(\mathcal{B}) = \min_{\alpha \in \mathcal{B}} w(\alpha)$. Then $\{\gamma\}$ is the only min-repair of $\mathcal{D}$ w.r.t. $\mathcal{T}$ since $\min(\{\beta, \gamma\}) = 1 < \min(\{\gamma\}) = 2$. Hence the set of min-repairs is not a subset of $\text{S-Rep}(\mathcal{D}, \mathcal{T})$.

### 5.4.2 Selecting a single $\mathcal{T}$-consistent dataset from a prioritized dataset

Instead of considering all optimal repairs of a prioritized KB or database $\mathcal{K}_{\succ}$, one may be interested in selecting a single $\mathcal{T}$-consistent dataset. Several such “repairs” have been proposed, depending on whether $\succ$ is based on a prioritization $P = \langle \mathcal{P}_1, \dots, \mathcal{P}_n \rangle$ of $\mathcal{D}$ (i.e., $\alpha \succ \beta$ iff $\{\alpha, \beta\} \subseteq \mathcal{C}$ for some conflict $\mathcal{C}$, $\alpha \in \mathcal{P}_i, \beta \in \mathcal{P}_j$ and $i < j$), a preorder $\trianglelefteq$ over $\mathcal{D}$ (i.e., $\alpha \succ \beta$ iff $\{\alpha, \beta\} \subseteq \mathcal{C}$ for some conflict $\mathcal{C}$ and $\alpha \succ \beta$), or is an arbitrary priority relation. These notions of repair stem from the KB area, so we give the definitions for KBs or
databases with anti-monotone ICs, but we could in principle extend them to handle database with universal constraints by considering literals as in Section 5.2. We provide below all definitions before presenting their relationships, properties, and an example.

The next definition presents the different kinds of “unique repair” that have been proposed when the dataset is partitioned into priority levels, i.e., the most restricted case.

**► Definition 73 (Unique repairs based on a prioritization [24]).** Let $K_>$ be a prioritized KB (or database with anti-monotone ICs) such that $K = \langle D, T \rangle$ and $>$ is based on a prioritization $P = \langle P_1, \dots, P_n \rangle$ of $D$.

- The possibilistic repair of $K_>$ is $\pi(K_>) = P_1 \cup \dots \cup P_{inc(K_>)-1}$, where $inc(K_>)$ is the inconsistency degree of $K_>$, which is such that $P_1 \cup \dots \cup P_{inc(K_>})$ is $T$-inconsistent and $P_1 \cup \dots \cup P_{inc(K_>} - 1)$ is $T$-consistent.

- The linear repair of $K_>$ is $\ell(K_>) = \ell(D)$ with:

- $\ell(P_1) = P_1$ if $P_1$ is $T$-consistent, $\ell(P_1) = \emptyset$ otherwise;

- for $i > 1$, $\ell(P_1 \cup \dots \cup P_i) = \ell(P_1 \cup \dots \cup P_{i-1}) \cup P_i$ if $\ell(P_1 \cup \dots \cup P_{i-1}) \cup P_i$ is $T$-consistent, $\ell(P_1 \cup \dots \cup P_i) = \ell(P_1 \cup \dots \cup P_{i-1})$ otherwise.

- The non-defeated repair of $K_>$ is $nd(K_>) = \bigcup_{i=1}^n R_i \cap$ where $R_i \cap = \bigcap_{R \in S-Rep(P_1 \cup \dots \cup P_i, T)} R$.

- The linear-based non-defeated repair of $K_>$ is $\ell nd(K_>) = \ell nd(D)$ with:

- $\ell nd(P_1) = \bigcap_{R \in S-Rep(P_1, T)} R$;

- for $i > 1$, $\ell nd(P_1 \cup \dots \cup P_i) = \ell nd(P_1 \cup \dots \cup P_{i-1}) \cup \bigcap_{R \in S-Rep(\ell nd(P_1 \cup \dots \cup P_{i-1}) \cup P_i, T)} R$.

- The prioritized inclusion-based non-defeated repair of $K_>$ is $\text{pind}(K_>) = \bigcup_{i=1}^n R_{P_i \cap}^i$ where $R_{P_i \cap}^i = \bigcap_{R \in \subseteq_{P-Rep}(P_1 \cup \dots \cup P_i, T)} R$. Equivalently, $\text{pind}(K_>) = \bigcap_{R \in \subseteq_{P-Rep}(K)} R$.

The “unique repairs” of Definition 74, for the case where only a preorder over the facts is available, rely on completing the preorder in all possible ways, yielding prioritizations used to apply notions from Definition 73. Two additional proposals, called *CElect* [22] and *Cπ* [97], add facts using the logical closure w.r.t. the ontology, thus are typically not subsets of $D$.

**► Definition 74 (Unique repairs based on a preorder [22]).** Let $K_>$ be a prioritized KB (or database with anti-monotone ICs) such that $>$ corresponds to a preorder $\leq$ over $D$. For each total preorder $\leq' $ extending $\leq$, let $>'$ correspond to the prioritization induced by $\leq'$.

- $\text{Elect}(K_>) = \bigcap_{\leq' \text{ total extension of } \leq} \text{nd}(K_>)$.

- $\text{PartialPR}(K_>) = \bigcap_{\leq' \text{ total extension of } \leq} \text{pind}(K_>)$.

The main “unique repair” that has been proposed in the general case of an arbitrary priority relation stems from abstract argumentation. Hence, we need to define the *grounded extension* of a SETAF. Given a (SET)AF $F = (\text{Args}, \rightsquigarrow)$, recall that the characteristic function of $F$ is defined by $\Gamma_F(A) = \{\alpha \mid \alpha \text{ is defended by } A\}$. Then $E \subseteq \text{Args}$ is a *complete extension* iff $E$ is conflict-free and $E = \Gamma_F(E)$, and the *grounded extension* of $F$ is the $\subseteq$-minimal complete extension, or equivalently, the least fixpoint of $\Gamma_F$.

**► Definition 75 (Unique repairs based on an arbitrary priority relation [30]).** Let $K_>$ be a prioritized KB (or database with anti-monotone ICs).

- The grounded repair of $K_>$, grounded($K_>$), is the grounded extension of the PSETAF $F_{K,>}$, associated with $K_>$ (cf. Section 5.2.2.1).

- For $X \in \{C, G, P\}$, the analogue of $\text{pind}(K_>)$ is $\bigcap_{R \in X-Rep(K_>)} R$.

Figure 3 shows the inclusion relationships between these types of repairs in the most specific case, when $>$ is induced by a prioritization. To obtain the relationships between repairs for preordered datasets, simply remove from the picture those that are not defined in this case.
<figure><img src="image_15.png" /></figure>

POLYNOMIAL COMPUTATION: given the conflict hypergraph and $>$, the repair can be computed in polynomial time
$\Rightarrow$ holds for all but $pind(K_>)$

COMPLETE W.R.T. ISOLATED VERTICES: contains all facts that do not belong to any conflict (i.e., includes $R \cap = \bigcap_{R \in S-Rep(K)} R$) $\Rightarrow$ holds for all but $\pi(K_>$), $\ell(K_>$)

SOUND W.R.T. PRIORITIZED INTERSECTION: included in the intersection of optimal repairs
$\Rightarrow$ holds for all but $\ell(K_>$), $\ellnd(K_>$)

■ **Figure 3** (left) Relationships between “unique repairs” when $>$ is induced by a prioritization of the dataset [24, 22, 30]. An arrow $X \to Y$ means that $X \subseteq Y$. (right) Relevant properties [24, 30].

Finally, for arbitrary priority relations, it holds that $grounded(K_>) \subseteq \bigcap_{R \in P-Rep(K_>)} R \subseteq \bigcap_{R \in G-Rep(K_>)} R \subseteq \bigcap_{R \in C-Rep(K_>)} R$ (the last two inclusions directly come from the relationship between completion-, globally- and Pareto-optimal repairs). Figure 3 also indicates relevant properties these repairs may have. In particular, they can be computed in polynomial time when the conflict hypergraph is given, except for the intersections of optimal repairs. We conclude with an example to illustrate the difference between all these “unique repairs”.

► **Example 76.** Assume that $K = (\mathcal{D}, \mathcal{T})$ has the conflict graph depicted below and let $P = (\mathcal{P}_1, \mathcal{P}_2, \mathcal{P}_3, \mathcal{P}_4)$ be the prioritization of $\mathcal{D}$ defined by: $\mathcal{P}_1 = \{\alpha, \beta, \gamma\}$, $\mathcal{P}_2 = \{\delta, \epsilon, \zeta\}$, $\mathcal{P}_3 = \{\eta, \theta, \kappa\}$, $\mathcal{P}_4 = \{\lambda, \mu\}$. Arrows on the conflict graph indicate the priority relation $>$ induced by $P$. The optimal repairs $(\subseteq_P-Rep(K_>))$ and “unique repairs” are given below. This example shows that all inclusions given in Figure 3 can be strict and that $\pi(K_>)$ and $\ell(K_>)$ do not satisfy COMPLETE W.R.T. ISOLATED VERTICES, since they do not contain $\mu$, while $\ell(K_>)$ and $\ellnd(K_>)$ do not satisfy SOUND W.R.T. PRIORITIZED INTERSECTION, since they contain $\eta$ which does not belong to the intersection of the optimal repairs (actually, $\eta$ does not belong to any of the optimal repairs).

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

$$
\begin{align*}
\subseteq_P-Rep(K_>) &= \left\{ \begin{array}{@{}l@{}} \alpha, \gamma, \delta, \theta, \lambda, \mu \\ \alpha, \gamma, \epsilon, \theta, \lambda, \mu \\ \beta, \gamma, \delta, \theta, \lambda, \mu \\ \beta, \gamma, \epsilon, \theta, \lambda, \mu \end{array} \right\} &
pind(K_>) &= \{\gamma, \theta, \lambda, \mu\} \\
grounded(K_>) &= \{\gamma, \theta, \mu\} &
nd(K_>) &= \{\gamma, \mu\} \\
\pi(K_>) &= \emptyset &
\ell(K_>) &= \{\eta, \theta, \kappa\} \\
\ellnd(K_>) &= \{\gamma, \eta, \theta, \mu\} &
\end{align*}
$$

► **Remark 77.** It is easy to define variants of $\pi(K_>)$ and $\ell(K_>)$ that satisfy COMPLETE W.R.T. ISOLATED VERTICES: simply start by modifying the prioritization to add a level of highest priority that contains all facts that do not belong to any conflict.

5.4.3 Soft repairs for weighted constraints

In the database setting, *soft constraints*, which are expected to generally hold in the dataset but not necessarily in a perfect manner, have been considered. In this context, weights are used to represent the cost of deleting some fact or violating some constraint [60].
**► Definition 78** (Soft repairs of a database with anti-monotone constraints [60]). Let $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$ be a database where $\mathcal{T}$ is a set of anti-monotone ICs and let $w: \mathcal{D} \cup \mathcal{T} \to \mathbb{N} \cup \{\infty\}$. A soft repair of $\mathcal{D}$ w.r.t. $\mathcal{T}$ is a dataset $\mathcal{R} \subseteq \mathcal{D}$ such that

$$ \text{cost}_{\mathcal{K}}^{w}(\mathcal{R}) = \sum_{\alpha \in \mathcal{D} \setminus \mathcal{R}} w(\alpha) + \sum_{\tau \in \mathcal{T}} w(\tau) |\text{Conf}(\mathcal{R}, \{\tau\})| $$
is minimal, i.e., there is no $\mathcal{R}' \subseteq \mathcal{D}$ such that $\text{cost}_{\mathcal{K}}^{w}(\mathcal{R}') < \text{cost}_{\mathcal{K}}^{w}(\mathcal{R})$.

Soft repairs are not dataset repairs since they may be $\mathcal{T}$-inconsistent. However, they generalize $\leq_w$-optimal repairs.

**► Proposition 79** ([60]). If $w$ is a function that assigns a positive weight to each fact of $\mathcal{D}$, then $\leq_w$-Rep($\mathcal{D}, \mathcal{T}$) is equal to the set of soft repairs of $\mathcal{D}$ w.r.t. $\mathcal{T}$ using $w'$ where $w'(\tau) = \infty$ for each $\tau \in \mathcal{T}$ and $w'(\alpha) = w(\alpha)$ for each $\alpha \in \mathcal{D}$.

The generalization of soft constraints to DL KBs does not give rise to “soft repairs” but rather to “soft models”, since the optimization is done at the level of the interpretation instead of the dataset [36]. In this context, the cost of an interpretation $\mathcal{I}$ is $\text{cost}_{\mathcal{K}}^{w}(\mathcal{I}) = \sum_{\alpha \in \mathcal{D}, \mathcal{I} \neq \alpha} w(\alpha) + \sum_{\tau \in \mathcal{T}} w(\tau) |\text{vio}_{\tau}(\mathcal{I})|$ with $\text{vio}_{\mathcal{C} \subseteq \mathcal{D}}(\mathcal{I}) = (C \sqcap \neg \mathcal{D})^{\mathcal{I}}$ for every concept inclusion $\mathcal{C} \subseteq \mathcal{D}$. Interpretations with minimal (or bounded) cost are then used to define variants of the certain and possible semantics.

# 6 Computational complexity of reasoning with (preferred) repairs

In this section, we present some complexity results on the following decision problems:

- Repair checking takes as input a database or KB $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$ and a dataset $\mathcal{R}$, and outputs “yes” if $\mathcal{R}$ is a (preferred) repair of $\mathcal{K}$, and “no” otherwise;

- BCQ entailment under CQA (resp. intersection, brave) semantics takes as input a database or KB $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$ and a BCQ $q$ and output “yes” if $\mathcal{K}$ entails $q$ under the (preferred repair-based) CQA (resp. intersection, brave) semantics, and “no” otherwise.

We focus on these three semantics since CQA is the most studied inconsistency-tolerant semantics and intersection and brave provide the most and least cautious under- and over-approximations (cf. Figure 2). The complexity of reasoning under most of the other inconsistency-tolerant semantics mentioned in Section 4.1 is summarized in [28, Fig. 3] for DL-Lite KBs, with more details in [29]. Other relevant tasks that received significant attention include, e.g., the problem of enumerating the (preferred) repairs, counting them, or deciding whether there is a unique preferred repair [93, 30, 101].

## 6.1 The case of standard repairs

We first present the complexity of reasoning with standard dataset repairs.

### 6.1.1 Repair checking

Table 4 shows the data and combined complexity of repair checking (in the database case we focus on $\Delta$-repairs but the complexity of $\subseteq$- and $\supseteq$-repair checking has also been studied [4, 130]). In Table 4, results for Datalog$^{\pm}$ and database ICs are mainly taken from [107, Table 3] and [11, Table 3], respectively, where the interested reader can find results for different complexity measures, additional languages, and proofs or pointers to the literature. Propositions 80, 81 and 82 state the results for DLs and refined data complexity results for Datalog$^{\pm}$. Most of these results are known but they are not always explicitly stated in the literature, and the proofs illustrate the use of classical algorithms.
<table><caption>Table 4 Complexity of repair checking. All non-"in" entries are completeness results.</caption><thead><tr><th></th><th></th><th></th><th>Data complexity</th><th colspan="2">Combined complexity</th></tr></thead><tbody><tr><td rowspan="4">DLs<br>S-Rep(K)</td><td>DL-Lite<sub>R</sub></td><td>in L</td><td rowspan="2">Prop. 82</td><td>NL</td><td>Prop. 82</td></tr><tr><td>DL-Lite<sub>R,∩</sub></td><td>in L</td><td>P</td><td rowspan="2">Prop. 81</td></tr><tr><td>E<sub>L</sub><sub>⊥</sub></td><td>P</td><td>P</td></tr><tr><td>ALC</td><td>DP</td><td rowspan="2">Prop. 80</td><td>EXP</td><td rowspan="2">Prop. 80</td></tr><tr><td>SHIQ</td><td>DP</td><td>EXP</td></tr><tr><td rowspan="5">Datalog<sup>±</sup><br>S-Rep(K)</td><td>L<sub>⊥</sub></td><td>in L</td><td rowspan="2">Prop. 82</td><td>P<sub>SPACE</sub></td><td rowspan="5">[107, Tab. 3]</td></tr><tr><td>A<sub>⊥</sub></td><td>in L</td><td>D<sub>EXP</sub></td></tr><tr><td>G<sub>⊥</sub></td><td>P</td><td>Prop. 81</td><td>2<sub>EXP</sub></td></tr><tr><td>S<sub>⊥</sub></td><td>in L</td><td>Prop. 82</td><td>EXP</td></tr><tr><td>F<sub>⊥</sub></td><td>P</td><td>Prop. 81</td><td>EXP</td></tr><tr><td rowspan="2">ICs<br>S-Rep(K)</td><td>FD</td><td>in L</td><td rowspan="2">[11, Tab. 3]</td><td>in L</td><td rowspan="2">[11, Tab. 3]</td></tr><tr><td>DC</td><td>in L</td><td>DP</td></tr><tr><td rowspan="3">ICs<br>S-Rep<sub>Δ</sub>(K)</td><td>full TGD</td><td>P</td><td rowspan="3">[11, Tab. 3]</td><td>DP</td><td rowspan="3">[11, Tab. 3]</td></tr><tr><td>UC</td><td>coNP</td><td>Π<sub>2</sub><sup>P</sup></td></tr><tr><td>TGD</td><td>coNP</td><td>Π<sub>3</sub><sup>P</sup></td></tr></tbody></table>

**Algorithms for repair checking.** The complexity upper bounds are shown using two classical algorithms for repair checking. Let $K = \langle D, T \rangle$ be a KB or a database and $R$ be a dataset (repair candidate). The non-deterministic algorithm is as follows:

1. check that $\langle R, T \rangle \not= \perp$,

2. check that $R$ minimally differs from $D$ by considering the complement (co-2): to show that $R$ does not minimally differ from $D$, guess $R'$ such that $\langle R', T \rangle \not= \perp$ and $R'\Delta D \subseteq R\Delta D$. The deterministic algorithm works for KBs or databases with anti-monotone ICs, since in these cases, $R$ must be a subset of $D$ and is not maximal iff there is an immediate superset of $R$ in $D$ which is $T$-consistent:

1. check that $R \subseteq D$ and that $\langle R, T \rangle \not= \perp$,

2. check that $R$ is maximal by checking that for each $\alpha \in D \setminus R$, $\langle R \cup \{\alpha\}, T \rangle \models \perp$.

**Basic lower bounds.** Complexity lower bounds for consistency checking (Table 3) immediately transfer to repair checking since $D$ is a repair of $\langle D, T \rangle$ iff $D$ is $T$-consistent.

**Proposition 80 (ALC and SHIQ).** For ALC and SHIQ, repair checking is DP-complete w.r.t. data complexity, and EXP-complete w.r.t. combined complexity.

**Proof.** The combined complexity upper bound follows from the deterministic algorithm for repair checking and the fact that consistency checking is in EXP. The matching lower bound comes from the EXP-hardness of consistency checking.

For the data complexity upper bound, we use the non-deterministic algorithm. Since consistency checking is in NP, step 1 can be done with a call to an NP oracle and step 2 with a call to a coNP oracle: indeed, (co-2) is in NP since we can guess a certificate of polynomial size that consists of (i) $R' \subseteq D$ and (ii) a certificate that $\langle R', T \rangle \not= \perp$, and check this certificate in P. We obtain the DP lower bound via a reduction from the DP-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 can use truth constants true (1) and false (0) instead of variables (this is w.l.o.g. since 2+2SAT is NP-complete [128]). Let $\varphi_1$ and $\varphi_2$ be two sets of clauses $\{c_1^1, \dots, c_{m_1}^1\}$ and $\{c_1^2, \dots, c_{m_2}^2\}$ over variables $x_1^1, \dots, x_{n_1}^1$ and $x_1^2, \dots, x_{n_2}^2$ (and truth values 1, 0), respectively. We define an $\mathcal{ALC}$ KB $\mathcal{K} = (\mathcal{D}, \mathcal{T})$ by:

$$ \mathcal{T} = \{V \sqsubseteq T \sqcup F, T \sqcap F \sqsubseteq \bot, \exists P_1.F \sqcap \exists P_2.F \sqcap \exists N_1.T \sqcap \exists N_2.T \sqsubseteq F, \exists Cl.F \sqsubseteq F\} $$

and $\mathcal{D} = \mathcal{D}_1 \cup \mathcal{D}_2 \cup \{F(0), T(1)\}$ with:

$$ \begin{aligned} \mathcal{D}_i = & \{T(\varphi_i)\} \cup \{Cl(\varphi_i, c_k^i) \mid 1 \le k \le m_i\} \cup \{V(x_j^i) \mid 1 \le j \le n_i\} \cup \\ & \{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 \\ & \{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\} \end{aligned} $$

We claim that $\mathcal{D} \setminus \{T(\varphi_2)\} \in \mathcal{S-Rep}(\mathcal{K})$ iff $\varphi_1$ is satisfiable and $\varphi_2$ is unsatisfiable. Indeed, it is easy to show that for $i \in \{1, 2\}$, $\mathcal{D}_i \cup \{F(0), T(1)\}$ is $\mathcal{T}$-consistent iff $\varphi_i$ is satisfiable, since there is a one-to-one correspondence between models of $\langle \mathcal{D}_i \cup \{F(0), T(1)\}, \mathcal{T} \rangle$, which assign each $x_j^i$ to $T$ or $F$ in a way that does not enforce any $c_k^i$ to be assigned to $F$, and valuations of the $x_j^i$'s that satisfy $\varphi_i$. Moreover, $\mathcal{D}_i \cup \{F(0), T(1)\} \setminus \{T(\varphi_i)\}$ is $\mathcal{T}$-consistent, since in this case there is a model that assigns all individuals but 1 to $F$. Since $\mathcal{D}_1$ and $\mathcal{D}_2$ are disjoint, the claim follows easily. $\quad \blacksquare$

**► Proposition 81 (P bounds).** For all ontology languages from Table 4 but $\mathcal{ALC}$ and $\mathcal{SHIQ}$, repair checking is in P w.r.t. data complexity. Matching lower bounds hold for $\mathcal{EL}_{\perp}$, $\mathcal{G}_{\perp}$ and $\mathcal{F}_{\perp}$. For $\mathcal{DL-Lite}_{\mathcal{R}}$, $\mathcal{DL-Lite}_{\mathcal{R}, \sqcap}$ and $\mathcal{EL}_{\perp}$, repair checking is also in P w.r.t. combined complexity. Matching lower bounds hold for $\mathcal{DL-Lite}_{\mathcal{R}, \sqcap}$ and $\mathcal{EL}_{\perp}$.

**Proof.** For the upper bounds, we use the deterministic algorithm and the fact that consistency checking is in P for the considered languages and complexity measures. The lower bounds come from P-hardness of consistency checking in data or combined complexity. $\quad \blacksquare$

**► Proposition 82 (Below P).** Repair checking is in L w.r.t. data complexity for $\mathcal{DL-Lite}_{\mathcal{R}}$, $\mathcal{DL-Lite}_{\mathcal{R}, \sqcap}$, $\mathcal{L}_{\perp}$, $\mathcal{A}_{\perp}$ and $\mathcal{S}_{\perp}$, and NL-complete w.r.t. combined complexity for $\mathcal{DL-Lite}_{\mathcal{R}}$.

**Proof.** For the data complexity upper bound, the $\mathcal{DL-Lite}_{\mathcal{R}}$ and $\mathcal{DL-Lite}_{\mathcal{R}, \sqcap}$ cases follow from the $\mathcal{S}_{\perp}$ case (cf. Figure 1). For $\mathcal{L}_{\perp}$, $\mathcal{A}_{\perp}$ and $\mathcal{S}_{\perp}$, we use a data-independent reduction from repair checking in any of these languages to repair checking for a database with DCs, which is in L w.r.t. data complexity (cf. Table 4). Indeed, by Proposition 7, since $\mathcal{L}$, $\mathcal{A}$ and $\mathcal{S}$ are UCQ-rewritable (Fact 5), for every ontology $\mathcal{T}$, there exists a BUCQ $q_{\perp}^{\mathcal{T}}$ such that for every dataset $\mathcal{B}$, $\langle \mathcal{B}, \mathcal{T} \rangle \models \bot$ iff $\mathcal{I}_{\mathcal{B}} \models q_{\perp}^{\mathcal{T}}$ iff $\langle \mathcal{B}, \mathcal{T}_{\mathcal{DC}} \rangle \models \bot$, where $\mathcal{T}_{\mathcal{DC}}$ is the set of DCs that contains $q \to \bot$ for each BCQ $q$ in $q_{\perp}^{\mathcal{T}}$. Hence, $\mathcal{R} \in \mathcal{S-Rep}(\mathcal{D}, \mathcal{T})$ iff $\mathcal{R} \in \mathcal{S-Rep}(\mathcal{D}, \mathcal{T}_{\mathcal{DC}})$.

Regarding the combined complexity for $\mathcal{DL-Lite}_{\mathcal{R}}$, the lower bound comes from the NL-hardness of consistency checking. For the upper bound, observe that since consistency checking is in NL w.r.t. combined complexity, and NL = coNL, inconsistency checking is also in NL. The deterministic algorithm for repair checking can thus be adapted as follows: guess a certificate that consists of (i) a certificate that $\langle \mathcal{R}, \mathcal{T} \rangle \not\models \bot$ and (ii) certificates that $\langle \mathcal{R} \cup \{\alpha\}, \mathcal{T} \rangle \models \bot$ for each $\alpha \in \mathcal{D} \setminus \mathcal{R}$. The certificate is of polynomial size and can be verified by a deterministic logarithmic-space bounded Turing machine that has an additional read-only read-once input tape, since each certificate from (i)-(ii) is of polynomial size and verifiable by such a machine, and all certificates can be verified independently. $\quad \blacksquare$
<table><caption>■ Table 5 Complexity of BCQ entailment under CQA, intersection, and brave semantics. All non-"in" entries are completeness results (except undecidability results).</caption><thead><tr><th rowspan="2"></th><th rowspan="2"></th><th colspan="3">Data complexity</th><th colspan="3">Combined complexity</th></tr><tr><th>CQA</th><th>Int.</th><th>brave</th><th>CQA</th><th>Int.</th><th>brave</th></tr></thead><tbody><tr><td rowspan="5">DLs<br>S-Rep(K)</td><td>DL-Lite<sub>R</sub></td><td>coNP</td><td>in AC<sup>0</sup></td><td>in AC<sup>0</sup></td><td>Π<sub>2</sub><sup>P</sup></td><td>NP</td><td>NP</td></tr><tr><td>DL-Lite<sub>R,∩</sub></td><td>coNP</td><td>in AC<sup>0</sup></td><td>in AC<sup>0</sup></td><td>Π<sub>2</sub><sup>P</sup></td><td>Θ<sub>2</sub><sup>P</sup></td><td>NP</td></tr><tr><td>EL<sub>⊥</sub></td><td>coNP</td><td>coNP</td><td>NP</td><td>Π<sub>2</sub><sup>P</sup></td><td>Θ<sub>2</sub><sup>P</sup></td><td>NP</td></tr><tr><td>ALC</td><td>Π<sub>2</sub><sup>P</sup></td><td>Π<sub>2</sub><sup>P</sup></td><td>Σ<sub>2</sub><sup>P</sup></td><td>EXP</td><td>EXP</td><td>EXP</td></tr><tr><td>SHIQ</td><td>Π<sub>2</sub><sup>P</sup></td><td>Π<sub>2</sub><sup>P</sup></td><td>Σ<sub>2</sub><sup>P</sup></td><td>2EXP</td><td>2EXP</td><td>2EXP</td></tr><tr><td rowspan="5">Datalog<sup>±</sup><br>S-Rep(K)</td><td>L<sub>⊥</sub></td><td>coNP</td><td>in AC<sup>0</sup></td><td>in AC<sup>0</sup></td><td>PSPACE</td><td>PSPACE</td><td>PSPACE</td></tr><tr><td>A<sub>⊥</sub></td><td>coNP</td><td>in AC<sup>0</sup></td><td>in AC<sup>0</sup></td><td>P<sup>NEXP</sup></td><td>P<sup>NEXP</sup></td><td>P<sup>NEXP</sup></td></tr><tr><td>G<sub>⊥</sub></td><td>coNP</td><td>coNP</td><td>NP</td><td>2EXP</td><td>2EXP</td><td>2EXP</td></tr><tr><td>S<sub>⊥</sub></td><td>coNP</td><td>in AC<sup>0</sup></td><td>in AC<sup>0</sup></td><td>EXP</td><td>EXP</td><td>EXP</td></tr><tr><td>F<sub>⊥</sub></td><td>coNP</td><td>coNP</td><td>NP</td><td>EXP</td><td>EXP</td><td>EXP</td></tr><tr><td rowspan="2">ICs<br>S-Rep(K)</td><td>FD</td><td>coNP</td><td>in AC<sup>0</sup></td><td>in AC<sup>0</sup></td><td>Π<sub>2</sub><sup>P</sup></td><td></td><td></td></tr><tr><td>DC</td><td>coNP</td><td>in AC<sup>0</sup></td><td>in AC<sup>0</sup></td><td>Π<sub>2</sub><sup>P</sup></td><td></td><td></td></tr><tr><td rowspan="3">ICs<br>S-Rep<sub>Δ</sub>(K)</td><td>full TGD</td><td>coNP</td><td>coNP</td><td>P</td><td>EXP</td><td></td><td></td></tr><tr><td>UC</td><td>Π<sub>2</sub><sup>P</sup></td><td>Π<sub>2</sub><sup>P</sup></td><td>Σ<sub>2</sub><sup>P</sup></td><td>Π<sub>2</sub><sup>EXP</sup></td><td></td><td></td></tr><tr><td>TGD</td><td>undec.</td><td></td><td></td><td>undec.</td><td></td><td></td></tr></tbody></table>

### 6.1.2 BCQ entailment under CQA, intersection, and brave semantics

Table 5 shows the data and combined complexity of deciding BCQ entailment under the CQA, intersection, and brave semantics. The results given in Table 5 are taken from:

- [11, Tab. 1] for the CQA semantics over databases with ICs,

- [104, Tab. 2, 3 & 6] for the CQA and intersection semantics over Datalog<sup>±</sup> KBs,

- [29, Fig. 2, 3 & 4] for DL-Lite<sub>R</sub>, EL<sub>⊥</sub> and ALC, [41, Th. 3 & Fig. 1] for DL-Lite<sub>R,∩</sub>, and [126, Fig. 2] for SHIQ (plus straightforward upper bound for brave).

The complexity of BCQ entailment under the intersection and brave semantics over databases and brave semantics in Datalog<sup>±</sup> has not been systematically investigated. In the remaining of this section, we present some classical algorithms for BCQ entailment under the three semantics and provide proofs for the few new results on Datalog<sup>±</sup> and databases (for which we consider data complexity, on which we focus in the next section on preferred repairs).

**Classical algorithms.** Most upper complexity bounds are shown using the non-deterministic versions of Algorithms 1, 2 and 3, where one guesses a repair that does not entail the query to show that it does not hold under CQA semantics, a repair that entails the query to show that it holds under brave semantics, and the appropriate *B* and *R*<sub>1</sub>, ..., *R*<sub>*n*</sub> to show that the query is not entailed under intersection semantics. Note that in the case of brave semantics, since every *T*-consistent subset of *D* can be extended into a standard repair, it is sufficient to check that ⟨R, T⟩ ≠ ⊥ instead of R ∈ S-Rep(K) in Algorithm 2 when X = S. These algorithms can be adapted for semantics based on Δ-repairs of databases with UCs, by considering subsets of *Facts*<sub>*D*</sub><sup>*T*</sup> (whose size is exponential w.r.t. the maximal arity of the predicates in *T* and polynomial w.r.t. the size of *D*) instead of subsets of *D*. This does not extend to ICs with existential quantifiers in the head such as TGDs, since in this case repairs may use constants that do not occur in K.
**Algorithm 1 X-CQA**

**Input:** a KB or database with anti-monotone ICs $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$ and a BCQ $q$

**Output:** true iff $\mathcal{K}$ entails $q$ under CQA semantics based on $X-\text{Rep}(\mathcal{K})$

for $\mathcal{R} \subseteq \mathcal{D}$ do

if $\mathcal{R} \in X-\text{Rep}(\mathcal{K})$ and $\langle \mathcal{R}, \mathcal{T} \rangle \not\models q$ then

return false

return true

**Algorithm 2 X-brave**

**Input:** a KB or database with anti-monotone ICs $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$ and a BCQ $q$

**Output:** true iff $\mathcal{K}$ entails $q$ under brave semantics based on $X-\text{Rep}(\mathcal{K})$

for $\mathcal{R} \subseteq \mathcal{D}$ do

if $\mathcal{R} \in X-\text{Rep}(\mathcal{K})$ and $\langle \mathcal{R}, \mathcal{T} \rangle \models q$ then

return true

return false

When the conflicts can be computed efficiently, Algorithm 4 provides an efficient way of deciding BCQ entailment under intersection semantics.

**Basic lower bounds.** Complexity lower bounds for BCQ entailment under the classical semantics (Table 2) immediately transfer to BCQ entailment under CQA, intersection and brave semantics. Indeed, the hardness results for BCQ entailment under the classical semantics hold in the case where $\mathcal{D}$ is assumed to be $\mathcal{T}$-consistent, and in this case the classical, CQA, intersection and brave semantics all coincide.

**AC⁰ upper bounds.** The AC⁰ upper bounds in Table 5 follow from the following result [41].

**► Proposition 83** ([41, Theorems 1, 2, 3]). If CQ answering under $\mathcal{L}$ is FO-rewritable and for every ontology $\mathcal{T}$ in $\mathcal{L}$ and BCQ $q$, there exist $\ell$ and $m$ such that for every $\mathcal{D}$, (i) every minimal $\mathcal{T}$-consistent subset $\mathcal{S}$ of $\mathcal{D}$ such that $\langle \mathcal{S}, \mathcal{T} \rangle \models q$ has cardinality at most $\ell$ and (ii) every conflict of $\langle \mathcal{D}, \mathcal{T} \rangle$ has cardinality at most $m$, then CQ answering under the intersection and brave semantics in $\mathcal{L}$ is FO-rewritable: for every ontology $\mathcal{T}$ and BCQ $q$, there exists an FO-sentence $\varphi_{\mathcal{T},q}^{\cap}$ (resp. $\varphi_{\mathcal{T},q}^{\text{brave}}$) such that for every $\mathcal{D}$, $q$ is entailed by $\langle \mathcal{D}, \mathcal{T} \rangle$ under intersection (resp. brave) semantics iff $\mathcal{I}_{\mathcal{D}} \models \varphi_{\mathcal{T},q}^{\cap}$ (resp. $\mathcal{I}_{\mathcal{D}} \models \varphi_{\mathcal{T},q}^{\text{brave}}$).

**► Corollary 84** (AC⁰ bounds). BCQ entailment under intersection and brave semantics is in AC⁰ w.r.t. data complexity for DL-Lite<sub>R</sub>, DL-Lite<sub>R,∩</sub>, L<sub>⊥</sub>, A<sub>⊥</sub>, S<sub>⊥</sub>, FDs and DCs.

**Algorithm 3 X-intersection**

**Input:** a KB or database with anti-monotone ICs $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$ and a BCQ $q$

**Output:** true iff $\mathcal{K}$ entails $q$ under intersection semantics based on $X-\text{Rep}(\mathcal{K})$

for $\mathcal{B} \subseteq \mathcal{D}$ with $\mathcal{B} = \{\alpha_1, \dots, \alpha_n\}$ do

for $\mathcal{R}_1 \subseteq \mathcal{D}, \dots, \mathcal{R}_n \subseteq \mathcal{D}$ such that $\alpha_i \notin \mathcal{R}_i$ ($1 \le i \le n$) do

if $\mathcal{R}_i \in X-\text{Rep}(\mathcal{K})$ for $1 \le i \le n$ and $\langle \mathcal{D} \setminus \mathcal{B}, \mathcal{T} \rangle \not\models q$ then

return false

return true
**Algorithm 4** Intersection semantics from conflicts

**Input:** a KB or database with anti-monotone ICs $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$ and a BCQ $q$

**Output:** true iff $\mathcal{K}$ entails $q$ under (plain) intersection semantics

if $\langle \mathcal{T}, \mathcal{D} \setminus \bigcup_{C \in \text{Conf}(\mathcal{K})} \mathcal{C} \rangle \models q$ **then**
return true
return false

**Proof.** These languages satisfy the conditions of Proposition 83. Indeed, CQ answering is UCQ-rewritable (cf. Fact 5), hence FO-rewritable and:

(i) for DCs (hence also FDs) the size of minimal $\mathcal{T}$-consistent subsets $\mathcal{S}$ of $\mathcal{D}$ such that $\langle \mathcal{S}, \mathcal{T} \rangle \models q$ is bounded by $|q|$, and for $L_\perp, A_\perp$ and $S_\perp$ (hence also DL-Lite$_R$ and DL-Lite$_{R,\perp}$), it is bounded by the maximal number of atoms in some BCQ in $\text{Rew}(q, \mathcal{T})$;

(ii) for DCs (hence also FDs) the size of conflicts is bounded by the maximal number of atoms in some DC body, and for $L_\perp, A_\perp$ and $S_\perp$ (hence also DL-Lite$_R$ and DL-Lite$_{R,\perp}$), by Proposition 7, for every ontology $\mathcal{T}$, there exists a BUCQ $q_\perp^\mathcal{T}$ such that for every dataset $\mathcal{D}$, $\langle \mathcal{D}, \mathcal{T} \rangle \models \perp$ iff $\mathcal{I}_\mathcal{D} \models q_\perp^\mathcal{T}$ so the size of conflicts is bounded by the maximal number of atoms in some BCQ of $q_\perp^\mathcal{T}$.

Example 85 illustrates why Proposition 83 does not apply to the other ontology languages considered in Table 5: the size of the conflicts cannot be bounded independently from $\mathcal{D}$.

**► Example 85.** Let $\mathcal{T} = \{R(x, y) \wedge A(x) \rightarrow A(y), A(x) \wedge B(x) \rightarrow \perp\}$, which belongs to $F_\perp$, $G_\perp$ and $\mathcal{EL}_\perp$. For every $n \ge 1$, we can build a dataset $\mathcal{D}$ of size $n+2$ which is a conflict (of itself) w.r.t. $\mathcal{T}: \mathcal{D} = \{A(a_0), R(a_0, a_1), \dots, R(a_{n-1}, a_n), B(a_n)\}$.

Note that if we interpret $\mathcal{T}$ as a set of UCs in Example 85, it also shows that the size of the conflicts cannot be bounded independently from $\mathcal{D}$ for databases with UCs. It is actually undecidable to determine whether there exists $\ell \in \mathbb{N}$ such that for every dataset $\mathcal{D}$, $\max_{C \in \text{Conf}(\mathcal{D}, \mathcal{T})} |C| \le \ell$ when $\mathcal{T}$ is a set of full TGDs [32, Theorem 5]$^3$.

**Brave semantics in Datalog$^±$.** For brave semantics and Datalog$^±$, the $\mathbb{AC}^0$ upper bounds come from Corollary 84 and the other bounds in Table 5 follows easily from known results:

**► Proposition 86.** BCQ entailment under brave semantics is PSPACE-complete for $L_\perp$, P$^{NEXP}$-complete for $A_\perp$, 2EXP-complete for $G_\perp$, and EXP-complete for $S_\perp$ and $F_\perp$ w.r.t. combined complexity, and NP-complete for $G_\perp$ and $F_\perp$ w.r.t. data complexity.

**Proof.** The NP data complexity upper bounds follow from the non-deterministic version of Algorithm 2, since both repair checking and BCQ entailment are in P w.r.t. data complexity for $G_\perp$ and $F_\perp$. For the matching lower bound, we remark that the reduction used in the proof of NP-hardness of BCQ entailment under brave semantics in $\mathcal{EL}_\perp$ [29, Theorem 29] builds an ontology without existential on the right-hand side, which is thus in $G_\perp$ and $F_\perp$.

The 2EXP and EXP combined complexity upper bounds for $G_\perp$, $S_\perp$ and $F_\perp$ follow from Algorithm 2 (since repair checking and BCQ entailment are both in 2EXP or EXP, respectively) and the lower bounds from the respective combined complexity of BCQ entailment.

The PSPACE combined complexity upper bound for $L_\perp$ follows from the non-deterministic version of Algorithm 2, since repair checking and BCQ entailment are in PSPACE for $L_\perp$ and NPSPACE = PSPACE. The lower bound comes from that of BCQ entailment in $L_\perp$.

<footnote>$^3$ Theorem 5 in [32] is stated for universal constraints but the proof uses only full TGDs.</footnote>
The $P^{\text{NEXP}}$ combined complexity upper bound for $A_{\perp}$ follows from the non-deterministic version of Algorithm 2, since repair checking is in $\text{DEXP}$ and BCQ entailment in $\text{NEXP}$ for $A_{\perp}$, so that the “check” phase can be done in $P^{\text{NEXP}}$, and the fact that $\text{NP}^{\text{NEXP}} = P^{\text{NEXP}}$ [89, 104]. The lower bound follows from the reduction from the $P^{\text{NEXP}}$-hard extended exponential tiling problem used to show the lower bound for intersection semantics in [104, Theorem 6.2]: given an extended tiling system $\mathcal{E}$, a KB $\langle \mathcal{D}_{\mathcal{E}}, \mathcal{T}_{\mathcal{E}} \rangle$ is built such that $\mathcal{E}$ is valid iff $\text{Yes}()$ is entailed by $\langle \mathcal{D}_{\mathcal{E}}, \mathcal{T}_{\mathcal{E}} \rangle$ under intersection semantics, and since (i) $\text{Yes}() \in \mathcal{D}_{\mathcal{E}}$, (ii) $\text{Yes}()$ does not occur in the body of any TGD and (iii) the only NC that contains $\text{Yes}()$ is $\phi(\vec{x}) \wedge \text{Yes}() \wedge \text{No}() \to \perp$, it follows that $\mathcal{E}$ is valid iff $q = \exists \vec{x} \phi(\vec{x}) \wedge \text{No}()$ is not entailed under brave semantics. ◀

**Data complexity of brave and intersection semantics in databases.** For brave and intersection BCQ entailment over databases, the $\text{AC}^0$ upper bounds come from Corollary 84, the data complexity results for UCs are taken from [32, Tab. 1] (they follow from the proof of [32, Theorem 3]), and the other results given in Table 5 are proved below.

**► Proposition 87 (Full TGD).** For the IC language of full TGDs and data complexity, BCQ entailment under brave semantics is P-complete and BCQ entailment under intersection semantics is coNP-complete.

**Proof.** For brave semantics, we remark that for every database $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$ such that $\mathcal{T}$ is a set of full TGDs, for every BCQ $q$, $q$ is entailed by $\mathcal{K}$ under brave semantics iff $q$ is (classically) entailed by the F (a.k.a. Datalog) KB $\mathcal{K}_F = \langle \mathcal{D}, \mathcal{T} \rangle$. Indeed, it is known that for full TGDs, there exists a unique $\supseteq$-repair $\mathcal{R}$, which can be computed in polynomial time w.r.t. the size of the dataset via the chase procedure [130], and we can show that every $\mathcal{R}' \in \text{S-Rep}_{\Delta}(\mathcal{K})$ is such that $\mathcal{R}' \subseteq \mathcal{R}$. Since BCQ evaluation is monotone, it follows that there exists $\mathcal{R}' \in \text{S-Rep}_{\Delta}(\mathcal{K})$ such that $q$ holds in $\mathcal{R}'$ iff $q$ holds in $\mathcal{R}$. Finally, since $\mathcal{K}_F \models q$ iff $q$ holds in $\mathcal{R}$ (by the fixpoint semantics of Datalog, cf. [1, Sec. 12.3]), we obtain that $q$ is entailed by $\mathcal{K}$ under brave semantics iff $q$ is classically entailed by $\mathcal{K}_F$. The upper bound then follows from the fact that BCQ entailment in F is in P and the lower bound from the reduction that shows P-hardness of BCQ entailment in F [70, Th. 4.4].

For intersection semantics, the coNP upper bound follows from the non-deterministic version of Algorithm 3 (adapted for databases with UCs), since repair checking and BCQ entailment are in P and the repair size is polynomially bounded w.r.t. data complexity. For the lower bound, we use a reduction from UNSAT. Let $\varphi$ be a conjunction of clauses $c_1, \dots, c_m$ over variables $x_1, \dots, x_n$ and define $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$ by:

$$ 
\begin{aligned}
\mathcal{T} &= \{ \text{Next}(z_1, z_2) \wedge \text{Check}(z_2) \wedge \text{Pos}(z_2, x_1) \wedge \text{True}(x_1) \to \text{Check}(z_1), \\
& \quad \text{Next}(z_1, z_2) \wedge \text{Check}(z_2) \wedge \text{Neg}(z_2, x_1) \wedge \text{False}(x_1) \to \text{Check}(z_1), \\
& \quad \text{Check}(z_1) \wedge \text{Unsat}(z_1) \to \text{B}(z_1), \text{True}(x_1) \wedge \text{False}(x_1) \to \text{B}(z_1) \} \\
\mathcal{D} &= \{ \text{Unsat}(c_0) \} \cup \{ \text{Check}(c_m) \} \cup \{ \text{Next}(c_{j-1}, c_j) \mid 1 \le j \le m \} \cup \{ \text{Pos}(c_j, x_i) \mid x_i \in c_j \} \cup \\
& \quad \{ \text{Neg}(c_j, x_i) \mid \neg x_i \in c_j \} \cup \{ \text{True}(x_i), \text{False}(x_i) \mid 1 \le i \le n \}
\end{aligned}
$$

We claim that $\text{Unsat}(c_0)$ is entailed by $\mathcal{K}$ under intersection semantics iff $\varphi$ is unsatisfiable. Indeed, if there exists a valuation $\nu$ of $x_1, \dots, x_n$ that satisfies $\varphi$, the following dataset is a $\Delta$-repair of $\mathcal{D}$ w.r.t. $\mathcal{T}$, so $\text{Unsat}(c_0)$ does not hold under intersection semantics.

$$ 
\begin{aligned}
\mathcal{R}_{\nu} &= \{ \text{Check}(c_j) \mid 0 \le j \le m \} \cup \{ \text{Next}(c_{j-1}, c_j) \mid 1 \le j \le m \} \cup \{ \text{Pos}(c_j, x_i) \mid x_i \in c_j \} \cup \\
& \quad \{ \text{Neg}(c_j, x_i) \mid \neg x_i \in c_j \} \cup \{ \text{True}(x_i) \mid \nu(x_i) = 1 \} \cup \{ \text{False}(x_i) \mid \nu(x_i) = 0 \}
\end{aligned}
$$
In the other direction, if there is a $\Delta$-repair $\mathcal{R}$ of $\mathcal{D}$ w.r.t. $\mathcal{T}$ such that $\text{Unsat}(c_0) \notin \mathcal{R}$, then $\text{B}() \notin \mathcal{R}$ and $\text{Check}(c_0) \in \mathcal{R}$ (otherwise $\mathcal{R} \cup \{\text{Unsat}(c_0)\}$ would be $\mathcal{T}$-consistent). Since $\text{Check}(c_0) \in \mathcal{R}$, there must exist $x_i$ such that $\{\text{Next}(c_0, c_1), \text{Check}(c_1), \text{Pos}(c_1, x_i), \text{True}(x_i)\}$ or $\{\text{Next}(c_0, c_1), \text{Check}(c_1), \text{Neg}(c_1, x_i), \text{False}(x_i)\}$ is included in $\mathcal{R}$ (otherwise $\mathcal{R} \setminus \{\text{Check}(c_0)\}$ would be $\mathcal{T}$-consistent), and we can show that for every $1 \le j \le m$, there must exist $x_i$ such that either $\{\text{Next}(c_{j-1}, c_j), \text{Check}(c_j), \text{Pos}(c_j, x_i), \text{True}(x_i)\}$ or $\{\text{Next}(c_{j-1}, c_j), \text{Check}(c_j), \text{Neg}(c_j, x_i), \text{False}(x_i)\}$ is included in $\mathcal{R}$. Moreover, since $\text{B}() \notin \mathcal{R}$, for every $x_i$, either $\text{True}(x_i)$ or $\text{False}(x_i)$ does not belong to $\mathcal{R}$ so the valuation $\nu_{\mathcal{R}}$ defined by $\nu_{\mathcal{R}}(x_i) = 1$ iff $\text{True}(x_i) \in \mathcal{R}$ satisfies all clauses of $\varphi$. ◀

## 6.2 Reasoning with preferred repairs

In this section, we present the impact of using preferred repairs on the computational complexity. Table 6 shows the data complexity of reasoning with X-optimal repairs for $X \in \{\le, \le_w, \le_P, \subseteq_P, \text{Pareto}, \text{globally}, \text{completion}\}$, for languages for which repairs are $\subseteq$-repairs and consistency checking and BCQ entailment are in P. The lower bounds apply to languages that extend either $\text{DL-Lite}_{\text{core}}$, FD, or NC, yielding tight data complexity bounds for all semantics based on optimal repairs for $\text{DL-Lite}_{\text{core}}$, $\text{DL-Lite}_{\mathcal{R}}$, $\text{DL-Lite}_{\mathcal{R},\sqcap}$, $L_\perp$, $A_\perp$, $G_\perp$, $S_\perp$, $F_\perp$, FD and DC. Similarly, Table 7 shows the data complexity of reasoning with preference program-based prioritized KBs, for languages for which repairs are $\subseteq$-repairs and consistency checking and BCQ entailment are in P, but since such repairs have not been considered in as many settings as the others, we only report the lower bounds for the languages considered in the original paper [50]. For the results given in Table 6, we present the algorithms that yield the upper bounds [33, 107, 102, 129] and give references or show the lower bounds in Sections 6.2.1 and 6.2.2. We then discuss these results and mention some additional complexity results that do not fall into the setting considered in Table 6 (e.g., on combined complexity or for more expressive languages) in Section 6.2.3.

### 6.2.1 Repair checking

This section presents the proofs for the results on repair checking given in Table 6.

**► Proposition 88.** For every ontology language or anti-monotone IC language for which consistency checking and BCQ entailment are in P w.r.t. data complexity, the data complexity of repair checking is in coNP for X-optimal repairs for $X \in \{\le, \le_w, \le_P, \text{globally}\}$ and in P for X-optimal repairs for $X \in \{\subseteq_P, \text{Pareto}, \text{completion}\}$. Matching coNP lower bounds hold for every ontology language or IC language that extends $\text{DL-Lite}_{\text{core}}$, NC or FD.

**Upper bounds.** The upper bounds are obtained via Algorithms 5 to 9, using the non-deterministic versions of Algorithms 5 and 6 where one guesses an appropriate $B \subseteq \mathcal{D}$ to show that $\mathcal{R} \notin \text{X-Rep}(\mathcal{K})$. The correctness of the algorithms straightforwardly follows from the respective definitions of preferred repairs, except for the completion-optimal repair case, which was shown in [129, Corollary 4].

**Lower bounds.** The coNP lower bound for globally-optimal repair checking has been shown for a logical theory that contains four FDs [129, Theorem 2] as well as for a $\text{DL-Lite}_{\text{core}}$ ontology that contains only axioms that can be written as NCs [30, Theorem 10]. The coNP lower bound for $\le$-optimal repair checking (hence also for $\le_w$- and $\le_P$-optimal repair checking, since $\le$-optimal repairs can be obtained as special cases of $\le_w$- or $\le_P$-optimal repairs) has been shown for a logical theory that contains a single NC [103, Corollary 1].