**Table 6** Data complexity of repair checking and BCQ entailment under CQA, intersection, and brave semantics with $\leq$-optimal repairs, or Pareto-, globally- or completion-optimal repairs. Upper bounds hold for every ontology or anti-monotone IC language for which consistency checking and BCQ entailment are in P. Lower bounds hold for every language that extends either DL-Lite<sub>core</sub>, FD, or NC. †: $\Theta_2^P$ if there is a data-independent bound on the weights or number or priority levels.

<table><thead><tr><th></th><th>Repair checking</th><th>CQA</th><th>Intersection</th><th>Brave</th></tr></thead><tbody><tr><td>$\leq$-Rep($\mathcal{K}$)</td><td>coNP</td><td>$\Theta_2^P$</td><td>$\Theta_2^P$</td><td>$\Theta_2^P$</td></tr><tr><td>$\leq_w$-Rep($\mathcal{K}$)</td><td>coNP</td><td>$\Delta_2^P$<sup>†</sup></td><td>$\Delta_2^P$<sup>†</sup></td><td>$\Delta_2^P$<sup>†</sup></td></tr><tr><td>$\leq_P$-Rep($\mathcal{K}$)</td><td>coNP</td><td>$\Delta_2^P$<sup>†</sup></td><td>$\Delta_2^P$<sup>†</sup></td><td>$\Delta_2^P$<sup>†</sup></td></tr><tr><td>$\subseteq_P$-Rep($\mathcal{K}$)</td><td>in P</td><td>coNP</td><td>coNP</td><td>NP</td></tr><tr><td>$P$-Rep($\mathcal{K}_>$)</td><td>in P</td><td>coNP</td><td>coNP</td><td>NP</td></tr><tr><td>$C$-Rep($\mathcal{K}_>$)</td><td>in P</td><td>coNP</td><td>coNP</td><td>NP</td></tr><tr><td>$G$-Rep($\mathcal{K}_>$)</td><td>coNP</td><td>$\Pi_2^P$</td><td>$\Pi_2^P$</td><td>$\Sigma_2^P$</td></tr></tbody></table>

**Table 7** Data complexity of repair checking and BCQ entailment under CQA, intersection, and brave semantics with $\Pi_{\leq}$-preferred repairs. Upper bounds hold for every ontology or anti-monotone IC language for which consistency checking and BCQ entailment are in P. Lower bounds hold for all Datalog<sup>±</sup> fragments we consider [50] (note that [50] allows for constants in TGDs and NCs). The results for brave semantics are not explicitly given in [50] but both the upper and lower bounds can be obtained by adapting straightforwardly the proofs for the other semantics.

<table><thead><tr><th></th><th>Repair checking</th><th>CQA</th><th>Intersection</th><th>Brave</th></tr></thead><tbody><tr><td>$Pr \leq$-Rep($\mathcal{K}_{\Pi}$)</td><td>coNP</td><td>$\Pi_2^P$</td><td>$\Pi_2^P$</td><td>$\Sigma_2^P$</td></tr><tr><td>$Pr \leq$-Rep($\mathcal{K}_{\Pi}$)</td><td>coNP</td><td>$\Theta_2^P$</td><td>$\Theta_2^P$</td><td>$\Theta_2^P$</td></tr></tbody></table>

**Algorithm 5** $\leq$-optimal repair checking for $\leq \in \{\leq, \leq_w, \leq_P\}$

**Input:** $\mathcal{K} = \langle D, \mathcal{T} \rangle$ and $\mathcal{R} \subseteq D$ (and weight function $w$ or prioritization $P$ when relevant)

**Output:** true iff $\mathcal{R} \in \leq$-Rep($\mathcal{K}$)

for $B \subseteq D$ do

if $B$ is $\mathcal{T}$-consistent and $\mathcal{R} \prec B$ then

return false

return true

**Algorithm 6** Globally-optimal repair checking

**Input:** $\mathcal{K}_> = (\langle D, \mathcal{T} \rangle, >)$ and $\mathcal{R} \subseteq D$

**Output:** true iff $\mathcal{R} \in G$-Rep($\mathcal{K}_>$)

for $B \subseteq D$ such that $B \neq \mathcal{R}$ do

if $B$ is $\mathcal{T}$-consistent and $\forall \alpha \in \mathcal{R} \setminus B, \exists \beta \in B \setminus \mathcal{R}$ such that $\beta > \alpha$ then

return false

return true
■ **Algorithm 7** $\subseteq_P$-optimal repair checking

**Input:** $K = \langle D, \mathcal{T} \rangle$ with prioritization $P = \langle \mathcal{P}_1, \dots, \mathcal{P}_n \rangle$ and $\mathcal{R} \subseteq D$

**Output:** true iff $\mathcal{R} \in \subseteq_P \text{-Rep}(K)$

if $\mathcal{R}$ is not $\mathcal{T}$-consistent **then**
return false

for $1 \le i \le n$ and $\alpha \in (D \setminus \mathcal{R}) \cap \mathcal{P}_i$ **do**

if $\mathcal{R} \cap (\mathcal{P}_1 \cup \dots \cup \mathcal{P}_i) \cup \{\alpha\}$ is $\mathcal{T}$-consistent **then**
return false

return true

■ **Algorithm 8** Pareto-optimal repair checking

**Input:** $K_\succ = (\langle D, \mathcal{T} \rangle, \succ)$ and $\mathcal{R} \subseteq D$

**Output:** true iff $\mathcal{R} \in P-\text{Rep}(K_\succ)$

if $\mathcal{R}$ is not $\mathcal{T}$-consistent **then**
return false

for $\beta \in (D \setminus \mathcal{R})$ **do**

if $\mathcal{R} \cup \{\beta\} \setminus \{\alpha \mid \beta \succ \alpha\}$ is $\mathcal{T}$-consistent **then**
return false

return true

■ **Algorithm 9** Completion-optimal repair checking

**Input:** $K_\succ = (\langle D, \mathcal{T} \rangle, \succ)$ and $\mathcal{R} \subseteq D$

**Output:** true iff $\mathcal{R} \in C-\text{Rep}(K_\succ)$

if $\mathcal{R}$ is not $\mathcal{T}$-consistent **then**
return false

$D' \leftarrow D, \mathcal{R}' \leftarrow \emptyset$

while $S := \{\alpha \mid \alpha \in D', \forall \beta \in D', \beta \not\succ \alpha\} \neq \emptyset$ **do**

if $S \cap \mathcal{R} = \emptyset$ **then**
return false

choose $\alpha \in S \cap \mathcal{R}$

