🤖 AI

Cost-Based Semantics for Querying Inconsistent Weighted Knowledge Bases

This paper proposes a quantitative framework for querying inconsistent weighted description logic knowledge bases by defining certain and possible answers based on cost-bounded or optimal-cost interpretations, and provides a comprehensive analysis of the computational complexity for these problems across logics ranging from ELbot to ALCO.

Original authors: Meghyn Bienvenu, Camille Bourgaux, Robin Jean

Published 2026-08-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Meghyn Bienvenu, Camille Bourgaux, 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

The Messy Reality of Perfect Logic

Imagine you are trying to solve a giant puzzle, but someone has secretly swapped a few pieces or painted over the edges. In the world of computer science, specifically in a field called Knowledge Representation, we build massive digital puzzles called "Knowledge Bases." These are like giant instruction manuals that tell computers how the world works, mixing a set of general rules (like "all birds can fly") with specific facts (like "Tweety is a bird").

Usually, these puzzles are designed to be perfect. If the rules and facts don't clash, the computer can easily tell you the answer to any question you ask. But in the real world, data is messy. Sometimes the facts contradict the rules, or two facts fight each other. In the old way of doing things, if a computer found even one tiny contradiction, it would throw up its digital hands and say, "I give up! Since everything is broken, anything could be true." This is a problem because it means the computer stops giving you useful answers.

To fix this, researchers have tried different strategies. Some try to surgically remove the bad pieces to make the puzzle consistent again. Others say, "Let's just look at the biggest chunk of the puzzle that does fit." But these methods often treat every piece of data as equally important, or they force a binary choice: either a rule is absolute law, or it's trash. What if some rules are just "usually true" and some facts are "very likely" while others are "maybe"? This paper explores a new way to handle these messy, contradictory puzzles by assigning a "price tag" to every mistake.

The Price Tag Approach to Broken Puzzles

In this paper, the authors introduce a clever new way to query these messy, inconsistent knowledge bases. Instead of trying to force the puzzle to be perfect, they treat it like a game where you can break the rules, but every time you do, you have to pay a fine.

Think of your knowledge base as a strict bouncer at a club. In the old days, if you violated even one rule, the bouncer kicked you out and refused to talk to you at all. In this new system, the bouncer has a ledger. Some rules are "Hard Laws" (like "You must be 21 to enter"), and breaking them costs an infinite amount of money—so you simply can't do it. Other rules are "Soft Suggestions" (like "Wear a tie"). Breaking a soft rule costs a small fee, say 5 dollars. If you have a fact that is very reliable, it costs a lot to ignore it; if a fact is shaky, it costs very little to ignore it.

The computer then looks at all the possible ways to interpret the data. Some interpretations might break a few soft rules, costing a little money. Others might break many, costing a fortune. The computer calculates the "total cost" for each possible scenario.

The authors define two main ways to find answers based on this cost:

The "Best Deal" Approach: The computer only looks at the scenarios that cost the absolute minimum amount of money. It asks, "What is true in the cheapest, most efficient way to make sense of this mess?"
The "Budget" Approach: The computer sets a spending limit (a budget). It asks, "What is true in any scenario that stays under this budget?" This is useful if you want to know what answers are "robust"—meaning they hold true even if you are willing to pay a little extra to fix the data.

The paper doesn't just propose this idea; it rigorously tests how hard it is for a computer to do this math. The authors analyzed the "complexity" of the problem, which is basically a measure of how much computing power and time it would take to solve these puzzles as they get bigger. They looked at different types of logic systems, ranging from simple ones (like basic category rules) to very complex ones (with numbers, specific names, and intricate relationships).

Their findings are a mix of good news and "it depends." They proved that for the most complex types of logic, figuring out the answers is incredibly difficult for computers—it's in a class of problems that could take an exponential amount of time to solve as the data grows. However, for simpler, more common types of logic used in many real-world applications, the problem is manageable, though still tricky. They also discovered that the way you write down the "costs" (whether you use a simple count or a huge number) changes how hard the problem is for the computer.

Crucially, the authors show that this new method isn't just a guess; it's a mathematically proven framework. They demonstrated that if your data happens to be perfect (no contradictions), their method gives you the exact same answers as the traditional, perfect methods. But when the data is broken, their method gives you a ranked list of answers: some are "certain" (they appear in the cheapest, best scenarios), and some are "possible" (they appear in at least one cheap scenario).

In short, this paper provides a mathematical toolkit for computers to say, "Okay, the data is messy, but if we ignore the least important mistakes, here is what is most likely true." It turns a "system crash" into a "negotiation," allowing us to get useful answers even when the information we have is far from perfect.

Technical Summary: Cost-Based Semantics for Querying Inconsistent Weighted Knowledge Bases

Problem Statement
Ontology-mediated query answering (OMQA) relies on Description Logic (DL) knowledge bases (KBs) consisting of a TBox (ontology) and an ABox (data). Classical OMQA semantics, based on first-order logic, fails to provide informative answers when the KB is inconsistent, as everything is entailed from a contradiction. While existing approaches handle inconsistency via repairs (e.g., AR and brave semantics), these typically assume the TBox is reliable and only modify the ABox. Furthermore, standard repair semantics often treat all assertions as equally reliable or rely on cardinality-based maximality, lacking a nuanced way to prioritize conflicting information based on varying degrees of trust.

