Paper deep dive
Using ASP(Q) to Handle Inconsistent Prioritized Data
Meghyn Bienvenu, Camille Bourgaux, Robin Jean, Giuseppe Mazzotta
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 96%
Last extracted: 4/26/2026, 8:34:44 PM
Summary
The paper explores the use of Answer Set Programming (ASP) and its extension with quantifiers (ASP(Q)) to handle inconsistent prioritized data. It focuses on implementing three notions of optimal repairs: Pareto-, globally-, and completion-optimal. The authors present the first implementation of globally-optimal repair-based semantics and the grounded semantics (a tractable under-approximation) using ASP(Q). The research demonstrates that ASP(Q) provides a compact way to model problems in the polynomial hierarchy and evaluates the feasibility and performance of these semantics through experimental evaluation.
Entities (8)
Relation Signals (3)
Meghyn Bienvenu → affiliatedwith → University of Bordeaux
confidence 100% · Meghyn Bienvenu1 ... Univ. Bordeaux
ASP(Q) → extends → Answer Set Programming
confidence 100% · ASP(Q) extends ASP by allowing quantification over answer sets of different ASP programs.
Grounded semantics → isapproximationof → Globally-optimal repair
confidence 90% · the grounded semantics, which is a tractable under-approximation of all these optimal repair-based semantics.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We explore the use of answer set programming (ASP) and its extension with quantifiers, ASP(Q), for inconsistency-tolerant querying of prioritized data, where a priority relation between conflicting facts is exploited to define three notions of optimal repairs (Pareto-, globally- and completion-optimal). 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 repair-based 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.
Tags
Links
- Source: https://arxiv.org/abs/2604.21603v1
- Canonical: https://arxiv.org/abs/2604.21603v1
Trouble viewing inline? Open PDF directly →
Full Text
125,539 characters extracted from source content.
Expand or collapse full text
Using ASP(Q) to Handle Inconsistent Prioritized Data Meghyn Bienvenu1 Camille Bourgaux2 Robin Jean 1 Giuseppe Mazzotta3 1Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, Talence, France 2DI ENS, ENS, CNRS, PSL University & Inria, Paris, France 3University of Calabria, Rende, Italy meghyn.bienvenu, robin.jean@u-bordeaux.fr, camille.bourgaux@ens.fr, giuseppe.mazzotta@unical.it Abstract We explore the use of answer set programming (ASP) and its extension with quantifiers, ASP(Q), for inconsistency-tolerant querying of prioritized data, where a priority relation between conflicting facts is exploited to define three notions of optimal repairs (Pareto-, globally- and completion-optimal). 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 repair-based 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. (?; ?) 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 (?; ?; ?). 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. (?) for a survey). In particular, ? (?) 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 (?; ?; ?; ?), two implementations (?; ?), and a framework for specifying and computing priority relations (?). 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., (?; ?; ?; ?; ?; ?) for relevant examples and (?, Table 8) for an overview). The two implementations of optimal repair-based semantics follow this path: the one by ? (?) is based on the use of tractable approximations and SAT solvers, and that by ? (?) 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 (?), which complicate modeling “beyond the capabilities of the common ASP laymen” (?). Moreover, efficiency-wise it has been shown that in many cases of practical interest alternative formalisms are preferred to disjunctive ASP (?). 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 hierarchy (?). ASP(Q) has already been used to tackle problems related to planning (?; ?) and abstract argumentation (?). We investigate the use of ASP(Q) and ASP to implement optimal repair-based semantics. Compared to the previous ASP-based implementation by ? (?), we handle globally-optimal repairs thanks to ASP(Q) and improve the system performance by using tractable approximations in a similar way as ? (?). Moreover, we explore the use of another tractable approximation of the optimal repair-based semantics, called the grounded semantics (?), which has never been implemented so far. Our experimental evaluation shows that using globally-optimal repairs is considerably more challenging than for Pareto- or completion-optimal 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≥1n≥ 1, and let n P_n 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)P(c_1,…,c_n) with P∈nP∈ P_n, ci∈c_i∈ C for 1≤i≤n1≤ 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 (?) and denial constraints of the form α1∧…∧αn→⊥ _1 … _n→ , where each αi _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 has some model. Otherwise, K is inconsistent, denoted ⊧⊥K . A conflict of =(,)K=(D,T) is an inclusion-minimal subset ⊆C 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 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 α,β⊆\α,β\ for some ∈()C (K). It is total if for every pair α≠βα≠β such that α,β⊆\α,β\ for some ∈()C (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 (K). • A Pareto improvement of ℛR is a T-consistent ℬ⊆B such that there is β∈ℬ∖ℛβ with β≻αβ α for every α∈ℛ∖ℬα . • A global improvement of ℛR is a T-consistent ℬ⊆B such that ℬ≠ℛB and for every α∈ℛ∖ℬα there exists β∈ℬ∖ℛβ 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_ ) (K_ ) (K_ ). Queries, Repair-Based Semantics A conjunctive query (CQ) is a conjunction of atoms P(t1,…,tn)P(t_1,…,t_n) (P∈nP∈ P_n, ti∈∪t_i∈ C∪ V), where some variables may be existentially quantified. Given a query q(x→)q( x), with free variables x→ x, and a tuple of constants a→ a such that |a→|=|x→|| a|=| x|, q(a→)q( a) denotes the first-order sentence obtained by replacing each variable in x→ x by the corresponding constant in a→ a. A (certain) answer to q(x→)q( x) over K is a tuple a→ a of constants such that q(a→)q( a) holds in every model of K, denoted ⊧q(a→)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,CX∈\S,P,G,C\ and consider a prioritized KB ≻K_ with =(,)K=(D,T), query q(x→)q( x), and tuple of constants a→ a. Then a→ a is an answer to q(x→)q( x) over ≻K_ • under X-brave semantics, denoted ≻⊧braveXq(a→)K_ _ brave^Xq( a), if (ℛ,)⊧q(a→)(R,T) q( a) for some ℛ∈(≻)R (K_ ); • under X-AR semantics, denoted ≻⊧ARXq(a→)K_ _ AR^Xq( a), if (ℛ,)⊧q(a→)(R,T) q( a) for every ℛ∈(≻)R (K_ ); • under X-IAR semantics, denoted ≻⊧IARXq(a→)K_ _ IAR^Xq( a), if (ℬ,)⊧q(a→)(B,T) q( a) where ℬ=⋂ℛ∈(≻)ℛB= _R (K_ )R. It is known that ≻⊧IARXq⇒≻⊧ARXq⇒≻⊧braveXqK_ _ IAR^Xq _ _ AR^Xq _ _ brave^Xq. A cause for q(a→)q( a) w.r.t. =(,)K=(D,T) is an inclusion-minimal T-consistent subset ⊆C such that (,)⊧q(a→)(C,T) q( a). The set of causes for q(a→)q( a) w.r.t. K is denoted by (q(a→),)Causes(q( a),K). We will use the following characterizations of the semantics: • ≻⊧braveXq(a→)K_ _ brave^Xq( a) iff there exist ℛ∈(≻)R (K_ ) and ∈(q(a→),)C (q( a),K) such that ⊆ℛC ; • ≻⊧̸ARXq(a→)K_ _ AR^Xq( a) iff there exists ℛ∈(≻)R (K_ ) such that for every ∈(q(a→),)C (q( a),K), ⊈ℛC ; • ≻⊧IARXq(a→)K_ _ IAR^Xq( a) iff there exists ∈(q(a→),)C (q( a),K) such that ⊆⋂ℛ∈(≻)ℛC _R (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→)q( x) are assumed to be fixed) of query answering under these semantics (cf. survey (?, Table 6)). Theorem 1. Let ℒL be an FOL fragment for which KB consistency and query entailment are in PTime. Query entailment for ℒL KBs is in Σ2p ^p_2 under G-brave semantics, in Π2p ^p_2 under G-AR and G-IAR semantics, and for X∈S,P,CX∈\S,P,C\, it is in NP under X-brave semantics, and in coNPco NP under X-AR and X-IAR semantics. Theorem 2. Let ℒL be any FOL fragment that extends DL-Litecore or FDs. Query entailment for ℒL KBs is Σ2p ^p_2-hard under G-brave semantics, Π2p ^p_2-hard under G-AR and G-IAR semantics, NP-hard under X-brave semantics for X∈P,CX∈\P,C\, and coNPco NP-hard under X-AR semantics for X∈S,P,CX∈\S,P,C\ and under X-IAR semantics for X∈P,CX∈\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 ↝⊆(2∖∅)× (2^D \ \)×D is defined by: ↝=(∖α,α)∣∈(),α∈,∀β∈,α⊁β. =\(C \α\,α) (K),α ,∀β ,α β\. We write ℬ↝αB α for (ℬ,α)∈↝(B,α)∈ . The characteristic function Γ:2↦2 :2^D 2^D is defined by Γ(ℬ)=α∣ℰ↝α⇒∃ℱ⊆ℬ,β∈ℰ s.t. ℱ↝β. (B)=\α α ,β s.t. F β\. The grounded repair of ≻K_ is the inclusion-minimal ⊆G such that G is T-consistent and =Γ()G= (G), or equivalently, the least fixpoint of Γ . A tuple a→ a is an answer to q(x→)q( x) over ≻K_ under grounded semantics, denoted ≻⊧GRq(a→)K_ _ GRq( a), if (,)⊧q(a→)(G,T) q( a). It is known that ≻⊧GRq(a→)K_ _ GRq( a) implies ≻⊧IARPq(a→)K_ _ IAR^Pq( a), so answers that hold under the grounded semantics hold under X-IAR for X∈P,G,CX∈\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 PTime, then grounded query entailment for ℒL KBs is in PTime (?). Example 1. Consider the KB =(,)K=(D,T) with: = =\ A(a),B(a),C(a),D(a),A(b),B(b),C(b) A(a),B(a),C(a),D(a),A(b),B(b),C(b)\ = =\ A(x)∧B(x)→⊥,B(x)∧C(x)→⊥, A(x) B(x)→ ,\ B(x) C(x)→ , C(x)∧D(x)→⊥,D(x)∧A(x)→⊥ C(x) D(x)→ ,\ D(x) A(x)→ \ The conflicts and repairs of K are as follows: ()= (K)\!=\!\ A(a),B(a),B(a),C(a),C(a),D(a), \A(a),B(a)\,\B(a),C(a)\,\C(a),D(a)\, D(a),A(a),A(b),B(b),B(b),C(b) \D(a),A(a)\,\A(b),B(b)\,\B(b),C(b)\\ ()= (K)\!=\!\ A(a),C(a),B(b),B(a),D(a),B(b) \A(a),C(a),B(b)\,\B(a),D(a),B(b)\ A(a),C \A(a),C (a),A(b),C(b),B(a),D(a),A(b),C(b) (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)A(a) B(a), C(a)≻D(a)C(a) D(a), A(b)≻B(b)A(b) B(b), and B(b)≻C(b)B(b) C(b). (≻)=(≻)=A(a),C(a),A(b),C(b) (K_ )=GRep(K_ )=\\A(a),C(a),A(b),C(b)\\ (≻)=(≻)∪B(a),D(a),A(b),C(b) (K_ )=GRep(K_ )∪\\B(a),D(a),A(b),C(b)\\ We thus obtain, e.g., ≻⊧ARGA(a)K_ _ AR^GA(a) while ≻⊧̸ARPA(a)K_ _ AR^PA(a), ≻⊧bravePB(a)K_ _ brave^PB(a) while ≻⊧̸braveGB(a)K_ _ brave^GB(a), and ≻⊧IARXC(b)K_ _ IAR^XC(b) for X∈P,G,CX∈\P,G,C\. The grounded repair of ≻K_ is =A(b),C(b)G=\A(b),C(b)\. Indeed, the attack relation ↝ is as written below, so Γ(∅)=A(b) ( )=\A(b)\, since A(b)A(b) is the only fact of D that is not attacked, Γ(A(b))=A(b),C(b) (\A(b)\)=\A(b),C(b)\, and Γ(A(b),C(b))=A(b),C(b) (\A(b),C(b)\)=\A(b),C(b)\. A(a)↝B(a) \A(a)\ B(a) B(a)↝C(a) \B(a)\ C(a) C(a)↝B(a) \C(a)\ B(a) C(a)↝D(a) \C(a)\ D(a) D(a)↝A(a) \D(a)\ A(a) A(a)↝D(a) \A(a)\ D(a) A(b)↝B(b) \A(b)\ B(b) B(b)↝C(b) \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(t_1,…,t_n) where p is a predicate of arity n≥0n≥ 0 and each term t_i 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 a not~a, where not represents negation as failure. It is negative if it is of the form a not~a, positive otherwise. An ASP program111We consider core ASP, without disjunction in rule heads. is a finite set of rules of the form h:-l1,…,lnh\ :\!-\ l_1,…,l_n (with n≥0n≥ 0), whose head h is an atom, and whose body l1,…,lnl_1,…,l_n is interpreted as the conjunction of the literals l1,…,lnl_1,…,l_n. 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\ :\!-\ l_1,…,l_n), and a fact is a rule with an empty body (h:-h\ :\!-\ ). We also allow choice rules of the forms h:-l1,…,ln\h\\ :\!-\ l_1,…,l_n and 1h1;h21:-l1,…,ln1\h_1;h_2\1\ :\!-\ l_1,…,l_n: the former is used to choose to either add or omit h, and the latter enforces that precisely one of h1h_1 and h2h_2 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 (?). 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 PU_P of constants appearing in P and the Herbrand Base of P is the set ℬPB_P of ground atoms constructed from predicates of P and constants in PU_P. We denote by (P)ground(P) the set of all possible ground rules obtained from rules in P by proper variable substitution with constants in PU_P (cf. (?)). An interpretation is a set of atoms I⊆ℬPI _P. A positive (resp. negative) ground literal l=al=a (resp. l=al= not~a) is true w.r.t. an interpretation I if a∈Ia∈ I (resp. a∉Ia∉ 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∈(P)r (P). The GL-reduct (?) of P w.r.t. I is the program PIP^I obtained from (P)ground(P) by (i)(i) removing each rule having at least one negative body literal false w.r.t. I; and (ii)(i) 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 PIP^I. We denote by AS(P)AS(P) the set of all answer sets of P. A program P is coherent if it has some answer set. ASP(Q) ASP with quantifiers (ASP(Q)) (?) extends ASP by allowing quantification over answer sets of different ASP programs. An ASP(Q) program is an expression of the form: □1P1…□nPn:C _1P_1… _nP_n:C (1) where C is a stratified222Stratified programs respect some conditions that prevent default negation to be involved in recursion. ASP program (?) with constraints and for each i∈1,…,ni∈\1,…,n\, □i∈∃st,∀st _i∈\∃^st,∀^st\ is a quantifier and PiP_i 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: P(I)= _P(I)= a:-∣a∈ℬP∩I∪:-a∣a∈ℬP∖I \a\ :\!-\ a _P∩ I\∪\\ :\!-\ a a _P I\ ΠP,I= _P,I= □1P1∪P(I)…□nPn:C _1P_1 _P(I)… _nP_n:C The ASP(Q) semantics is defined inductively: • ∃stP:C∃^stP:C is coherent if and only if there exists M∈AS(P)M∈ AS(P) such that C∪P(M)C _P(M) is coherent; • ∀stP:C∀^stP:C is coherent if and only if for each M∈AS(P)M∈ AS(P), C∪P(M)C _P(M) is coherent; • ∃stPΠ∃^stP~ is coherent if and only if there exists M∈AS(P)M∈ AS(P) such that ΠP,M _P,M is coherent; • ∀stPΠ∀^stP~ is coherent if and only if for each M∈AS(P)M∈ AS(P), ΠP,M _P,M is coherent. The quantified answer sets of an existential ASP(Q) program ∃stPΠ∃^stP~ , with Π of form (1), are all M∈AS(P)M∈ AS(P) such that ΠP,M _P,M is coherent. Example 2. Let Π=∃stP1∀stP2:C =∃^stP_1∀^stP_2:C where: P1=:-:-:-:-P_1= \ array[]l a\ :\!-\ not~b\\ b\ :\!-\ not~a\\ c\ :\!-\ not~d\\ d\ :\!-\ not~c\\ array \ P2=:-,:-,:-,:-,P_2= \ array[]l e\ :\!-\ a,not~f\\ f\ :\!-\ a,not~e\\ \ :\!-\ e,d\\ \ :\!-\ f,d\\ array \ C=:-C= \ array[]l \ :\!-\ f\\ array \ Let us check whether Π is coherent, i.e., whether there is an answer set M1M_1 of P1P_1 such that ∀stP2∪P1(M1):C∀^stP_2 _P_1(M_1):C is coherent. We have AS(P1)=,,,,,,,AS(P_1)=\\ a, c\,\ a, d\,\ b, c\,\ b, d\\. Consider first M1=,M_1=\ a, c\ and let P2′=P2∪P1(M1)P_2 =P_2 _P_1(M_1). P2′P _2 has two answer sets: M2′=,,M_2 =\ a, c, e\ and M2′=,,M_2 =\ a, c, f\, so for ∀stP2′:C∀^stP _2:C to be coherent, both C∪P2′(M2′)C _P_2 (M_2 ) and C∪P2′(M2′)C _P_2 (M_2 ) have to be coherent. However, C∪P2′(M2′)C _P_2 (M_2 ) is incoherent (it contains both :- \ :\!-\ f and :- f\ :\!-\ ). Thus, M1=,M_1=\ a, c\ is not a quantified answer set of Π and so not a witness for the coherence of Π . Consider now M1=,M_1=\ b, c\. Then P2′=P2∪P1(M1)P_2 =P_2 _P_1(M_1) has exactly one answer set, M2=,M_2=\ b, c\. In this case C∪P2′(M2)C _P_2 (M_2) is coherent as f is false w.r.t. M2M_2. Thus, M1=,M_1=\ b, c\ is a quantified answer set of Π and Π is coherent. Let us now consider Π′ of the form ∃stP1∀stP2:C′∃^stP_1∀^stP_2:C where C′=:-C =\ \ :\!-\ not~fail\. Observe that fail does not appear in any rule head of P1P_1, P2P_2, and C′C . Hence, C′∪P2∪P1(M1)(M2)C _P_2 _P_1(M_1)(M_2) will be incoherent for every choice of M1∈AS(P1)M_1∈ AS(P_1) and M2∈AS(P2∪P1(M1))M_2∈ AS(P_2 _P_1(M_1)), 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=,M_1=\ a, d\ is a quantified answer set of Π′ because P2′=P2∪P1(M1)P_2 =P_2 _P_1(M_1) is incoherent, so the universal quantification over answer sets of P2′P_2 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 ? (?), 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 (q(a→),)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. Πℎ _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. 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 _1 _2 stands for Π1∪Π2 _1∪ _2): ΠG= ^G_brave= ∃stΠℎΠΠ∀stΠ:C ∃^st _ReachAll _Rep _SomeCause∀^st _GImp:C ΠG= _AR^G= ∃stΠℎΠΠ∀stΠ:C ∃^st _ReachAll _Rep _NoCause∀^st _GImp:C with C=:-C=\\ :\!-\ not~fail\. Let us first explain how ΠG ^G_brave works. We want to check whether there exists ℛ∈(≻)R (K_ ) such that ⊆ℛC for some ∈(q(a→),)C (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 α∈ℛα , 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 α∉ℛα , so the constraint :-(),() \ :\!-\ conf(C),not~solved(C) imposes that 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 α∈∖ℛα with identifier A using () keepOut(A). The last constraint imposes that every α∉ℛα is marked by keepOut, meaning that there is a conflict C such that α∈α and ∖α⊆ℛC \α\ , i.e., ℛ∪αR∪\α\ is T-inconsistent. • 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 , and the atom sat is derived if there exists some cause C for which () violatedCause(C) is not derived (hence ⊆ℛC ). The constraint in Π∖Π _SomeCause _SatIfCause imposes that sat is true, so at least one cause must be included. Hence, an answer set of Πℎ∪Π∪Π _ReachAll∪ _Rep∪ _SomeCause corresponds to some ℛ∈()R (K) with (ℛ,)⊧q(a→)(R,T) q( a). The second program of ΠG ^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 and ℛ∖ℬR , using predicates impMinusRepair and repairMinusImp, respectively. This is used to (i) check whether ℬ≠ℛB with the two rules that derive diff if either ℬ∖ℛ≠∅B ≠ or ℛ∖ℬ≠∅R ≠ and (i) check whether for every α∈ℛ∖ℬα , there exists β∈ℬ∖ℛβ such that β≻αβ α with the rule that derives () ok(A) if α∈ℛ∖ℬα with identifier A satisfies this condition. The atom _ fake\_improvement is derived when (i) or (i) is not satisfied, i.e., if diff is false or if () ok(A) is false for the identifier A of some α∈ℛ∖ℬα . 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=Πℎ∪Π∪ΠP_1= _ReachAll∪ _Rep∪ _SomeCause and P2=ΠP_2= _GImp, a quantified answer set M of ΠG ^G_brave must be an answer set of P1P_1 such that P2∪P1(M)P_2 _P_1(M) is incoherent. The next proposition follows. Proposition 1. ≻⊧braveGq(a→)K_ _ brave^Gq( a) iff ΠG ^G_brave is coherent. The program for G-AR, ΠG _AR^G, is exactly as ΠG ^G_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→)q( a). Indeed, :-∈Π \ :\!-\ sat∈ _NoCause requires that sat is not derived by Π _SatIfCause, so that there is no cause C such that ⊆ℛC . Proposition 2. ≻⊧ARGq(a→)K_ _ AR^Gq( a) iff ΠG _AR^G is incoherent. We also considered an alternative program of the form ∀stP∃stP′:C′∀^stP∃^stP :C for G-AR, but as it was less efficient in practice, we present it only in the appendix. P- and C- Brave and AR For X∈P,CX∈\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. ΠX= _brave^X= Πℎ∪Π∪Π∪Π _ReachAll∪ _SubRep∪ _XOpt∪ _SomeCause ΠX= _AR^X= Πℎ∪Π∪Π∪Π _ReachAll∪ _SubRep∪ _XOpt∪ _NoCause As explained in the case X=GX=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 ? (?). • 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) α∈ℛα , or (i) α is attacked by ∖αC \α\ for some conflict C such that ∖α⊆ℛC \α\ . The constraint :-(),() \ :\!-\ reachable(A),not~valid(A) thus ensures that every α∉ℛα is attacked by a set of facts included in ℛR. This means that ℛR is ⊆ -maximal and Pareto-optimal: otherwise, there would be α∉ℛα 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) α∈ℛα , or (i) α is in a conflict C such that ∖α⊆ℛC \α\ and α⊁′βα β for every β∈∖αβ \α\. The constraint :-(),() \ :\!-\ reachable(A),not~valid(A) thus ensures that every α∉ℛα 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,CX∈\P,C\, ≻⊧braveXq(a→)K_ _ brave^Xq( a) iff ΠX _brave^X is coherent, and ≻⊧ARXq(a→)K_ _ AR^Xq( a) iff ΠX _AR^X is incoherent. X-IAR We compute ⋂ℛ∈(≻)ℛ _R (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. ΠΓ(∅) _ ( ) (,):-(,). unsafe(A,0)\ :\!-\ attacks(C,A). (,):-(,),(,). safe(A,0)\ :\!-\ inConf(C,A),not~unsafe(A,0). ΠΓincr _ 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). 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 ? (?) and ? (?), 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 (?). Definition 3. Given a prioritized KB ≻K_ with =(,)K=(D,T) in ≻K_ and ℬ⊆B , (ℬ) R_ s(B) is the set of facts reachable from ℬB in the directed hypergraph333A node γ is reachable from a set of nodes ℬB in a directed hypergraph if γ∈ℬγ or there exists a node β reachable from ℬB and some edge (β,ℰ)(β,E) such that γ∈ℰγ . whose edges are (α,ℰ)∣ℰ↝α=(α,ℰ)∣ℰ∪α∈(),∀β∈ℰ,α⊁β\(α,E) α\=\(α,E) ∪\α\ (K),∀β ,α β\ and (ℬ) R_ w(B) is the set of facts reachable from ℬB in the directed hypergraph whose edges are (α,ℰ)∣ℰ∪α∈(),∃β∈ℰ,α⊁β\(α,E) ∪\α\ (K),∃β ,α β\. Note that (ℬ)⊆(ℬ) R_ s(B) R_ w(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 (α,β)∣α,β∈(),α⊁β\(α,β) \α,β\ (K),α β\. Theorem 3. Let X∈P,G,CX∈\P,G,C\, ℬ⊆B , ℬr=(ℬ)B_r= R_ w(B), ℬr=(ℬr,)K^B_r=(B_r,T) and ≻ℬr ^B_r be the restriction of ≻ to ℬrB^r. • If ℛ∈(≻)R (K_ ), then ℛ∩ℬr∈(≻ℬrℬr)R _r (K^B_r_ ^B_r). • If ℛ∈(≻ℬrℬr)R (K^B_r_ ^B_r), then there exists ℛ′∈(≻)R (K_ ) such that ℛ=ℛ′∩ℬrR=R _r. Theorem 4. If ℬr=(ℬ)B_r= R_ w(B) is replaced by ℬr=(ℬ)B_r= R_ s(B), Theorem 3 still holds for X∈P,CX∈\P,C\. We can thus replace Πℎ _ReachAll by Πℎ _ReachW or Πℎ _ReachS (if X∈P,CX∈\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 compute (ℬ) R_ s(B) and (ℬ) R_ w(B) for ℬ=⋃∈(q(a→),)B= _C (q( a),K)C, respectively. We leave open whether Theorem 4 holds for X=GX=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 globally-optimal 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). Pareto-Optimality We use again the fact that when the conflicts are binary the attack relation is straightforward (β↝α\β\ α iff α,β∈()\α,β\ (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 (?; ?), 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 globally-optimal repairs: ≻⊧ARPq(a→)K_ _ AR^Pq( a) implies ≻⊧ARGq(a→)K_ _ AR^Gq( a) (hence also ≻⊧braveGq(a→)K_ _ brave^Gq( a)) and ≻⊧̸bravePq(a→)K_ _ brave^Pq( a) implies ≻⊧̸braveGq(a→)K_ _ brave^Gq( a) (hence also ≻⊧̸ARGq(a→)K_ _ AR^Gq( a)). 4 Experiments Our experimental evaluation aims at (i) evaluating the impact of adopting globally-optimal repairs, (i) assessing the grounded semantics, and (i) 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 Γ(∅) ( )? • 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 ∩S\! _S\! Γ1∖∩S\! ^1\! \! _S\! Γ2∖Γ1\! ^2\! \! ^1\! Γ3∖Γ2\! ^3\! \! ^2\! Γ4∖Γ3\! ^4\! \! ^3\! u1c1 ≻ns\ ^ns 73351 921 1365 0 0 u1c50 43779 7289 21319 1329 8 u1c1 ≻ss\ ^s 73351 1225 881 0 0 u1c50 43779 8493 9368 11 0 u1c1 ≻nb\ ^nb 73131 989 1406 4 0 u1c50 43612 10777 18629 52 0 Table 3: Number of facts in the different parts of the grounded repair: ∩S=⋂ℛ∈()ℛ _S= _R (K)R, Γi=Γi(∅) ^i= ^i( ). ≻ss ^s ≻ns ^ns ∖∩S\!G\! \! _S\! Γ1∖∩S\! ^1\! \! _S\! ∖∩S\!G\! \! _S\! Γ1∖∩S\! ^1\! \! _S\! u1c1 1.58 0.16 2.10 0.16 u1c20 14.92 1.26 21.22 1.39 u1c50 61.80 3.53 126.39 3.80 u5c1 7.85 0.68 10.70 0.68 u5c20 129.31 7.12 240.34 7.11 u5c50 304.11 14.55 oom 14.69 u20c1 23.75 2.41 47.05 2.39 u20c20 oom 36.07 oom 33.13 Table 4: Time (in seconds) to compute the facts that belong to the grounded repair G or to Γ1=Γ(∅) ^1= ( ) (among those that belong to some conflict) from the precomputed attack relation. ∩S\! _S\! ∖∩S\!G\! \! _S\! ∩P∖\! _P\! \!G\! ∩G∖∩P\! _G\! \! _P\! ∩C∖∩G\! _C\! \! _G\! u1c1 ≻ns\ ^ns 73351 2286 0 0 0 u1c10 65310 10134 3 22 1 u1c20 56646 18507 82 46 7 Table 5: Size of grounded repair G and optimal repair intersections: ∩X=⋂ℛ∈(≻)ℛ _X= _R (K_ )R for X∈S,P,G,CX∈\S,P,G,C\. Following ? (?), we translated into ASP programs a subset of the ORBITS benchmark (?) which provides several conflict sets, priority relations, and potential answers associated with their causes built from the CQAPri benchmark (?), a synthetic benchmark adapted from LUBM20∃^∃_20 (?) to evaluate inconsistency-tolerant query answering over DL-Lite KBs. To experiment also with non-binary conflicts, ? (?) 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 ∈1,5,10,20,30,50 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. 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 ∈1,5,10,20 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 ^s is built from priority levels, hence is such that globally-, Pareto- and completion-optimal repairs coincide, while ≻ns ^ns is not score-structured and allows us to distinguish between the three kinds of repairs. Moreover, ≻ss ^s assigns a priority between the two facts of about 40% of the conflicts and this proportion is about 30% for ≻ns ^ns. For the non-binary conflicts case, we use a priority relation ≻nb ^nb resulting from some preference rules given by ? (?) which assigns a priority between two facts that belong to some conflict in about 90% of the cases. Queries We use the 8 queries ? (?) 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 pyrunlim444pyrunlim is available at https://github.com/alviano/python.git. As ASP(Q) solver we used the casper system (?)555Other ASP(Q) systems are available, such as qasp (?) and pyqasp (?), but casper performed better in our preliminary evaluation., and as ASP solver we used clingo (?). 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). Triv GR∖ Pot∖ P-AR∖ G-AR∖ C-AR∖ P-brave∖ G-brave∖ C-brave∖ u1c1 ≻ns ^ns 1465 59 1 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) u1c20 937 584 35 1 (0) 0 (10) 1 (0) 17 (0) 16 (6) 17 (0) u1c50 625 875 141 26 (0) 9 (82) 20 (56) 79 (0) 28 (81) 38 (40) u5c1 7637 316 10 0 (0) 0 (0) 0 (0) 2 (0) 2 (0) 2 (0) u5c20 4947 3035 224 37 (0) 6 (96) 32 (32) 91 (0) 51 (151) 83 (18) u1c1 ≻nb ^nb 1447 76 2 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) u1c20 940 571 45 0 (0) 0 (2) 0 (0) 1 (0) 0 (2) 1 (0) u1c50 680 823 138 0 (0) 0 (43) 0 (0) 20 (0) 13 (37) 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. Figure 1: Time (in seconds, y-axis) to decide for each q(a→)q( a), dataset uXcY, and priority relation, whether q(a→)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)(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) 4.2 Experimental Results In what follows, we summarize our main observations. 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→)q( a), dataset uXcY, and priority relation, if q(a→)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 _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,CX∈\P,G,C\. This is also the reason that we did not conduct further experimental evaluations of the X-IAR semantics. Impact of Localization Unsurprisingly, localization is crucial. For example, on u1c10 with ≻nb ^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,CX∈\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,CX∈\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)(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,CX∈\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∖ 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 ^s 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 completion-optimal 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 Appendix A Proofs for Section 3 See 1 Proof Sketch. (⇐)( ) Assume that ΠG ^G_brave has a quantified answer set M. Since M∈AS(P1)M∈ AS(P_1), the set ℛR that contains all facts whose identifiers are in ∣()∈M\ 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→)q( a). Moreover, since P2∪P1(M)P_2 _P_1(M) is incoherent, ℛR does not have any global improvement. Hence ≻⊧braveGq(a→)K_ _ brave^Gq( a). (⇒)( ) Conversely, assume that ΠG ^G_brave is incoherent. Let ℛ∈()R (K) be such that ℛR contains some cause for q(a→)q( a). The interpretation M that contains (i) () inRepair(A) for every identifier A of α∈ℛα and (i) the atoms (deterministically) derived by P1∖():-()P_1 \ \inRepair(A)\\ :\!-\ reachable(A)\ is such that M∈AS(P1)M∈ AS(P_1). Since M is such that P2∪P1(M)P_2 _P_1(M) is coherent (otherwise ΠG ^G_brave will be coherent), ℛR admits a global improvement. Thus ≻⊧̸braveGq(a→)K_ _ brave^Gq( a). ∎ 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 , and the set of facts reachable from ℬB (w.r.t. ‘weak’ reachability) ℬr=(ℬ)B_r= R_ w(B), which is used to define the prioritized KB ≻ℬrℬrK^B_r_ ^B_r by ℬr=(ℬr,)K^B_r=(B_r,T) and ≻ℬr ^B_r the restriction of ≻ to ℬrB^r. In the proofs of the propositions, we will use the set of minimal (w.r.t. ≻ ) facts of a conflict: for every ∈()C (K) let Min()=γ|∀δ∈,γ⊁δMin(C)=\γ|∀δ ,γ δ\. We recall that if ≻′ is a total priority relation, there is a unique Pareto-, globally- and completion-optimal repair (?), 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,CX∈\P,G,C\, if ℛ∈(≻)R (K_ ), then ℛ∩ℬr∈(≻ℬrℬr)R _r (K^B_r_ ^B_r). Proof. Case =X=P. Let ℛ∈(≻)R (K_ ) and suppose for a contradiction that ℛ∩ℬr∉(≻ℬrℬr)R _r (K^B_r_ ^B_r): there exists ℛ0⊆ℬrR_0 _r such that there exists β∈ℛ0∖(ℛ∩ℬr)β _0 (R _r), such that β≻αβ α for all α∈(ℛ∩ℬr)∖ℛ0α∈(R _r) _0. Let ℛ0~=β∪(ℛ0∩ℛ)∪(ℛ∖ℬr) R_0=\β\∪(R_0 )∪(R _r). We build a Pareto improvement of ℛR w.r.t. ≻K_ by removing selected elements from ℛ0~ R_0 to obtain a contradiction with ℛ∈(≻)R (K_ ). Claim 1. For every ∈()C (K) such that ⊆ℛ0~C R_0, there exists γ∈ _C such that β≻γβ _C. Proof of claim. Let ∈()C (K) be such that ⊆ℛ0~C R_0. First, note that β∈β as otherwise ⊆ℛC , which contradicts the T-consistency of ℛR. Moreover, ∩(ℛ∖ℬr)≠∅C∩(R _r)≠ as otherwise ⊆ℛ0C _0 which contradicts the T-consistency of ℛ0R_0. By definition of ℬr=(ℬ)B_r= R_ w(B), and since β∈ℬrβ _r, if for every γ∈γ , β⊁γβ γ, it would hold that ⊆ℬrC _r. Since we showed that ∩(ℛ∖ℬr)≠∅C∩(R _r)≠ , it follows that there exists γ∈ _C such that β≻γβ _C. (end of claim proof) Let Γℛ0~=γ∣∈(),⊆ℛ0~,β≻γ _ R_0=\ _C (K),C R_0,β _C\ and ℛ0′=ℛ0~∖Γℛ0~R _0= R_0 _ R_0. As ℛ0′R _0 is obtained by removing at least one fact per conflict included in ℛ0~ R_0, it is T-consistent. Also: ℛ0′∖ℛ _0 =(ℛ0~∖Γℛ0~)∖ℛ =( R_0 _ R_0) =((β∪(ℛ0∩ℛ)∪(ℛ∖ℬr))∖Γℛ0~)∖ℛ =((\β\∪(R_0 )∪(R _r)) _ R_0) =β since β∉Γℛ0~ and β∉ℛ; =\β\ since $β ∈ _ R_0$ and $β $; ℛ∖ℛ0′ _0 =ℛ∖(ℛ0~∖Γℛ0~) =R ( R_0 _ R_0) =((ℛ∩ℬr)∖ℛ0)∪Γℛ0~ since Γℛ0~⊆ℛ. =((R _r) _0)∪ _ R_0 since $ _ R_0 $. By construction of ℛ0′R _0, for every α∈ℛ∖ℛ0′α _0, β≻αβ α. Hence ℛ0′R _0 is a Pareto improvement of ℛR, which contradicts ℛ∈(≻)R (K_ ). Therefore ℛ∩ℬr∈(≻ℬrℬr)R _r (K^B_r_ ^B_r). Case =X=G. Let ℛ∈(≻)R (K_ ) and suppose for a contradiction that ℛ∩ℬr∉(≻ℬrℬr)R _r (K^B_r_ ^B_r): there exists ℛ0⊆ℬrR_0 _r such that ℛ0≠ℛ∩ℬrR_0 _r and for every α∈(ℛ∩ℬr)∖ℛ0α∈(R _r) _0, there exists β∈ℛ0∖(ℛ∩ℬr)β _0 (R _r) such that β≻αβ α. Let ℛ0~=ℛ0∪(ℛ∖ℬr) R_0=R_0∪(R _r). We build a global improvement of ℛR w.r.t. ≻K_ by removing selected elements from ℛ0~ R_0 to obtain a contradiction with ℛ∈(≻)R (K_ ). We first show that for every ∈()C (K) such that ⊆ℛ0~C R_0, there exist β∈∩(ℛ0∖(ℛ∩ℬr)) _C ∩(R_0 (R _r)) and γ∈∖(ℛ0∖(ℛ∩ℬr)) _C (R_0 (R _r)) such that β≻γ _C _C. Let ∈()C (K) be such that ⊆ℛ0~C R_0. First, note that ∩(ℛ0∖(ℛ∩ℬr))≠∅C∩(R_0 (R _r))≠ as otherwise ⊆ℛC , which contradicts the T-consistency of ℛR. Moreover, ∩(ℛ∖ℬr)≠∅C∩(R _r)≠ as otherwise ⊆ℛ0C _0, which contradicts the T-consistency of ℛ0R_0. Claim 2. For every ∈()C (K) such that ⊆ℛ0~C R_0, Min()⊆ℛ∖ℬrMin(C) _r Proof of claim. By definition of ℬr=(ℬ)B_r= R_ w(B), if there was α∈Min()α∈ Min(C) such that α∈ℬrα _r, it would hold that ⊆ℬrC _r. Since ∩(ℛ∖ℬr)≠∅C∩(R _r)≠ , it follows that Min()⊆ℛ∖ℬrMin(C) _r. (end of claim proof) We define (βi)i∈ℕ∈ℕ( _i)_i ^N with β0∈∩(ℛ0∖(ℛ∩ℬr)) _0 ∩(R_0 (R _r)) (such β0 _0 exists since ∩(ℛ0∖(ℛ∩ℬr))≠∅C∩(R_0 (R _r))≠ ) and for i∈ℕi : • if βi∈ℛ0 _i _0 then let βi+1∈ _i+1 be such that βi≻βi+1 _i _i+1 (such βi+1 _i+1 exists because Min()⊆ℛ∖ℬrMin(C) _r and ℛ0⊆ℬrR_0 _r so βi∉Min() _i∉ Min(C)); • otherwise (βi∉ℛ0 _i _0), let βi+1=βi _i+1= _i. As D is finite and ≻ is acyclic the sequence is ultimately constant. Let j=mini∈ℕ(βi+1∉ℛ0∖(ℛ∩ℬr))j= _i ( _i+1 _0 (R _r)). Let β=βj _C= _j and γ=βj+1 _C= _j+1. By definition of j we have β∈ℛ0∖(ℛ∩ℬr) _C _0 (R _r) and γ∉ℛ0∖(ℛ∩ℬr) _C _0 (R _r), and by construction of (βi)i∈ℕ( _i)_i , it holds that β≻γ _C _C. Let Γℛ0~=γ∣∈(),⊆ℛ0~ _ R_0=\ _C (K),C R_0\ and ℛ0′=ℛ0~∖Γℛ0~R _0= R_0 _ R_0. As ℛ0′R _0 is obtained by removing at least one fact per conflict included in ℛ0~ R_0, it is T-consistent. Also: ℛ0′∖ℛ _0 =(ℛ0~∖Γℛ0~)∖ℛ =( R_0 _ R_0) =(ℛ0∖(ℛ∩ℬr))∖Γℛ0~ =(R_0 (R _r)) _ R_0 =ℛ0∖(ℛ∩ℬr) =R_0 (R _r) as for all γ∈Γℛ0~ _C∈ _ R_0 we have γ∉ℛ0∖(ℛ∩ℬr) _C _0 (R _r), and ℛ∖ℛ0′ _0 =ℛ∖(ℛ0~∖Γℛ0~) =R ( R_0 _ R_0) =ℛ∖((ℛ0∪(ℛ∖ℬr))∖Γℛ0~) =R ((R_0∪(R _r)) _ R_0) =((ℛ∩ℬr)∖ℛ0)∪Γℛ0~. =((R _r) _0)∪ _ R_0. Let α∈ℛ∖ℛ0′α _0: • If α∈(ℛ∩ℬr)∖ℛ0α∈(R _r) _0, by assumption on ℛ0R_0, there exists β∈ℛ0∖(ℛ∩ℬr)=ℛ0′∖ℛβ _0 (R _r)=R _0 such that β≻αβ α. • Otherwise, α∈Γℛ0~α∈ _ R_0 is equal to some γ _C and β=β= _C is such that β∈ℛ0∖(ℛ∩ℬr)=ℛ0′∖ℛβ _0 (R _r)=R _0 (by definition of the β _C) and β≻αβ α (since β≻γ _C _C). Hence ℛ0′R _0 is a global improvement of ℛR, which contradicts ℛ∈(≻)R (K_ ). Therefore ℛ∩ℬr∈(≻ℬrℬr)R _r (K^B_r_ ^B_r). Case =X=C. Let ℛ∈(≻)R (K_ ), i.e., ℛ∈(≻′)R (K_ ) for some ≻′ completion of ≻ . Thus, by the case X=PX=P of the proposition that we have already shown, we have ℛ∩ℬr∈(≻′ℬrℬr)R _r (K_ ^B_r^B_r). As ≻′ℬr ^B_r is a completion of ≻ℬr ^B_r in ℬrK^B_r we directly obtain that ℛ∩ℬr∈(≻ℬrℬr)R _r (K_ ^B_r^B_r). ∎ Proposition 5. For X∈P,G,CX∈\P,G,C\, if ℛ∈(≻ℬrℬr)R (K^B_r_ ^B_r), then there exists ℛ′∈(≻)R (K_ ) such that ℛ=ℛ′∩ℬrR=R _r. Proof. Case =X=P. Let ℛ∈(≻ℬrℬr)R (K_ ^B_r^B_r). Following the proof of Lemma 9 from the extended version of (?), we build some ℛ∗⊆R^* as required by the proposition as follows: let ℛ′=ℛR =R, ′=D =D, and repeat the following steps until ′D is empty: • Choose α∈′α such that β⊁αβ α for all β∈′β . • If ℛ′∪αR ∪\α\ is T-consistent, add α to ℛ′R . • Remove α from ′D . Let ℛ∗R^* be the final ℛ′R . First, note that ℛ⊆ℛ∗∩ℬrR ^* _r by initialization of ℛ∗R^* and definition of ℛR. Also ℛ∗∩ℬr⊆ℛR^* _r as otherwise there would exist α∈(ℛ∗∩ℬr)∖ℛα∈(R^* _r) but then ℛ∪αR∪\α\ would be T-consistent and hence a Pareto improvement of ℛR. Thus ℛ=ℛ∗∩ℬrR=R^* _r. We show that ℛ∗∈(≻)R^* (K_ ). Suppose for a contradiction there exists ℛ0⊆R_0 such that there exists β∈ℛ0∖ℛ∗β _0 ^* such that β≻αβ α for every α∈ℛ∗∖ℛ0α ^* _0. Since β∉ℛ∗β ^*, by construction of ℛ∗R^*, there exists ∈()C (K) such that β∈β and ∖β⊆ℛ′C \β\ when β was chosen in the construction of ℛ∗R^* (otherwise β would have been added to ℛ′R ). Claim 3. For every ∈()C (K) such that β∈β , Min()∩ℛ=∅Min(C) = . Proof of claim. Suppose for a contradiction Min()∩ℛ≠∅Min(C) ≠ , i.e., there exists γ∈∩ℛ⊆∩ℬrγ _r such that γ⊁δγ δ for every δ∈δ . By definition of ℬr=(ℬ)B_r= R_ w(B), ⊆ℬrC _r, and in particular β∈ℬrβ _r. Hence ℛ0∩ℬrR_0 _r is a Pareto improvement of ℛR, which contradicts the assumption ℛ∈(≻ℬrℬr)R (K^B_r_ ^B_r). (end of claim proof) As ℛ0R_0 is T-consistent, ∖β⊈ℛ0C \β\ _0 so there is α0∈∩(ℛ∗∖ℛ0) _0 ∩(R^* _0). Hence β≻α0β _0 (by definition of ℛ0R_0 and β). Since α0 _0 has been chosen after β in the construction of ℛ∗R^* and was already in ℛ′R when β was considered, we necessarily have that α0∈ℛ _0 . Hence, since Min()∩ℛ=∅Min(C) = , there exists α1∈ _1 with α0≻α1 _0 _1. Because β≻α0≻α1β _0 _1, α1 _1 was chosen after β in the construction of ℛ∗R^* thus necessarily α1∈ℛ _1 . Thus we can iterate the argument to create an infinite chain β≻α0≻α1≻…β _0 _1 … with all αi∈ℛ _i . As ≻ is acyclic and D is finite we obtain a contradiction. Therefore ℛ∗∈(≻)R^* (K_ ). Case =X=G. Let ℛ∈(≻ℬrℬr)R (K_ ^B_r^B_r). As we did in the case X=PX=P, let ℛ′=ℛR =R, ′=D =D, and repeat the following steps until ′D is empty: • Choose α∈′α such that β⊁αβ α for all β∈′β . • If ℛ′∪αR ∪\α\ is T-consistent, add α to ℛ′R . • Remove α from ′D . Let ℛ∗R^* be the final ℛ′R . As in the case X=PX=P, we obtain ℛ=ℛ∗∩ℬrR=R^* _r. We show that ℛ∗∈(≻)R^* (K_ ). Suppose for a contradiction there exists ℛ0⊆R_0 such that ℛ0≠ℛ∗R_0 ^* and for every α∈ℛ∗∖ℛ0α ^* _0, there exists β∈ℛ0∖ℛ∗β _0 ^* such that β≻αβ α. Assume for a contradiction that there exists α∈ℛ∖ℛ0α _0. Since ℛ∖ℛ0⊆ℛ∗∖ℛ0R _0 ^* _0, there exists β∈ℛ0∖ℛ∗β _0 ^* such that β≻αβ α. By definition of ≻ , β≻αβ α implies that there exists ∈(≻)C (K_ ) such that α,β⊆\α,β\ . In particular, as α⊁βα β and α∈ℬrα _r we must have ⊆ℬrC _r hence β∈ℬrβ _r. Therefore for every α∈ℛ∖(ℛ0∩ℬr)α (R_0 _r) there exists β∈(ℛ0∩ℬr)∖ℛβ∈(R_0 _r) such that β≻αβ α, which contradicts ℛ∈(≻ℬrℬr)R (K_ ^B_r^B_r). Thus ℛ⊆ℛ0R _0. Hence ℛ=ℛ0∩ℬrR=R_0 _r (otherwise we have a contradiction with ℛR being inclusion-maximal). Let α0 _0 be the first element of (ℛ∗∪ℛ0)∖ℬr(R^* _0) _r considered in the construction of ℛ∗R^*. • If α0∈ℛ∗∖ℛ0 _0 ^* _0 then there exists β∈ℛ0∖ℛ∗β _0 ^* such that β≻α0β _0 but then β∉ℬrβ _r because as we previously showed ℛ∗∩ℬr=ℛ=ℛ0∩ℬrR^* _r=R=R_0 _r thus ℛ0∖ℛ∗⊆∖ℬrR_0 ^* _r. Hence β has been considered before α0 _0 which contradicts our assumption. • If α0∈ℛ0∖ℛ∗ _0 _0 ^* then there exists ∈()C (K) such that α0∈ _0 and ∖α0⊆ℛ=ℛ∗∩ℬrC \ _0\ =R^* _r (otherwise α0 _0 would have been added) but then ∖α0⊆ℛ0∩ℬrC \ _0\ _0 _r as ℛ=ℛ0∩ℬrR=R_0 _r. Hence ⊆ℛ0C _0 and as ∈()C (K) this contradicts the fact that ℛ0R_0 is T-consistent. • Thus α0∈ℛ∗∩ℛ0 _0 ^* _0. Suppose we proved that the i first elements α0,…,αi−1 _0,…, _i-1 of (ℛ∗∪ℛ0)∖ℬr(R^* _0) _r considered in the construction of ℛ∗R^* are in ℛ∗∩ℛ0R^* _0, and let αi∈(ℛ∗∪ℛ0)∖ℬr _i∈(R^* _0) _r be the next one. • If αi∈ℛ∗∖ℛ0 _i ^* _0 then there exists β∈ℛ0∖ℛ∗β _0 ^* such that β≻αiβ _i but then β∉ℬrβ _r has been considered before αi _i which contradicts our assumption. • If αi∈ℛ0∖ℛ∗ _i _0 ^* then there exists ∈()C (K) such that αi∈ _i and ∖αi⊆ℛ∪α0,…,αi−1C \ _i\ ∪\ _0,…, _i-1\ but then (because ℛ=ℛ0∩ℬrR=R_0 _r and α0,…,αi−1⊆ℛ0\ _0,…, _i-1\ _0) we have ⊆ℛ0C _0. As ∈()C (K) this contradicts the fact that ℛ0R_0 is T-consistent. • Thus αi∈ℛ∗∩ℛ0 _i ^* _0. Therefore we have recursively that ℛ∗=ℛ0R^*=R_0 which contradicts our assumption. Case =X=C. Let ℛ∈(≻ℬrℬr)R (K_ ^B_r^B_r). There exists a completion ≻′ℬr ^B_r of ≻ℬr ^B_r in ℬrK^B_r such that ℛ∈(≻′ℬrℬr)R (K_ ^B_r^B_r). Let ≻′ be a completion of ≻ in K that agrees with ≻′ℬr ^B_r on ℬrK^B_r. We showed that there exists ℛ′∈(≻′)R (K_ ) such that ℛ=ℛ′∩ℬrR=R _r. Since ≻′ is a completion of ≻ in K, we obtain ℛ′∈(≻)R (K_ ). ∎ Proof of Theorem 4 Proposition 6 and Proposition 7 below correspond to the first and second item of Theorem 4, respectively. Here ℬr=(ℬ)B_r= R_ s(B), is the set of facts reachable from ℬB w.r.t. ‘strong’ reachability. Proposition 6. For X∈P,G,CX∈\P,G,C\, if ℛ∈(≻)R (K_ ), then ℛ∩ℬr∈(≻ℬrℬr)R _r (K^B_r_ ^B_r). 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 ℬr=(ℬ)B_r= R_ w(B) is used, now use ℬr=(ℬ)B_r= R_ s(B). ∎ Proposition 7. For X∈P,CX∈\P,C\, if ℛ∈(≻ℬrℬr)R (K^B_r_ ^B_r), then there exists ℛ′∈(≻)R (K_ ) such that ℛ=ℛ′∩ℬrR=R _r. Proof. Case =X=P. The proof is the same as the one for Proposition 5 in case X=PX=P, except that the proof of Claim 3, which is the only place where the fact that ℬr=(ℬ)B_r= R_ w(B) is used, now use ℬr=(ℬ)B_r= R_ s(B). Case =X=C. Same proof as Proposition 5. ∎ Appendix B Alternative ASP(Q) Encoding for G-AR For G-AR semantics, we considered the following alternative ASP(Q) encoding. ΠG 2= _AR^G\ 2= ∀stΠℎΠ∃stΠ:CARG 2 ∀^st _ReachAll _Rep∃^st _PartGImp:C_AR^G\ 2 with CARG 2= C_AR^G\ 2= Π _SatIfCause :-,_. \\ :\!-\ not~sat,not~global\_improvement.\ and Π _PartGImp is obtained from Π _GImp by removing the constraint (:-\ :\!-\ _ not~global\_improvement). This second program for G-AR, ΠG 2 _AR^G\ 2, intuitively checks whether for every ℛ∈()R (K), there exists some ℬ⊆B such that either ℛR contains some cause for q(a→)q( a) or ℬB is a global improvement for ℛR, so that ℛ∈(≻)R (K_ ) implies (ℛ,)⊧q(a→)(R,T) q( a). Specifically, if we let P1=Πℎ∪ΠP_1= _ReachAll∪ _Rep and P2=ΠP_2= _PartGImp, so that ΠG 2=∀stP1∃stP2:CARG 2 _AR^G\ 2=∀^stP_1∃^stP_2:C_AR^G\ 2, we know that ΠG 2 _AR^G\ 2 is coherent if for every M1∈AS(P1)M_1∈ AS(P_1), ∃stP2∪P1(M1):CARG 2∃^stP_2 _P_1(M_1):C_AR^G\ 2 is coherent, i.e., if for P2′=P2∪P1(M1)P _2=P_2 _P_1(M_1), there exists M2∈AS(P2′)M_2∈ AS(P _2) such that CARG 2∪P2′(M2)C_AR^G\ 2 _P _2(M_2) is coherent. We have seen that answer sets of P1P_1 correspond to repairs, and that given a repair ℛR, P2P_2 guesses a T-consistent ℬB and derives _ global\_improvement iff ℬB is a global improvement of ℛR, and the part Π _SatIfCause of the constraint CARG 2C_AR^G\ 2 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 ≻⊧ARGq(a→)K_ _ AR^Gq( a). Proposition 8. ≻⊧ARGq(a→)K_ _ AR^Gq( a) iff ΠG 2 _AR^G\ 2 is coherent. Appendix C Experimental Setting This section recalls statistics on the benchmarks we used in our experiments (cf. (?; ?; ?)). 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 (?). Priority Relations For the binary conflicts case, we use two priority relations from the ORBITS benchmark: ≻ss ^s is score-structured and was built using 5 levels of priority to which facts were randomly assigned, and ≻ns ^ns was built by considering each (binary) conflict and assigning a random preference between the facts with a probability 0.80.8, except if doing so created a cycle, then checking that ≻ns ^ns was indeed not score-structured (?). These priority relations are such that ≻ss ^s assigns a priority between the two facts of about 40% of the conflicts and this proportion is about 30% for ≻ns ^ns. For the non-binary case, we use one priority relation ≻nb ^nb resulting from the set of preference rules Σ1a∪Σ2a∪Σ3a _1^a∪ _2^a∪ _3^a and “going down” cycle resolution strategy defined by ? (?). 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 (?, 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 ^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 ^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 non-binary conflicts and one priority relation (cf. Table 16). # facts # facts in conflicts % facts in conflicts # conflicts u1c1 75,724 2,373 3 2,314 u1c5 75,951 6,412 8 8,476 u1c10 76,201 10,891 14 14,261 u1c20 76,821 20,175 26 28,232 u1c30 77,447 26,086 34 45,484 u1c50 78,593 34,814 44 81,304 u5c1 463,691 12,191 3 11,984 u5c5 465,157 45,906 10 53,398 u5c10 466,919 83,263 18 109,453 u5c20 470,674 137,836 29 231,771 u5c30 474,368 172,245 36 345,461 u5c50 481,400 221,900 46 583,714 u20c1 1,983,493 69,597 4 73,212 u20c5 1,989,788 253,141 13 335,194 u20c10 1,997,445 408,398 20 662,725 u20c20 2,013,048 610,271 30 1,314,991 u20c30 2,028,069 748,664 37 1,933,956 u20c50 2,056,957 946,819 46 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 85 10 137 3 538 195 507 50 1525 u1c5 85 10 137 3 544 195 508 50 1532 u1c10 85 10 138 6 551 195 508 50 1543 u1c20 85 10 138 6 564 195 508 50 1556 u1c30 87 10 142 6 585 195 508 50 1583 u1c50 87 10 149 7 628 195 515 50 1641 u5c1 85 10 137 20 3366 1112 3183 50 7963 u5c5 85 10 137 20 3408 1112 3188 50 8010 u5c10 85 10 138 23 3472 1112 3190 50 8080 u5c20 85 10 138 24 3584 1112 3203 50 8206 Table 8: Number of potential answers. Appendix D Experimental Results We present here additional results from our experimental evaluation. Tractable Approximations Tables 11, 11 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 14, 14 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 Figure 5 shows how ΠG _AR^G and ΠG 2 _AR^G\ 2 compare. We choose to focus on ΠG _AR^G 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,CX∈\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)(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. u1c1 u1c5 u1c10 u1c20 u1c30 u1c50 u5c1 u5c5 u5c10 u5c20 ∩S _S 73351 69539 65310 56646 51361 43779 451500 419251 383656 332838 Γ(∅)∖∩S ( ) _S 921 1705 3021 5391 6105 7289 3740 13149 22920 32449 ∖∩SG _S 2286 6009 10134 18507 23339 29945 11704 43435 78368 126482 % G not Γ(∅) ( ) 1.8% 5.7% 9.4% 17.5% 23.1% 30.7% 1.7% 6.5% 12% 20.5% Table 9: Number of facts in ∩S=⋂ℛ∈()ℛ _S= _R (K)R, Γ(∅) ( ) (trivially P-IAR), and the grounded repair G, in ≻ns ^ns case. u1c1 u1c5 u1c10 u1c20 u1c30 u1c50 u5c1 u5c5 u5c10 u5c20 ∩S _S 73351 69539 65310 56646 51361 43779 451500 419251 383656 332838 Γ(∅)∖∩S ( ) _S 1225 2193 3981 5988 6851 8493 5354 16022 27965 40829 ∖∩SG _S 2106 4256 7831 13020 15235 17872 10036 33370 59103 90164 % G not Γ(∅) ( ) 1.2% 2.8% 5.3% 10.1% 12.6% 15.2% 1% 3.8% 7% 11.7% Table 10: Number of facts in ∩S=⋂ℛ∈()ℛ _S= _R (K)R, Γ(∅) ( ) (trivially P-IAR), and the grounded repair G, in ≻ss ^s case. u1c1 u1c5 u1c10 u1c20 u1c30 u1c50 u5c1 u5c5 ∩S _S 73131 69327 65098 56439 51165 43612 451280 419039 Γ(∅)∖∩S ( ) _S 989 2561 4364 7668 8883 10777 5994 21399 ∖∩SG _S 2399 6089 10066 18279 22916 29458 11684 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=⋂ℛ∈()ℛ _S= _R (K)R, Γ(∅) ( ) (trivially P-IAR), and the grounded repair G, in ≻nb ^nb case. Triv GR Step 1 Step 2 Step 3 u1c1 1465 1524 59 - - u1c5 1366 1525 159 - - u1c10 1186 1527 341 0 - u1c20 937 1521 555 29 - u1c30 754 1518 730 34 - u1c50 625 1500 800 75 0 u5c1 7637 7953 316 - - u5c5 6958 7948 990 0 - u5c10 6069 7964 1894 1 - u5c20 4947 7982 2972 62 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(∅) ^i+1( ) minus those w.r.t. Γi(∅) ^i( ). “-” indicates that this step was not needed to compute the grounded repair. Case of ≻ns ^ns. Triv GR Step 1 Step 2 u1c1 1477 1525 48 - u1c5 1385 1450 65 - u1c10 1215 1447 232 - u1c20 931 1305 374 0 u1c30 731 1030 299 0 u1c50 618 770 152 0 u5c1 7706 7901 195 - u5c5 7044 7635 591 - u5c10 6213 7300 1087 0 u5c20 5169 6649 1480 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(∅) ^i+1( ) minus those w.r.t. Γi(∅) ^i( ). “-” indicates that this step was not needed to compute the grounded repair. Case of ≻ss ^s. Triv GR Step 1 Step 2 u1c1 1447 1523 75 1 u1c5 1369 1524 155 0 u1c10 1167 1526 359 0 u1c20 940 1511 571 0 u1c30 789 1515 726 0 u1c50 680 1503 817 6 u5c1 7708 7946 237 1 u5c5 7209 7951 742 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(∅) ^i+1( ) minus those w.r.t. Γi(∅) ^i( ). “-” indicates that this step was not needed to compute the grounded repair. Case of ≻nb ^nb. ∖∩SG _S Γ(∅)∖∩S ( ) _S u1c1 ≻ns ^ns 2.10 0.16 u1c5 ≻ns ^ns 6.63 0.33 u1c10 ≻ns ^ns 9.25 0.51 u1c20 ≻ns ^ns 21.22 1.39 u1c30 ≻ns ^ns 47.65 2.43 u1c50 ≻ns ^ns 126.39 3.80 u5c1 ≻ns ^ns 10.70 0.68 u5c5 ≻ns ^ns 54.50 2.69 u5c10 ≻ns ^ns 71.88 4.08 u5c20 ≻ns ^ns 240.34 7.11 u5c30 ≻ns ^ns 376.27 10.53 u5c50 ≻ns ^ns MEMOUT 14.69 u20c1 ≻ns ^ns 47.05 2.39 u20c5 ≻ns ^ns 219.98 9.88 u20c10 ≻ns ^ns 441.24 18.09 u20c20 ≻ns ^ns MEMOUT 33.13 u20c30 ≻ns ^ns MEMOUT 50.23 u20c50 ≻ns ^ns MEMOUT 80.3 u1c1 ≻ss ^s 1.58 0.16 u1c5 ≻ss ^s 4.62 0.50 u1c10 ≻ss ^s 7.30 0.69 u1c20 ≻ss ^s 14.92 1.26 u1c30 ≻ss ^s 32.41 2.40 u1c50 ≻ss ^s 61.80 3.53 u5c1 ≻ss ^s 7.85 0.68 u5c5 ≻ss ^s 27.04 2.65 u5c10 ≻ss ^s 52.14 4.33 u5c20 ≻ss ^s 129.31 7.12 u5c30 ≻ss ^s 201.37 10.60 u5c50 ≻ss ^s 304.11 14.55 u20c1 ≻ss ^s 23.75 2.41 u20c5 ≻ss ^s 106.77 9.47 u20c10 ≻ss ^s 341.53 18.24 u20c20 ≻ss ^s MEMOUT 36.07 u20c30 ≻ss ^s MEMOUT 51.29 u20c50 ≻ss ^s MEMOUT 80.31 u1c1 ≻nb ^nb 1.19 0.14 u1c5 ≻nb ^nb 4.03 0.66 u1c10 ≻nb ^nb 6.82 1.02 u1c20 ≻nb ^nb 13.81 1.50 u1c30 ≻nb ^nb 25.34 2.33 u1c50 ≻nb ^nb 53.35 3.97 u5c1 ≻nb ^nb 4.55 0.83 u5c5 ≻nb ^nb 23.03 2.89 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. 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→)q( a), dataset uXcY, and priority relation, if q(a→)q( a) holds under X-AR. (left) X=P, (middle) X=C, (right) X=G 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→)q( a), dataset uXcY, and priority relation, if q(a→)q( a) holds under X-brave. (left) X=P, (middle) X=C, (right) X=G Figure 5: Comparison of ΠG _AR^G (‘exists_forall_G-AR’) and ΠG 2 _AR^G\ 2 (‘forall_exists_G-AR’), both with localization and specific encoding for binary conflicts. (left) Time for ΠG 2 _AR^G\ 2 (y-axis) vs time for ΠG _AR^G (x-axis) to decide for each q(a→)q( a), dataset u1cY (binary conflict cases), and priority relation, if q(a→)q( a) holds under G-AR. (right) Time (in seconds, y-axis) to decide for each q(a→)q( a), dataset uXcY (binary conflict cases), and priority relation, whether q(a→)q( a) holds under G-AR using ΠG _AR^G and ΠG 2 _AR^G\ 2, with instances sorted by increasing solving time along the x-axis (i.e., a point (i,j)(i,j) indicates that i instances could be solved within j seconds). (a) u1c1 ≻ns ^ns (b) u1c1 ≻ss ^s (c) u5c1 ≻ns ^ns (d) u5c1 ≻ss ^s (e) u1c5 ≻ns ^ns (f) u1c5 ≻ss ^s (g) u5c5 ≻ns ^ns (h) u5c5 ≻ss ^s (i) u1c10 ≻ns ^ns (j) u1c10 ≻ss ^s (k) u5c10 ≻ns ^ns (l) u5c10 ≻ss ^s (m) u1c20 ≻ns ^ns (n) u1c20 ≻ss ^s (o) u5c20 ≻ns ^ns (p) u5c20 ≻ss ^s (q) u1c30 ≻ns ^ns (r) u1c30 ≻ss ^s (s) u5c30 ≻ns ^ns (t) u5c30 ≻ss ^s (u) u1c50 ≻ns ^ns (v) u1c50 ≻ss ^s (w) u5c50 ≻ns ^ns (x) u5c50 ≻ss ^s Figure 6: Time (in seconds) to decide for each q(a→)q( a) whether q(a→)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)(i,j) indicates that i instances could be solved within j seconds). Empty plots: in the case of u1c1 ≻ss ^s, 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). (a) u1c1 ≻nb ^nb (b) u5c1 ≻nb ^nb (c) u1c5 ≻nb ^nb (d) u5c5 ≻nb ^nb (e) u1c10 ≻nb ^nb (f) u1c20 ≻nb ^nb (g) u1c30 ≻nb ^nb (h) u1c50 ≻nb ^nb Figure 7: Time (in seconds) to decide for each q(a→)q( a) whether q(a→)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)(i,j) indicates that i instances could be solved within j seconds). Triv GR∖ P-AR∖ G-AR∖ C-AR∖ P-brave∖ G-brave∖ C-brave∖ u1c1 ≻ns ^ns 1465 59 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) u1c5 ≻ns ^ns 1366 159 0 (0) 0 (0) 0 (0) 2 (0) 2 (0) 2 (0) u1c10 ≻ns ^ns 1186 341 0 (0) 0 (0) 0 (0) 6 (0) 6 (0) 6 (0) u1c20 ≻ns ^ns 937 584 1 (0) 0 (10) 1 (0) 17 (0) 16 (6) 17 (0) u1c30 ≻ns ^ns 754 764 6 (0) 0 (30) 6 (0) 38 (0) 19 (30) 38 (0) u1c50 ≻ns ^ns 625 875 26 (0) 9 (82) 20 (56) 79 (0) 28 (81) 38 (40) u5c1 ≻ns ^ns 7637 316 0 (0) 0 (0) 0 (0) 2 (0) 2 (0) 2 (0) u5c5 ≻ns ^ns 6958 990 22 (0) 21 (2) 22 (0) 31 (0) 30 (2) 31 (0) u5c10 ≻ns ^ns 6069 1895 22 (0) 8 (27) 22 (0) 46 (0) 34 (22) 46 (0) u5c20 ≻ns ^ns 4947 3035 37 (0) 6 (96) 32 (32) 91 (0) 51 (151) 83 (18) u1c1 ≻ss ^s 1477 48 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) u1c5 ≻ss ^s 1385 65 0 (0) 0 (0) 0 (0) 81 (0) 81 (0) 81 (0) u1c10 ≻ss ^s 1215 232 0 (0) 0 (0) 0 (0) 92 (0) 92 (0) 92 (0) u1c20 ≻ss ^s 931 374 0 (0) 0 (27) 0 (0) 238 (0) 228 (10) 238 (0) u1c30 ≻ss ^s 731 299 0 (0) 0 (73) 0 (0) 519 (0) 475 (46) 519 (0) u1c50 ≻ss ^s 618 152 0 (0) 0 (434) 0 (0) 807 (0) 512 (310) 807 (0) u5c1 ≻ss ^s 7706 195 0 (0) 0 (0) 0 (0) 55 (0) 55 (0) 55 (0) u5c5 ≻ss ^s 7044 591 1 (0) 1 (0) 1 (0) 348 (0) 348 (0) 348 (0) u5c10 ≻ss ^s 6213 1087 1 (0) 1 (73) 1 (0) 716 (0) 684 (38) 716 (0) u5c20 ≻ss ^s 5169 1480 2 (0) 2 (468) 2 (0) 1437 (0) 992 (533) 1437 (0) u1c1 ≻nb ^nb 1447 76 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) 0 (0) u1c5 ≻nb ^nb 1369 155 0 (0) 0 (1) 0 (0) 1 (0) 0 (1) 1 (0) u1c10 ≻nb ^nb 1167 359 0 (0) 0 (1) 0 (0) 1 (0) 0 (1) 1 (0) u1c20 ≻nb ^nb 940 571 0 (0) 0 (2) 0 (0) 1 (0) 0 (2) 1 (0) u1c30 ≻nb ^nb 789 726 0 (0) 0 (10) 0 (0) 6 (0) 5 (5) 6 (0) u1c50 ≻nb ^nb 680 823 0 (0) 0 (43) 0 (0) 20 (0) 13 (37) 20 (0) u5c1 ≻nb ^nb 7708 238 0 (0) 0 (0) 0 (0) 2 (0) 2 (0) 2 (0) u5c5 ≻nb ^nb 7209 742 0 (0) 0 (1) 0 (0) 3 (0) 2 (1) 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 ^s), 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.