$\mathcal{R}' \leftarrow \mathcal{R}' \cup \{\alpha\}, D' \leftarrow D' \setminus (\{\alpha\} \cup \{\beta \mid (\mathcal{R}' \cup \{\beta\}, \mathcal{T}) \models \perp\})$

return true
We show next that it also holds for FD and for DL-Lite<sub>core</sub> (using only axioms that can be written as NCs) by two reductions from 3-SAT. Let $\varphi = c_1 \wedge \dots \wedge c_m$ be a conjunction of clauses of three literals over variables $x_1, \dots, x_n$.

For the FD case, define $K_{FD} = \langle D_{FD}, T_{FD} \rangle$ with

$$ 
\begin{aligned}
\mathcal{T}_{\text{FD}} = & \{ P(x_1, x_2, x_3, x_4, x_5) \wedge P(y_1, y_2, y_3, y_4, y_5) \wedge x_1 = y_1 \rightarrow x_2 = y_2, \\
& P(x_1, x_2, x_3, x_4, x_5) \wedge P(y_1, y_2, y_3, y_4, y_5) \wedge x_2 = y_2 \rightarrow x_3 = y_3, \\
& P(x_1, x_2, x_3, x_4, x_5) \wedge P(y_1, y_2, y_3, y_4, y_5) \wedge x_4 = y_4 \rightarrow x_5 = y_5 \}
\end{aligned}
$$

$$ D_{\text{FD}} = \{ P(c_j, x_i, 1, a, b) \mid x_i \in c_j, 1 \le j \le m \} \cup \{ P(c_j, x_i, 0, a, b) \mid \neg x_i \in c_j, 1 \le j \le m \} \\ \cup \{ P(d_j, e, f, a, c) \mid 1 \le j \le m-1 \} $$

We can show that $\mathcal{R} = \{P(d_j, e, f, a, c) \mid 1 \le j \le m-1\}$ is not a $\le$-optimal repair of $K_{FD}$ iff $\varphi$ is satisfiable. Indeed, $\mathcal{R}$ is $\mathcal{T}_{FD}$-consistent and $|\mathcal{R}| = m-1$, so $\mathcal{R} \notin \leq -\text{Rep}(K_{FD})$ iff there exists a $\mathcal{T}_{FD}$-consistent $\mathcal{R}' \subseteq D_{FD}$ of size at least $m$. Such $\mathcal{R}'$ necessarily contains only facts of the form $P(c_j, x_i, \dots, a, b)$ because of the last FD, so contains exactly $m$ facts because of the first two FDs. It is easy to check that the valuation $\nu$ of the $x_i$ defined by $\nu(x_i) = 1$ iff $\mathcal{R}'$ contains some $P(c_j, x_i, 1, a, b)$ satisfies every clause. In the other direction, every valuation that satisfies $\varphi$ can be used to build a repair of size $m$.

For the DL-Lite<sub>core</sub> (and NC) case, define $K_{DL} = \langle D_{DL}, T_{DL} \rangle$ with

$$ 
\begin{aligned}
\mathcal{T}_{\text{DL}} = & \{ \exists P_{\ell}^{-} \sqsubseteq \neg \exists N_{k}^{-} \mid 1 \le \ell, k \le 3 \} \cup \{ \exists U^{-} \sqsubseteq \neg \exists P_{\ell}, \exists U^{-} \sqsubseteq \neg \exists N_{\ell} \mid 1 \le \ell \le 3 \} \cup \\
& \{ S \sqsubseteq \neg \exists U \} \cup \{ \exists P_{\ell}^{-} \sqsubseteq \neg \exists P_{k}, \exists N_{\ell}^{-} \sqsubseteq \neg \exists N_{k}, \exists P_{\ell}^{-} \sqsubseteq \neg \exists N_{k} \mid 1 \le \ell \neq k \le 3 \}
\end{aligned}
$$

$$ D_{\text{DL}} = \{S(\varphi)\} \cup \{U(\varphi, c_j) \mid 1 \le j \le m\} \cup \{P_{\ell}(c_j, x_i) \mid x_i \text{ is the } \ell^{\text{th}} \text{ literal of } c_j\} \cup \{N_{\ell}(c_j, x_i) \mid \neg x_i \text{ is the } \ell^{\text{th}} \text{ literal of } c_j\} $$

We can show that $\mathcal{R} = \{U(\varphi, c_j) \mid 1 \le j \le m\}$ is not a $\le$-optimal repair of $K_{DL}$ iff $\varphi$ is satisfiable. Indeed, $\mathcal{R}$ is $\mathcal{T}_{DL}$-consistent and $|\mathcal{R}| = m$, so $\mathcal{R} \notin \leq -\text{Rep}(K_{DL})$ iff there exists a $\mathcal{T}_{DL}$-consistent $\mathcal{R}' \subseteq D_{DL}$ of size at least $m+1$. Since every repair of $K_{DL}$ contains at most one fact of the form $P_{\ell}(c_j, x_i)$ or $N_k(c_j, x_i)$ per $c_j$, and such fact prevents the corresponding $U(\varphi, c_j)$ to belong to the repair, the only way to obtain a repair of size $m+1$ is to select exactly one $P_{\ell}(c_j, x_i)$ or $N_k(c_j, x_i)$ per $c_j$, remove all $U(\varphi, c_j)$, and keep $S(\varphi)$. Since each $x_i$ cannot occur both in $P_{\ell}$- and $N_k$-facts, such repair $\mathcal{R}'$ corresponds to a valuation $\nu$ of the $x_i$ such that $\nu(x_i) = 1$ iff $\mathcal{R}'$ contains some $P_{\ell}(c_j, x_i)$ and it is easy to check that $\nu$ satisfies $\varphi$. In the other direction, every satisfying valuation can be used to build a repair of size $m+1$.

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

This section presents the proofs for the results on BCQ entailment under the different semantics given in Table 6.

**Proposition 89.** 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 BCQ entailment under CQA or intersection (resp. brave) with X-optimal repairs is in

coNP (resp. NP) for $X \in \{\subseteq_P, \text{Pareto, completion}\}$;

$\Pi_2^P$ (resp. $\Sigma_2^P$) for $X = \text{globally}$;

$\Delta_2^P$ for $X \in \{\leq_w, \leq_P\}$;

$\Theta_2^P$ for $X = \leq$ and for $X \in \{\leq_w, \leq_P\}$ if there is a data-independent bound on the weights or number of priority levels.

Matching lower bounds hold for every ontology language or IC language that extends DL-Lite<sub>core</sub>, NC or FD.
5:50 Inconsistency-Tolerant Semantics Based on (Preferred) Repairs

**Upper bounds.** For semantics based on X-optimal repairs with $X \in \{\subseteq_P, \text{Pareto}, \text{completion}\}$, since X-optimal repair checking is in P, the coNP and NP upper bounds for BCQ entailment under X-CQA, X-brave and X-intersection semantics follow from the non-deterministic versions of Algorithms 1, 2 and 3 for $X \in \{\subseteq_P, P, C\}$. Similarly, for semantics based on globally-optimal repairs, since globally-optimal repair checking is in coNP, the $\Pi_2^P$ and $\Sigma_2^P$ upper bounds for BCQ entailment under G-CQA, G-brave and G-intersection follow from these algorithms. For the other kinds of repairs, we use the reduction of $\leq$- and $\leq_P$-optimal repairs to $\leq_w$-optimal ones and Algorithms 11, 12 and 13 for semantics based on $\leq_w$-optimal repairs. These algorithms rely on an NP oracle to check the existence of $\mathcal{R} \subseteq \mathcal{D}$ as required both in the function OptimalWeightByBinarySearch (Algorithm 10) and the final condition.

■ Algorithm 10 OptimalWeightByBinarySearch

**Input:** $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$, a weight function $w: \mathcal{D} \to \mathbb{N}$

**Output:** the weight $u_{opt}$ of $\leq_w$-optimal repairs

$u_{min} \leftarrow 0, u_{max} \leftarrow \sum_{\alpha \in \mathcal{D}} w(\alpha)$

while $u_{min} < u_{max}$, let $u = u_{min} + \lceil \frac{u_{max} - u_{min}}{2} \rceil$ and do

if there exists a $\mathcal{T}$-consistent $\mathcal{R} \subseteq \mathcal{D}$ such that $\sum_{\alpha \in \mathcal{R}} w(\alpha) \ge u$ then

$u_{min} \leftarrow u$

else

$u_{max} \leftarrow u - 1$

return $u_{max}$

■ Algorithm 11 $\leq_w$-CQA

**Input:** $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$, a weight function $w: \mathcal{D} \to \mathbb{N}$, and a BCQ $q$

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

$u_{opt} \leftarrow \text{OptimalWeightByBinarySearch}(\mathcal{K}, w)$

if there exists a $\mathcal{T}$-consistent $\mathcal{R} \subseteq \mathcal{D}$ such that $\sum_{\alpha \in \mathcal{R}} w(\alpha) = u_{opt}$ and $\langle \mathcal{R}, \mathcal{T} \rangle \not= q$ then

return false

return true

■ Algorithm 12 $\leq_w$-brave

**Input:** $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$, a weight function $w: \mathcal{D} \to \mathbb{N}$, and a BCQ $q$

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

$u_{opt} \leftarrow \text{OptimalWeightByBinarySearch}(\mathcal{K}, w)$

if there exists a $\mathcal{T}$-consistent $\mathcal{R} \subseteq \mathcal{D}$ such that $\sum_{\alpha \in \mathcal{R}} w(\alpha) = u_{opt}$ and $\langle \mathcal{R}, \mathcal{T} \rangle \models q$ then

return true

return false

The number of calls to the NP oracle is logarithmically bounded in $\sum_{\alpha \in \mathcal{D}} w(\alpha)$ so is polynomial w.r.t. the size of $\mathcal{D}$ if the weights (considered part of $\mathcal{D}$) are encoded in binary, and logarithmic if the weights are encoded in unary or if there exists a constant $k$ independent of $\mathcal{D}$ such that $w(\alpha) \le k$ for every $\alpha$, since in this case $\sum_{\alpha \in \mathcal{D}} w(\alpha) \le k|\mathcal{D}|$. In particular, this is the case for $\leq_w$-optimal repairs (case $w(\alpha) = 1$). For $\leq_P$-optimal repairs, we use the reduction to $\leq_w$-optimal repairs presented in Section 5.1: given $P = \langle \mathcal{P}_1, \dots, \mathcal{P}_n \rangle$, let $u = (\max_{i=1}^n |\mathcal{P}_i|) + 1$, and $w(\alpha) = u^{n-i}$ for $\alpha \in \mathcal{P}_i$, then $\leq_P$-Rep($\mathcal{D}, \mathcal{T}$) $\leq_w$-Rep($\mathcal{D}, \mathcal{T}$). Again, if $n$ is bounded by a constant $k$ independent from $\mathcal{D}$, the resulting weights are bounded by $(|\mathcal{D}| + 1)^{k-1}$ so $\sum_{\alpha \in \mathcal{D}} w(\alpha) \le (|\mathcal{D}| + 1)^k$ and the number of oracle calls is logarithmic.
■ Algorithm 13 $\leq_w$-intersection

Input: $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$, a weight function $w: \mathcal{D} \to \mathbb{N}$, and a BCQ $q$

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

$u_{opt} \leftarrow \text{OptimalWeightByBinarySearch}(\mathcal{K}, w)$

if there exist $\mathcal{B} \subseteq \mathcal{D}$ with $\mathcal{B} = \{\alpha_1, \dots, \alpha_n\}$ and $\mathcal{T}$-consistent $\mathcal{R}_1 \subseteq \mathcal{D}, \dots, \mathcal{R}_n \subseteq \mathcal{D}$ such that $\alpha_i \notin \mathcal{R}_i$, $\Sigma_{\alpha \in \mathcal{R}_i} w(\alpha) = u_{opt}$ for $1 \le i \le n$, and $\langle \mathcal{D} \setminus \mathcal{B}, \mathcal{T} \rangle \not= q$ then

return false

return true

**Lower bounds.** For semantics based on X-optimal repairs with $X \in \{\subseteq_P, \text{Pareto}, \text{completion}\}$, the coNP and NP lower bounds have been shown in the case of $\subseteq_P$-optimal repair-based semantics for DL-Lite$_{core}$ [44, Prop. 6.2.3 and 6.2.8] and the ontologies used in the reduction are equivalent to sets of NCs. Since in the case where a priority relation $> $ is induced by a prioritization $P = \langle \mathcal{P}_1, \dots, \mathcal{P}_n \rangle$, Pareto- and completion-optimal repairs coincide with $\subseteq_P$-optimal repairs, these lower bounds transfer to the cases of Pareto- and completion-optimal repairs. For FD, the coNP and NP lower bounds have been shown for X-CQA [129, Theorem 3] and for X-intersection and X-brave [31, Theorem 3], either directly for $X = \subseteq_P$ or using a priority relation that can be induced by a prioritization.

For semantics based on globally-optimal repairs, the $\Pi_2^P$ and $\Sigma_2^P$ lower bounds have been shown for DL-Lite$_{core}$ using ontologies equivalent to sets of NCs [30, Theorem 10], and the $\Pi_2^P$-hardness proof for G-CQA with FDs [129, Theorem 2] immediately yields the lower bound for G-intersection and G-brave semantics. Indeed, it uses as query a fact $p_\exists$ from the dataset, and every repair that does not contain $p_\exists$ contains $p_\forall$. Hence $p_\exists$ is entailed under G-CQA iff it is entailed under G-intersection iff $p_\forall$ is not entailed G-brave semantics.

For semantics based on X-optimal repairs with $X \in \{\leq, \leq_w, \leq_P\}$, a $\Theta_2^P$ lower bound has been shown for $\leq$-CQA, $\leq$-intersection and $\leq$-brave semantics (hence transfers to $\leq_w$- and $\leq_P$-optimal repair-based semantics, even in the case where the weights are bounded by a constant and there is a single priority level) [44, Prop. 6.2.4 and 6.2.9] and the reductions can be easily adapted to use only NCs. The lower bound for $\leq$-CQA has also been shown for a logical theory that contains a single NC [103, Theorem 4]. For FD, we use a reduction from the following $\Theta_2^P$-hard problem [103, Lemma 6]: given a graph $\mathcal{G} = (V, E)$ and a vertex $v_d \in V$, decide if $v_d$ belongs to all (cardinality) maximum independent sets (MISs) of $\mathcal{G}$. Assume w.l.o.g. that every $v \in V$ belongs to some $e \in E$ and define $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$ as follows, where for $v \in V$, $ne(v) = |\{e \mid v \in e, e \in E\}|$ is the number of edges of $\mathcal{G}$ in which $v$ occurs.

$$ \mathcal{T} = \{R(x_1, x_2, x_3, x_4) \wedge R(y_1, y_2, y_3, y_4) \wedge x_1 = y_1 \rightarrow x_2 = y_2, $$

$$ R(x_1, x_2, x_3, x_4) \wedge R(y_1, y_2, y_3, y_4) \wedge x_2 = y_2 \rightarrow x_3 = y_3 \} $$

$$ \mathcal{D} = \{R(e, v, 1, j) \mid v \in e, e \in E, 1 \leq j \leq 2\} \cup \{R(v, v, 0, i) \mid v \in V, 1 \leq i \leq 2ne(v) - 1\} $$

We show that $v_d$ belongs to all MISs of $\mathcal{G}$ iff $\exists x R(x, v_d, 1, 1)$ is entailed under $\leq$-CQA (resp. $\leq$-intersection) semantics, iff $R(v_d, v_d, 0, 1)$ is not entailed under $\leq$-brave semantics. We first show a correspondence between $\leq$-optimal repairs of $\mathcal{K}$ and MISs of $\mathcal{G}$:

- Given an independent set $S \subseteq V$ of $\mathcal{G}$, define $\mathcal{R}_S = \{R(e, v, 1, j) \mid R(e, v, 1, j) \in \mathcal{D}, v \in S\} \cup \{R(v, v, 0, i) \mid R(v, v, 0, i) \in \mathcal{D}, v \notin S\}$. $\mathcal{R}_S$ satisfies the second FD by construction and the first one because $S$ is an independent set. Hence $\mathcal{R}_S$ is $\mathcal{T}$-consistent. Moreover, $|\mathcal{R}_S| = \Sigma_{v \in S} 2ne(v) + \Sigma_{v \notin S} (2ne(v) - 1) = \Sigma_{v \in V} 2ne(v) - |V \setminus S|$.
- Given a $\mathcal{T}$-consistent subset $\mathcal{R} \subseteq \mathcal{D}$, define $S_{\mathcal{R}} = \{v \mid R(e, v, 1, j) \in \mathcal{R}\}$. For each $v \in S_{\mathcal{R}}$, $\mathcal{R}$ does not contain any fact of the form $R(v, v, 0, i)$ (or it would violate the second FD) and for each $v \notin S_{\mathcal{R}}$, by definition of $S_{\mathcal{R}}$, $\mathcal{R}$ does not contain any fact of the form $R(e, v, 1, j)$. Hence $|\mathcal{R}| \le \sum_{v \in S_{\mathcal{R}}} 2ne(v) + \sum_{v \notin S_{\mathcal{R}}} (2ne(v) - 1) = \sum_{v \in V} 2ne(v) - |V \setminus S_{\mathcal{R}}|$.

- Let $\mathcal{R} \in \leq -\text{Rep}(\mathcal{K})$. We show that $S_{\mathcal{R}}$ is an independent set of $\mathcal{G}$. Assume for a contradiction that there is an edge $e_0 = (v_1, v_2)$ such that $v_1, v_2 \in S_{\mathcal{R}}$. For $k \in \{1, 2\}$, let $\mathcal{R}_k = \mathcal{R} \setminus \{R(e', v_k, 1, j) \mid v_k \in e', e' \in E, 1 \le j \le 2\} \cup \{R(v_k, v_k, 0, i) \mid 1 \le i \le 2ne(v_k) - 1\}$. Since $\mathcal{R}$ is $\mathcal{T}$-consistent, it is easy to check that the $\mathcal{R}_k$ are also $\mathcal{T}$-consistent. Since $v_1, v_2 \in S_{\mathcal{R}}$, $\mathcal{R}$ must contain some facts of the form $R(e_1, v_1, 1, j)$ and $R(e_2, v_2, 1, j)$ (by definition of $S_{\mathcal{R}}$). Hence $\mathcal{R}$ does not contain any fact of the form $R(v_1, v_1, 0, i)$ nor $R(v_2, v_2, 0, i)$. Moreover, by the first FD, there is $k \in \{1, 2\}$ such that $\mathcal{R}$ does not contain $R(e_0, v_k, 1, j)$ for $1 \le j \le 2$. Hence there is $k \in \{1, 2\}$ such that $\mathcal{R}_k$ is obtained from $\mathcal{R}$ by adding exactly $2ne(v_k) - 1$ facts of the form $R(v_k, v_k, 0, i)$ and removing at most $2ne(v_k) - 2$ facts of the form $R(e', v_k, 1, j)$ so $|\mathcal{R}_k| > |\mathcal{R}|$. This contradicts the fact that $\mathcal{R} \in \leq -\text{Rep}(\mathcal{K})$. Hence $S_{\mathcal{R}}$ is an independent set of $\mathcal{G}$.

- Let $\mathcal{R} \in \leq -\text{Rep}(\mathcal{K})$. We have shown that $S_{\mathcal{R}}$ is an independent set of $\mathcal{G}$ and $|\mathcal{R}| \le \sum_{v \in V} 2ne(v) - |V \setminus S_{\mathcal{R}}|$. Assume for a contradiction that there exists an independent set $S$ of $\mathcal{G}$ such that $|S| > |S_{\mathcal{R}}|$. We have shown that $|\mathcal{R}_S|$ is $\mathcal{T}$-consistent and $|\mathcal{R}_S| = \sum_{v \in V} 2ne(v) - |V \setminus S|$. It follows that $|\mathcal{R}_S| = \sum_{v \in V} 2ne(v) - |V \setminus S| > \sum_{v \in V} 2ne(v) - |V \setminus S_{\mathcal{R}}| \ge |\mathcal{R}|$, which contradicts $\mathcal{R} \in \leq -\text{Rep}(\mathcal{K})$. We conclude that $S_{\mathcal{R}}$ is a MIS of $\mathcal{G}$.

- Let $S \subseteq V$ be a MIS of $\mathcal{G}$. Since $S$ is an independent set, $\mathcal{R}_S$ is $\mathcal{T}$-consistent and $|\mathcal{R}_S| = \sum_{v \in V} 2ne(v) - |V \setminus S|$. Assume for a contradiction that $\mathcal{R}_S \notin \leq -\text{Rep}(\mathcal{K})$ and let $\mathcal{R} \in \leq -\text{Rep}(\mathcal{K})$. We have shown that $S_{\mathcal{R}}$ is an independent set of $\mathcal{G}$ and $|\mathcal{R}| \le \sum_{v \in V} 2ne(v) - |V \setminus S_{\mathcal{R}}|$. Since we assumed that $|\mathcal{R}| > |\mathcal{R}_S|$, it follows that $|S_{\mathcal{R}}| > |S|$, which contradicts that $S$ is a MIS of $\mathcal{G}$. We conclude that $\mathcal{R}_S \in \leq -\text{Rep}(\mathcal{K})$.

Assume that $v_d$ belongs to every MIS of $\mathcal{G}$ and let $\mathcal{R} \in \leq -\text{Rep}(\mathcal{K})$. Since $S_{\mathcal{R}}$ is a MIS of $\mathcal{G}$, $v_d \in S_{\mathcal{R}}$ so there exists $R(e_d, v_d, 1, j) \in \mathcal{R}$ and $\mathcal{R}$ does not contain any fact of form $R(v_d, v_d, 0, j)$ and contains $R(e_d, v_d, 1, 1)$ (by maximality). Hence $\exists x R(x, v_d, 1, 1)$ is entailed under $\leq$-intersection (hence $\leq$-CQA) semantics and $R(v_d, v_d, 0, 1)$ is not entailed under $\leq$-brave semantics. In the other direction, assume that there exists a MIS $S$ of $\mathcal{G}$ such that $v_d \notin S$. Then $\mathcal{R}_S \in \leq -\text{Rep}(\mathcal{K})$ is such that there is no fact of the form $R(e, v_d, 1, j)$ in $\mathcal{R}_S$ and $R(v_d, v_d, 0, 1) \in \mathcal{R}_S$ so $R(v_d, v_d, 0, 1)$ is entailed under $\leq$-brave semantics and $\exists x R(x, v_d, 1, 1)$ is not entailed under $\leq$-CQA (hence nor under $\leq$-intersection) semantics.

For semantics based on X-optimal repairs with $X \in \{\leq_w, \leq_P\}$ (in the case where the weights and priority levels are not bounded independently from the data), a $\Delta_2^P$ lower bound has been shown for $\leq_P$-CQA, $\leq_P$-intersection and $\leq_P$-brave semantics (hence transfers to $\leq_w$-optimal repair-based semantics) in DL-Lite<sub>core</sub> [44, Prop. 6.2.4 and 6.2.9] and the ontology used in the reductions uses only NCs. For FD, we use a reduction from the following $\Delta_2^P$-hard problem [96]: given a satisfiable CNF formula $\varphi = c_1 \wedge \dots \wedge c_m$ over variables $x_1, \dots, x_n$, decide whether the lexicographically maximum truth assignment $\nu_{\max}$ satisfying $\varphi$ with respect to $(x_1, \dots, x_n)$ is such that $\nu_{\max}(x_n) = 1$. Define $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$ and a prioritization $P = \langle \mathcal{P}_1, \dots, \mathcal{P}_{n+1} \rangle$ as follows:

$$ \mathcal{T} = \{R(x_1, x_2, x_3) \wedge R(y_1, y_2, y_3) \wedge x_1 = y_1 \rightarrow x_2 = y_2, \\ \qquad R(x_1, x_2, x_3) \wedge R(y_1, y_2, y_3) \wedge x_2 = y_2 \rightarrow x_3 = y_3\} $$

$$ \mathcal{D} = \mathcal{P}_1 \cup \dots \cup \mathcal{P}_{n+1} \text{ with} $$

$$ \mathcal{P}_1 = \{R(c_j, x_i, 1) \mid x_i \in c_j, 1 \le j \le m\} \cup \{R(c_j, x_i, 0) \mid \neg x_i \in c_j, 1 \le j \le m\} $$

$$ \mathcal{P}_{i+1} = \{R(x_i, x_i, 1)\} \text{ for } 1 \le i \le n $$
We can show that $R(x_n, x_n, 1)$ is entailed under $\leq_P$-CQA (resp. $\leq_P$-intersection, $\leq_P$-brave) semantics iff $\nu_{\max}(x_n) = 1$. Indeed, since $\varphi$ is satisfiable, for each satisfying valuation $\nu$, we can obtain a $\mathcal{T}$-consistent subset of $m$ facts from $\mathcal{P}_1$ by selecting exactly one fact of the form $R(c_j, x_i, \nu(x_i))$ per $c_j$ and complete it into a (standard) repair by adding all $R(x_i, x_i, 1)$ such that no fact of the form $R(c_j, x_i, 0)$ has been selected. Since it is not possible to keep more than $m$ facts from $\mathcal{P}_1$ because of the first FD, and each other $\mathcal{P}_i$ contains a single fact, the $\leq_P$-repairs all contain the same set of facts from $\bigcup_{i=1}^n \mathcal{P}_{i+1}$ and these facts correspond to the $x_i$ set to 1 by $\nu_{\max}$.

### 6.2.3 Comments and additional results

When looking at Tables 6 and 7, we can distinguish three kinds of preferred repairs depending on their impact on the data complexity:

- Those for which the complexity of repair checking and BCQ entailment under CQA is the same as in the case of standard repairs ($\subseteq_P$, Pareto- and completion-optimal). Intuitively, these preferred repairs correspond to some “local” preference, so that given a repair, we can decide whether it is a preferred repair without guessing or computing another preferred repair. Note that the complexity of intersection and brave semantics nevertheless increases for the cases where it was in $AC^0$ for standard repairs.

- Those for which the complexity of repair checking and BCQ entailment under CQA increases to coNP-complete and $\Delta_2^P$- or $\Theta_2^P$-complete ($\leq_-$, $\leq_w^-$, $\leq_P$-optimal and $\Pi_{\leq}^-$ preferred). Intuitively, for these kinds of preferred repairs, we can precompute the value of a global parameter (such as the weight of the $\leq_w$-optimal repairs or the number of preference rules satisfied by $\Pi_{\leq}^-$-preferred repairs) that allows us to check efficiently that a $\mathcal{T}$-consistent subset of $\mathcal{D}$ is a preferred repair.

- Those for which the complexity of repair checking and BCQ entailment under CQA jumps to coNP-complete and $\Pi_2^P$-complete (globally-optimal and $\Pi_{\subseteq}^-$-preferred). Intuitively, for these kinds of preferred repairs, there is no better option than relying on the naïve guess-and-check algorithm to determine whether a repair is a preferred repair.

We conclude this section by mentioning various other complexity results for reasoning under CQA, intersection and brave semantics using preferred repairs.

**Combined complexity.** The combined complexity of BCQ entailment under CQA and intersection semantics based on $\leq$-optimal repairs over Datalog$^\pm$ KBs have been studied for $\leq \in \{\leq, \leq_w, \subseteq_P, \subseteq_P\}$ and shown to coincide with the standard repair case for all fragments of Datalog$^\pm$ we consider (cf. [108, Tables 2 and 3] for $\leq$ and [107, Tables 4, 5, 6, 7] for $\leq_w, \leq_P$ and $\subseteq_P$). Intuitively, this is because the combined complexity of BCQ entailment under these semantics is already very high when using standard repairs. In contrast, for DL-Lite$_R$, the combined complexity of CQA does not change ($\Pi_2^P$-complete) but the one of intersection semantics increases from NP-complete to $\Theta_2^P$ or $\Delta_2^P$ when $\leq_-$, $\subseteq_P^-$, $\leq_w^-$ or $\leq_P$-optimal repairs are used [33, Figure 1], and the one of brave semantics increases similarly when using $\leq_-$, $\leq_w^-$ or $\leq_P$-optimal repairs (but remains NP-complete in the case of $\subseteq_P$-optimal repairs) [44, Table 6.1]. Note that this difference between CQA and intersection or brave in combined complexity contrasts with the data complexity where CQA and intersection have the same complexity and brave is complete for the complement class.

**Preferred repairs for more expressive DLs.** It has been shown that fact entailment over SHIQ KBs under $\leq_w$-CQA semantics is $\Theta_2^P$-complete when the input size is measured by
the number of facts in $\mathcal{D}$ (hence assuming a data-independent bound on the weights) [73]. We can extend this result and obtain $\Delta_2^P$-complete (resp. $\Theta_2^P$-complete when the weights are bounded) data complexity for BCQ entailment under $\le_w$-CQA, as well as under $\le_p$-intersection (extended as usual to $\le_P$ and $\le$). The lower bounds are inherited from DL-Lite$_{core}$ and the upper bounds follow from Algorithms 11 and 13. Indeed, since consistency checking in SHIQ is in NP, an NP-oracle can decide whether there exists a $\mathcal{T}$-consistent subset $\mathcal{R}$ of $\mathcal{D}$ of at least a given weight by guessing the certificate of the $\mathcal{T}$-consistency of $\mathcal{R}$ together with $\mathcal{R}$, and similarly, since BCQ entailment is in coNP, the oracle can guess the certificate that $\langle \mathcal{R}, \mathcal{T} \rangle \not\models q$ (resp. $\langle \mathcal{D} \setminus \mathcal{B}, \mathcal{T} \rangle \not\models q$) together with $\mathcal{R}$ (resp. $\mathcal{B}$ and the $\mathcal{R}_1, \dots, \mathcal{R}_n$) and the $\mathcal{T}$-consistency certificate(s).

**Preferred $\Delta$-repairs of databases with universal constraints.** The data complexity of reasoning with optimal repairs based on a priority relation has been studied in the case of databases with UCs: in this case, using $\subseteq_P$-optimal, Pareto-optimal, completion-optimal or globally-optimal repairs instead of standard $\Delta$-repairs does not increase the data complexity of BCQ entailment under CQA, intersection and brave semantics, which remains $\Pi_2^P / \Sigma_2^P$-complete (cf. Table 5) [32, Theorem 3]. For $\le$-optimal repairs, the data complexity actually decreases: it is $\Theta_2^P$-complete [74, Theorem 4]. The lower bound comes from the FD case and the upper bound follows from the fact that we can pre-compute by binary search the minimal size of the symmetric difference between a $\Delta$-repair and $\mathcal{D}$, then use it to check in P whether a subset of $\text{Facts}_\mathcal{D}^\mathcal{T}$ is a $\le$-optimal $\Delta$-repair.

**Optimal repairs based on a transitive priority relation.** In the case of repairs based on a priority relation $>$, it has been shown (for DL-Lite$_{core}$ and NCs) that all lower bounds given in Table 6 hold even in the case where $> $ is assumed to be transitive [30, Theorem 14] (while transitivity decreases the complexity of deciding whether there is a unique globally-optimal repair [92, Corollary 7.7]).

# 7 Implementations of (preferred) repair-based semantics

Table 8 provides a (partial) overview of the systems that have been implemented for answering queries under (preferred) repair-based semantics. They are divided in four groups, based on the semantics they support:

- the systems of the first group target CQA, intersection and brave semantics with both standard and preferred repairs based on priority ($\subseteq_P$, Pareto- and completion-optimal);

- the second group consists of implementations of $\le_w$- and/or $\le$-CQA for expressive DLs or database constraints;

- the systems of the third group implement (plain) intersection semantics for DL KBs;

- the last group consists of systems that implement (plain) CQA for databases.

Most of the systems in this last group further fall into two categories: approaches that handle general CQs and potentially expressive ICs and rely on solvers (e.g., SAT, Binary Integer Programming (BIP), Answer Set Programming (ASP)), and those that impose strong restrictions on the setting (key constraints and restriction to some classes of CQs) to ensure that CQA is FO rewritable and apply rewriting techniques. Indeed, the database community conducted an extensive study of the complexity of BCQ entailment under CQA with key constraints for different kinds of CQ, which is out of the scope of these lecture notes.

In the remainder of the section, we illustrate the prominent approach of CQA relying on solvers by presenting some SAT encodings for CQA based on standard or Pareto-optimal repairs, then give a few details on the approaches to tractable semantics and approximations.
<table><caption>Table 8 Overview of implementations of (preferred) repair-based semantics. X-Sem stands for semantics Sem based on repairs from X-Rep(K). Recall that a system that supports $\leq_w$-Sem also supports $\leq$-Sem, and that a system that supports P- or C-Sem also supports $\subseteq_P$-Sem. We focus on (preferred) repair-based semantics (cf. Section 4.1) and omit here the alternative semantics implemented in some systems.</caption><thead><tr><th></th><th>semantics</th><th>input supported</th><th>main techniques</th></tr></thead><tbody><tr><td>[37]<br>(2025)</td><td>X-CQA/X-inter./X-brave<br>for X ∈ {S, P, C}</td><td>D, metadata, pref. rules,<br>DCs, UCQ</td><td>ASP</td></tr><tr><td>ORBITS [31]<br>(2022)</td><td>X-CQA/X-inter./X-brave<br>for X ∈ {S, P, C}</td><td>binary Conf(K), >,<br>pot. answers + causes</td><td>SAT + poly. approx.</td></tr><tr><td>CQAPri [33, 35]<br>(2014)</td><td>X-CQA/X-inter./X-brave<br>for X ∈ {S, &le;P}</td><td>D (possibly with P),<br>DL-Lite<sub>R</sub> onto., CQ</td><td>SAT + poly. approx.</td></tr><tr><td>[73]<br>(2013)</td><td>&le;<sub>w</sub>-CQA</td><td>D, w, SHIQ onto.,<br>CQ without &exist;</td><td>SAT</td></tr><tr><td>[74]<br>(2010)</td><td>&le;-CQA</td><td>D, UCs,<br>CQ</td><td>SAT</td></tr><tr><td>[133]<br>(2018)</td><td>S-inter.</td><td>D, E L H<sub>&perp;</sub><sup>dr</sup> onto.<br>(with restr.), CQ</td><td>(disj.) Datalog<sup>&not;</sup> rew.</td></tr><tr><td>SaQAI [134]<br>(2016)</td><td>S-inter.</td><td>D, DL-Lite<sub>R</sub> onto.,<br>CQ</td><td>comp. &cap;<sub>R&isin;S-Rep(K)</sub> R</td></tr><tr><td>QuID [127, 99]<br>(2012)</td><td>S-inter.</td><td>D, DL-Lite<sub>A</sub> onto.,<br>CQ</td><td>FO rewriting<br>annot. with Conf(K)<br>comp. &cap;<sub>R&isin;S-Rep(K)</sub> R</td></tr><tr><td>CAvSAT [71, 72]<br>(2019)</td><td>S-CQA</td><td>D, DCs,<br>CQ</td><td>SAT + poly. approx.<br>SQL rewriting</td></tr><tr><td>EQUIP [95]<br>(2013)</td><td>S-CQA</td><td>D, keys,<br>CQ</td><td>BIP + poly. approx.</td></tr><tr><td>[86, 87, 77, 117]<br>[114, 115](2001-15)</td><td>S-CQA</td><td>D, keys to UCs,<br>CQ to UCQ<sup>&not;</sup></td><td>logic programing</td></tr><tr><td>Hippo [64, 65]<br>(2004)</td><td>S-CQA</td><td>D, DCs,<br>UCQ without &exist;</td><td>indep. set of Conf(K)</td></tr><tr><td>LinCQA [79]<br>(2023)</td><td>S-CQA</td><td>D, keys,<br>FO rew. CQ</td><td>SQL rewriting<br>non-rec. Datalog<sup>&not;</sup> rew.</td></tr><tr><td>Conquesto [91]<br>(2020)</td><td>S-CQA</td><td>D, keys,<br>FO rew. CQ</td><td>non-rec. Datalog<sup>&not;</sup> rew.</td></tr><tr><td>Conquer [82, 83]<br>(2005)</td><td>S-CQA</td><td>D, keys,<br>FO rew. CQ</td><td>SQL rewriting<br>annot. with Conf(K)</td></tr></tbody></table>
## 7.1 Examples of encodings for CQA

When encoding BCQ entailment under some intractable semantics into SAT, BIP, or ASP, it is crucial to produce encodings that are small enough to be handled efficiently. Localization techniques have been considered since the early implementations based on logic programming (see e.g., [77]). In this section, we present some examples of SAT encodings for CQA semantics using standard or Pareto-optimal repairs (applicable to $\subseteq_P$-optimal repairs) that have been proposed for cases where the conflicts and minimal $\mathcal{T}$-consistent subsets of the dataset that support the query can be efficiently computed (in polynomial time w.r.t. data complexity), such as DL-Lite, $L_\perp$, $A_\perp$, or $S_\perp$ KBs, or databases with DCs. Indeed, most of the recent implementations of CQA that handle unrestricted CQs and relatively expressive constraints use encodings based on these sets [95, 33, 71, 31, 37]. Several variants of such encodings have been proposed. In particular, we can treat each candidate answer separately, reducing each entailment to an instance of (here) SAT, or use the same encoding to handle all potential answers, and rely on some optimization variant (e.g., weighted MaxSAT), or incremental solving. We refer the interested reader to [31] for a comparison of different SAT encodings and different reasoning modes of SAT solvers. The encodings we present next are used by CQAPri [33] and implemented among others by ORBITS [31] (restricted to the case of binary conflicts, which simplifies the encodings). An ASP version of these encodings (for the general case where conflicts may not be binary) has also recently been implemented [37].

Given a KB or database $\mathcal{K} = \langle \mathcal{D}, \mathcal{T} \rangle$, a CQ $q(\vec{x})$, and a tuple $\vec{a}$, a cause for $q(\vec{a})$ in $\mathcal{K}$ is a $\subseteq_P$-minimal $\mathcal{T}$-consistent subset $\mathcal{C}$ of $\mathcal{D}$ such that $\langle \mathcal{C}, \mathcal{T} \rangle \models q(\vec{a})$. We denote by $\text{Causes}(q(\vec{a}), \mathcal{K})$ the set of all causes for $q(\vec{a})$ in $\mathcal{K}$. Recall from Sections 3.3 and 5.2.2.1 that given a prioritized KB or database $\mathcal{K}_> = (\mathcal{K}, >)$ we have the following notation (attack relations of the SETAF corresponding to $\mathcal{K}$ and of the PSETAF corresponding to $\mathcal{K}_>$, respectively):

- $\mathcal{B} \rightsquigarrow_{\mathcal{K}} \alpha$ iff $\mathcal{B} \cup \{\alpha\} \in \text{Conf}(\mathcal{K})$ and $\alpha \notin \mathcal{B}$;

- $\mathcal{B} \rightsquigarrow_{>} \alpha$ iff $\mathcal{B} \rightsquigarrow_{\mathcal{K}} \alpha$ and $\alpha \not\models \beta$ for every $\beta \in \mathcal{B}$.

The propositional formula $\Phi_{CQA}(q(\vec{a}))$ is satisfiable iff $\vec{a}$ is not an answer to $q(\vec{x})$ over $\mathcal{K}$ under the CQA semantics.

$$ \Phi_{CQA}(q(\vec{a})) = \left( \bigwedge_{C \in \text{Causes}(q(\vec{a}), \mathcal{K})} \varphi_{\neg C} \right) \wedge \varphi_{\text{cons}}(F) \quad \text{where} $$

$$ \varphi_{\neg C} = \left( \bigvee_{\substack{\alpha \in \mathcal{C}, \\ \mathcal{B} \rightsquigarrow_{\mathcal{K}} \alpha}} x_{\mathcal{B}} \right) \wedge \left( \bigwedge_{\substack{\alpha \in \mathcal{C}, \mathcal{B} \rightsquigarrow_{\mathcal{K}} \alpha, \\ \beta \in \mathcal{B}}} \neg x_{\mathcal{B}} \vee x_{\beta} \right) \quad \text{and} \quad \varphi_{\text{cons}}(F) = \left( \bigwedge_{\substack{\alpha \in F, \\ \mathcal{B} \rightsquigarrow_{\mathcal{K}} \alpha}} \neg x_{\alpha} \vee \bigvee_{\beta \in \mathcal{B}} \neg x_{\beta} \right) $$

and $F = \{\beta | x_{\beta}$ occurs in $\bigwedge_{C \in \text{Causes}(q(\vec{a}), \mathcal{K})} \varphi_{\neg C}\}$. Intuitively, the set of facts $\beta$ such that $x_{\beta}$ is assigned to true by a satisfying valuation for $\Phi_{CQA}(q(\vec{a}))$ is $\mathcal{T}$-consistent and contradicts every cause for $q(\vec{a})$ in $\mathcal{K}$, hence can be extended into a repair of $\mathcal{K}$ that does not entail $q(\vec{a})$. Indeed, for each cause $\mathcal{C}$ of $q(\vec{a})$ in $\mathcal{K}$, $\varphi_{\neg C}$ ensures that we choose some $\alpha \in \mathcal{C}$ and some $\mathcal{B}$ such that $\mathcal{B} \cup \{\alpha\} \in \text{Conf}(\mathcal{K})$, and select all facts from $\mathcal{B}$, and $\varphi_{\text{cons}}(F)$ ensures that the set of selected facts is $\mathcal{T}$-consistent.

To use Pareto-optimal repairs instead of standard ones, it suffices to slightly modify $\varphi_{\neg C}$ to take into account the priority relation and to add an additional component $\varphi_{P-\text{max}}(F)$ that ensures that the selected facts can be extended into a Pareto-optimal repair by stating that a relevant fact $\alpha$ can only be omitted if we include a contradicting set of facts that are not dominated by $\alpha$. The propositional formula $\Phi_{P-CQA}(q(\vec{a}))$ is satisfiable iff $\vec{a}$ is not an answer to $q(\vec{x})$ over $\mathcal{K}_>$ under the CQA semantics based on Pareto-optimal repairs.
$$ \Phi_{\text{P-CQA}}(q(\vec{a})) = \left( \bigwedge_{C \in \text{Causes}(q(\vec{a}), \mathcal{K})} \varphi_{-C}^{\succ} \right) \wedge \varphi_{\text{P-max}}(F) \wedge \varphi_{\text{cons}}(F') \quad \text{where} $$

$$ \varphi_{-C}^{\succ} = (\bigvee_{\substack{\alpha \in \mathcal{C}, \\ B \rightsquigarrow \alpha}} x_B) \wedge \bigwedge_{\substack{\alpha \in \mathcal{C}, B \rightsquigarrow \alpha, \\ \beta \in \mathcal{B}}} \neg x_B \vee x_{\beta} \quad \text{and} $$

$$ \varphi_{\text{P-max}}(F) = \bigwedge_{\alpha \in \mathbb{R}(F)} (x_{\alpha} \vee \bigvee_{B \rightsquigarrow \alpha} x_B) \wedge \bigwedge_{\substack{\alpha \in \mathbb{R}(F), \\ B \rightsquigarrow \alpha, \beta \in \mathcal{B}}} \neg x_B \vee x_{\beta} $$

$F = \{\beta | x_{\beta} \text{ occurs in } \bigwedge_{C \in \text{Causes}(q(\vec{a}), \mathcal{K})} \varphi_{-C}^{\succ}\}$, $F' = \{\beta | x_{\beta} \text{ occurs in } \varphi_{\text{P-max}}(F)\}$, and $\mathbb{R}(F)$ is the set of facts reachable from $F$ in the following sense: $\beta$ is reachable from $F$ if $\beta \in F$ or if there exists $\gamma$ reachable from $F$ and $B$ such that $\beta \in B$ and $B \rightsquigarrow \gamma$.

**► Example 90.** Recall the KB $\mathcal{K}$ from Examples 15, 51 and 59, whose conflict hypergraph, priority relation and Pareto-optimal repairs are recalled below, and let $q(x) = B(x)$.

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

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

$$ P-\text{Rep}(\mathcal{K}) = \{\mathcal{R}_1, \mathcal{R}_3\} \text{ 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)\} $$

The only cause for $q(a)$ is $\mathcal{C} = \{B(a)\}$ and the SAT encodings to decide whether $q(a)$ holds under CQA based on standard and Pareto-optimal repairs, respectively, are as follows (for readability we write $A, B, C, D, E$ instead of $A(a), B(a), C(a), D(a), E(a)$ in indexes).

$$ \Phi_{\text{CQA}}(q(a)) = x_{\{A,C\}} \wedge (\neg x_{\{A,C\}} \vee x_A) \wedge (\neg x_{\{A,C\}} \vee x_C) \\ \wedge (\neg x_A \vee \neg x_B \vee \neg x_C) $$

$$ \begin{aligned} \Phi_{\text{P-CQA}}(q(a)) = & x_{\{A,C\}} \wedge (\neg x_{\{A,C\}} \vee x_A) \wedge (\neg x_{\{A,C\}} \vee x_C) \\ & \wedge (x_A \vee x_{\{B,C\}}) \wedge (\neg x_{\{B,C\}} \vee x_B) \wedge (\neg x_{\{B,C\}} \vee x_C) \\ & \wedge (x_B \vee x_{\{A,C\}}) \wedge (\neg x_{\{A,C\}} \vee x_A) \wedge (\neg x_{\{A,C\}} \vee x_C) \\ & \wedge (x_C \vee x_{\{E\}}) \wedge (\neg x_{\{E\}} \vee x_E) \\ & \wedge (x_D \vee x_{\{A\}} \vee x_{\{E\}}) \wedge (\neg x_{\{A\}} \vee x_A) \wedge (\neg x_{\{E\}} \vee x_E) \\ & \wedge (x_E \vee x_{\{D\}}) \wedge (\neg x_{\{D\}} \vee x_D) \\ & \wedge (\neg x_A \vee \neg x_B \vee \neg x_C) \wedge (\neg x_A \vee \neg x_D) \wedge (\neg x_C \vee \neg x_E) \wedge (\neg x_D \vee \neg x_E) \end{aligned} $$

$\Phi_{\text{CQA}}(q(a))$ is satisfiable (assign $x_{\{A,C\}}$, $x_A$ and $x_C$ to true and $x_B$ to false), and indeed $q(a)$ is not entailed under CQA based on standard repairs because of $\mathcal{R}_2$. On the other hand, $q(a)$ holds under P-CQA and $\Phi_{\text{P-CQA}}(q(a))$ is indeed unsatisfiable: to satisfy $\varphi_{-C}^{\succ}$ (first line), we need to assign $x_A$ and $x_C$ to true, which implies that $x_D$ and $x_E$ are assigned to false to satisfy $\varphi_{\text{cons}}(F')$ (last line), but assigning $x_E$ to false implies that $x_D$ must be assigned to true to satisfy $(x_E \vee x_{\{D\}}) \wedge (\neg x_{\{D\}} \vee x_D)$. Note that $\Phi_{\text{P-CQA}}(q(a))$ is much bigger than $\Phi_{\text{CQA}}(q(a))$: this is because we need to take into account all facts reachable from $A(a)$ and $C(a)$ to ensure Pareto-optimality. However, in practice, the size of both kinds of encodings remains typically much smaller than the dataset size.
## 7.2 Tractable semantics and approximations

Several methods have been proposed for tractable semantics, in particular for the intersection semantics and languages for which CQ answering is UCQ-rewritable. Indeed, UCQ-rewritability ensures that the size of the conflicts and causes can be bounded independently from the dataset, hence that CQ answering under intersection semantics is FO-rewritable (cf. Proposition 83 and Corollary 84). The methods for intersection semantics in this tractable case fall into two categories:

- Data-independent rewritings: compute $\varphi_{\mathcal{T},q}^{\cap}$ such that for every $\mathcal{D}$, $q$ is entailed by $\langle \mathcal{D}, \mathcal{T} \rangle$ under intersection iff $\mathcal{I}_{\mathcal{D}} \models \varphi_{\mathcal{T},q}^{\cap}$. For example, if we extend the ontology of Example 15 with $B \sqsubseteq Q$ and $E \sqsubseteq Q$ and consider the query $q(x) = Q(x)$, an FO-rewriting of $q(x)$ w.r.t. $\mathcal{T}$ is $\varphi_{\mathcal{T},q}^{\cap}(x) = Q(x) \lor (B(x) \land \neg A(x)) \lor (B(x) \land \neg C(x)) \lor (E(x) \land \neg C(x) \land \neg D(x))$.

- Methods based on the computation of Conf($\mathcal{K}$), which can be computed in polynomial time w.r.t. data complexity and used in different manners:

- evaluate the queries on $\langle \mathcal{R} \cap, \mathcal{T} \rangle$ where $\mathcal{R} \cap = \bigcap_{\mathcal{R} \in \text{S-Rep}(\mathcal{K})} \mathcal{R} = \mathcal{D} \setminus \bigcup_{\mathcal{C} \in \text{Conf}(\mathcal{K})} \mathcal{C}$;

- annotate the facts in $\mathcal{D}$ that belong to some conflicts and rewrite the queries to ignore the annotated facts;

- compute the query causes in polynomial time w.r.t. data complexity and check whether some cause is such that none of its fact belongs to some conflict.

Many systems that implement intractable semantics use tractable approximations to reserve the use of solvers for the complex cases. For example, when computing answers to a query under CQA semantics (based on standard repairs) EQUIP, CQAPri, CAvSAT and ORBITS all use the intersection semantics to get a subset of the answers that hold under CQA in polynomial time, before checking whether the other potential answers hold via translation to BIP or SAT. Even in the case of preferred repairs, for which all semantics are intractable, CQAPri and ORBITS use as a tractable under-approximation of Pareto- or completion-optimal repair-based intersection (hence also of CQA and brave) semantics the set of answers that have some cause $\mathcal{C}$ such that for every $\alpha \in \mathcal{C}$, there is no $\mathcal{B} \leadsto_{\alpha} \alpha$.

# 8 Summary and outlook

We have seen that many inconsistency-tolerant semantics have been proposed to handle inconsistent databases or knowledge bases, most of them being based on repairs, and surveyed the different kinds of preferred repairs that can be used to obtain more accurate answers when some preference information is available. We presented the properties of these preferred repairs, their relationships and how they relate to other formalisms for inconsistency handling (such as abstract argumentation). We also summarized some results on the computational complexity of reasoning with (preferred) repairs and gave a brief overview of existing implementations. We conclude these lecture notes by mentioning some recent related work on repair-based semantics and research directions.

**Extensions of repair-based semantics to new settings.** Repairs, CQA, brave and intersection semantics have been defined for RDF graphs that do not validate a set of SHACL (Shapes Constraint Language) constraints [5, 6]. SHACL is related to DLs but makes the closed-world assumption. In this case, a repair is obtained by deleting some facts and/or adding some facts from a given set of hypotheses. Both subset-minimal and cardinality-minimal repairs, corresponding to $\Delta$- and $\leq$-optimal $\Delta$-repairs, have been considered. Repairs and CQA have also been studied in the related setting of graph databases [21, 3], and preferred repairs
(based on weights or on a partial order over the set of edge labels and data values) have started to be considered in this context [2]. Another relevant setting is that of temporal databases or KBs [66, 45, 38], which includes a large number of frameworks, since the dataset facts may be annotated with time points or time intervals, the constraints may be atemporal or temporal (including rigid predicates whose interpretation is required not to change over time), and several temporal query languages have been designed. Several definitions of repair have been proposed in these contexts. When facts are annotated with time points and constraints are atemporal, we can repair each snapshot individually, possibly taking into account predicate rigidity [45], or use a more global approach to favor fact persistence (so that, e.g., two identical consecutive snapshots are repaired in the same way) [66]. When time intervals and temporal constraints are used, three notions of repair have been defined, based upon deleting whole facts, seeing intervals as sets of time points and deleting punctual facts, or minimally shrinking the time intervals of facts [38]. Finally, CQA has recently been extended to databases whose facts are annotated with values from a naturally ordered positive semiring [94]. In this setting, the answer to a Boolean query is a semiring value, and the consistent answer of such query is defined as the minimum of the semiring values that the query takes over all repairs.

**Reasoning tasks beyond query answering.** The question of explaining the result of a query attracted a lot of attention, both in the database and KB settings, and is all the more crucial when dealing with repair-based semantics, since an answer can be true under a given semantics and not under another one. Some work in this direction has been conducted for DL and Datalog<sup>±</sup> KBs, with explanations defined as (sets of) subsets of the dataset [34, 35, 105, 106]. Preferences among these explanations (smallest explanations...) have also been considered. Research effort is still needed to make such data-centric explanations more understandable, e.g., by relating them to the ontology and presenting them in a concise way. Moreover, while the existing definitions of explanations could be straightforwardly extended to preferred repair-based semantics, they would probably not be useful to understand the query result by themselves. For example, a cause is an explanation for query entailment under the brave semantics, but while in the case of standard repairs, every cause can be extended to a repair, we would need to explain why a cause belongs to some preferred repair to justify entailment under preferred repair-based brave semantics. Another related reasoning task that attracted some attention in the context of inconsistent KBs is that of abduction, i.e., the task of minimally extending the dataset so that some query is entailed under intersection semantics [75].

References

1. Serge Abiteboul, Richard Hull, and Victor Vianu. *Foundations of Databases*. Addison-Wesley, 1995.

2. Sergio Abriola, Santiago Cifuentes, Nina Pardal, and Edwin Pin Baque. Data-graph repairs: the preferred approach. In *Proceedings of the 15th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW)*, 2023.

3. Sergio Abriola, María Vanina Martínez, Nina Pardal, Santiago Cifuentes, and Edwin Pin Baque. On the complexity of finding set repairs for data-graphs. *Journal of Artificial Intelligence Research (JAIR)*, 76:721–759, 2023.

4. Foto N. Afrati and Phokion G. Kolaitis. Repair checking in inconsistent databases: algorithms and complexity. In *Proceedings of the 12th International Conference on Database Theory (ICDT)*, 2009.
5:60 Inconsistency-Tolerant Semantics Based on (Preferred) Repairs

5 Shqiponja Ahmetaj, Robert David, Magdalena Ortiz, Axel Polleres, Bojken Shehu, and Mantas Simkus. Reasoning about explanations for non-validation in SHACL. In *Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning (KR)*, 2021.

6 Shqiponja Ahmetaj, Timo Camillo Merkl, and Reinhard Pichler. Consistent query answering over SHACL constraints. In *Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning (KR)*, 2024.

7 Leila Amgoud and Claudette Cayrol. Inferring from inconsistency in preference-based argumentation frameworks. *Journal of Automated Reasoning* (JAR), 29(2):125–169, 2002.

8 Marcelo Arenas, Leopoldo E. Bertossi, and Jan Chomicki. Consistent query answers in inconsistent databases. In *Proceedings of the 18th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS)*, 1999.

9 Marcelo Arenas, Leopoldo E. Bertossi, and Jan Chomicki. Answer sets for consistent query answering in inconsistent databases. *Theory and Practice of Logic Programming (TPLP)*, 3(4-5):393–424, 2003.

10 Abdallah Arioua, Madalina Croitoru, and Srdjan Vesic. Logic-based argumentation with existential rules. *International Journal of Approximate Reasoning*, 90:76–106, 2017.

11 Sebastian Arming, Reinhard Pichler, and Emanuel Sallinger. Complexity of repair checking and consistent query answering. In *Proceedings of the 19th International Conference on Database Theory (ICDT)*, 2016.

12 Alessandro Artale, Diego Calvanese, Roman Kontchakov, and Michael Zakharyaschev. The DL-Lite family and relations. *Journal of Artificial Intelligence Research (JAIR)*, 36:1–69, 2009.

13 Franz Baader, Sebastian Brandt, and Carsten Lutz. Pushing the *EL* envelope. In *Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI)*, 2005.

14 Franz Baader, Diego Calvanese, Deborah L. McGuinness, Daniele Nardi, and Peter F. Patel-Schneider, editors. *The Description Logic Handbook: Theory, Implementation, and Applications*. Cambridge University Press, 2003.

15 Franz Baader, Patrick Koopmann, and Francesco Kriegel. Optimal repairs in the description logic *EL* revisited. In *Proceedings of the 18th European Conference on Logics in Artificial Intelligence (JELIA)*, 2023.

16 Franz Baader, Patrick Koopmann, Francesco Kriegel, and Adrian Nuradiansyah. Computing optimal repairs of quantified ABoxes w.r.t. static *EL* TBoxes. In *Proceedings of the 28th International Conference on Automated Deduction (CADE)*, 2021.

17 Franz Baader and Francesco Kriegel. Pushing optimal ABox repair from *EL* towards more expressive Horn-DLS. In *Proceedings of the 19th International Conference on Principles of Knowledge Representation and Reasoning (KR)*, 2022.

18 Franz Baader, Francesco Kriegel, and Adrian Nuradiansyah. Inconsistency- and error-tolerant reasoning w.r.t. optimal repairs of *EL*<sup>⊥</sup> ontologies. In *Proceedings of the 13th International Symposium on Foundations of Information and Knowledge Systems (FoIKS)*, 2024.

19 Jean-François Baget, Salem Benferhat, Zied Bouraoui, Madalina Croitoru, Marie-Laure Mugnier, Odile Papini, Swan Rocher, and Karim Tabia. A general modifier-based framework for inconsistency-tolerant query answering. In *Proceedings of the 15th International Conference Principles of Knowledge Representation and Reasoning (KR)*, 2016.

20 Jean-François Baget, Michel Leclère, Marie-Laure Mugnier, and Eric Salvat. On rules with existential variables: Walking the decidability line. *Artificial Intelligence (AIJ)*, 175(9-10):1620–1654, 2011.

21 Pablo Barceló, Gaëlle Fontaine, Sylvain Salvati, and Sophie Tison. Corrections to "On the data complexity of consistent query answering over graph databases [Journal of Computer and System Sciences 88 (2017) 164-194]". *Journal of Computer and System Sciences*, 155:103694, 2026.
22 Sihem Belabbes, Salem Benferhat, and Jan Chomicki. Handling inconsistency in partially preordered ontologies: the Elect method. *Journal of Logic and Computation*, 31(5):1356–1388, 2021.

23 Salem Benferhat, Zied Bouraoui, Madalina Croitoru, Odile Papini, and Karim Tabia. Non-objection inference for inconsistency-tolerant query answering. In *Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI)*, 2016.

24 Salem Benferhat, Zied Bouraoui, and Karim Tabia. How to select one preferred assertional-based repair from inconsistent and prioritized DL-Lite knowledge bases? In *Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI)*, 2015.

