💻 computer science

Using ASP(Q) to Handle Inconsistent Prioritized Data

This paper introduces and implements an ASP(Q)-based framework for inconsistency-tolerant querying of prioritized data using Pareto-, global-, and completion-optimal repairs, providing the first systems for globally-optimal and grounded semantics while analyzing their computational complexity and practical feasibility.

Original authors: Meghyn Bienvenu, Camille Bourgaux, Robin Jean, Giuseppe Mazzotta

Published 2026-04-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Meghyn Bienvenu, Camille Bourgaux, Robin Jean, Giuseppe Mazzotta

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the manager of a busy restaurant kitchen. You have a list of orders (your data) and a set of strict rules for how meals must be prepared (your logical theory).

Usually, everything runs smoothly. But sometimes, chaos strikes. Maybe a customer ordered a steak that is both "well-done" and "rare" at the same time, or perhaps two chefs are trying to use the same pan simultaneously. Your kitchen is now inconsistent. You can't serve the meal as is; you have to make a choice to fix the problem.

This paper is about how to make the best possible choices when your data is messy, using a powerful new tool called ASP(Q).

The Problem: Too Many Ways to Fix a Mess

When your kitchen has a conflict, you have to throw out some orders or change some instructions to make everything work again. In computer science, these "fixed" versions of your data are called Repairs.

Usually, there isn't just one way to fix the mess. There are dozens.

The "Brave" Chef: "I'll just pick any fix that works and serve that." (Optimistic, but risky).
The "Cautious" Chef: "I'll only serve what every possible fix agrees on." (Very safe, but you might serve very little food).
The "Average" Chef: "I'll serve what works in most fixes." (A middle ground).

But what if some ingredients are more important than others? What if the customer's "Rare" preference is more important than the "Well-done" one? This is where Priorities come in. We want to find the "Best" repair, not just a repair.

The Three Levels of "Best"

The paper focuses on three specific ways to define "Best," based on how strictly we apply the priority rules:

Pareto-Optimal (The "Local Hero"): You can't improve the meal without making something else worse. It's a good fix, but maybe not the perfect one.
Completion-Optimal (The "Tie-Breaker"): You assume that if the rules don't say which ingredient is better, you just pick one arbitrarily to make a decision.
Globally-Optimal (The "Grandmaster"): This is the gold standard. It looks at the entire kitchen at once. It asks: "Is there any other way to fix this that is strictly better according to our priorities?" If the answer is no, you have the Global Optimal repair.

The Catch: Finding the "Grandmaster" (Global Optimal) fix is incredibly hard for computers. It's like trying to solve a Rubik's cube while blindfolded, while someone else is shaking the table. Previous computers could only handle the "Local Hero" and "Tie-Breaker" fixes. They gave up on the "Grandmaster" because it was too complex.

The Solution: A New Tool (ASP(Q))

The authors built a new system using a programming language called ASP(Q).

Think of standard programming as a single person trying to solve a puzzle. ASP(Q) is like having a team of detectives working in a specific hierarchy:

Detective A says: "I found a possible fix."
Detective B (the boss) says: "Okay, but for every single way Detective A could have solved it, is there a better way?"
Detective C says: "And for every single way Detective B found, is there a better way?"

This "quantifier" power (asking "for all" or "there exists") allows the computer to handle the massive complexity of the Global Optimal repair without getting lost. It's like upgrading from a bicycle to a high-speed train to cross a mountain.

The "Grounded" Shortcut

Even with this super-tool, checking every single possibility takes too long for huge datasets. So, the authors also tested a clever shortcut called Grounded Semantics.

Imagine you are trying to find the safest path through a minefield.

The Full Check: You walk every single possible path to see which ones are safe. (Slow, but thorough).
The Grounded Shortcut: You look at the map and say, "Okay, these specific spots are definitely safe because no mines are pointing at them." You start there, then see what becomes safe because of that, and keep going.

The paper discovered something surprising: The shortcut works almost as well as the full check! In many cases, the "Grounded" answer was exactly the same as the complex "Global Optimal" answer, but it was computed in seconds instead of hours.

What They Found (The Results)

The team ran thousands of experiments on fake data (like a simulated database of millions of records).

The "Grandmaster" is finally possible: They successfully implemented the Global Optimal repair for the first time. It's slower than the other methods (as expected), but it works.
The Shortcut is a Superstar: The "Grounded" approach was incredibly effective. It caught almost all the correct answers that the complex methods found, but it was much faster.
The Strategy: The best way to run a kitchen (or a database) is to:
- First, use the Grounded Shortcut to get a quick, safe answer.
- If that doesn't give a clear answer, then try the harder Pareto method.
- Only if you absolutely need the perfect "Grandmaster" answer, use the heavy Global Optimal tool (and be prepared to wait).

The Takeaway

This paper is a breakthrough because it finally lets computers handle the most difficult kind of messy data using the most logical, priority-based rules. It also teaches us that sometimes, a smart, simple shortcut (Grounded Semantics) is the most practical tool for the job, saving us from needing to solve the hardest puzzles every single time.

In short: We finally have a way to fix the messiest data perfectly, but we also found a super-fast way to get 99% of the way there.

1. Problem Statement

The paper addresses the challenge of inconsistency-tolerant query answering over prioritized knowledge bases (KBs). In scenarios where data conflicts with a logical theory (e.g., ontologies or database constraints), standard query answering fails. The standard approach involves repair-based semantics, where queries are evaluated over "repairs" (maximal consistent subsets of the data).

When data is prioritized (i.e., some facts are preferred over others in case of conflict), three specific notions of optimal repairs are defined based on a priority relation $\succ$ :

Pareto-optimal: No single fact can be swapped for a strictly better one.
Globally-optimal: No subset of facts can be swapped for a strictly better subset.
Completion-optimal: The repair is globally optimal under some total completion of the priority relation.

