🤖 AI

A Rule-Based Approach to Specifying Preferences over Conflicting Facts and Querying Inconsistent Knowledge Bases

This paper introduces a declarative rule-based framework that utilizes answer set programming to specify and compute priority relations between conflicting facts for querying inconsistent knowledge bases, addressing the challenges of cyclic preferences through acyclicity analysis and pragmatic cycle removal techniques.

Original authors: Meghyn Bienvenu, Camille Bourgaux, Katsumi Inoue, Robin Jean

Published 2026-08-04

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Meghyn Bienvenu, Camille Bourgaux, Katsumi Inoue, Robin Jean

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 librarian of a massive, chaotic library where some books have been accidentally glued together with contradictory pages. One book says, "The sky is blue," while another, glued to the same shelf, insists, "The sky is green." In the world of computer science, this is called an "inconsistent knowledge base." When a computer tries to answer a question using this messy library, it gets stuck. To fix this, scientists have developed a method called "repairing." Think of it as a librarian who, instead of throwing the whole library away, carefully snips out the conflicting pages to create a clean, consistent version of the story. But here's the tricky part: if you have a hundred conflicting pages, there are thousands of ways to snip them out. Which version of the story should the computer trust?

Usually, the computer tries to be super cautious and only accepts answers that appear in every possible clean version. But sometimes, we know some facts are more reliable than others. Maybe the "blue sky" book was written by a famous astronomer, while the "green sky" one was a child's doodle. If we could tell the computer, "Trust the astronomer over the doodle," it could pick the best version of the story. This is where the new paper comes in. It tackles the problem of how to tell the computer which facts are better without forcing a human to manually rank every single page in the library.

The authors, a team of researchers from France and Japan, have built a clever new system that lets users write simple "preference rules" to solve this puzzle. Instead of manually sorting thousands of facts, you can just write instructions like, "If two facts conflict, keep the one added more recently," or "If a fact comes from a trusted source, keep it over one from an unknown source." The paper introduces a framework where these rules automatically generate a priority list, telling the computer which facts to save and which to discard when conflicts arise.