25 Leopoldo E. Bertossi. *Database Repairing and Consistent Query Answering*. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2011.

26 Leopoldo E. Bertossi. Database repairs and consistent query answering: Origins and further developments. In *Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS)*, 2019.

27 Meghyn Bienvenu. On the complexity of consistent query answering in the presence of simple ontologies. In *Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI)*, 2012.

28 Meghyn Bienvenu. A short survey on inconsistency handling in ontology-mediated query answering. *Künstliche Intelligenz*, 34(4):443–451, 2020.

29 Meghyn Bienvenu and Camille Bourgaux. Inconsistency-tolerant querying of description logic knowledge bases. In *Tutorial Lectures of the 12th International Reasoning Web Summer School (RW)*, 2016.

30 Meghyn Bienvenu and Camille Bourgaux. Querying and repairing inconsistent prioritized knowledge bases: Complexity analysis and links with abstract argumentation. In *Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning (KR)*, 2020.

31 Meghyn Bienvenu and Camille Bourgaux. Querying inconsistent prioritized data with ORBITS: Algorithms, implementation, and experiments. In *Proceedings of the 19th International Conference on Principles of Knowledge Representation and Reasoning (KR)*, 2022.

32 Meghyn Bienvenu and Camille Bourgaux. Inconsistency handling in prioritized databases with universal constraints: Complexity analysis and links with active integrity constraints. In *Proceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning (KR)*, 2023.

