arXiv CSopen access

Using ASP(Q) to Handle Inconsistent Prioritized Data

Using ASP(Q) to Handle Inconsistent Prioritized Data

arXiv:2604.21603v1 [cs.LO] 23 Apr 2026

Meghyn Bienvenu1 , Camille Bourgaux2 , Robin Jean 1 , Giuseppe Mazzotta3 1 Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, Talence, France 2 DI ENS, ENS, CNRS, PSL University & Inria, Paris, France 3 University of Calabria, Rende, Italy {meghyn.bienvenu, robin.jean}@u-bordeaux.fr, [email protected], [email protected] Abstract We explore the use of answer set programming (ASP) and its extension with quantifiers, ASP(Q), for inconsistencytolerant querying of prioritized data, where a priority relation between conflicting facts is exploited to define three notions of optimal repairs (Pareto-, globally- and completionoptimal). We consider the variants of three well-known semantics (AR, brave and IAR) that use these optimal repairs, and for which query answering is in the first or second level of the polynomial hierarchy for a large class of logical theories. Notably, this paper presents the first implementation of globally-optimal repair-based semantics, as well as the first implementation of the grounded semantics, which is a tractable under-approximation of all these optimal repairbased semantics. Our experimental evaluation sheds light on the feasibility of computing answers under globally-optimal repair semantics and the impact of adopting different semantics, approximations, and encodings.

1

Introduction

Repair-based semantics are a prominent means of obtaining meaningful answers to queries posed over some data which is inconsistent w.r.t. some logical theory, both in the relational database and ontology-mediated query answering setting (cf. (Bertossi 2019; Bienvenu 2020) for brief overviews). In this context, a repair is a subset-maximal subset of the data consistent with the logical theory. The most well-known repair-based semantics, called AR in the KR community, requires that the query holds in every repair, while the less cautious brave semantics requires that it holds in some repair, and the more cautious IAR semantics that it holds in the intersection of all repairs (Arenas, Bertossi, and Chomicki 1999; Lembo et al. 2010; Bienvenu and Rosati 2013). Several notions of preferred repairs have been proposed to take into account some preference information and consider only a subset of all the possible repairs to evaluate the queries (cf. (Bourgaux 2025) for a survey). In particular, Staworko, Chomicki, and Marcinkowski (2012) introduced three kinds of optimal repairs based on a priority relation between conflicting facts, which have attracted a lot of interest in the last decade with extensive complexity analyses (Kimelfeld, Livshits, and Peterfreund 2017; Kimelfeld, Livshits, and Peterfreund 2020; Bienvenu and Bourgaux 2020; Bienvenu and Bourgaux

2023), two implementations (Bienvenu and Bourgaux 2022; Bienvenu et al. 2025), and a framework for specifying and computing priority relations (Bienvenu et al. 2025). However, only two of these three kinds of repairs have actually been implemented in the existing systems, namely the Pareto- and completion-optimal repairs. This is due to the higher complexity of reasoning with the third kind of repairs, called globally-optimal. Indeed, for a large class of database constraints and ontology languages, the data complexity of query answering under the variants of AR, IAR and brave that use Pareto- or completion-optimal repairs is in the first level of the polynomial hierarchy, while it is in the second level for the globally-optimal repair-based variants. Most implementations of repair-based semantics encode query entailment under some intractable semantics into SAT, binary integer programming, or answer set programming (ASP) to take advantage of the efficient solvers that exist for these problems (see, e.g., (Greco, Greco, and Zumpano 2003; Eiter et al. 2008; Manna, Ricca, and Terracina 2013; Kolaitis, Pema, and Tan 2013; Bienvenu, Bourgaux, and Goasdoué 2014; Dixit and Kolaitis 2019) for relevant examples and (Bourgaux 2025, Table 8) for an overview). The two implementations of optimal repair-based semantics follow this path: the one by Bienvenu and Bourgaux (2022) is based on the use of tractable approximations and SAT solvers, and that by Bienvenu et al. (2025) uses ASP. A notable difference between the two systems is that the former focuses on the case where the conflicts (i.e., the minimal sets of facts inconsistent w.r.t. the logical theory) are of size at most two while the latter handles conflicts of arbitrary size. ASP (with disjunctive rules) can be used to model problems up to the second level of the polynomial hierarchy, meaning that semantics based on globally-optimal repairs could theoretically be implemented in ASP. However, this requires advanced techniques, such as saturation (Eiter and Gottlob 1995), which complicate modeling “beyond the capabilities of the common ASP laymen” (Gebser, Kaminski, and Schaub 2011). Moreover, efficiency-wise it has been shown that in many cases of practical interest alternative formalisms are preferred to disjunctive ASP (Amendola et al. 2022). Among alternative formalisms, answer set programming with quantifiers (ASP(Q)) uses quantifiers over answer sets of ASP programs and provides a natural and compact way of modeling problems in the entire polynomial hierar-

chy (Amendola, Ricca, and Truszczynski 2019). ASP(Q) has already been used to tackle problems related to planning (Fandinno et al. 2021; Faber, Morak, and Chrpa 2022) and abstract argumentation (Faber 2024). We investigate the use of ASP(Q) and ASP to implement optimal repair-based semantics. Compared to the previous ASP-based implementation by Bienvenu et al. (2025), we handle globally-optimal repairs thanks to ASP(Q) and improve the system performance by using tractable approximations in a similar way as Bienvenu and Bourgaux (2022). Moreover, we explore the use of another tractable approximation of the optimal repair-based semantics, called the grounded semantics (Bienvenu and Bourgaux 2020), which has never been implemented so far. Our experimental evaluation shows that using globally-optimal repairs is considerably more challenging than for Pareto- or completionoptimal repairs, while at the same time demonstrating the utility of different optimizations, in particular, the surprising effectiveness of the grounded semantics. Proofs and additional details on the experiments are provided in the appendix. All materials to reproduce the experiments are available from https://github.com/rjean007/ InconsistentPrioritizedData-ASPQ.

2

Preliminaries

In this section, we introduce the relevant background on inconsistency-tolerant semantics and ASP(Q).

2.1

Optimal Repair-Based Semantics

We recall the framework of inconsistency-tolerant querying of prioritized knowledge bases. All notions will be illustrated in Example 1. Let P, C and V be three disjoint sets of predicates, constants and variables, respectively. We assume that each predicate has some arity n ≥ 1, and let Pn be the set of the n-ary predicates in P. Knowledge Bases, Conflicts, Repairs A knowledge base (KB) K = (D, T ) consists of a dataset D and a logical theory T : D is a finite set of facts of the form P (c1 , . . . , cn ) with P ∈ Pn , ci ∈ C for 1 ≤ i ≤ n, and T is a finite set of first-order logic (FOL) sentences built from P, C and V. Typically, T will be either an ontology (e.g., formulated in some description logic) or a set of database constraints. In particular, we consider description logics of the DL-Lite family (Calvanese et al. 2007) and denial constraints of the form α1 ∧ . . . ∧ αn → ⊥, where each αi is a relational or inequality atom, which include functional dependencies (FDs). A KB K = (D, T ) is consistent, and D is called T -consistent, if D ∪ T has some model. Otherwise, K is inconsistent, denoted K |= ⊥. A conflict of K = (D, T ) is an inclusion-minimal subset C ⊆ D such that (C, T ) |= ⊥. The set of conflicts of K is denoted Conf (K). A (subset) repair of K is an inclusion-maximal subset R ⊆ D such that (R, T ) ̸|= ⊥. The set of repairs of K is denoted SRep(K). Prioritized KBs, Optimal Repairs A priority relation ≻ for a KB K = (D, T ) is an acyclic binary relation over the facts of D such that α ≻ β implies that {α, β} ⊆ C for some C ∈ Conf (K). It is total if for every pair α ̸= β