However, there's a catch. If you write too many rules, they might get into a loop. For example, Rule A says "Fact 1 is better than Fact 2," Rule B says "Fact 2 is better than Fact 3," but Rule C says "Fact 3 is better than Fact 1." This creates a circular argument where nothing is truly the best. The paper's main discovery is a set of strategies to break these loops. The authors propose four different ways to untangle these knots, ranging from a "go up" method (prioritizing the most important rules first) to a "grounded" method (only trusting facts that aren't part of a confusing loop). They tested these methods using a computer program called "Answer Set Programming," which is like a super-smart logic solver.

The researchers found that while their system is powerful and flexible, it can be a bit slow compared to older, more rigid methods, especially when dealing with huge libraries of data. In their experiments, they tested scenarios with up to 2 million facts and found that their system could successfully untangle complex conflicts and answer questions, even when the conflicts were messy and non-binary (involving more than just two facts). They also proved mathematically that for certain types of simple rules, you can be 100% sure the system won't get stuck in a loop, but for more complex rules, you might need to use their "loop-breaking" strategies. Ultimately, this paper doesn't just offer a new way to fix messy data; it offers a way for humans to speak their logic in plain English rules, letting the computer handle the heavy lifting of deciding which version of the truth to believe.

Technical Summary: A Rule-Based Approach to Specifying Preferences over Conflicting Facts and Querying Inconsistent Knowledge Bases

Problem Statement

Inconsistency-tolerant semantics, particularly those based on subset repairs, are a standard approach for querying knowledge bases (KBs) that violate constraints. While frameworks exist to define "optimal repairs" using a priority relation between conflicting facts (e.g., the prioritized database framework by Staworko et al.), a critical gap remains: how to conveniently specify the priority relation itself.

Existing literature assumes the priority relation is given, but it is unrealistic to expect users to manually input a binary relation between all conflicting facts. Furthermore, when users attempt to specify preferences via rules, these rules may induce cycles (e.g., fact A is preferred to B, B to C, and C to A), rendering the relation invalid since priority relations must be acyclic. The paper addresses the challenge of declaratively specifying these preferences and resolving the resulting cycles to enable practical querying of inconsistent KBs.

Methodology

1. Rule-Based Preference Specification

The authors introduce a declarative framework where priority relations are derived from preference rules evaluated over a dataset $D$ and a meta-database $M$ .

Meta-database: A dataset $F$ containing metadata (e.g., dates, source reliability) linked to facts in $D$ via unique identifiers.
Preference Rules: Rules of the form $Cond(x_1, x_2) \to pref(x_1, x_2)$ $C o n d (x_{1}, x_{2}) \to p r e f (x_{1}, x_{2})$ , where the body $Cond$ can reference:
- The presence/absence of facts in $D$ .
- Metadata in $F$ (e.g., comparing dates or reliability scores).
- Ontology axioms (e.g., subclass relationships).
- Negation and inequalities.
Induced Relation: A rule induces a preference $pref(id(\alpha), id(\beta))$ if the condition holds. The actual priority relation $\succ_{\Sigma, K, M}$ is formed by filtering these induced preferences to include only pairs $(\alpha, \beta)$ that appear together in a conflict.

2. Handling Cycles

Since induced relations may contain cycles, the paper proposes two complementary strategies:

Static Acyclicity Checking: Investigating whether a set of rules is guaranteed to produce an acyclic relation for any dataset.
- The paper proves that for the general language $PL_{DL}$ , checking acyclicity is undecidable.
- However, for a restricted language $PL_{pos}$ (positive rules without ontology atoms or negation) and binary denial constraints, the problem is decidable in coNP.
- The concept of strong acyclicity is introduced: a set of rules is strongly acyclic if the induced relation is acyclic for any KB and meta-database, regardless of conflicts.
Pragmatic Cycle Resolution: When rules are not guaranteed to be acyclic, the system allows users to partition rules into priority levels ( $\Sigma_1, \dots, \Sigma_n$ $Σ_{1}, \dots, Σ_{n}$ ), where lower indices denote higher priority. Four strategies are defined to extract an acyclic sub-relation:
1. Going Up ( $\succ_u$ ): Iteratively add levels starting from the lowest index (highest priority, $\Sigma_1$ ), stopping if adding the next level would form a cycle.
2. Going Down ( $\succ_d$ ): Start with the union of all levels and iteratively remove pairs from the highest index (lowest priority) levels that participate in cycles until acyclicity is achieved.
3. Refined Going Up ( $\succ_{ru}$ ): A variant that removes cycles within a level before adding the next.
4. Grounded ( $\succ_g$ ): A fixpoint approach inspired by grounded extensions in argumentation frameworks.
- The paper establishes theoretical relationships between these strategies (e.g., $\succ_u \subseteq \succ_d \subseteq \succ_g$ ) and links them to existing notions like possibilistic repairs and non-defeated repairs.

3. Implementation

The authors implemented an end-to-end system using Answer Set Programming (ASP):

Input Encoding: Logic programs encode the dataset, meta-database, constraints, queries, and preference rules.
Conflict & Cause Computation: The system computes conflicts and causes (minimal inconsistent subsets) using ASP. Notably, this implementation handles non-binary conflicts (conflicts of arbitrary size), whereas many existing tools are limited to binary conflicts.
Priority Computation: The cycle resolution strategies are encoded as ASP programs to derive the final priority relation.
Query Answering: The system evaluates queries under various semantics (Brave, AR, IAR) combined with repair types (Subset, Pareto-optimal, Completion-optimal).

Key Results

Theoretical Contributions

Undecidability: Proved that checking if a general set of preference rules yields an acyclic relation is undecidable.
Decidability: Proved that for positive rules without ontology atoms ( $PL_{pos}$ ) and binary denial constraints, acyclicity checking is decidable in coNP.
Strategy Equivalence: Established that the proposed cycle resolution strategies correspond to known repair notions in the literature (Possibilistic, Non-defeated, Grounded) when mapped to a specific KB structure.

Experimental Evaluation

The system was evaluated on the CQAPri benchmark (synthetic DL-Lite KBs) with varying sizes (up to ~2M facts) and conflict densities.

Cycle Resolution Performance:
- The Going Down ( $\succ_d$ ) strategy was found to be significantly faster to compute than $\succ_g$ and $\succ_u$ in most scenarios, while often producing similar results (coinciding in many cases).
- The Refined Going Up ( $\succ_{ru}$ ) strategy caused memory overflows even on small datasets due to the complexity of the ASP encoding.
- The system successfully computed priority relations for datasets with high conflict proportions (up to 46%) and large numbers of preference facts.
Query Answering Performance:
- The ASP-based system was generally slower than the existing SAT-based tool ORBITS (by orders of magnitude on large datasets) for computing answers under optimal repair semantics.
- However, the ASP system succeeded in answering queries under C-AR and C-brave semantics in cases where ORBITS failed (time-out or memory overflow).
- The system is the first to implement optimal repair-based semantics for non-binary conflicts.

Significance and Claims

The paper claims to provide the first declarative, rule-based framework for specifying priority relations in inconsistent KBs, addressing a gap that has hindered the practical adoption of prioritized repair semantics.

Flexibility: By allowing rules to reference metadata and ontology axioms, the framework offers a flexible way to define inconsistency management policies without manual binary relation input.
Cycle Management: The paper provides a pragmatic solution to the cycle problem, offering multiple resolution strategies and theoretical guarantees for specific rule classes.
Implementation: The implementation demonstrates the feasibility of using ASP for this task, particularly its ability to handle non-binary conflicts, a feature missing in current state-of-the-art tools like ORBITS.
Modesty: The authors acknowledge that while their ASP implementation is less efficient than SAT-based approaches for binary conflicts, it offers greater expressiveness (handling arbitrary conflict sizes) and modularity (e.g., easier to extend to other repair computations). They do not claim to have surpassed SAT in raw speed but highlight the unique capabilities of their approach.

The work concludes by identifying future directions, including extending static analysis to broader theory classes, investigating uniqueness of optimal repairs, and building a fully automated pipeline to generate logic programs from standard data formats.