33 Meghyn Bienvenu, Camille Bourgaux, and François Goasdoué. Querying inconsistent description logic knowledge bases under preferred repair semantics. In *Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI)*, 2014.

34 Meghyn Bienvenu, Camille Bourgaux, and François Goasdoué. Explaining inconsistency-tolerant query answering over description logic knowledge bases. In *Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI)*, 2016.

35 Meghyn Bienvenu, Camille Bourgaux, and François Goasdoué. Computing and explaining query answers over inconsistent DL-Lite knowledge bases. *Journal of Artificial Intelligence Research (JAIR)*, 64:563–644, 2019.

36 Meghyn Bienvenu, Camille Bourgaux, and Robin Jean. Cost-based semantics for querying inconsistent weighted knowledge bases. In *Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning (KR)*, 2024.

37 Meghyn Bienvenu, Camille Bourgaux, and Robin Jean. A rule-based approach to specifying preferences over conflicting facts and querying inconsistent knowledge bases. In *Proceedings of the 22nd International Conference on Principles of Knowledge Representation and Reasoning (KR)*, 2025.

38 Meghyn Bienvenu, Camille Bourgaux, and Atefe Khodadaditaghanaki. Inconsistency handling in DatalogMTL. In *Proceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI)*, 2025.
39 Meghyn Bienvenu and Pierre Bourhis. Mixed-world reasoning with existential rules under active-domain semantics. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), 2019.