This paper addresses the challenge of querying inconsistent DL KBs by introducing a quantitative framework. The core problem is to define meaningful certain and possible answers when both TBox axioms and ABox assertions can be violated, with violations penalized according to assigned weights.

Methodology and Framework
The authors propose a Weighted Knowledge Base (WKB) framework, denoted as $K_\omega = (\langle \mathcal{T}, \mathcal{A} \rangle, \omega)$ .

Weights: A cost function $\omega$ assigns a value in $\mathbb{N}_{>0} \cup \{+\infty\}$ to every axiom in $\mathcal{T}$ and assertion in $\mathcal{A}$ . Infinite weights represent "hard" constraints that must be satisfied, while finite weights represent "soft" constraints where higher values indicate greater reliability.
Cost of Interpretation: The cost of an interpretation $I$ is defined as the sum of the weights of all violated axioms and assertions. Specifically, for a concept inclusion $\tau$ , the cost includes $\omega_\tau \times |vio_\tau(I)|$ , where $vio_\tau(I)$ is the set of domain elements violating the inclusion. Assertions can be violated at most once.
Semantics: The paper defines four query entailment semantics based on the cost of interpretations:
1. $k$ -cost-bounded certain ( $K_\omega \models^k_c q$ ): $q$ holds in all interpretations with cost $\le k$ .
2. $k$ -cost-bounded possible ( $K_\omega \models^k_p q$ ): $q$ holds in at least one interpretation with cost $\le k$ .
3. Opt-cost certain ( $K_\omega \models^{opt}_c q$ ): $q$ holds in all interpretations with minimal cost ( $optc(K_\omega)$ ).
4. Opt-cost possible ( $K_\omega \models^{opt}_p q$ ): $q$ holds in at least one interpretation with minimal cost.

The framework generalizes existing repair semantics. Specifically, when TBox axioms have infinite weights, the opt-cost certain semantics coincides with the $\le_\omega$ -AR semantics (Bienvenu, Bourgaux, and Goasdoué 2014), which selects repairs that maximize the sum of weights of retained assertions.

Key Contributions
The primary contribution is a comprehensive analysis of the combined and data complexity of the main decision problems in this setting:

Bounded Cost Satisfiability (BCS): Determining if an interpretation with cost $\le k$ exists.
Certain and Possible Answer Recognition: Deciding entailment under the four defined semantics.

The study covers a range of Description Logics from the lightweight $\mathcal{EL}^\bot$ to the expressive $\mathcal{ALCO}$ (and $\mathcal{ALCO}^\mathcal{Q}$ for upper bound proofs), handling both Instance Queries (IQs) and Conjunctive Queries (CQs).

Complexity Results
The paper establishes tight complexity bounds, summarized as follows:

Combined Complexity:
- Most problems are EXPTIME-complete.
- Certain answer recognition for CQs (both bounded and opt-cost) is 2EXPTIME-complete. This high complexity arises from the need to verify entailment across all models of a specific cost, which relates to circumscribed KBs.
- These bounds hold even when weights and the cost bound $k$ are encoded in binary.
Data Complexity:
- Bounded Cost Satisfiability (BCS): NP-complete.
- Bounded Cost Answering (IQs/CQs): NP-complete (possible) and coNP-complete (certain).
- Optimal Cost Answering: The complexity depends heavily on the encoding of weights:
  - If weights are encoded in unary or bounded independently of the ABox size, the problems are $\Theta^p_2$ -complete (solvable in polynomial time with logarithmic calls to an NP oracle).
  - If weights are encoded in binary and can be exponential relative to the ABox size, the problems become $\Delta^p_2$ -complete (solvable in polynomial time with access to an NP oracle).
- The paper notes that for opt-cost certain semantics with binary weights, the upper bound remains open, though lower bounds are $\Delta^p_2$ -hard.

Significance and Claims
The authors claim to provide an "almost complete picture" of the complexity landscape for querying inconsistent KBs under a cost-based semantics. The significance of the work lies in:

Quantitative Flexibility: Moving beyond binary consistency to a graded approach where answers can be ranked or filtered based on their "robustness" (i.e., whether they hold in interpretations close to the optimal cost).
Generalization: Unifying concepts from soft constraints in databases (Carmeli et al. 2021) and weighted repairs in ontologies, showing that optimal-cost semantics naturally generalize preferred repair semantics.
Technical Depth: The complexity proofs leverage and adapt advanced techniques from DL reasoning, including:
- Filtration and bounded model properties to establish upper bounds.
- Reductions from cardinality query answering and circumscribed KBs to establish lower bounds.
- Adaptations of "interlacing" and "quotient" constructions from counting query literature (Manière 2022) to handle the specific constraints of weighted violations.

The paper concludes by identifying future directions, specifically the extension of these results to DLs with inverse roles, role inclusions, and functional roles (e.g., the DL-Lite family), noting that current techniques for upper bounds do not readily transfer to these constructs. It also highlights the challenge of developing practical algorithms for implementation.

The Messy Reality of Perfect Logic

The Price Tag Approach to Broken Puzzles

More like this