Using ASP(Q) to Handle Inconsistent Prioritized Data

Camille Bourgaux; Giuseppe Mazzotta; Meghyn Bienvenu; Robin Jean

arxiv: 2604.21603 · v2 · submitted 2026-04-23 · 💻 cs.LO · cs.AI· cs.DB

Using ASP(Q) to Handle Inconsistent Prioritized Data

Meghyn Bienvenu , Camille Bourgaux , Robin Jean , Giuseppe Mazzotta This is my paper

Pith reviewed 2026-05-08 13:51 UTC · model grok-4.3

classification 💻 cs.LO cs.AIcs.DB

keywords inconsistency-tolerant queryingprioritized dataanswer set programmingASP(Q)optimal repairsrepair semanticsgrounded semanticsinconsistent databases

0 comments

The pith

ASP(Q) encodings let systems compute query answers from inconsistent data by selecting optimal repairs according to fact priorities.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows how answer set programming extended with quantifiers can manage queries over data containing conflicts when a priority order on facts is available. It defines three optimal repair notions—Pareto, global, and completion—and adapts the AR, brave, and IAR semantics to return only answers supported by these preferred repairs. The encodings keep query answering inside the first or second level of the polynomial hierarchy for many logical theories. Experiments demonstrate that globally-optimal repair semantics can now be computed in practice for the first time, and the grounded semantics supplies a fast under-approximation that works across all three optimal-repair variants.

Core claim

We encode the computation of answers under Pareto-optimal, globally-optimal, and completion-optimal repair semantics into ASP(Q) programs, thereby obtaining the first implementations of the globally-optimal repair semantics and of the grounded semantics, a polynomial-time under-approximation of all optimal-repair variants, while preserving the known complexity bounds for the underlying logical theories.

What carries the argument

ASP(Q) programs that translate a given priority relation on conflicting facts into constraints selecting only Pareto-, globally-, or completion-optimal repairs and then evaluate adapted AR, brave, and IAR queries over those repairs.

Load-bearing premise

A priority relation on facts can be used to define the three optimal repairs so that ASP(Q) programs correctly compute the corresponding query answers without exceeding the stated polynomial-hierarchy complexity.

What would settle it

An example database, priority relation, and query for which the ASP(Q) program returns an answer that no optimal repair supports, or whose running time exceeds the polynomial-hierarchy bound claimed for the semantics.

Figures

Figures reproduced from arXiv: 2604.21603 by Camille Bourgaux, Giuseppe Mazzotta, Meghyn Bienvenu, Robin Jean.

**Figure 1.** Figure 1: Time (in seconds, y-axis) to decide for each view at source ↗

**Figure 2.** Figure 2: Time for the generic encoding (y-axis) vs time for the en view at source ↗

**Figure 3.** Figure 3: Time for the generic encoding (y-axis) vs time for the encoding specific for binary conflicts (x-axis), both with localization, to view at source ↗

**Figure 4.** Figure 4: Time for the generic encoding (y-axis) vs time for the encoding specific for binary conflicts (x-axis), both with localization, to view at source ↗

**Figure 5.** Figure 5: Comparison of Π G AR (‘exists forall G-AR’) and Π G 2 AR (‘forall exists G-AR’), both with localization and specific encoding for binary conflicts. (left) Time for Π G 2 AR (y-axis) vs time for Π G AR (x-axis) to decide for each q(⃗a), dataset u1cY (binary conflict cases), and priority relation, if q(⃗a) holds under G-AR. (right) Time (in seconds, y-axis) to decide for each q(⃗a), dataset uXcY (binary conf… view at source ↗

**Figure 6.** 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 exp… view at source ↗

**Figure 7.** 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) view at source ↗

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper delivers the first implementations of globally-optimal repair-based semantics and the grounded semantics for prioritized inconsistency-tolerant querying using ASP(Q).

read the letter

This paper delivers the first implementations of globally-optimal repair-based semantics and the grounded semantics for inconsistency-tolerant querying of prioritized data using ASP(Q). The authors encode Pareto-, globally-, and completion-optimal repairs, then apply them to the AR, brave, and IAR query variants. They also give complexity results placing the problems in the first or second level of the polynomial hierarchy for a large class of theories, plus experiments that test feasibility and compare the semantics and approximations in practice. The grounded semantics is presented as a tractable under-approximation of the optimal ones. What the paper does well is closing the implementation gap for the globally-optimal case and showing through experiments how different choices affect both answers and runtime. The ASP(Q) approach fits the quantified preference checks naturally. The main soft spot is that the encodings must match the optimality definitions exactly to preserve both correctness and the stated complexity bounds; any mismatch in how priorities are compared could admit spurious repairs or alter hardness. The experiments illustrate the points but remain preliminary and would benefit from larger instances or more varied priority relations. This work is aimed at researchers in knowledge representation and databases who need practical tools for prioritized repairs rather than pure theory. Readers looking for encodings or comparisons of semantics will find usable material. I would bring it to a reading group to go over the programs. It is worth citing if one is building similar systems. It deserves peer review because the implementations and supporting results are concrete enough to warrant referee scrutiny.