40 Meghyn Bienvenu and Magdalena Ortiz. Ontology-mediated query answering with data-tractable description logics. In Tutorial Lectures of the 11th Reasoning Web International Summer School (RW), 2015.

41 Meghyn Bienvenu and Riccardo Rosati. Tractable approximations of consistent query answering for robust ontology-based data access. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI), 2013.

42 Bart Bogaerts and Luís Cruz-Filipe. Fixpoint semantics for active integrity constraints. Artificial Intelligence (AIJ), 255:43–70, 2018.

43 Philip Bohannon, Michael Flaster, Wenfei Fan, and Rajeev Rastogi. A cost-based model and effective heuristic for repairing constraints by value modification. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD), 2005.

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

45 Camille Bourgaux, Patrick Koopmann, and Anni-Yasmin Turhan. Ontology-mediated query answering over temporal and inconsistent data. Semantic Web, 10(3):475–521, 2019.

46 Gerhard Brewka, Ilkka Niemelä, and Miroslaw Truszczynski. Answer set optimization. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI), 2003.

47 Samuel R. Buss and Louise Hay. On truth-table reducibility to SAT. Information and Computation, 91(1):86–102, 1991.

48 Marco Calautti, Marco Console, and Andreas Pieris. Counting database repairs under primary keys revisited. In Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), 2019.