The Core Challenge:
While query answering under Pareto- and completion-optimal repairs is known to be in the first level of the polynomial hierarchy (NP or coNP), answering queries under globally-optimal repairs is significantly harder, residing in the second level of the polynomial hierarchy ( $\Sigma^p_2$ or $\Pi^p_2$ ).

Existing implementations (e.g., using SAT or standard ASP) handle the easier cases but fail to implement globally-optimal semantics efficiently due to modeling complexity.
Standard ASP with disjunctive rules can theoretically handle $\Sigma^p_2$ problems but requires complex techniques (like saturation) that are difficult to model and often inefficient in practice.

2. Methodology

The authors propose a novel approach using Answer Set Programming with Quantifiers (ASP(Q)) to encode and solve these high-complexity semantics.

A. ASP(Q) Framework

ASP(Q) extends standard ASP by allowing quantification over the answer sets of different programs ( $\exists_{st}$ and $\forall_{st}$ ). This allows for a natural and compact encoding of problems in the polynomial hierarchy without resorting to complex saturation techniques.

Encoding Strategy: The paper encodes the existence of a repair containing a query cause (for "Brave" semantics) or the non-existence of a global improvement (for "AR" semantics) using nested quantifiers.
- Example: To check if a query holds under G-AR (Globally-optimal AR), the system checks if for every repair $R$ , there is no global improvement $B$ such that $R$ is not optimal. This maps naturally to a $\forall \exists$ structure in ASP(Q).

B. Key Optimizations

To make the approach feasible, the authors introduce several optimizations:

Localization (Reachability): Instead of considering the entire dataset, the encoding is restricted to "reachable" facts.
- Weak Reachability ( $R_w$ ): Used for globally-optimal repairs.
- Strong Reachability ( $R_s$ ): Used for Pareto- and completion-optimal repairs.
- This drastically reduces the search space by ignoring facts irrelevant to the specific query causes and conflicts.
Binary Conflict Simplification: When conflicts involve only two facts (binary), the attack relations and repair constraints can be simplified, leading to more efficient encodings.
Tractable Under-Approximations: The authors utilize the Grounded Semantics (derived from abstract argumentation) as a tractable under-approximation.
- The grounded repair is a subset of all optimal repairs.
- If a query holds under grounded semantics, it holds under all optimal repair semantics.
- This allows the system to filter out many answers quickly without invoking the expensive $\Sigma^p_2$ solver.
Hybrid Strategy: The system first checks for answers using tractable approximations (Grounded, Trivial P-IAR). Only for unresolved candidates does it invoke the full ASP(Q) encoding for Pareto, Completion, or Global semantics.

3. Key Contributions

First Implementation of Globally-Optimal Semantics: The paper presents the first working system capable of computing query answers based on globally-optimal repairs, a task previously considered too complex for practical implementation.
First Implementation of Grounded Semantics: It implements the grounded semantics for prioritized KBs, providing a fast, tractable under-approximation for all optimal repair semantics.
ASP(Q) Encoding: It demonstrates the practical utility of ASP(Q) for problems in the second level of the polynomial hierarchy, moving beyond theoretical feasibility to experimental validation.
Comprehensive Experimental Evaluation: The authors provide a rigorous comparison of:
- Different semantics (Pareto vs. Global vs. Completion).
- Different encodings (Generic vs. Binary-specific).
- The impact of localization.
- The effectiveness of the grounded approximation.

4. Experimental Results

The evaluation used the ORBITS and CQAPri benchmarks with datasets ranging from 75k to 2M facts, including both binary and non-binary (size 10) conflicts.

Feasibility of Global Semantics: While computing globally-optimal repairs is significantly slower than Pareto/Completion variants (often resulting in timeouts on larger datasets), the ASP(Q) approach successfully solved many instances, proving feasibility.
Effectiveness of Grounded Semantics:
- The grounded repair captures a vast majority of the answers found by the more complex semantics.
- In many cases, the set of answers under Grounded semantics is identical to or very close to the intersection of all optimal repairs (X-IAR).
- Runtime Impact: Using grounded semantics as a filter reduces the number of instances requiring the expensive $\Sigma^p_2$ solver by a significant margin.
Localization Impact: Localization is critical; without it, the system times out on almost all non-grounded instances.
Binary vs. Non-Binary: Simplified encodings for binary conflicts generally improve performance for Pareto semantics but show mixed results for Global semantics (sometimes faster, sometimes slower depending on the instance).
Semantics Comparison:
- Pareto-optimal repairs are the fastest to compute.
- Globally-optimal repairs yield fewer answers (more cautious) than Pareto but are computationally much more expensive.
- The three types of optimal repairs often yield the same answers in practice, suggesting that the expensive global computation might be unnecessary for many real-world cases if a cheaper semantics (like Pareto) is used first.

5. Significance

Theoretical Advancement: This work bridges the gap between theoretical complexity results (polynomial hierarchy levels) and practical implementation, showing that ASP(Q) is a viable tool for $\Sigma^p_2$ problems.
Practical Utility: By introducing the grounded semantics as a preprocessing step, the authors provide a strategy to handle inconsistent prioritized data efficiently. This allows systems to return high-confidence answers quickly while reserving heavy computation for ambiguous cases.
Framework for Future Work: The paper establishes a framework for specifying and computing priority relations and offers a baseline for future research in inconsistency-tolerant querying, particularly for large-scale datasets where standard repair-based approaches are too slow.

In conclusion, the paper successfully demonstrates that ASP(Q) enables the first practical implementation of globally-optimal repair semantics, while highlighting that grounded semantics serves as a highly effective, low-cost approximation for handling inconsistent prioritized data.