Referee Report

1 major / 1 minor

Summary. The paper explores the use of answer set programming (ASP) and its extension with quantifiers, ASP(Q), for inconsistency-tolerant querying of prioritized data. It defines three notions of optimal repairs (Pareto-, globally-, and completion-optimal) induced by a priority relation on conflicting facts, develops corresponding variants of the AR, brave, and IAR semantics, states that query answering lies in the first or second level of the polynomial hierarchy for a large class of theories, presents the first implementations of globally-optimal repair-based semantics and of the grounded semantics (a tractable under-approximation), and reports experimental results on feasibility and the impact of different semantics and encodings.

Significance. If the ASP(Q) encodings are shown to be faithful to the semantic definitions, the work is significant for supplying the first implementations of globally-optimal and grounded repair semantics. This bridges theoretical inconsistency-tolerant reasoning with practical computation, enabling prioritized data repair in logic-based systems and providing a tractable approximation that can be used across multiple optimality criteria.

major comments (1)

The load-bearing step is the claim that the ASP(Q) programs for Pareto-, globally-, and completion-optimal repairs (and their AR/brave/IAR variants) produce answer sets that correspond exactly to the repairs satisfying the optimality criteria. The stated polynomial-hierarchy complexity bounds hold only if these encodings introduce no extra quantifier alternations or spurious models; an explicit argument or proof of semantic equivalence between the logical optimality definitions and the ASP(Q) rules is required to support both the complexity results and the novelty of the implementations.

minor comments (1)

The abstract refers to an experimental evaluation but provides no information on the datasets, instance sizes, or performance metrics used; including these details would improve the clarity of the feasibility claims.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive assessment of our work and for the constructive major comment. We address the point below and will revise the manuscript to strengthen the presentation of the encodings.

read point-by-point responses

Referee: The load-bearing step is the claim that the ASP(Q) programs for Pareto-, globally-, and completion-optimal repairs (and their AR/brave/IAR variants) produce answer sets that correspond exactly to the repairs satisfying the optimality criteria. The stated polynomial-hierarchy complexity bounds hold only if these encodings introduce no extra quantifier alternations or spurious models; an explicit argument or proof of semantic equivalence between the logical optimality definitions and the ASP(Q) rules is required to support both the complexity results and the novelty of the implementations.

Authors: We agree that establishing semantic equivalence is essential for the validity of the complexity results and the correctness of the implementations. The current manuscript defines the optimality criteria, presents the ASP(Q) encodings, and provides informal arguments that the answer sets correspond to the optimal repairs. However, these arguments stop short of a complete formal proof. In the revised version we will add a dedicated subsection (or appendix) containing a formal proof of equivalence for the Pareto-, globally-, and completion-optimal repairs under the AR, brave, and IAR semantics. The proof will show that every answer set of the ASP(Q) program corresponds to an optimal repair and vice versa, and that no additional quantifier alternations or spurious models are introduced beyond those already accounted for in the complexity analysis. revision: yes

Circularity Check

0 steps flagged

No circularity: new ASP(Q) encodings implement independent semantic definitions

full rationale

The paper defines Pareto-, globally-, and completion-optimal repairs from a given priority relation on facts, then supplies ASP(Q) programs whose answer sets are claimed to correspond to those repairs under AR/brave/IAR variants. These encodings are presented as novel implementations that preserve the stated PH complexity bounds; no equation or result is obtained by fitting parameters to data and relabeling the fit as a prediction, nor does any central claim reduce to a self-citation whose content is itself unverified. The work is self-contained against external benchmarks (prior repair semantics and ASP(Q) solvers) and introduces the first concrete programs for globally-optimal and grounded semantics.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard background results in answer-set programming and inconsistency-tolerant querying; no new free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)

domain assumption Query answering under the defined optimal-repair semantics lies in the first or second level of the polynomial hierarchy for a large class of logical theories.
Invoked to bound the complexity of the new semantics.

pith-pipeline@v0.9.0 · 5453 in / 1288 out tokens · 48260 ms · 2026-05-08T13:51:12.048353+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

6 extracted references · 6 canonical work pages

[1]

Bourgaux, C