49 Marco Calautti, Marco Console, and Andreas Pieris. Benchmarking approximate consistent query answering. In Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), 2021.

50 Marco Calautti, Sergio Greco, Cristian Molinaro, and Irina Trubitsyna. Preference-based inconsistency-tolerant query answering under existential rules. Artificial Intelligence (AIJ), 312:103772, 2022.

51 Marco Calautti, Leonid Libkin, and Andreas Pieris. An operational approach to consistent query answering. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), 2018.

52 Marco Calautti, Ester Livshits, Andreas Pieris, and Markus Schneider. Counting database repairs entailing a query: The case of functional dependencies. In Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), 2022.

53 Marco Calautti, Ester Livshits, Andreas Pieris, and Markus Schneider. Combined approximations for uniform operational consistent query answering. Proceedings of the ACM on Management of Data (PACMMOD), 2(2):99, 2024.

54 Andrea Calì, Georg Gottlob, and Michael Kifer. Taming the infinite chase: Query answering under expressive relational constraints. Journal of Artificial Intelligence Research (JAIR), 48:115–174, 2013.

55 Andrea Calì, Georg Gottlob, and Thomas Lukasiewicz. Datalog extensions for tractable query answering over ontologies. In Semantic Web Information Management - A Model-Based Perspective, pages 249–279. 2009.