such that {α, β} ⊆ C for some C ∈ Conf (K), either α ≻ β or β ≻ α. A completion of ≻ is a total priority relation ≻′ ⊇ ≻. A prioritized KB K≻ is a KB K with a priority relation ≻ for K. Three kinds of optimal repairs are defined: Definition 1. Let K≻ be a prioritized KB with K = (D, T ) and R ∈ SRep(K). • A Pareto improvement of R is a T -consistent B ⊆ D such that there is β ∈ B \ R with β ≻ α for every α ∈ R \ B. • A global improvement of R is a T -consistent B ⊆ D such that B ̸= R and for every α ∈ R\B there exists β ∈ B\R such that β ≻ α. The repair R is: • Pareto-optimal if there is no Pareto improvement of R; • globally-optimal if there is no global improvement of R; • completion-optimal if R is a globally-optimal repair of K≻′ , for some completion ≻′ of ≻. We denote by PRep(K≻ ), GRep(K≻ ) and CRep(K≻ ) the sets of Pareto-, globally- and completion-optimal repairs. It is known that CRep(K≻ ) ⊆ GRep(K≻ ) ⊆ PRep(K≻ ). Queries, Repair-Based Semantics A conjunctive query (CQ) is a conjunction of atoms P (t1 , . . . , tn ) (P ∈ Pn , ti ∈ C ∪ V), where some variables may be existentially quantified. Given a query q(⃗x), with free variables ⃗x, and a tuple of constants ⃗a such that |⃗a| = |⃗x|, q(⃗a) denotes the first-order sentence obtained by replacing each variable in ⃗x by the corresponding constant in ⃗a. A (certain) answer to q(⃗x) over K is a tuple ⃗a of constants such that q(⃗a) holds in every model of K, denoted K |= q(⃗a). When the KB is inconsistent, we consider the following alternative semantics, parameterized by the considered type of repair. Definition 2. Fix X ∈ {S, P, G, C} and consider a prioritized KB K≻ with K = (D, T ), query q(⃗x), and tuple of constants ⃗a. Then ⃗a is an answer to q(⃗x) over K≻ • under X-brave semantics, denoted K≻ |=X a), if brave q(⃗ (R, T ) |= q(⃗a) for some R ∈ XRep(K≻ ); • under X-AR semantics, denoted K≻ |=X a), if AR q(⃗ (R, T ) |= q(⃗a) for every R ∈ XRep(K≻ ); • under X-IAR semantics, T denoted K≻ |=X a), if IAR q(⃗ (B, T ) |= q(⃗a) where B = R∈XRep(K≻ ) R. X X It is known that K≻ |=X IAR q ⇒ K≻ |=AR q ⇒ K≻ |=brave q. A cause for q(⃗a) w.r.t. K = (D, T ) is an inclusion-minimal T -consistent subset C ⊆ D such that (C, T ) |= q(⃗a). The set of causes for q(⃗a) w.r.t. K is denoted by Causes(q(⃗a), K). We will use the following characterizations of the semantics: • K≻ |=X a) iff there exist R ∈ XRep(K≻ ) and C ∈ brave q(⃗ Causes(q(⃗a), K) such that C ⊆ R; • K≻ ̸|=X a) iff there exists R ∈ XRep(K≻ ) such that AR q(⃗ for every C ∈ Causes(q(⃗a), K), C ̸⊆ R; • K≻ |=X q(⃗a) iff there exists C ∈ Causes(q(⃗a), K) such IART that C ⊆ R∈XRep(K≻ ) R.

Theorems 1 and 2 summarize known results on the data complexity (where the sizes of the logical theory T and query q(⃗x) are assumed to be fixed) of query answering under these semantics (cf. survey (Bourgaux 2025, Table 6)).

Theorem 1. Let L be an FOL fragment for which KB consistency and query entailment are in PT IME. Query entailment for L KBs is in Σp2 under G-brave semantics, in Πp2 under G-AR and G-IAR semantics, and for X ∈ {S, P, C}, it is in NP under X-brave semantics, and in coNP under XAR and X-IAR semantics. Theorem 2. Let L be any FOL fragment that extends DLLitecore or FDs. Query entailment for L KBs is Σp2 -hard under G-brave semantics, Πp2 -hard under G-AR and GIAR semantics, NP-hard under X-brave semantics for X ∈ {P, C}, and coNP-hard under X-AR semantics for X ∈ {S, P, C} and under X-IAR semantics for X ∈ {P, C}. Attack Relation, Grounded Semantics The grounded semantics for prioritized KBs comes from the area of abstract argumentation. For prioritized KB K≻ with K = (D, T ), the attack relation ⇝⊆ (2D \ {∅}) × D is defined by: ⇝= {(C \{α}, α) | C ∈ Conf (K), α ∈ C, ∀β ∈ C, α ̸≻ β}. We write B ⇝ α for (B, α) ∈⇝. The characteristic function Γ : 2D 7→ 2D is defined by Γ(B) = {α | E ⇝ α ⇒ ∃F ⊆ B, β ∈ E s.t. F ⇝ β}. The grounded repair of K≻ is the inclusion-minimal G ⊆ D such that G is T -consistent and G = Γ(G), or equivalently, the least fixpoint of Γ. A tuple ⃗a is an answer to q(⃗x) over K≻ under grounded semantics, denoted K≻ |=GR q(⃗a), if (G, T ) |= q(⃗a). It is known that K≻ |=GR q(⃗a) implies K≻ |=P a), so answers that hold under the grounded seIAR q(⃗ mantics hold under X-IAR for X ∈ {P, G, C}. Moreover, if L is an FOL fragment for which the conflicts size is bounded independently from the data and KB consistency and query entailment are in PT IME, then grounded query entailment for L KBs is in PT IME (Bienvenu and Bourgaux 2020). Example 1. Consider the KB K = (D, T ) with: D = {A(a), B(a), C(a), D(a), A(b), B(b), C(b)} T = {A(x) ∧ B(x) → ⊥, B(x) ∧ C(x) → ⊥, C(x) ∧ D(x) → ⊥, D(x) ∧ A(x) → ⊥} The conflicts and repairs of K are as follows: Conf (K) = {{A(a), B(a)}, {B(a), C(a)}, {C(a), D(a)}, {D(a), A(a)}, {A(b), B(b)}, {B(b), C(b)}} SRep(K) = {{A(a), C(a), B(b)}, {B(a), D(a), B(b)} {A(a), C(a), A(b), C(b)}, {B(a), D(a), A(b), C(b)}} Let us define a priority relation ≻ for K by A(a) ≻ B(a), C(a) ≻ D(a), A(b) ≻ B(b), and B(b) ≻ C(b). CRep(K≻ ) = GRep(K≻ ) = {{A(a), C(a), A(b), C(b)}} PRep(K≻ ) = GRep(K≻ ) ∪ {{B(a), D(a), A(b), C(b)}} P We thus obtain, e.g., K≻ |=G AR A(a) while K≻ ̸|=AR A(a), P G K≻ |=brave B(a) while K≻ ̸|=brave B(a), and K≻ |=X IAR C(b) for X ∈ {P, G, C}. The grounded repair of K≻ is G = {A(b), C(b)}. Indeed, the attack relation ⇝ is as written below, so Γ(∅) = {A(b)}, since A(b) is the only fact

of D that is not attacked, Γ({A(b)}) = {A(b), C(b)}, and Γ({A(b), C(b)}) = {A(b), C(b)}. {A(a)} ⇝ B(a) {C(a)} ⇝ D(a) {A(b)} ⇝ B(b)

{B(a)} ⇝ C(a) {C(a)} ⇝ B(a) {D(a)} ⇝ A(a) {A(a)} ⇝ D(a) {B(b)} ⇝ C(b)

Note that G is indeed included in the intersection of the Pareto-optimal repairs (which is actually equal to G here).

2.2

Answer Set Programming with Quantifiers

We now recall basic notions about Answer Set Programming (ASP) and ASP with Quantifiers (ASP(Q)). ASP In ASP, atoms take the form p(t1 , . . . , tn ) where p is a predicate of arity n ≥ 0 and each term ti is either a constant (integer or alphanumeric string starting with lowercase letter) or a variable (alphanumeric string starting with uppercase letter). A literal is an atom a or its negation not a, where not represents negation as failure. It is negative if it is of the form not a, positive otherwise. An ASP program1 is a finite set of rules of the form h : - l1 , . . . , ln (with n ≥ 0), whose head h is an atom, and whose body l1 , . . . , ln is interpreted as the conjunction of the literals l1 , . . . , ln . Every rule must be safe, i.e., each variable appearing in it appears in some positive body literal. A constraint is a rule with an empty head ( : - l1 , . . . , ln ), and a fact is a rule with an empty body (h : - ). We also allow choice rules of the forms {h} : - l1 , . . . , ln and 1{h1 ; h2 }1 : - l1 , . . . , ln : the former is used to choose to either add or omit h, and the latter enforces that precisely one of h1 and h2 holds, when the rule body is satisfied. Choice rules are syntactic sugar which do not increase the expressive power but enable compact and intuitive modeling (Calimeri et al. 2020). An ASP expression (atom, rule, program, etc.) is ground if it contains no variable. Given an ASP program P , the Herbrand Universe of P is the set UP of constants appearing in P and the Herbrand Base of P is the set BP of ground atoms constructed from predicates of P and constants in UP . We denote by ground (P ) the set of all possible ground rules obtained from rules in P by proper variable substitution with constants in UP (cf. (Calimeri et al. 2020)). An interpretation is a set of atoms I ⊆ BP . A positive (resp. negative) ground literal l = a (resp. l = not a) is true w.r.t. an interpretation I if a ∈ I (resp. a ∈ / I), and false otherwise. A conjunction of ground literals is true w.r.t. I if all the literals are true w.r.t. I, and false otherwise. An interpretation I satisfies a ground rule r if the body of r is false or its head is true w.r.t. I. It is a model of an ASP program P if it satisfies every r ∈ ground (P ). The GL-reduct (Gelfond and Lifschitz 1991) of P w.r.t. I is the program P I obtained from ground (P ) by (i) removing each rule having at least one negative body literal false w.r.t. I; and (ii) removing negative literals from the remaining rules. An answer set of P is an interpretation I such that I is a subset-minimal model of P I . We denote by AS(P ) the set of all answer sets of P . A program P is coherent if it has some answer set. 1

We consider core ASP, without disjunction in rule heads.

ASP(Q) ASP with quantifiers (ASP(Q)) (Amendola, Ricca, and Truszczynski 2019) extends ASP by allowing quantification over answer sets of different ASP programs. An ASP(Q) program is an expression of the form: □1 P1 . . . □n Pn : C

(1)

where C is a stratified2 ASP program (Ceri, Gottlob, and Tanca 1990) with constraints and for each i ∈ {1, . . . , n}, □i ∈ {∃st , ∀st } is a quantifier and Pi is an ASP program. Given an ASP(Q) program Π of form (1), an ASP program P , and an interpretation I, define the following set of facts and constraints and ASP(Q) program, respectively: fixP (I ) ={a : - | a ∈ BP ∩ I} ∪ { : - a | a ∈ BP \ I} ΠP,I =□1 P1 ∪ fixP (I ) . . . □n Pn : C The ASP(Q) semantics is defined inductively: • ∃st P : C is coherent if and only if there exists M ∈ AS(P ) such that C ∪ fixP (M ) is coherent; • ∀st P : C is coherent if and only if for each M ∈ AS(P ), C ∪ fixP (M ) is coherent; • ∃st P Π is coherent if and only if there exists M ∈ AS(P ) such that ΠP,M is coherent; • ∀st P Π is coherent if and only if for each M ∈ AS(P ), ΠP,M is coherent. The quantified answer sets of an existential ASP(Q) program ∃st P Π, with Π of form (1), are all M ∈ AS(P ) such that ΠP,M is coherent. Example 2. Let Π = ∃st P1 ∀st P2 : C where:     a : - not b  e : - a, not f        b : - not a f : - a, not e P1 = P2 =     c : - not d    : - e, d  d : - not c : - f, d C = { :- f } Let us check whether Π is coherent, i.e., whether there is an answer set M1 of P1 such that ∀st P2 ∪ fixP1 (M1 ) : C is coherent. We have AS(P1 ) = {{a, c}, {a, d}, {b, c}, {b, d}}. Consider first M1 = {a, c} and let P2′ = P2 ∪ fixP1 (M1 ). P2′ has two answer sets: M2′ = {a, c, e} and M2′′ = {a, c, f}, so for ∀st P2′ : C to be coherent, both C ∪ fixP2′ (M2′ ) and C ∪ fixP2′ (M2′′ ) have to be coherent. However, C ∪ fixP2′ (M2′′ ) is incoherent (it contains both : - f and f : - ). Thus, M1 = {a, c} is not a quantified answer set of Π and so not a witness for the coherence of Π. Consider now M1 = {b, c}. Then P2′ = P2 ∪ fixP1 (M1 ) has exactly one answer set, M2 = {b, c}. In this case C ∪ fixP2′ (M2 ) is coherent as f is false w.r.t. M2 . Thus, M1 = {b, c} is a quantified answer set of Π and Π is coherent. Let us now consider Π′ of the form ∃st P1 ∀st P2 : C ′ where C ′ = { : - not fail}. Observe that fail does not appear in any rule head of P1 , P2 , and C ′ . Hence, C ′ ∪ fixP2 ∪fixP1 (M1 ) (M2 ) will be incoherent for every choice of 2 Stratified programs respect some conditions that prevent default negation to be involved in recursion.

M1 ∈ AS(P1 ) and M2 ∈ AS(P2 ∪ fixP1 (M1 )), since fail is false w.r.t. any answer set of these programs. Nonetheless, this does not imply that Π′ is incoherent as well. Indeed, M1 = {a, d} is a quantified answer set of Π′ because P2′ = P2 ∪ fixP1 (M1 ) is incoherent, so the universal quantification over answer sets of P2′ is trivially satisfied.

3

Encoding Semantics in ASP(Q)

In this section, we present our approach to compute the answers that hold under the considered optimal repair-based semantics using ASP and ASP(Q) from their causes, the conflicts and the priority relation. Following Bienvenu et al. (2025), we assume that the input is given by ASP facts on the following predicates: conf and cause are unary predicates that store identifiers of the KB conflicts Conf (K) and query answer causes Causes(q(⃗a), K), respectively, inConf and inCause are binary predicates such that inConf(C, A) (resp. inCause(C, A)) means that the fact with identifier A belongs to the conflict (resp. cause) with identifier C, and pref is a binary predicate such that pref(A, B) means that α ≻ β, where α and β are the facts with identifiers A and B respectively.

3.1

Naive Encodings

The logic programs we assemble to build ASP(Q) encodings for semantics based on optimal repairs are given in Table 1. G-Brave and G-AR Using the programs from Table 1, we build the following ASP(Q) programs for G-brave and G-AR semantics (where Π1 Π2 stands for Π1 ∪ Π2 ): st st ΠG brave =∃ ΠReachAll ΠRep ΠSomeCause ∀ ΠGImp : C st st ΠG AR =∃ ΠReachAll ΠRep ΠNoCause ∀ ΠGImp : C

with C = { : - not fail}. Let us first explain how ΠG brave works. We want to check whether there exists R ∈ GRep(K≻ ) such that C ⊆ R for some C ∈ Causes(q(⃗a), K). First, applying the existential quantifier over ΠReachAll ∪ ΠRep ∪ ΠSomeCause serves to search for the existence of a repair that contains a cause. Since the facts that do not appear in any conflict belong to every repair, in what follows, we do not distinguish between actual repairs of K and repairs of (D′ , T ), where D′ contains all facts that occur in some conflict or some cause (i.e., facts whose identifiers are mentioned in our input ASP programs). • The rules in ΠReachAll compute the set of all such facts, encoded as atoms of the form reachable(A), where A is a fact identifier (we will see next how to restrict this set of facts using some notions of reachability, hence the name). • The rules in ΠRep compute a repair R of the set of facts whose identifiers appear in the reachable(A) atoms. The rules in ΠSubRep ⊆ ΠRep compute a T -consistent set R of facts as follows. The choice rule in ΠSubRep guesses for each relevant fact α with identifier A whether α ∈ R, which is encoded as inRepair(A). Remaining rules in ΠSubRep enforce T -consistency: solved(C) is derived if C is the identifier of a conflict which contains a fact α with identifier A such that α ∈ / R, so the constraint : - conf(C), not solved(C) imposes that

ΠReachAll

reachable(A) : - inCause(C, A). reachable(A) : - inConf(C, A).

ΠAttack

non attacking(C, A) : - conf(C), inConf(C, A), inConf(C, B), A != B, pref(A, B). attacks(C, A) : - conf(C), inConf(C, A), not non attacking(C, A).

ΠReachS

ΠAttack reachable(A) : - cause(C), inCause(C, A). reachable(A) : - conf(C), attacks(C, B), reachable(B), inConf(C, A).

ΠReachW

weak attacks(C, A) : - conf(C), inConf(C, A), inConf(C, B), A != B, not pref(A, B). reachable(A) : - cause(C), inCause(C, A). reachable(A) : - conf(C), weak attacks(C, B), reachable(B), inConf(C, A).

ΠReachBin

reachable(A) : - cause(C), inCause(C, A). reachable(A) : - conf(C), inConf(C, B), reachable(B), inConf(C, A), not pref(B, A).

ΠSubRep

{inRepair(A)} : - reachable(A). solved(C) : - inConf(C, A), not inRepair(A). : - conf(C), not solved(C).

ΠRep

ΠSubRep safe(C) : - inConf(C, A), inConf(C, B), not A = B, not inRepair(A), not inRepair(B). keepOut(A) : - inConf(C, A), not inRepair(A), not safe(C). : - reachable(A), not inRepair(A), not keepOut(A).

ΠSatIfCause

violatedCause(C) : - inCause(C, A), not inRepair(A). sat : - cause(C), not violatedCause(C).

ΠSomeCause

ΠSatIfCause : - not sat.

ΠNoCause

ΠSatIfCause : - sat.

ΠGImp

{global imp(A)} : - reachable(A). solved global(C) : - inConf(C, A), not global imp(A). : - conf(C), not solved global(C). impMinusRepair(A) : - global imp(A), not inRepair(A). repairMinusImp(A) : - inRepair(A), not global imp(A). diff : - impMinusRepair(A). diff : - repairMinusImp(A). fake improvement : - not diff. ok(A) : - repairMinusImp(A), impMinusRepair(B), pref(B, A). fake improvement : - repairMinusImp(A), not ok(A). global improvement : - not fake improvement. : - not global improvement.

ΠPOpt

ΠAttack valid(A) : - reachable(A), inRepair(A). invalid att(C, A) : - reachable(A), attacks(C, A), inConf(C, B), not inRepair(B), not A = B. valid(A) : - reachable(A), conf(C), not inRepair(A), attacks(C, A), not invalid att(C, A). : - reachable(A), not valid(A).

ΠPOptBin

valid(A) : - reachable(A), inRepair(A). valid(A) : - reachable(A), conf(C), not inRepair(A), inConf(C, A), not pref(A, B), inConf(C, B), inRepair(B). : - reachable(A), not valid(A).

ΠCompl

pref comp(A, B) : - reachable(A), reachable(B), pref(A, B). 1{pref comp(A, B); pref comp(B, A)}1 : - reachable(A), reachable(B), inConf(C, A), inConf(C, B), not pref(A, B), not pref(B, A), not A = B. trans cl comp(A, B) : - pref comp(A, B). trans cl comp(A, B) : - trans cl comp(A, Y), pref comp(Y, B). : - trans cl comp(A, A).

ΠCOpt

ΠCompl valid(A) : - reachable(A), inRepair(A). invalid att(C, A) : - reachable(A), not inRepair(A), inConf(C, A), not A = B, inConf(C, B), not inRepair(B). invalid att(C, A) : - reachable(A), not inRepair(A), inConf(C, A), inConf(C, B), not A = B, pref comp(A, B). valid(A) : - reachable(A), not inRepair(A), inConf(C, A), not invalid att(C, A). : - reachable(A), not valid(A).

Table 1: Logic programs used to built the ASP(Q) programs that filter query answers that hold under X-brave or X-AR semantics from facts on predicates conf, inConf, pref, cause and inCause. Intuitively, variables A, B are intended for some fact identifiers, and C for some conflict or cause identifier.

at least one fact from each conflict is excluded. The rules in ΠRep \ ΠSubRep ensure ⊆-maximality. Specifically, they identify each conflict C with identifier C that contains at least two facts not in R, encoded by safe(C), and for every non-safe conflict C, they mark the only fact α ∈ C \ R with identifier A using keepOut(A). The last constraint imposes that every α ∈ / R is marked by keepOut, meaning that there is a conflict C such that α ∈ C and C \ {α} ⊆ R, i.e., R ∪ {α} is T -inconsistent.

P- and C- Brave and AR For X ∈ {P, C}, since the data complexity of query answering under X-brave and X-AR semantics is in the first level of the polynomial hierarchy, we use the following plain ASP programs, which verify whether there exists an optimal repair that either contains some cause or does not contain any cause for the query.

• The rules in ΠSomeCause ensure R contains some cause. The rules in ΠSatIfCause derive violatedCause(C) for every cause C with identifier C such that C ̸⊆ R, and the atom sat is derived if there exists some cause C for which violatedCause(C) is not derived (hence C ⊆ R). The constraint in ΠSomeCause \ ΠSatIfCause imposes that sat is true, so at least one cause must be included.

As explained in the case X = G, ΠReachAll ∪ ΠSubRep guesses a T -consistent set R of facts. The programs ΠPOpt and ΠCOpt ensure that R is a Pareto- or completion-optimal repair, respectively, and were used by Bienvenu et al. (2025). • The rules in ΠAttack ⊆ ΠPOpt compute the attack relation ⇝. They produce attacks(C, A) if C and A are identifiers of a conflict C and fact α such that C \ {α} ⇝ α. The next rules in ΠPOpt derive valid(A) for the identifier A of a fact α if (i) α ∈ R, or (ii) α is attacked by C \ {α} for some conflict C such that C \ {α} ⊆ R. The constraint : - reachable(A), not valid(A) thus ensures that every α ∈ / R is attacked by a set of facts included in R. This means that R is ⊆-maximal and Paretooptimal: otherwise, there would be α ∈ / R such that R ∪ {α} \ {β | α ≻ β} is T -consistent and α would not be attacked by any subset of R. • The rules in ΠCompl ⊆ ΠCOpt guess a completion ≻′ of ≻, using pref comp(A, B) to indicate that α ≻′ β, where α and β have identifiers A and B. The next rules in ΠCOpt derive valid(A) for the identifier A of a fact α if (i) α ∈ R, or (ii) α is in a conflict C such that C \ {α} ⊆ R and α ̸≻′ β for every β ∈ C \ {α}. The constraint : - reachable(A), not valid(A) thus ensures that every α ∈ / R is attacked (w.r.t. the attack relation defined w.r.t. ≻′ ) by a set of facts included in R. Finally, as before, ΠSomeCause (resp. ΠNoCause ) enforces that R contains a cause (resp. does not contain any cause). Proposition 3. For X ∈ {P, C}, K≻ |=X a) iff ΠX brave q(⃗ brave X X is coherent, and K≻ |=AR q(⃗a) iff ΠAR is incoherent. T X-IAR We compute R∈XRep(K≻ ) R by checking for each fact whether it holds under X-AR (since a fact holds under X-AR iff it is in every optimal repair). It is then possible to use this set to evaluate the queries under X-IAR.

Hence, an answer set of ΠReachAll ∪ΠRep ∪ΠSomeCause corresponds to some R ∈ SRep(K) with (R, T ) |= q(⃗a). The second program of ΠG brave , ΠGImp , is then used to search for a global improvement of R. • The three first rules guess a T -consistent set of facts B, in the same way as ΠSubRep did, using global imp to store the identifiers of the facts in B. The remaining rules verify whether B is indeed a global improvement of R. • Two rules compute B \ R and R \ B, using predicates impMinusRepair and repairMinusImp, respectively. This is used to (i) check whether B ̸= R with the two rules that derive diff if either B \ R ̸= ∅ or R \ B ̸= ∅ and (ii) check whether for every α ∈ R \ B, there exists β ∈ B \ R such that β ≻ α with the rule that derives ok(A) if α ∈ R \ B with identifier A satisfies this condition. The atom fake improvement is derived when (i) or (ii) is not satisfied, i.e., if diff is false or if ok(A) is false for the identifier A of some α ∈ R \ B. Hence, if fake improvement is false, B is a global improvement of R, and global improvement is derived. • The final constraint enforces that global improvement has been derived, so that B is a global improvement of R. Finally, C contains only the constraint : - not fail and fail does not appear in the head of any rule. Hence, as explained in Example 2, if we let P1 = ΠReachAll ∪ ΠRep ∪ ΠSomeCause and P2 = ΠGImp , a quantified answer set M of ΠG brave must be an answer set of P1 such that P2 ∪ fixP1 (M ) is incoherent. The next proposition follows. a) iff ΠG Proposition 1. K≻ |=G brave q(⃗ brave is coherent. G The program for G-AR, ΠG AR , is exactly as Πbrave except that ΠSomeCause is replaced by ΠNoCause , which ensures that the repair R built by ΠReachAll ∪ ΠRep does not contain any cause for q(⃗a). Indeed, : - sat ∈ ΠNoCause requires that sat is not derived by ΠSatIfCause , so that there is no cause C such that C ⊆ R.

Proposition 2. K≻ |=G a) iff ΠG AR q(⃗ AR is incoherent. We also considered an alternative program of the form ∀st P ∃st P ′ : C ′ for G-AR, but as it was less efficient in practice, we present it only in the appendix.

ΠX brave =ΠReachAll ∪ ΠSubRep ∪ ΠXOpt ∪ ΠSomeCause ΠX AR =ΠReachAll ∪ ΠSubRep ∪ ΠXOpt ∪ ΠNoCause

3.2

Localization

To avoid considering the whole dataset in the encodings, we localize them to relevant facts, defined from the query causes using some notions of reachability w.r.t. the conflicts and priority relation. We define two such notions of reachability (strong and weak). The first one was already used to localize SAT or ASP encodings by Bienvenu and Bourgaux (2022) and Bienvenu et al. (2025), and the proofs of the theorems below are strongly inspired by the proofs of correctness of the SAT encodings for non-binary conflicts given in the extended version of (Bienvenu and Bourgaux 2022). Definition 3. Given a prioritized KB K≻ with K = (D, T ) in K≻ and B ⊆ D, Rs (B) is the set of facts reachable from

ΠΓ(∅)

unsafe(A, 0) : - attacks(C, A). safe(A, 0) : - inConf(C, A), not unsafe(A, 0).

ΠΓincr

safe(A, t) : - safe(A, t − 1). non subset(C, A, t) : - conf(C), inConf(C, A), inConf(C, B), A != B, not safe(B, t − 1). subset(C, A, t) : - conf(C), inConf(C, A), not non subset(C, A, t). protected(C, A, t) : - attacks(C, A), inConf(C, B), A != B, attacks(C2, B), subset(C2, B, t). unsafe(A, t) : - attacks(C, A), not protected(C, A, t). safe(A, t) : - inConf(C, A), not unsafe(A, t). continue(t) : - safe(A, t), not safe(A, t − 1).

Table 2: Logic programs used to compute the grounded repair from facts on predicates conf, inConf, and attacks (computed by ΠAttack ).

B in the directed hypergraph3 whose edges are {(α, E) | E ⇝ α} = {(α, E) | E ∪ {α} ∈ Conf (K), ∀β ∈ E, α ̸≻ β} and Rw (B) is the set of facts reachable from B in the directed hypergraph whose edges are {(α, E) | E ∪ {α} ∈ Conf (K), ∃β ∈ E, α ̸≻ β}. Note that Rs (B) ⊆ Rw (B) and that the these two sets coincide when the conflicts are binary: in this case, reachability is done in the oriented graph whose edges are {(α, β) | {α, β} ∈ Conf (K), α ̸≻ β}. Theorem 3. Let X ∈ {P, G, C}, B ⊆ D, Br = Rw (B), KBr = (Br , T ) and ≻Br be the restriction of ≻ to B r . Br • If R ∈ XRep(K≻ ), then R ∩ Br ∈ XRep(K≻ Br ).

•

Br ′ If R ∈ XRep(K≻ Br ), then there exists R ∈ XRep(K≻ ) ′ such that R = R ∩ Br .

Theorem 4. If Br = Rw (B) is replaced by Br = Rs (B), Theorem 3 still holds for X ∈ {P, C}. We can thus replace ΠReachAll by ΠReachW or ΠReachS (if X ∈ {P, C}) in the naive encodings, in order to restrict the set of facts from D considered (whose identifiers are stored in reachable). Indeed, these programs comS pute Rs (B) and Rw (B) for B = C∈Causes(q(⃗a),K) C, respectively. We leave open whether Theorem 4 holds for X = G.

3.3

Simplified Encoding for Binary Conflicts

When the conflicts are of size exactly 2 (we assume that any self-inconsistent fact has been removed from the dataset), we can simplify the encodings as follows. Reachable Facts First, as explained earlier, the set of relevant (reachable) facts is easier to compute with binary conflicts: we replace ΠReachW or ΠReachS by ΠReachBin . Repairs In the encodings for semantics based on globallyoptimal repairs, which build a full, ⊆-maximal, repair, we modify ΠRep by replacing the two rules of ΠRep that compute the facts that are necessary to keep out of the repair by the simpler rules (with one negation instead of four): dangerous(C) : - conf(C), inConf(C, A), inRepair(A). keepOut(A) : - dangerous(C), inConf(C, A), not inRepair(A). 3

A node γ is reachable from a set of nodes B in a directed hypergraph if γ ∈ B or there exists a node β reachable from B and some edge (β, E) such that γ ∈ E.

Pareto-Optimality We use again the fact that when the conflicts are binary the attack relation is straightforward ({β} ⇝ α iff {α, β} ∈ Conf (K) and α ̸≻ β), and that including a single conflicting fact is sufficient to exclude a fact, to replace ΠPOpt by ΠPOptBin .

3.4

Approximations

Another way to answer queries under optimal repair-based semantics more efficiently is to use approximations to compute subsets or supersets of the answers and thus avoid relying on more demanding programs for some answers. Tractable Under-Approximations of P-IAR We use a preprocessing step that identifies a subset of the answers that hold under P-IAR (hence under all the considered semantics). We consider two tractable such under-approximations: the grounded semantics (recalled in Section 2.1) and the trivially P-IAR answers (Bienvenu, Bourgaux, and Goasdoué 2014; Bienvenu and Bourgaux 2022), which have some cause such that none of its fact is attacked (w.r.t. ⇝). Note that the trivially P-IAR answers are those that hold w.r.t. Γ(∅). Table 2 shows the ASP programs used to compute Γ(∅) then incrementally compute the grounded repair. Using incremental solving mirrors the fixpoint definition of grounded semantics and allows for a very direct encoding. Once we have computed one of these two sets, we use it to filter the answers that have some cause included in it. P-AR and P-Brave We also investigate the use of semantics whose data complexity is in the first level of the polynomial hierarchy, e.g., based on Pareto-optimal repairs, to obtain lower or upper bounds on semantics based on globallyoptimal repairs: K≻ |=P a) implies K≻ |=G a) AR q(⃗ AR q(⃗ G q(⃗ a ) implies (hence also K≻ |=brave q(⃗a)) and K≻ ̸|=P brave K≻ ̸|=G a) (hence also K≻ ̸|=G a)). AR q(⃗ brave q(⃗

4

Experiments

Our experimental evaluation aims at (i) evaluating the impact of adopting globally-optimal repairs, (ii) assessing the grounded semantics, and (iii) comparing the different approaches of the same problem in terms of runtime. In more detail, we consider the following questions: • What proportion of the intersection of optimal repairs is given by the grounded repair? And by the trivially P-IAR facts (i.e., Γ(∅))? What is the overhead in term of runtime to compute the grounded repair instead of Γ(∅)?

∩S

Γ1 \∩S

Γ2 \Γ1

Γ3 \Γ2

Γ4 \Γ3

u1c1 ≻ns u1c50

73351 43779

921 7289

1365 21319

0 1329

0 8

u1c1 ≻ss u1c50

73351 43779

1225 8493

881 9368

0 11

0 0

u1c1 ≻nb u1c50

73131 43612

989 10777

1406 18629

4 52

0 0

Table 3: Number T of facts in the different parts of the grounded repair: ∩S = R∈SRep(K) R, Γi = Γi (∅). ≻ss

≻ns 1

G \∩S

Γ \∩S

G \∩S

Γ1 \∩S

u1c1 u1c20 u1c50

1.58 14.92 61.80

0.16 1.26 3.53

2.10 21.22 126.39

0.16 1.39 3.80

u5c1 u5c20 u5c50

7.85 129.31 304.11

0.68 7.12 14.55

10.70 240.34 oom

0.68 7.11 14.69

u20c1 u20c20

23.75 oom

2.41 36.07

47.05 oom

2.39 33.13

Table 4: Time (in seconds) to compute the facts that belong to the grounded repair G or to Γ1 = Γ(∅) (among those that belong to some conflict) from the precomputed attack relation.

• Given a semantics, what is the impact of localization or binary conflicts-specific encodings? • What is the impact of using globally-optimal repairs instead of Pareto- or completion-optimal ones, both in terms of the answers obtained and runtime overhead?

4.1

Experimental Setting

Following Bienvenu et al. (2025), we translated into ASP programs a subset of the ORBITS benchmark (Bienvenu and Bourgaux 2022) which provides several conflict sets, priority relations, and potential answers associated with their causes built from the CQAPri benchmark (Bourgaux 2016), a synthetic benchmark adapted from LUBM∃20 (Lutz et al. 2013) to evaluate inconsistency-tolerant query answering over DL-Lite KBs. To experiment also with non-binary conflicts, Bienvenu et al. (2025) added a denial constraint that yields conflicts of size 10 and built some priority relations for this case using preference rules. Datasets The datasets of the CQAPri benchmark are named uXcY, with X and Y related to the size and the proportion of facts involved in some conflicts respectively, and are such that uXcY ⊆ uXcY′ for Y ≤ Y′ and uXcY ⊆ uX′ cY for X ≤ X′ . Since our focus is on the use of the more demanding globally-optimal repairs, we mostly use the smallest datasets u1cY with Y ∈ {1, 5, 10, 20, 30, 50}, which contain from 75K to 78K facts. The proportion of facts involved in some (binary) conflict in these datasets ranges from 3% to 44% and the corresponding conflict sets contain from 2K to 81K conflicts, involving 2K to 34K facts.

u1c1 u1c10 ≻ns u1c20

∩S

G \∩S

∩P \G

∩G \∩P

∩C \∩G

73351 65310 56646

2286 10134 18507

0 3 82

0 22 46

0 1 7

Table 5:TSize of grounded repair G and optimal repair intersections: ∩X = R∈XRep(K≻ ) R for X ∈ {S, P, G, C}.

Forty non-binary conflicts are generated (in all datasets) when the additional denial constraint is considered. We also run a few experiments with some larger datasets u5cY with Y ∈ {1, 5, 10, 20}, with 12K to 231K conflicts involving 12K to 137K facts. Priority Relations In the binary conflicts case, we use the two priority relations of the ORBITS benchmark: ≻ss is built from priority levels, hence is such that globally-, Pareto- and completion-optimal repairs coincide, while ≻ns is not score-structured and allows us to distinguish between the three kinds of repairs. Moreover, ≻ss assigns a priority between the two facts of about 40% of the conflicts and this proportion is about 30% for ≻ns . For the non-binary conflicts case, we use a priority relation ≻nb resulting from some preference rules given by Bienvenu et al. (2025) which assigns a priority between two facts that belong to some conflict in about 90% of the cases. Queries We use the 8 queries Bienvenu et al. (2025) selected from the CQAPri benchmark for having a lower number of potential answers. The total number of potential answers over all queries ranges from 1,525 (on u1c1) to 8,206 (on u5c20). Setup All experiments were executed on a machine equipped with an Intel(R) Xeon(R) CPU E7-8880 v4 @ 2.20GHz, running Debian GNU/Linux 12, with memory and CPU (i.e., user+system) limited to 8GB and 600s. Time and memory usage have been measured with pyrunlim4 . As ASP(Q) solver we used the CASPER system (Andrea, Mazzotta, and Ricca 2026)5 , and as ASP solver we used CLINGO (Gebser et al. 2017). Preprocessing Reported times exclude the computation of the attack relation using ΠAttack , as it can be considered a query-independent preprocessing task. Computing the attack relation took at most 5 seconds for the u1cY datasets (small datasets), about 30 seconds for u5c20 (largest dataset we used for the query answering task) and up to about one hour for u20c50 (dataset with 2M facts, 46% of facts involved in some conflict, and 3M conflicts, which we considered only for the task of computing the grounded repair).

4.2

Experimental Results

In what follows, we summarize our main observations. 4

pyrunlim is available at https://github.com/alviano/python.git Other ASP(Q) systems are available, such as QASP (Amendola et al. 2022) and PYQASP (Faber, Mazzotta, and Ricca 2023), but CASPER performed better in our preliminary evaluation. 5

u1c1 u1c20 u1c50 u5c1 u5c20 u1c1 u1c20 u1c50

≻ns

≻nb

Triv 1465 937 625 7637 4947 1447 940 680

GR\Triv 59 584 875 316 3035 76 571 823

Pot\GR 1 35 141 10 224 2 45 138

P-AR\GR 0 (0) 1 (0) 26 (0) 0 (0) 37 (0) 0 (0) 0 (0) 0 (0)

G-AR\GR 0 (0) 0 (10) 9 (82) 0 (0) 6 (96) 0 (0) 0 (2) 0 (43)

C-AR\GR 0 (0) 1 (0) 20 (56) 0 (0) 32 (32) 0 (0) 0 (0) 0 (0)

P-brave\GR 0 (0) 17 (0) 79 (0) 2 (0) 91 (0) 0 (0) 1 (0) 20 (0)

G-brave\GR 0 (0) 16 (6) 28 (81) 2 (0) 51 (151) 0 (0) 0 (2) 13 (37)

C-brave\GR 0 (0) 17 (0) 38 (40) 2 (0) 83 (18) 0 (0) 1 (0) 20 (0)

Table 6: Number of answers found trivially P-IAR (Triv), grounded (GR) but not trivially P-IAR, potential answers (Pot) not grounded, and X-AR or X-brave but not grounded. The number of potential answers for which we ran out of time (600s) is given in parenthesis.

600 500 400 300 200 100 0

600 500 400 300 200 100 0

0

1000

2000

G-AR P-AR C-AR G-BRAVE P-BRAVE C-BRAVE 0 50 100 150 200 250 300 350

3000

4000

5000

600 500 400 300 200 100 0

0

50

100 150 200 250 300 350

Figure 1: Time (in seconds, y-axis) to decide for each q(⃗a), dataset uXcY, and priority relation, whether q(⃗a) holds under X-AR/X-brave, with instances sorted by increasing solving time along the x-axis (i.e., a point (i, j) indicates that i instances could be solved within j seconds). (left) binary conflicts case (u1cY and u5cY, two priority relations) (right) non-binary conflicts case (u1cY, one priority relation) 5 4 3 2 1 0

0

1

2

3

4

5

600 500 400 300 200 100 0

0 100 200 300 400 500 600

600 500 400 300 200 100 0

is also the reason that we did not conduct further experimental evaluations of the X-IAR semantics.

0 100 200 300 400 500 600

Figure 2: Time for the generic encoding (y-axis) vs time for the encoding specific for binary conflicts (x-axis), both with localization, to decide for each q(⃗a), dataset uXcY, and priority relation, if q(⃗a) holds under X-AR. (left) X=P (middle) X=C (right) X=G

Tractable Approximations Table 3 shows the number of plain (S-)IAR facts (not involved in any conflict, ∩S ), other trivially P-IAR facts (Γ(∅)), and facts added at each step of the incremental computation of the grounded repair, for some example datasets and priority relations. Over all the cases we consider, the proportion of facts that belong to the grounded repair but which are not trivially P-IAR (i.e., are in G \ Γ(∅)) varies from 1%-2% on the datasets with a low proportion of facts in conflicts (uXc1) to 15%-31% (depending on the priority relation) on the dataset with the highest proportion of facts in conflicts u1c50. Table 4 gives examples of times needed to compute the grounded repair and the trivially P-IAR facts. Over all the cases we consider, computing G instead of Γ(∅) from the attack relation multiplies the runtime by up to 34 but it remains below 600s. However, we encounter memory problems for larger datasets (note that for this task we also used datasets u20cY of 2M facts). Table 5 shows the size of the grounded repair and how many facts are added by taking the intersections of the optimal repairs. Given the cost of checking whether each non-grounded fact holds under X-(I)AR, these numbers suggest the interest of using grounded rather than X-IAR for X ∈ {P, G, C}. This

Impact of Localization Unsurprisingly, localization is crucial. For example, on u1c10 with ≻nb , we manage to decide for 99% of the pairs of a potential answer (which does not hold under grounded) and a semantics (X-AR or X-brave with X ∈ {P, G, C}) whether the answer holds under the semantics, while they all yield a time-out without localization. We adopt localization (using weak reachability for globally-optimal repairs and strong one for Pareto- and completion-optimal repairs) in the rest of the experiments. Impact of Specific Encoding for Binary Conflicts Figure 2 compares for each potential answer (which does not hold under grounded), dataset with binary conflicts, and priority relation, the time needed to decide if it holds under X-AR semantics with and without using the simplified encodings proposed in the case of binary conflicts. We can see that this simplification is indeed generally helpful when X=P, and mostly neutral when X=C. When X=G, we observe a more diverse outcome: even if the binary conflicts-specific encoding improves the performance in a majority of cases, there are a significant number of cases where it is the opposite. Moreover, the difference between the two encodings is more important (in particular, the two encodings do not lead to time-out on the same instances). Semantics Comparison in Terms of Runtimes Figure 1 shows the times needed to decide whether a potential answer which does not hold under grounded semantics holds under a given semantics for X-AR and X-brave with X ∈ {P, G, C}, over all the cases we consider, using localization and the specific encoding for binary conflicts when possible. Recall that in a cactus plot instances are sorted by solving

time, so a point (i, j) in the plot indicates that for the considered semantics, there were i instances which could be (individually) solved within j seconds. These results confirm that using globally-optimal repairs is significantly more difficult in practice than using Pareto- or even completion-optimal repairs, and the difference becomes more pronounced as the proportion of facts involved in some conflicts increases. Semantics Comparison in Terms of Answers Table 6 shows the number of answers we obtain under the different semantics and the number of potential (non grounded) answers for which we did not manage to determine whether they hold under the considered semantics in our 600s time limit. A first observation is that the grounded semantics seems to be a very good approximation of the X-AR semantics (X ∈ {P, G, C}). This is key to achieving feasibility as it allows us to reduce the number of potential answers for which we need to call the procedures for the P/C-AR/brave semantics (cf. the column Pot\GR which gives the number of potential answers for which we actually need to use the encodings for X-AR or X-brave semantics). For X-brave answers however, we do observe cases where a large share of the answers cannot be obtained without using the designated encodings (in particular in the ≻ss case, which is omitted from the table as in this case the three kinds of optimal repair coincide). Another useful information is that the three kinds of repairs seem to often yield the same answers (recall that answers that hold under P-AR semantics are included in those that hold under G-AR semantics, which are included in those that hold under C-AR semantics, and the inclusions for the X-brave semantics are the other way around).

5

Conclusion

In this paper, we have presented the first implementation of globally-optimal repair-based semantics, using ASP(Q), and of the grounded semantics, making it possible for the first time to compare these semantics with the previously implemented semantics based upon Pareto- and completionoptimal repairs. While we are able to compute query answers for some instances with globally-optimal repairs, the runtimes are significantly longer, with more timeouts, than for the Pareto- and completion-optimal repairs, in line with the worst-case complexity. This suggests that even if we aim to compute G-AR and G-brave answers, a better strategy is to first test whether the candidate answer holds under P-AR semantics and P-brave semantics (which are the fastest optimal repair semantics) and only call the G-AR and G-brave procedures if the status remains unresolved. Our evaluation also highlighted the surprising effectiveness of the grounded semantics as an approximation of the optimal repair-based semantics, an insight which moreover can be applied also to non-ASP-based implementations. Importantly, the grounded repair can be computed as a preprocessing task, thus making it possible to employ a principled inconsistency-tolerant semantics with little overhead compared to standard query answering. This suggests the interest of developing highly optimized methods for computing and updating the grounded repair for very large datasets.

Acknowledgements This work was supported by the ANR AI Chair INTENDED (ANR-19-CHIA-0014); by the Italian Ministry of Industrial Development (MISE) under project EI-TWIN n. F/310168/05/X56 CUP B29J24000680005; and by the Italian Ministry of Research (MUR) under project PNRR FAIR - Spoke 9 - WP 9.1 CUP H23C22000860006.

AI Declaration The authors have not employed any Generative AI tools.

References Amendola, G.; Cuteri, B.; Ricca, F.; and Truszczynski, M. 2022. Solving problems in the polynomial hierarchy with ASP(Q). In Proceedings of LPNMR. Amendola, G.; Ricca, F.; and Truszczynski, M. 2019. Beyond NP: quantifying over answer sets. Theory Pract. Log. Program. 19(5-6):705–721. Andrea, C.; Mazzotta, G.; and Ricca, F. 2026. 2-ASP(Q) solving based on CEGAR. In Proceedings of AAAI. Arenas, M.; Bertossi, L. E.; and Chomicki, J. 1999. Consistent query answers in inconsistent databases. In Proceedings of PODS. Bertossi, L. E. 2019. Database repairs and consistent query answering: Origins and further developments. In Proceedings of PODS. Bienvenu, M., and Bourgaux, C. 2020. Querying and repairing inconsistent prioritized knowledge bases: Complexity analysis and links with abstract argumentation. In Proceedings of KR. Bienvenu, M., and Bourgaux, C. 2022. Querying inconsistent prioritized data with ORBITS: algorithms, implementation, and experiments. In Proceedings of KR. Bienvenu, M., and Bourgaux, C. 2023. Inconsistency handling in prioritized databases with universal constraints: Complexity analysis and links with active integrity constraints. In Proceedings of KR. Bienvenu, M., and Rosati, R. 2013. Tractable approximations of consistent query answering for robust ontologybased data access. In Proceedings of IJCAI. Bienvenu, M.; Bourgaux, C.; Inoue, K.; and Jean, R. 2025. A rule-based approach to specifying preferences over conflicting facts and querying inconsistent knowledge bases. In Proceedings of KR. Bienvenu, M.; Bourgaux, C.; and Goasdoué, F. 2014. Querying inconsistent description logic knowledge bases under preferred repair semantics. In Proceedings of AAAI. Bienvenu, M. 2020. A short survey on inconsistency handling in ontology-mediated query answering. Künstliche Intelligenz 34(4):443–451. Bourgaux, C. 2016. Inconsistency Handling in OntologyMediated Query Answering. (Gestion des incohérences pour l’accès aux données en présence d’ontologies). Ph.D. Dissertation, University of Paris-Saclay, France.

Bourgaux, C. 2025. Inconsistency-tolerant semantics based on (preferred) repairs. In Proceedings of RW. Calimeri, F.; Faber, W.; Gebser, M.; Ianni, G.; Kaminski, R.; Krennwallner, T.; Leone, N.; Maratea, M.; Ricca, F.; and Schaub, T. 2020. ASP-Core-2 input language format. Theory Pract. Log. Program. 20(2):294–309. Calvanese, D.; De Giacomo, G.; Lembo, D.; Lenzerini, M.; and Rosati, R. 2007. Tractable reasoning and efficient query answering in description logics: The DL-Lite family. Journal of Automated Reasoning (JAR) 39(3):385–429. Ceri, S.; Gottlob, G.; and Tanca, L. 1990. Logic Programming and Databases. Surveys in computer science. Dixit, A. A., and Kolaitis, P. G. 2019. A SAT-based system for consistent query answering. In Proceedings of SAT. Eiter, T., and Gottlob, G. 1995. On the computational cost of disjunctive logic programming: Propositional case. Ann. Math. Artif. Intell. 15(3-4):289–323. Eiter, T.; Fink, M.; Greco, G.; and Lembo, D. 2008. Repair localization for query answering from inconsistent databases. ACM Trans. Database Syst. 33(2):10:1–10:51. Faber, W.; Mazzotta, G.; and Ricca, F. 2023. An efficient solver for ASP(Q). Theory Pract. Log. Program. 23(4):948– 964. Faber, W.; Morak, M.; and Chrpa, L. 2022. Determining action reversibility in STRIPS using answer set programming with quantifiers. In Proceedings of PADL. Faber, W. 2024. Solving argumentation problems using answer set programming with quantifiers: Preliminary report. In Proceedings of ICLP-WS. Fandinno, J.; Laferrière, F.; Romero, J.; Schaub, T.; and Son, T. C. 2021. Planning with incomplete information in quantified answer set programming. Theory Pract. Log. Program. 21(5):663–679. Gebser, M.; Kaminski, R.; Kaufmann, B.; and Schaub, T. 2017. Multi-shot ASP solving with clingo. CoRR abs/1705.09811. Gebser, M.; Kaminski, R.; and Schaub, T. 2011. Complex optimization in answer set programming. Theory Pract. Log. Program. 11(4-5):821–839. Gelfond, M., and Lifschitz, V. 1991. Classical negation in logic programs and disjunctive databases. New Gener. Comput. 9(3/4):365–386. Greco, G.; Greco, S.; and Zumpano, E. 2003. A logical framework for querying and repairing inconsistent databases. IEEE Trans. Knowl. Data Eng. 15(6):1389–1408. Kimelfeld, B.; Livshits, E.; and Peterfreund, L. 2017. Detecting ambiguity in prioritized database repairing. In Proceedings of ICDT. Kimelfeld, B.; Livshits, E.; and Peterfreund, L. 2020. Counting and enumerating preferred database repairs. Theor. Comput. Sci. 837:115–157. Kolaitis, P. G.; Pema, E.; and Tan, W. 2013. Efficient querying of inconsistent databases with binary integer programming. Proc. VLDB Endow. 6(6):397–408.

Lembo, D.; Lenzerini, M.; Rosati, R.; Ruzzi, M.; and Savo, D. F. 2010. Inconsistency-tolerant semantics for description logics. In Proceedings of RR. Lutz, C.; Seylan, I.; Toman, D.; and Wolter, F. 2013. The combined approach to OBDA: Taming role hierarchies using filters. In Proceedings of ISWC. Manna, M.; Ricca, F.; and Terracina, G. 2013. Consistent query answering via ASP from different perspectives: Theory and practice. Theory Pract. Log. Program. 13(2):227– 252. Staworko, S.; Chomicki, J.; and Marcinkowski, J. 2012. Prioritized repairing and consistent query answering in relational databases. Annals of Mathematics and Artificial Intelligence (AMAI) 64(2-3):209–246.

A

Proofs for Section 3

Proposition 1. K≻ |=G a) iff ΠG brave q(⃗ brave is coherent. Proof Sketch. (⇐) Assume that ΠG brave has a quantified answer set M . Since M ∈ AS(P1 ), the set R that contains all facts whose identifiers are in {A | inRepair(A) ∈ M } (extended with facts that do not appear in any conflict nor cause) is a repair of K that contains a cause for q(⃗a). Moreover, since P2 ∪ fixP1 (M ) is incoherent, R does not have any global improvement. Hence K≻ |=G a). brave q(⃗ (⇒) Conversely, assume that ΠG brave is incoherent. Let R ∈ SRep(K) be such that R contains some cause for q(⃗a). The interpretation M that contains (i) inRepair(A) for every identifier A of α ∈ R and (ii) the atoms (deterministically) derived by P1 \ {{inRepair(A)} : - reachable(A)} is such that M ∈ AS(P1 ). Since M is such that P2 ∪ fixP1 (M ) is coherent (otherwise ΠG brave will be coherent), R admits a global improvement. Thus K≻ ̸|=G a). brave q(⃗ Proof of Theorem 3 We prove Proposition 4 and Proposition 5 below, which correspond two the first and second item of Theorem 3, respectively. Recall that we consider a prioritized KB K≻ with K = (D, T ), a subset B ⊆ D, and the set of facts reachable from B (w.r.t. ‘weak’ reachability) Br = Rw (B), which is used to define the prioritized KB Br Br K≻ = (Br , T ) and ≻Br the restriction of ≻ to B r . Br by K In the proofs of the propositions, we will use the set of minimal (w.r.t. ≻) facts of a conflict: for every C ∈ Conf (K) let M in(C) = {γ|∀δ ∈ C, γ ̸≻ δ}. We recall that if ≻′ is a total priority relation, there is a unique Pareto-, globally- and completion-optimal repair (Staworko, Chomicki, and Marcinkowski 2012), so one can define completion-optimal repairs equivalently as those that are Pareto-optimal or globally-optimal w.r.t. some completion ≻′ of ≻. Proposition 4. For X ∈ {P, G, C}, if R ∈ XRep(K≻ ), Br then R ∩ Br ∈ XRep(K≻ Br ). Proof. Case X = P. Let R ∈ PRep(K≻ ) and suppose for Br a contradiction that R ∩ Br ∈ / PRep(K≻ Br ): there exists R0 ⊆ Br such that there exists β ∈ R0 \ (R ∩ Br ), such that β ≻ α for all α ∈ (R ∩ Br ) \ R0 .

f0 = {β} ∪ (R0 ∩ R) ∪ (R \ Br ). We build a Pareto Let R improvement of R w.r.t. K≻ by removing selected elements f0 to obtain a contradiction with R ∈ PRep(K≻ ). from R f0 , there Claim 1. For every C ∈ Conf (K) such that C ⊆ R exists γC ∈ C such that β ≻ γC . f0 . Proof of claim. Let C ∈ Conf (K) be such that C ⊆ R First, note that β ∈ C as otherwise C ⊆ R, which contradicts the T -consistency of R. Moreover, C ∩ (R \ Br ) ̸= ∅ as otherwise C ⊆ R0 which contradicts the T -consistency of R0 . By definition of Br = Rw (B), and since β ∈ Br , if for every γ ∈ C, β ̸≻ γ, it would hold that C ⊆ Br . Since we showed that C ∩ (R \ Br ) ̸= ∅, it follows that there exists γC ∈ C such that β ≻ γC . (end of claim proof) f0 , β ≻ γC } and Let Γ f = {γC | C ∈ Conf (K), C ⊆ R R0

f0 \ Γ f . As R′ is obtained by removing at least one R′0 = R 0 R0 f0 , it is T -consistent. Also: fact per conflict included in R f0 \ Γ f ) \ R R′0 \ R = (R R0 = (({β} ∪ (R0 ∩ R) ∪ (R \ Br )) \ ΓR f0 ) \ R = {β} since β ̸∈ ΓR f0 and β ̸∈ R; f0 \ Γ f ) R \ R′0 = R \ (R R0 = ((R ∩ Br ) \ R0 ) ∪ ΓR f0 ⊆ R. f0 since ΓR By construction of R′0 , for every α ∈ R \ R′0 , β ≻ α. Hence R′0 is a Pareto improvement of R, which contradicts Br R ∈ PRep(K≻ ). Therefore R ∩ Br ∈ PRep(K≻ Br ). Case X = G. Let R ∈ GRep(K≻ ) and suppose for a conBr tradiction that R ∩ Br ∈ / GRep(K≻ Br ): there exists R0 ⊆ Br such that R0 ̸= R ∩ Br and for every α ∈ (R ∩ Br ) \ R0 , there exists β ∈ R0 \ (R ∩ Br ) such that β ≻ α. f0 = R0 ∪ (R \ Br ). We build a global improvement Let R f0 to of R w.r.t. K≻ by removing selected elements from R obtain a contradiction with R ∈ GRep(K≻ ). We first show that for every C ∈ Conf (K) such that C ⊆ f R0 , there exist βC ∈ C ∩ (R0 \ (R ∩ Br )) and γC ∈ C \ (R0 \ (R ∩ Br )) such that βC ≻ γC . Let C ∈ Conf (K) be f0 . First, note that C ∩ (R0 \ (R ∩ Br )) ̸= ∅ such that C ⊆ R as otherwise C ⊆ R, which contradicts the T -consistency of R. Moreover, C ∩ (R \ Br ) ̸= ∅ as otherwise C ⊆ R0 , which contradicts the T -consistency of R0 . f0 , Claim 2. For every C ∈ Conf (K) such that C ⊆ R M in(C) ⊆ R \ Br Proof of claim. By definition of Br = Rw (B), if there was α ∈ M in(C) such that α ∈ Br , it would hold that C ⊆ Br . Since C ∩ (R \ Br ) ̸= ∅, it follows that M in(C) ⊆ R \ Br . (end of claim proof) We define (βi )i∈N ∈ C N with β0 ∈ C ∩ (R0 \ (R ∩ Br )) (such β0 exists since C ∩(R0 \(R∩Br )) ̸= ∅) and for i ∈ N: • if βi ∈ R0 then let βi+1 ∈ C be such that βi ≻ βi+1 (such βi+1 exists because M in(C) ⊆ R \ Br and R0 ⊆ Br so βi ∈ / M in(C));

• otherwise (βi ̸∈ R0 ), let βi+1 = βi . As D is finite and ≻ is acyclic the sequence is ultimately constant. Let j = mini∈N (βi+1 ̸∈ R0 \ (R ∩ Br )). Let βC = βj and γC = βj+1 . By definition of j we have βC ∈ R0 \ (R ∩ Br ) and γC ̸∈ R0 \ (R ∩ Br ), and by construction of (βi )i∈N , it holds that βC ≻ γC . f Let ΓR f0 = {γC | C ∈ Conf (K), C ⊆ R0 } and f0 \ Γ f . As R′ is obtained by removing at least R′ = R 0

0

R0

f0 , it is T -consistent. Also: one fact per conflict included in R f0 \ Γ f ) \ R R′0 \ R = (R R0 = (R0 \ (R ∩ Br )) \ ΓR f0 = R0 \ (R ∩ Br ) as for all γC ∈ ΓR f0 we have γC ̸∈ R0 \ (R ∩ Br ), and f0 \ Γ f ) R \ R′0 = R \ (R R0 = R \ ((R0 ∪ (R \ Br )) \ ΓR f0 ) = ((R ∩ Br ) \ R0 ) ∪ ΓR f0 . Let α ∈ R \ R′0 : • If α ∈ (R ∩ Br ) \ R0 , by assumption on R0 , there exists β ∈ R0 \ (R ∩ Br ) = R′0 \ R such that β ≻ α. • Otherwise, α ∈ ΓR f0 is equal to some γC and β = βC is such that β ∈ R0 \ (R ∩ Br ) = R′0 \ R (by definition of the βC ) and β ≻ α (since βC ≻ γC ). Hence R′0 is a global improvement of R, which contradicts Br R ∈ GRep(K≻ ). Therefore R ∩ Br ∈ GRep(K≻ Br ). Case X = C. Let R ∈ CRep(K≻ ), i.e., R ∈ PRep(K≻′ ) for some ≻′ completion of ≻. Thus, by the case X = P of the proposition that we have already shown, we have R ∩ Br ′ Br Br ∈ PRep(K≻ is a completion of ≻Br in ′ Br ). As ≻ Br Br K we directly obtain that R ∩ Br ∈ CRep(K≻ Br ). Br Proposition 5. For X ∈ {P, G, C}, if R ∈ XRep(K≻ Br ), ′ ′ then there exists R ∈ XRep(K≻ ) such that R = R ∩ Br . Br Proof. Case X = P. Let R ∈ PRep(K≻ Br ). Following the proof of Lemma 9 from the extended version of (Bienvenu and Bourgaux 2022), we build some R∗ ⊆ D as required by the proposition as follows: let R′ = R, D′ = D, and repeat the following steps until D′ is empty:

• Choose α ∈ D′ such that β ̸≻ α for all β ∈ D′ . • If R′ ∪ {α} is T -consistent, add α to R′ . • Remove α from D′ . Let R∗ be the final R′ . First, note that R ⊆ R∗ ∩ Br by initialization of R∗ and definition of R. Also R∗ ∩ Br ⊆ R as otherwise there would exist α ∈ (R∗ ∩ Br ) \ R but then R ∪ {α} would be T -consistent and hence a Pareto improvement of R. Thus R = R∗ ∩ Br . We show that R∗ ∈ PRep(K≻ ). Suppose for a contradiction there exists R0 ⊆ D such that there exists β ∈ R0 \ R∗

such that β ≻ α for every α ∈ R∗ \ R0 . Since β ̸∈ R∗ , by construction of R∗ , there exists C ∈ Conf (K) such that β ∈ C and C \ {β} ⊆ R′ when β was chosen in the construction of R∗ (otherwise β would have been added to R′ ). Claim 3. For every C ∈ Conf (K) such that β ∈ C, M in(C) ∩ R = ∅. Proof of claim. Suppose for a contradiction M in(C) ∩ R ̸= ∅, i.e., there exists γ ∈ C ∩ R ⊆ C ∩ Br such that γ ̸≻ δ for every δ ∈ C. By definition of Br = Rw (B), C ⊆ Br , and in particular β ∈ Br . Hence R0 ∩ Br is a Pareto improvement Br of R, which contradicts the assumption R ∈ PRep(K≻ Br ). (end of claim proof) As R0 is T -consistent, C \ {β} ̸⊆ R0 so there is α0 ∈ C ∩ (R∗ \ R0 ). Hence β ≻ α0 (by definition of R0 and β). Since α0 has been chosen after β in the construction of R∗ and was already in R′ when β was considered, we necessarily have that α0 ∈ R. Hence, since M in(C) ∩ R = ∅, there exists α1 ∈ C with α0 ≻ α1 . Because β ≻ α0 ≻ α1 , α1 was chosen after β in the construction of R∗ thus necessarily α1 ∈ R. Thus we can iterate the argument to create an infinite chain β ≻ α0 ≻ α1 ≻ . . . with all αi ∈ R. As ≻ is acyclic and D is finite we obtain a contradiction. Therefore R∗ ∈ PRep(K≻ ). Br Case X = G. Let R ∈ GRep(K≻ Br ). As we did in the ′ ′ case X = P , let R = R, D = D, and repeat the following steps until D′ is empty:

• Choose α ∈ D′ such that β ̸≻ α for all β ∈ D′ . • If R′ ∪ {α} is T -consistent, add α to R′ . • Remove α from D′ . ∗

′

Let R be the final R . As in the case X = P , we obtain R = R∗ ∩ Br . We show that R∗ ∈ GRep(K≻ ). Suppose for a contradiction there exists R0 ⊆ D such that R0 ̸= R∗ and for every α ∈ R∗ \ R0 , there exists β ∈ R0 \ R∗ such that β ≻ α. Assume for a contradiction that there exists α ∈ R \ R0 . Since R \ R0 ⊆ R∗ \ R0 , there exists β ∈ R0 \ R∗ such that β ≻ α. By definition of ≻, β ≻ α implies that there exists C ∈ Conf (K≻ ) such that {α, β} ⊆ C. In particular, as α ̸≻ β and α ∈ Br we must have C ⊆ Br hence β ∈ Br . Therefore for every α ∈ R \ (R0 ∩ Br ) there exists β ∈ (R0 ∩ Br ) \ R such that β ≻ α, which contradicts Br R ∈ GRep(K≻ Br ). Thus R ⊆ R0 . Hence R = R0 ∩ Br (otherwise we have a contradiction with R being inclusionmaximal). Let α0 be the first element of (R∗ ∪ R0 ) \ Br considered in the construction of R∗ . • If α0 ∈ R∗ \ R0 then there exists β ∈ R0 \ R∗ such that β ≻ α0 but then β ̸∈ Br because as we previously showed R∗ ∩ Br = R = R0 ∩ Br thus R0 \ R∗ ⊆ D \ Br . Hence β has been considered before α0 which contradicts our assumption. • If α0 ∈ R0 \ R∗ then there exists C ∈ Conf (K) such that α0 ∈ C and C \ {α0 } ⊆ R = R∗ ∩ Br (otherwise α0 would have been added) but then C \ {α0 } ⊆ R0 ∩ Br as

R = R0 ∩ Br . Hence C ⊆ R0 and as C ∈ Conf (K) this contradicts the fact that R0 is T -consistent. • Thus α0 ∈ R∗ ∩ R0 . Suppose we proved that the i first elements α0 , . . . , αi−1 of (R∗ ∪ R0 ) \ Br considered in the construction of R∗ are in R∗ ∩ R0 , and let αi ∈ (R∗ ∪ R0 ) \ Br be the next one. • If αi ∈ R∗ \ R0 then there exists β ∈ R0 \ R∗ such that β ≻ αi but then β ̸∈ Br has been considered before αi which contradicts our assumption. • If αi ∈ R0 \ R∗ then there exists C ∈ Conf (K) such that αi ∈ C and C \ {αi } ⊆ R ∪ {α0 , . . . , αi−1 } but then (because R = R0 ∩ Br and {α0 , . . . , αi−1 } ⊆ R0 ) we have C ⊆ R0 . As C ∈ Conf (K) this contradicts the fact that R0 is T -consistent. • Thus αi ∈ R∗ ∩ R0 . Therefore we have recursively that R∗ = R0 which contradicts our assumption. Br Case X = C. Let R ∈ CRep(K≻ Br ). There exists a comBr Br ′ Br Br pletion ≻ of ≻ in K such that R ∈ PRep(K≻ ′ Br ). B

Let ≻′ be a completion of ≻ in K that agrees with ≻′ r on KBr . We showed that there exists R′ ∈ PRep(K≻′ ) such that R = R′ ∩ Br . Since ≻′ is a completion of ≻ in K, we obtain R′ ∈ CRep(K≻ ). Proof of Theorem 4 Proposition 6 and Proposition 7 below correspond to the first and second item of Theorem 4, respectively. Here Br = Rs (B), is the set of facts reachable from B w.r.t. ‘strong’ reachability. Proposition 6. For X ∈ {P, G, C}, if R ∈ XRep(K≻ ), Br then R ∩ Br ∈ XRep(K≻ Br ). Proof. The proof is the same as that of Proposition 4, except that the proofs of Claims 1 and 2, which are the only places where Br = Rw (B) is used, now use Br = Rs (B). Br Proposition 7. For X ∈ {P, C}, if R ∈ XRep(K≻ Br ), then there exists R′ ∈ XRep(K≻ ) such that R = R′ ∩ Br .

Proof. Case X = P. The proof is the same as the one for Proposition 5 in case X = P , except that the proof of Claim 3, which is the only place where the fact that Br = Rw (B) is used, now use Br = Rs (B). Case X = C. Same proof as Proposition 5.

B

Alternative ASP(Q) Encoding for G-AR

For G-AR semantics, we considered the following alternative ASP(Q) encoding. 2 st st G2 ΠG AR =∀ ΠReachAll ΠRep ∃ ΠPartGImp : CAR

with

G2 CAR =ΠSatIfCause { : - not sat, not global improvement.}

and ΠPartGImp is obtained from ΠGImp by removing the constraint ( : - not global improvement).

2 This second program for G-AR, ΠG AR , intuitively checks whether for every R ∈ SRep(K), there exists some B ⊆ D such that either R contains some cause for q(⃗a) or B is a global improvement for R, so that R ∈ GRep(K≻ ) implies (R, T ) |= q(⃗a). Specifically, if we let P1 = 2 ΠReachAll ∪ ΠRep and P2 = ΠPartGImp , so that ΠG AR = st st G2 G2 ∀ P1 ∃ P2 : CAR , we know that ΠAR is coherent if G2 for every M1 ∈ AS(P1 ), ∃st P2 ∪ fixP1 (M1 ) : CAR is ′ coherent, i.e., if for P2 = P2 ∪ fixP1 (M1 ), there exists G2 M2 ∈ AS(P2′ ) such that CAR ∪ fixP2′ (M2 ) is coherent. We have seen that answer sets of P1 correspond to repairs, and that given a repair R, P2 guesses a T -consistent B and derives global improvement iff B is a global improvement G2 of R, and the part ΠSatIfCause of the constraint CAR derives sat iff R contains some cause. Hence, the remaining constraint, : - not sat, not global improvement, which ensures that either sat or global improvement has been derived, enforces the above characterization of K≻ |=G a). AR q(⃗ 2 Proposition 8. K≻ |=G a) iff ΠG AR q(⃗ AR is coherent.

C

Experimental Setting

This section recalls statistics on the benchmarks we used in our experiments (cf. (Bourgaux 2016; Bienvenu and Bourgaux 2022; Bienvenu et al. 2025)). Datasets Table 7 provides information on the size and conflicts of the datasets from the CQAPri benchmark that we used (binary conflicts). Regarding the density of the conflict graph, in u1c1, each of the facts involved in some conflict is in conflict with between 1 and 614 facts with an average of 2, and in u20c50, each of the facts involved in some conflict is in conflict with between 1 and 744 facts with an average of 6.6. The non-binary case adds the same 40 conflicts of size 10 to all datasets (Bienvenu et al. 2025). Priority Relations For the binary conflicts case, we use two priority relations from the ORBITS benchmark: ≻ss is score-structured and was built using 5 levels of priority to which facts were randomly assigned, and ≻ns was built by considering each (binary) conflict and assigning a random preference between the facts with a probability 0.8, except if doing so created a cycle, then checking that ≻ns was indeed not score-structured (Bienvenu and Bourgaux 2022). These priority relations are such that ≻ss assigns a priority between the two facts of about 40% of the conflicts and this proportion is about 30% for ≻ns . For the non-binary case, we use one priority relation ≻nb resulting from the set of preference rules Σa1 ∪ Σa2 ∪ Σa3 and “going down” cycle resolution strategy defined by Bienvenu et al. (2025). This priority relation assigns a priority between two facts that belong to some conflict in about 90% of the cases. Queries We use 8 queries from the CQAPri benchmark: q3, q5, q7, q10, q11, q14, q15, and q20 (see (Bourgaux 2016, Section 3.3.1) for the queries and characteristics). Table 8 shows the number of potential answers per query on the datasets we use for the query answering task.

Inputs Considered for Each Task For the task of computing the grounded repair, we considered the 18 datasets presented in Table 7, with the 2 priority relations given by the ORBITS benchmark, plus the 8 datasets with non-binary conflicts u1cY and u5c1, u5c5 with the priority relation ≻nb (cf. Table 15). The reason we were not able to use larger datasets in the case of non-binary conflicts is that we fail to compute the priority relation ≻nb for datasets larger than u5c5. For the task of query answering, we always use the 8 queries and considered a subset of these cases, eliminating the bigger (u20cY and u5c30, u5c50) datasets, which yields 10 datasets with 2 priority relations plus 8 datasets with nonbinary conflicts and one priority relation (cf. Table 16).

D

Experimental Results

We present here additional results from our experimental evaluation. Tractable Approximations Tables 9, 10 and 11 show the number of plain (S-)IAR facts (which are not involved in any conflict), other trivially P-IAR facts (Γ(∅)), and facts in the grounded repair (G). Tables 12, 13 and 14 show the number of query answers that are trivially P-IAR, grounded, and the number of answers additionally found by each incremental computation step of the grounded repair. Table 15 shows the time needed to compute the facts that belong to the grounded repair or to Γ(∅) (among those that belong to some conflict) from the precomputed attack relation. Impact of Specific Encoding for Binary Conflicts Figures 3 and 4 compare for each potential answer (which does not hold under grounded), dataset with binary conflicts, and priority relation, the time needed to decide if it holds under X-AR and X-brave semantics, respectively, with and without using the optimization proposed in the case of binary conflicts. Comparison of the Two ASP(Q) Encodings for G-AR G2 Figure 5 shows how ΠG AR and ΠAR compare. We choose G to focus on ΠAR which appears to perform a bit better in general. Semantics Comparison in Terms of Runtimes Figures 6 and 7 show the times needed to decide whether a potential answer which does not hold under grounded semantics holds under a given semantics for X-AR and X-brave with X ∈ {P, G, C}, in our different scenarios, using localization and the binary conflicts-specific encoding when possible. Instances are sorted by solving time, so a point (i, j) indicates that for the considered semantics, i instances could be (individually) solved within j seconds. Semantics Comparison in Terms of Answers Table 16 shows the number of answers we obtain under the different semantics and the number of potential (non grounded) answers for which we did not manage to determine whether they hold under the considered semantics in our 600s time limit.

# facts

# facts in conflicts

% facts in conflicts

# conflicts

u1c1 u1c5 u1c10 u1c20 u1c30 u1c50

75,724 75,951 76,201 76,821 77,447 78,593

2,373 6,412 10,891 20,175 26,086 34,814

3 8 14 26 34 44

2,314 8,476 14,261 28,232 45,484 81,304

u5c1 u5c5 u5c10 u5c20 u5c30 u5c50

463,691 465,157 466,919 470,674 474,368 481,400

12,191 45,906 83,263 137,836 172,245 221,900

3 10 18 29 36 46

11,984 53,398 109,453 231,771 345,461 583,714

u20c1 u20c5 u20c10 u20c20 u20c30 u20c50

1,983,493 1,989,788 1,997,445 2,013,048 2,028,069 2,056,957

69,597 253,141 408,398 610,271 748,664 946,819

4 13 20 30 37 46

73,212 335,194 662,725 1,314,991 1,933,956 3,130,377

Table 7: Size, number and percentage of facts involved in some conflict, and number of conflicts for each dataset of the CQAPri benchmark (binary conflicts) that we used in our experiments.

q3

q5

q7

q10

q11

q14

q15

q20

Total

u1c1 u1c5 u1c10 u1c20 u1c30 u1c50

85 85 85 85 87 87

10 10 10 10 10 10

137 137 138 138 142 149

3 3 6 6 6 7

538 544 551 564 585 628

195 195 195 195 195 195

507 508 508 508 508 515

50 50 50 50 50 50

1525 1532 1543 1556 1583 1641

u5c1 u5c5 u5c10 u5c20

85 85 85 85

10 10 10 10

137 137 138 138

20 20 23 24

3366 3408 3472 3584

1112 1112 1112 1112

3183 3188 3190 3203

50 50 50 50

7963 8010 8080 8206

Table 8: Number of potential answers.

u1c1

u1c5

u1c10

u1c20

u1c30

u1c50

u5c1

u5c5

u5c10

u5c20

73351 921 2286

69539 1705 6009

65310 3021 10134

56646 5391 18507

51361 6105 23339

43779 7289 29945

451500 3740 11704

419251 13149 43435

383656 22920 78368

332838 32449 126482

% G not Γ(∅) 1.8%

5.7%

9.4%

17.5%

23.1%

30.7%

1.7%

6.5%

12%

20.5%

∩S Γ(∅) \ ∩S G \ ∩S

Table 9: Number of facts in ∩S =

T

R∈SRep(K) R, Γ(∅) (trivially P-IAR), and the grounded repair G, in ≻

ns

case.

u1c1

u1c5

u1c10

u1c20

u1c30

u1c50

u5c1

u5c5

u5c10

u5c20

73351 1225 2106

69539 2193 4256

65310 3981 7831

56646 5988 13020

51361 6851 15235

43779 8493 17872

451500 5354 10036

419251 16022 33370

383656 27965 59103

332838 40829 90164

% G not Γ(∅) 1.2%

2.8%

5.3%

10.1%

12.6%

15.2%

1%

3.8%

7%

11.7%

∩S Γ(∅) \ ∩S G \ ∩S

Table 10: Number of facts in ∩S =

T

R∈SRep(K) R, Γ(∅) (trivially P-IAR), and the grounded repair G, in ≻

ss

case.

u1c1

u1c5

u1c10

u1c20

u1c30

u1c50

u5c1

u5c5

∩S Γ(∅) \ ∩S G \ ∩S

73131 989 2399

69327 2561 6089

65098 4364 10066

56439 7668 18279

51165 8883 22916

43612 10777 29458

451280 5994 11684

419039 21399 42969

% G not Γ(∅)

1.8%

4.7%

7.6%

14.2%

18.9%

25.6%

1.2%

4.7%

Table 11: Number of facts in ∩S =

T

R∈SRep(K) R, Γ(∅) (trivially P-IAR), and the grounded repair G, in ≻

nb

case.

Triv

GR

Step 1

Step 2

Step 3

u1c1 1465 u1c5 1366 u1c10 1186 u1c20 937 u1c30 754 u1c50 625 u5c1 7637 u5c5 6958 u5c10 6069 u5c20 4947

1524 1525 1527 1521 1518 1500 7953 7948 7964 7982

59 159 341 555 730 800 316 990 1894 2972

0 29 34 75 0 1 62

0 1

Table 12: Number of answers found trivially P-IAR (Triv) and grounded (GR). Column “Step i” gives the number of answers w.r.t. Γi+1 (∅) minus those w.r.t. Γi (∅). “-” indicates that this step was not needed to compute the grounded repair. Case of ≻ns .

u1c1 u1c5 u1c10 u1c20 u1c30 u1c50 u5c1 u5c5 u5c10 u5c20

Triv

GR

Step 1

Step 2

1477 1385 1215 931 731 618 7706 7044 6213 5169

1525 1450 1447 1305 1030 770 7901 7635 7300 6649

48 65 232 374 299 152 195 591 1087 1480

0 0 0 0 0

Table 13: Number of answers found trivially P-IAR (Triv) and grounded (GR). Column “Step i” gives the number of answers w.r.t. Γi+1 (∅) minus those w.r.t. Γi (∅). “-” indicates that this step was not needed to compute the grounded repair. Case of ≻ss .

u1c1 u1c5 u1c10 u1c20 u1c30 u1c50 u5c1 u5c5

Triv

GR

Step 1

Step 2

1447 1369 1167 940 789 680 7708 7209

1523 1524 1526 1511 1515 1503 7946 7951

75 155 359 571 726 817 237 742

1 0 0 0 0 6 1 0

Table 14: Number of answers found trivially P-IAR (Triv) and grounded (GR). Column “Step i” gives the number of answers w.r.t. Γi+1 (∅) minus those w.r.t. Γi (∅). “-” indicates that this step was not needed to compute the grounded repair. Case of ≻nb .

G \ ∩S

Γ(∅) \ ∩S

u1c1 ≻ u1c5 ≻ns u1c10 ≻ns u1c20 ≻ns u1c30 ≻ns u1c50 ≻ns u5c1 ≻ns u5c5 ≻ns u5c10 ≻ns u5c20 ≻ns u5c30 ≻ns u5c50 ≻ns u20c1 ≻ns u20c5 ≻ns u20c10 ≻ns u20c20 ≻ns u20c30 ≻ns u20c50 ≻ns

2.10 6.63 9.25 21.22 47.65 126.39 10.70 54.50 71.88 240.34 376.27 MEMOUT 47.05 219.98 441.24 MEMOUT MEMOUT MEMOUT

0.16 0.33 0.51 1.39 2.43 3.80 0.68 2.69 4.08 7.11 10.53 14.69 2.39 9.88 18.09 33.13 50.23 80.3

u1c1 ≻ss u1c5 ≻ss u1c10 ≻ss u1c20 ≻ss u1c30 ≻ss u1c50 ≻ss u5c1 ≻ss u5c5 ≻ss u5c10 ≻ss u5c20 ≻ss u5c30 ≻ss u5c50 ≻ss u20c1 ≻ss u20c5 ≻ss u20c10 ≻ss u20c20 ≻ss u20c30 ≻ss u20c50 ≻ss

1.58 4.62 7.30 14.92 32.41 61.80 7.85 27.04 52.14 129.31 201.37 304.11 23.75 106.77 341.53 MEMOUT MEMOUT MEMOUT

0.16 0.50 0.69 1.26 2.40 3.53 0.68 2.65 4.33 7.12 10.60 14.55 2.41 9.47 18.24 36.07 51.29 80.31

u1c1 ≻nb u1c5 ≻nb u1c10 ≻nb u1c20 ≻nb u1c30 ≻nb u1c50 ≻nb u5c1 ≻nb u5c5 ≻nb

1.19 4.03 6.82 13.81 25.34 53.35 4.55 23.03

0.14 0.66 1.02 1.50 2.33 3.97 0.83 2.89

ns

Table 15: Time (in seconds) to compute the facts that belong to the grounded repair G or to Γ(∅) (among those that belong to some conflict) from the precomputed attack relation.

4 3 2 1 0

0

1

2 3 4 time (bin_pareto_AR)

5

600

bin_completion_AR vs non_bin_completion_AR

500 400 300 200 100 0

0

100 200 300 400 500 time (bin_completion_AR)

bin_global_AR vs non_bin_global_AR

600 time (non_bin_global_AR)

time (non_bin_completion_AR)

time (non_bin_pareto_AR)

bin_pareto_AR vs non_bin_pareto_AR 5

500 400 300 200 100 0

600

0

100

200 300 400 500 time (bin_global_AR)

600

5 4 3 2 1 0

0

1

2 3 4 time (bin_pareto_BRAVE)

5

bin_completion_BRAVE vs non_bin_completion_BRAVE bin_global_BRAVE vs non_bin_global_BRAVE 600 600 time (non_bin_global_BRAVE)

time (non_bin_pareto_BRAVE)

bin_pareto_BRAVE vs non_bin_pareto_BRAVE

time (non_bin_completion_BRAVE)

Figure 3: Time for the generic encoding (y-axis) vs time for the encoding specific for binary conflicts (x-axis), both with localization, to decide for each q(⃗a), dataset uXcY, and priority relation, if q(⃗a) holds under X-AR. (left) X=P, (middle) X=C, (right) X=G

500 400 300 200 100 0

0

100 200 300 400 500 time (bin_completion_BRAVE)

600

500 400 300 200 100 0

0

100

200 300 400 500 time (bin_global_BRAVE)

600

Figure 4: Time for the generic encoding (y-axis) vs time for the encoding specific for binary conflicts (x-axis), both with localization, to decide for each q(⃗a), dataset uXcY, and priority relation, if q(⃗a) holds under X-brave. (left) X=P, (middle) X=C, (right) X=G

exists_forall_G-AR vs forall_exists_G-AR

time (forall_exists_G-AR)

600

exists_forall_G-AR

UNSAT SAT

500

600 500 400 300 200 100 0

400 300 200 100 0

0

100

200 300 400 500 time (exists_forall_G-AR)

0

forall_exists_G-AR

1000 2000 3000 4000 5000

600

G2 Figure 5: Comparison of ΠG AR (‘exists forall G-AR’) and ΠAR (‘forall exists G-AR’), both with localization and specific encoding for binary 2 G conflicts. (left) Time for ΠG (y-axis) vs time for Π (x-axis) to decide for each q(⃗a), dataset u1cY (binary conflict cases), and priority AR AR relation, if q(⃗a) holds under G-AR. (right) Time (in seconds, y-axis) to decide for each q(⃗a), dataset uXcY (binary conflict cases), and priority G2 relation, whether q(⃗a) holds under G-AR using ΠG AR and ΠAR , with instances sorted by increasing solving time along the x-axis (i.e., a point (i, j) indicates that i instances could be solved within j seconds).

G-AR P-AR

C-AR G-BRAVE

P-BRAVE C-BRAVE

G-AR P-AR

C-AR G-BRAVE

P-BRAVE C-BRAVE

G-AR P-AR

C-AR G-BRAVE

P-BRAVE C-BRAVE

G-AR P-AR

0.04

17.5

10

1.50 0.02

1.25 1.00

0.50

12.5

0.00

6

10.0

0.02

4

0.96

0.98

1.00

1.02

1.04

0.04

0.02

ns

0.00

0.02

5.0 2.5 0.0

0

0.04

2

4

ss

(a) u1c1 ≻ G-AR P-AR

7.5

2

0.04

0.25

15.0

8

0.75

P-BRAVE C-BRAVE

G-AR P-AR

P-BRAVE C-BRAVE

G-AR P-AR

4

10

2

5

0

0

0

C-AR G-BRAVE

2

3

4

5

6

G-AR P-AR

250

300

200

60

C-AR G-BRAVE

P-BRAVE C-BRAVE

150 100 50

0 0

10

20

(e) u1c5 ≻

30

40

50

60

70

80

0 0

10

20

G-AR P-AR

30

40

50

60

0

50

100

ns

(f) u1c5 ≻ P-BRAVE C-BRAVE

P-BRAVE C-BRAVE

G-AR P-AR

300

C-AR G-BRAVE

150

200

250

300

350

ss

(g) u5c5 ≻

C-AR G-BRAVE

350 60

50

300

400

100

7

70

40

400

ss

C-AR G-BRAVE

30

350

ns

G-AR P-AR

20

(d) u5c1 ≻ P-BRAVE C-BRAVE

200

1

10

ss

500

15

6

10

600

20

8

8

(c) u5c1 ≻

C-AR G-BRAVE

25

10

6

ns

(b) u1c1 ≻

C-AR G-BRAVE

P-BRAVE C-BRAVE

20.0

12

1.75

C-AR G-BRAVE

(h) u5c5 ≻ P-BRAVE C-BRAVE

G-AR P-AR

600

600

500

500

400

400

300

300

200

200

C-AR G-BRAVE

P-BRAVE C-BRAVE

250

50

200

40

150

30 20

100

10

50 0

0 2

4

6

8

10

12

14

16

0

0 0

20

ns

40

60

80

100

0

20

ss

(i) u1c10 ≻ G-AR P-AR

100

100

P-BRAVE C-BRAVE

G-AR P-AR

C-AR G-BRAVE

60

80

100

120

0

(k) u5c10 ≻ P-BRAVE C-BRAVE

G-AR P-AR

C-AR G-BRAVE

G-AR P-AR

600

600

500

500

500

500

400

400

400

400

300

300

300

300

200

200

200

200

100

100

100

0

0 10

15

20

25

30

35

50

ns

150

200

250

50

P-BRAVE C-BRAVE

G-AR P-AR

600

600

500

500

400

400

300

300

200

200

100

100

C-AR G-BRAVE

100

150

200

0

200

ns

(n) u1c20 ≻

C-AR G-BRAVE

500

600

700

800

C-AR G-BRAVE

P-BRAVE C-BRAVE

0 0

ss

(m) u1c20 ≻ G-AR P-AR

100

400

100

0 0

300

(l) u5c10 ≻ P-BRAVE C-BRAVE

600

5

200

ss

600

0

100

ns

(j) u1c10 ≻

C-AR G-BRAVE

40

G-AR P-AR

C-AR G-BRAVE

600

800

1000

1200

1400

1600

ss

(o) u5c20 ≻ P-BRAVE C-BRAVE

400

(p) u5c20 ≻ P-BRAVE C-BRAVE

G-AR P-AR

0.04

0.04

0.02

0.02

0.00

0.00

0.02

0.02

0.04

C-AR G-BRAVE

P-BRAVE C-BRAVE

0.04

0

0 0

10

20

30

40

50

60

0

ns

C-AR G-BRAVE

G-AR P-AR 600

500

500

400

400

300

300

200

200

100

100

0

0 20

40

60

80

100

ns

(u) u1c50 ≻

300

400

500

0.04

120

140

C-AR G-BRAVE

0.02

0.00

0.02

0.04

(s) u5c30 ≻ P-BRAVE C-BRAVE

G-AR P-AR

C-AR G-BRAVE

200

400

600

ss

(v) u1c50 ≻

800

0.02

0.00

0.02

0.04

ss

(t) u5c30 ≻ P-BRAVE C-BRAVE

G-AR P-AR

0.04

0.04

0.02

0.02

0.00

0.00

0.02

0.02

0.04 0

0.04

ns

(r) u1c30 ≻ P-BRAVE C-BRAVE

600

0

200

ss

(q) u1c30 ≻ G-AR P-AR

100

C-AR G-BRAVE

P-BRAVE C-BRAVE

0.04 0.04

0.02

0.00

0.02

ns

(w) u5c50 ≻

0.04

0.04

0.02

0.00

0.02

0.04

ss

(x) u5c50 ≻

Figure 6: Time (in seconds) to decide for each q(⃗a) whether q(⃗a) holds under X-AR/X-brave, with instances sorted by increasing solving time along the x-axis (i.e., a point (i, j) indicates that i instances could be solved within j seconds). Empty plots: in the case of u1c1 ≻ss , all potential answers are grounded so there was no potential answer left to check; in the other cases (s,t,w,x), we did not run these experiments as they would have taken too long (lots of answers to check and lots of time-out).

3.0 2.5 2.0 1.5 1.0 0.5 0.0

G-AR P-AR

1.0

C-AR G-BRAVE

1.2

1.4

P-BRAVE C-BRAVE

1.6

1.8

G-AR P-AR

2.0

16 14 12 10 8 6 4 2 0

2

4

nb

600 500 400 300 200 100 0

1

3

4

P-BRAVE C-BRAVE

5

6

7

G-AR P-AR

8

nb

600 500 400 300 200 100 0

2

4

8

12

14

16

600 500 400 300 200 100 0

0

10

C-AR G-BRAVE

20

P-BRAVE C-BRAVE

30

40

50

60

(d) u5c5 ≻

C-AR G-BRAVE

6

10

nb

(c) u1c5 ≻ G-AR P-AR

8

(b) u5c1 ≻

C-AR G-BRAVE

2

6

P-BRAVE C-BRAVE

nb

(a) u1c1 ≻ G-AR P-AR

C-AR G-BRAVE

P-BRAVE C-BRAVE

10

12

14

16

nb

(e) u1c10 ≻ G-AR P-AR 600 500 400 300 200 100 0

0

C-AR G-BRAVE

10

P-BRAVE C-BRAVE

20

30

40

nb

(f) u1c20 ≻ G-AR P-AR 600 500 400 300 200 100 0

0

10

C-AR G-BRAVE

20

30

P-BRAVE C-BRAVE

40

50

60

70

(g) u1c30 ≻nb G-AR P-AR 600 500 400 300 200 100 0

0

20

C-AR G-BRAVE

40

60

P-BRAVE C-BRAVE

80

100

120

140

nb

(h) u1c50 ≻

Figure 7: Time (in seconds) to decide for each q(⃗a) whether q(⃗a) holds under X-AR/X-brave, with instances sorted by increasing solving time along the x-axis (i.e., a point (i, j) indicates that i instances could be solved within j seconds).

u1c1 u1c5 u1c10 u1c20 u1c30 u1c50 u5c1 u5c5 u5c10 u5c20 u1c1 u1c5 u1c10 u1c20 u1c30 u1c50 u5c1 u5c5 u5c10 u5c20 u1c1 u1c5 u1c10 u1c20 u1c30 u1c50 u5c1 u5c5

≻ns ≻ns ≻ns ≻ns ≻ns ≻ns ≻ns ≻ns ≻ns ≻ns ≻ss ≻ss ≻ss ≻ss ≻ss ≻ss ≻ss ≻ss ≻ss ≻ss ≻nb ≻nb ≻nb ≻nb ≻nb ≻nb ≻nb ≻nb

Triv 1465 1366 1186 937 754 625 7637 6958 6069 4947 1477 1385 1215 931 731 618 7706 7044 6213 5169 1447 1369 1167 940 789 680 7708 7209

GR\Triv 59 159 341 584 764 875 316 990 1895 3035 48 65 232 374 299 152 195 591 1087 1480 76 155 359 571 726 823 238 742

P-AR\GR 0 (0) 0 (0) 0 (0) 1 (0) 6 (0) 26 (0) 0 (0) 22 (0) 22 (0) 37 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 1 (0) 1 (0) 2 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0)

G-AR\GR 0 (0) 0 (0) 0 (0) 0 (10) 0 (30) 9 (82) 0 (0) 21 (2) 8 (27) 6 (96) 0 (0) 0 (0) 0 (0) 0 (27) 0 (73) 0 (434) 0 (0) 1 (0) 1 (73) 2 (468) 0 (0) 0 (1) 0 (1) 0 (2) 0 (10) 0 (43) 0 (0) 0 (1)

C-AR\GR 0 (0) 0 (0) 0 (0) 1 (0) 6 (0) 20 (56) 0 (0) 22 (0) 22 (0) 32 (32) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 1 (0) 1 (0) 2 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0)