A short survey on inconsistency han- dling in ontology-mediated query answering.K ¨unstliche In- telligenz34(4):443–451. Bourgaux, C. 2016.Inconsistency Handling in Ontology- Mediated Query Answering. (Gestion des incoh´erences pour l’acc`es aux donn ´ees en pr ´esence d’ontologies). Ph.D. Dis- sertation, University of Paris-Saclay, France. Bourgaux, C

work page 2016
[2]

Ceri, S.; Gottlob, G.; and Tanca, L

Tractable reasoning and efficient query answering in description logics: The DL-Lite family.Jour- nal of Automated Reasoning (JAR)39(3):385–429. Ceri, S.; Gottlob, G.; and Tanca, L. 1990.Logic Program- ming and Databases. Surveys in computer science. Dixit, A. A., and Kolaitis, P. G

work page 1990
[3]

Gebser, M.; Kaminski, R.; and Schaub, T

Multi-shot ASP solving with clingo.CoRR abs/1705.09811. Gebser, M.; Kaminski, R.; and Schaub, T

work page arXiv
[4]

A Proofs for Section 3 Proposition 1.K ≻ |=G brave q(⃗ a)iffΠG brave is coherent

Prioritized repairing and consistent query answering in rela- tional databases.Annals of Mathematics and Artificial Intel- ligence (AMAI)64(2-3):209–246. A Proofs for Section 3 Proposition 1.K ≻ |=G brave q(⃗ a)iffΠG brave is coherent. Proof Sketch.(⇐)Assume thatΠ G brave has a quantified an- swer setM. SinceM∈AS(P 1), the setRthat contains all facts whos...

work page 2012
[5]

SinceC ∩(R \ B r)̸=∅, it follows thatM in(C)⊆ R \ B r

Claim 2.For everyC ∈Conf(K)such thatC ⊆ fR0, M in(C)⊆ R \ B r Proof of claim.By definition ofB r =R w(B), if there was α∈M in(C)such thatα∈ B r, it would hold thatC ⊆ B r. SinceC ∩(R \ B r)̸=∅, it follows thatM in(C)⊆ R \ B r. (end of claim proof) We define(β i)i∈N ∈ C N withβ 0 ∈ C ∩(R 0 \(R ∩ B r)) (suchβ 0 exists sinceC ∩(R 0 \(R∩B r))̸=∅) and fori∈N: ...

work page 2022
[6]

going down

B Alternative ASP(Q) Encoding for G-AR For G-AR semantics, we considered the following alterna- tive ASP(Q) encoding. ΠG2 AR =∀stΠReachAllΠRep∃stΠPartGImp :C G2 AR withC G2 AR =Π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,Π G2 AR, in...

work page 2016

[1] [1]

Bourgaux, C

A short survey on inconsistency han- dling in ontology-mediated query answering.K ¨unstliche In- telligenz34(4):443–451. Bourgaux, C. 2016.Inconsistency Handling in Ontology- Mediated Query Answering. (Gestion des incoh´erences pour l’acc`es aux donn ´ees en pr ´esence d’ontologies). Ph.D. Dis- sertation, University of Paris-Saclay, France. Bourgaux, C

work page 2016

[2] [2]

Ceri, S.; Gottlob, G.; and Tanca, L

Tractable reasoning and efficient query answering in description logics: The DL-Lite family.Jour- nal of Automated Reasoning (JAR)39(3):385–429. Ceri, S.; Gottlob, G.; and Tanca, L. 1990.Logic Program- ming and Databases. Surveys in computer science. Dixit, A. A., and Kolaitis, P. G

work page 1990

[3] [3]

Gebser, M.; Kaminski, R.; and Schaub, T

Multi-shot ASP solving with clingo.CoRR abs/1705.09811. Gebser, M.; Kaminski, R.; and Schaub, T

work page arXiv

[4] [4]

A Proofs for Section 3 Proposition 1.K ≻ |=G brave q(⃗ a)iffΠG brave is coherent

Prioritized repairing and consistent query answering in rela- tional databases.Annals of Mathematics and Artificial Intel- ligence (AMAI)64(2-3):209–246. A Proofs for Section 3 Proposition 1.K ≻ |=G brave q(⃗ a)iffΠG brave is coherent. Proof Sketch.(⇐)Assume thatΠ G brave has a quantified an- swer setM. SinceM∈AS(P 1), the setRthat contains all facts whos...

work page 2012

[5] [5]

SinceC ∩(R \ B r)̸=∅, it follows thatM in(C)⊆ R \ B r

Claim 2.For everyC ∈Conf(K)such thatC ⊆ fR0, M in(C)⊆ R \ B r Proof of claim.By definition ofB r =R w(B), if there was α∈M in(C)such thatα∈ B r, it would hold thatC ⊆ B r. SinceC ∩(R \ B r)̸=∅, it follows thatM in(C)⊆ R \ B r. (end of claim proof) We define(β i)i∈N ∈ C N withβ 0 ∈ C ∩(R 0 \(R ∩ B r)) (suchβ 0 exists sinceC ∩(R 0 \(R∩B r))̸=∅) and fori∈N: ...

work page 2022

[6] [6]

going down

B Alternative ASP(Q) Encoding for G-AR For G-AR semantics, we considered the following alterna- tive ASP(Q) encoding. ΠG2 AR =∀stΠReachAllΠRep∃stΠPartGImp :C G2 AR withC G2 AR =Π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,Π G2 AR, in...

work page 2016