56 Andrea Calì, Georg Gottlob, and Thomas Lukasiewicz. A general Datalog-based framework for tractable query answering over ontologies. Journal of Web Semantics, 14:57–83, 2012.

57 Andrea Calì, Georg Gottlob, and Andreas Pieris. Towards more expressive ontology languages: The query answering problem. Artificial Intelligence (AIJ), 193:87–128, 2012.
58 Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati. Tractable reasoning and efficient query answering in description logics: The DL-Lite family. *Journal of Automated Reasoning* (JAR), 2007.

59 Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati. Data complexity of query answering in description logics. In *Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning (KR)*, 2006.

60 Nofar Carmeli, Martin Grohe, Benny Kimelfeld, Ester Livshits, and Muhammad Tibi. Database repairing with soft functional dependencies. *ACM Transactions on Database Systems*, 49(2):8:1–8:34, 2024.

61 Luciano Caroprese, Sergio Greco, and Ester Zumpano. Active integrity constraints for database consistency maintenance. *IEEE Transactions on Knowledge and Data Engineering*, 21(7):1042–1058, 2009.

62 Luciano Caroprese and Miroslaw Truszczynski. Active integrity constraints and revision programming. *Theory and Practice of Logic Programming (TPLP)*, 11(6):905–952, 2011.

63 Ashok K. Chandra and Philip M. Merlin. Optimal implementation of conjunctive queries in relational data bases. In *Proceedings of the 9th Annual ACM Symposium on Theory of Computing (STOC)*, 1977.

64 Jan Chomicki, Jerzy Marcinkowski, and Slawomir Staworko. Computing consistent query answers using conflict hypergraphs. In *Proceedings of the ACM International Conference on Information and Knowledge Management (CIKM)*, 2004.

65 Jan Chomicki, Jerzy Marcinkowski, and Slawomir Staworko. Hippo: A system for computing consistent answers to a class of SQL queries. In *Proceedings of the 9th International Conference on Extending Database Technology (EDBT)*, 2004.

66 Jan Chomicki and Jef Wijsen. Consistent query answering for atemporal constraints over temporal databases. In *Proceedings of the 23rd International Symposium on Temporal Representation and Reasoning (TIME)*, 2016.

67 Madalina Croitoru and Srdjan Vesic. What can argumentation do for inconsistent ontology query answering? In *Proceedings of the 7th International Conference on Scalable Uncertainty Management (SUM)*, 2013.

68 Luís Cruz-Filipe. Grounded fixpoints and active integrity constraints. In *Technical Communications of the 32nd International Conference on Logic Programming (ICLP)*, 2016.

69 Luís Cruz-Filipe, Graça Gaspar, Patrícia Engrácia, and Isabel Nunes. Computing repairs from active integrity constraints. In *Proceedings of the 7th International Symposium on Theoretical Aspects of Software Engineering (TASE)*, 2013.

70 Evgeny Dantsin, Thomas Eiter, Georg Gottlob, and Andrei Voronkov. Complexity and expressive power of logic programming. *ACM Computing Surveys*, 33(3):374–425, 2001.

71 Akhil A. Dixit and Phokion G. Kolaitis. A SAT-based system for consistent query answering. In *Proceedings of the 22nd International Conference on Theory and Applications of Satisfiability Testing (SAT)*, 2019.

72 Akhil A. Dixit and Phokion G. Kolaitis. CAvSAT: Answering aggregation queries over inconsistent databases via SAT solving. In *Proceedings of the International Conference on Management of Data (SIGMOD)*, 2021.

73 Jianfeng Du, Guilin Qi, and Yi-Dong Shen. Weight-based consistent query answering over inconsistent SHIQ knowledge bases. *Knowledge and Information Systems*, 34(2):335–371, 2013.

74 Jianfeng Du, Yi-Dong Shen, and Guilin Qi. Decomposition-based consistent query answering in databases with universal constraints under cardinality-based semantics. In *Proceedings of the International Conference on Computational Intelligence and Software Engineering (CISE)*, 2010.
75 Jianfeng Du, Kewen Wang, and Yi-Dong Shen. Towards tractable and practical ABox abduction over inconsistent description logic ontologies. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI), 2015.

76 Phan Minh Dung. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artificial Intelligence (AIJ), 77(2):321–358, 1995.

77 Thomas Eiter, Michael Fink, Gianluigi Greco, and Domenico Lembo. Repair localization for query answering from inconsistent databases. ACM Transactions on Database Systems, 33(2):10:1–10:51, 2008.

78 Thomas Eiter, Thomas Lukasiewicz, and Livia Predoiu. Generalized consistent query answering under existential rules. In Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning (KR), 2016.

79 Zhiwei Fan, Paraschos Koutris, Xiating Ouyang, and Jef Wijsen. LinCQA: Faster consistent query answering with linear time guarantees. Proceedings of the ACM on Management of Data (PACMMOD), 1(1):38:1–38:25, 2023.

80 Sergio Flesca, Sergio Greco, and Ester Zumpano. Active integrity constraints. In Proceedings of the 6th International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP), 2004.

81 Giorgos Flouris and Antonis Bikakis. A comprehensive study of argumentation frameworks with sets of attacking arguments. International Journal of Approximate Reasoning, 109:55–86, 2019.

82 Ariel Fuxman, Elham Fazli, and Renée J. Miller. Conquer: Efficient management of inconsistent databases. In Proceedings of the ACM International Conference on Management of Data (SIGMOD), 2005.