P-brave\GR 0 (0) 2 (0) 6 (0) 17 (0) 38 (0) 79 (0) 2 (0) 31 (0) 46 (0) 91 (0) 0 (0) 81 (0) 92 (0) 238 (0) 519 (0) 807 (0) 55 (0) 348 (0) 716 (0) 1437 (0) 0 (0) 1 (0) 1 (0) 1 (0) 6 (0) 20 (0) 2 (0) 3 (0)

G-brave\GR 0 (0) 2 (0) 6 (0) 16 (6) 19 (30) 28 (81) 2 (0) 30 (2) 34 (22) 51 (151) 0 (0) 81 (0) 92 (0) 228 (10) 475 (46) 512 (310) 55 (0) 348 (0) 684 (38) 992 (533) 0 (0) 0 (1) 0 (1) 0 (2) 5 (5) 13 (37) 2 (0) 2 (1)

C-brave\GR 0 (0) 2 (0) 6 (0) 17 (0) 38 (0) 38 (40) 2 (0) 31 (0) 46 (0) 83 (18) 0 (0) 81 (0) 92 (0) 238 (0) 519 (0) 807 (0) 55 (0) 348 (0) 716 (0) 1437 (0) 0 (0) 1 (0) 1 (0) 1 (0) 6 (0) 20 (0) 2 (0) 3 (0)

Table 16: Number of answers found trivially P-IAR (Triv), grounded (GR) but not trivially P-IAR, and X-AR or X-brave but not grounded. The number of potential answers for which we ran out of time (600s) is given in parenthesis. When the priority is score-structured (≻ss ), note that all optimal repairs coincide so it is expected that the number of X-AR/X-brave answers is the same for every X.