83 Ariel Fuxman and Renée J. Miller. First-order query rewriting for inconsistent databases. In Proceedings of the 10th International Conference on Database Theory (ICDT), 2005.

84 Birte Glimm, Carsten Lutz, Ian Horrocks, and Ulrike Sattler. Conjunctive query answering for the description logic SHIQ. Journal of Artificial Intelligence Research (JAIR), 31:157–204, 2008.

85 Nikos Gorogiannis and Anthony Hunter. Instantiating abstract argumentation with classical logic arguments: Postulates and properties. Artificial Intelligence (AIJ), 175(9-10):1479–1497, 2011.

86 Gianluigi Greco, Sergio Greco, and Ester Zumpano. A logic programming approach to the integration, repairing and querying of inconsistent databases. In Proceedings of the 17th International Conference on Logic Programming (ICLP), 2001.

87 Gianluigi Greco, Sergio Greco, and Ester Zumpano. A logical framework for querying and repairing inconsistent databases. IEEE Transactions on Knowledge and Data Engineering, 15(6):1389–1408, 2003.

88 Sergio Greco, Cristian Molinaro, and Irina Trubitsyna. Computing approximate query answers over inconsistent knowledge bases. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), 2018.

89 Lane A. Hemachandra. The strong exponential hierarchy collapses. Journal of Computer and System Sciences, 39(3):299–322, 1989.

90 Ullrich Hustadt, Boris Motik, and Ulrike Sattler. Data complexity of reasoning in very expressive description logics. In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI), 2005.

91 Aziz Amezian El Khalfioui, Jonathan Joertz, Dorian Labeeuw, Gaëtan Staquet, and Jef Wijsen. Optimization of answer set programs for consistent query answering by means of first-order rewriting. In Proceedings of the 29th ACM International Conference on Information and Knowledge Management (CIKM), 2020.
92 Benny Kimelfeld, Ester Livshits, and Liat Peterfreund. Detecting ambiguity in prioritized database repairing. In *Proceedings of the 20th International Conference on Database Theory (ICDT)*, 2017.

93 Benny Kimelfeld, Ester Livshits, and Liat Peterfreund. Counting and enumerating preferred database repairs. *Theoretical Computer Science*, 837:115–157, 2020.

94 Phokion G. Kolaitis, Nina Pardal, Jonni Virtema, and Jef Wijsen. Rewriting consistent answers on annotated data. *Proceedings of the ACM on Management of Data (PACMMOD)*, 3(2):110:1–110:26, 2025.

95 Phokion G. Kolaitis, Enela Pema, and Wang-Chiew Tan. Efficient querying of inconsistent databases with binary integer programming. *Proceedings of the VLDB Endowment*, 6(6):397–408, 2013.

96 Mark W. Krentel. The complexity of optimization problems. *Journal of Computer and System Sciences*, 36(3):490–509, 1988.

97 Ahmed Laouar, Sihem Belabbes, and Salem Benferhat. Tractable closure-based possibilistic repair for partially ordered DL-Lite ontologies. In *Proceedings of the 18th European Conference on Artificial Intelligence (JELIA)*, 2023.

98 Domenico Lembo, Maurizio Lenzerini, Riccardo Rosati, Marco Ruzzi, and Domenico Fabio Savo. Inconsistency-tolerant semantics for description logics. In *Proceedings of the 4th International Conference on Web Reasoning and Rule Systems (RR)*, 2010.

99 Domenico Lembo, Maurizio Lenzerini, Riccardo Rosati, Marco Ruzzi, and Domenico Fabio Savo. Inconsistency-tolerant query answering in ontology-based data access. *Journal of Web Semantics*, 33:3–29, 2015.

100 Ester Livshits, Benny Kimelfeld, and Sudeepa Roy. Computing optimal repairs for functional dependencies. *ACM Transactions on Database Systems*, 45(1):4:1–4:46, 2020.

101 Ester Livshits, Benny Kimelfeld, and Jef Wijsen. Counting subset repairs with functional dependencies. *Journal of Computer and System Sciences*, 117:154–164, 2021.

102 Andrei Lopatenko and Leopoldo E. Bertossi. Complexity of consistent query answering in databases under cardinality-based and incremental repair semantics. In *Proceedings of the 11th International Conference on Database Theory (ICDT)*, 2007.

103 Andrei Lopatenko and Leopoldo E. Bertossi. Complexity of consistent query answering in databases under cardinality-based and incremental repair semantics (extended version). *CoRR*, abs/1605.07159, 2016.

104 Thomas Lukasiewicz, Enrico Malizia, Maria Vanina Martinez, Cristian Molinaro, Andreas Pieris, and Gerardo I. Simari. Inconsistency-tolerant query answering for existential rules. *Artificial Intelligence (AIJ)*, 307:103685, 2022.

105 Thomas Lukasiewicz, Enrico Malizia, and Cristian Molinaro. Explanations for inconsistency-tolerant query answering under existential rules. In *Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI)*, 2020.

106 Thomas Lukasiewicz, Enrico Malizia, and Cristian Molinaro. Explanations for negative query answers under inconsistency-tolerant semantics. In *Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI)*, 2022.

107 Thomas Lukasiewicz, Enrico Malizia, and Cristian Molinaro. Complexity of inconsistency-tolerant query answering in Datalog+/- under preferred repairs. In *Proceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning (KR)*, 2023.

108 Thomas Lukasiewicz, Enrico Malizia, and Andrius Vaicenavicius. Complexity of inconsistency-tolerant query answering in Datalog+/- under cardinality-based repairs. In *Proceedings of the 33rd AAAI Conference on Artificial Intelligence*, (AAAI), 2019.

109 Thomas Lukasiewicz, Maria Vanina Martinez, and Gerardo I. Simari. Inconsistency handling in Datalog+/- ontologies. In *Proceedings of the 20th European Conference on Artificial Intelligence (ECAI)*, 2012.
110 Carsten Lutz. The complexity of conjunctive query answering in expressive description logics. In *Proceedings of the 4th International Joint Conference on Automated Reasoning, (IJCAR)*, 2008.

111 Carsten Lutz, Inanç Seylan, and Frank Wolter. Ontology-mediated queries with closed predicates. In *Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI)*, 2015.

112 Yasir Mahmood, Markus Hecher, and Axel-Cyrille Ngonga Ngomo. Dung's argumentation framework: Unveiling the expressive power with inconsistent databases. In *Proceedings of the 39th AAAI Conference on Artificial Intelligence (AAAI)*, 2025.

113 Yasir Mahmood, Jonni Virtema, Timon Barlag, and Axel-Cyrille Ngonga Ngomo. Computing repairs under functional and inclusion dependencies via argumentation. In *Proceedings of the 13th International Symposium on Foundations of Information and Knowledge Systems (FoIKS)*, 2024.

114 Marco Manna, Francesco Ricca, and Giorgio Terracina. Consistent query answering via ASP from different perspectives: Theory and practice. *Theory and Practice of Logic Programming (TPLP)*, 13(2):227-252, 2013.

115 Marco Manna, Francesco Ricca, and Giorgio Terracina. Taming primary key violations to query large inconsistent data via ASP. *Theory and Practice of Logic Programming (TPLP)*, 15(4-5):696-710, 2015.

116 Lorenzo Marconi and Riccardo Rosati. Consistent query answering over existential rules with open and closed predicates. In *Proceedings of the 39th AAAI Conference on Artificial Intelligence (AAAI)*, 2025.

117 Mónica Caniupán Marileo and Leopoldo E. Bertossi. The consistency extractor system: Answer set programs for consistent query answering in databases. *Data & Knowledge Engineering*, 69(6):545-572, 2010.

118 Dany Maslowski and Jef Wijsen. A dichotomy in the complexity of counting database repairs. *Journal of Computer and System Sciences*, 79(6):958-983, 2013.

119 Nhung Ngo, Magdalena Ortiz, and Mantas Simkus. Closed predicates in description logics: Results on combined complexity. In *Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning (KR)*, 2016.

120 Magdalena Ortiz, Diego Calvanese, and Thomas Eiter. Data complexity of query answering in expressive description logics via tableaux. *Journal of Automated Reasoning (JAR)*, 41(1):61-98, 2008.

121 W3C OWL Working Group. OWL 2 Web Ontology Language: Document Overview, 2009. Available at http://www.w3.org/TR/owl2-overview/.

122 Horacio Tellez Perez and Jef Wijsen. Generalized weighted repairs. In *Proceedings of the 14th International Conference on Flexible Query Answering Systems (FQAS)*, 2021.

123 Reinhard Pichler and Sebastian Skritek. The complexity of evaluating tuple generating dependencies. In *Proceedings of the 14th International Conference on Database Theory (ICDT)*, 2011.

124 Antonella Poggi, Domenico Lembo, Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzini, and Riccardo Rosati. Linking data to ontologies. *Journal of Data Semantics*, 10:133-173, 2008.

125 Riccardo Rosati. On conjunctive query answering in *EL*. In *Proceedings of the International Workshop on Description Logics (DL)*, 2007.

126 Riccardo Rosati. On the complexity of dealing with inconsistency in description logic ontologies. In *Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI)*, 2011.

127 Riccardo Rosati, Marco Ruzzi, Mirko Graziosi, and Giulia Masotti. Evaluation of techniques for inconsistency handling in OWL 2 QL ontologies. In *Proceedings of the 11th International Semantic Web Conference (ISWC)*, 2012.
128 Andrea Schaerf. On the complexity of the instance checking problem in concept languages with existential quantification. *Journal of Intelligent Information Systems*, 2(3):265–278, 1993.

129 Slawek Staworko, Jan Chomicki, and Jerzy Marcinkowski. Prioritized repairing and consistent query answering in relational databases. *Annals of Mathematics and Artificial Intelligence (AMAI)*, 64(2-3):209–246, 2012.

130 Balder ten Cate, Gaëlle Fontaine, and Phokion G. Kolaitis. On the data complexity of consistent query answering. *Theory of Computing Systems (TOCS)*, 57(4):843–891, 2015.

131 Michaël Thomazo. *Conjunctive query answering under existential rules - Decidability, complexity, and algorithms*. PhD thesis, Montpellier 2 University, France, 2013.

132 Stephan Tobies. *Complexity results and practical algorithms for logics in knowledge representation*. PhD thesis, RWTH Aachen University, Germany, 2001.

133 Despoina Trivela, Giorgos Stoilos, and Vasilis Vassalos. A framework and positive results for IAR-answering. In *Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI)*, 2018.

134 Eleni Tsalapati, Giorgos Stoilos, Giorgos B. Stamou, and George Koletsos. Efficient query answering over expressive inconsistent description logics. In *Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI)*, 2016.

135 Moshe Y. Vardi. On the complexity of bounded-variable queries. In *Proceedings of the 14th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS)*, 1995.

136 Guohui Xiao, Diego Calvanese, Roman Kontchakov, Domenico Lembo, Antonella Poggi, Riccardo Rosati, and Michael Zakharyaschev. Ontology-based data access: A survey. In *Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI)*, 2018.