TLDR: This paper investigates the computational complexity of querying inconsistent knowledge bases using cost-based semantics, where interpretations are assigned costs based on violated weighted axioms. It extends previous work to more expressive Description Logics, including DL-Lite dialects. Key contributions include establishing a precise Delta-P2 complexity for optimal-cost certain answer semantics and, surprisingly, demonstrating that for DL-LiteHbool ontologies with a fixed cost bound, certain answers for instance queries and possible answers for conjunctive queries can be computed with the lowest possible data complexity (AC0) using first-order rewriting.
Ontology-Mediated Query Answering (OMQA) is a field that combines knowledge representation and database technologies to enhance data access by leveraging semantic information from ontologies. Ontologies, often expressed in Description Logics (DLs), provide a structured way to define knowledge. In a typical OMQA setup, a query is posed against a knowledge base, which consists of an ontology (TBox) and a dataset (ABox), to find “certain answers” – facts logically entailed by the knowledge base.
However, a significant challenge arises when the knowledge base is inconsistent. If an inconsistency exists, classical logic dictates that anything can be entailed, rendering all query answers trivially “certain” and thus meaningless. To address this, researchers have developed various inconsistency-tolerant semantics.
Many existing approaches, such as repair-based semantics, focus on scenarios where the ontology axioms are considered perfectly reliable, and inconsistencies are assumed to stem solely from errors in the dataset. These methods identify “repairs” – maximal consistent subsets of the ABox – and derive answers based on what holds in all or some of these repairs. While useful, this perspective doesn’t account for situations where ontology axioms themselves might be “soft” rules that generally hold but can admit rare exceptions.
A more recent quantitative approach, known as cost-based semantics, offers a solution for handling such ‘soft’ ontology axioms. Introduced in 2024, this framework assigns weights to axioms and assertions. These weights represent penalties incurred for violating them. An interpretation (a way of understanding the knowledge base) is then assigned a “cost” based on the sum of weights of the axioms and assertions it violates. The goal is to find query answers by considering interpretations that have either the optimal (minimum) cost or a cost below a fixed bound.
This paper, titled “Data Complexity of Querying Description Logic Knowledge Bases under Cost-Based Semantics” by Meghyn Bienvenu and Quentin Mani`ere, significantly advances the understanding of these cost-based semantics. While initial studies focused on a limited range of Description Logics, this research extends the analysis to more expressive DLs, including those with inverse roles and role inclusions, which are crucial for prominent DL-Lite dialects commonly used in OMQA.
The authors delve into the “data complexity” of these semantics, which measures how the computational effort scales with the size of the data (ABox), assuming the ontology and query are fixed. Their work provides a more precise understanding of the computational demands, sharpening several existing lower bounds and, for the first time, pinpointing the exact complexity of optimal-cost certain answer semantics, for which no non-trivial upper bound was previously known. They establish a Delta-P2 upper bound for these semantics, matching existing lower bounds.
Perhaps the most surprising and impactful finding of this research is a breakthrough in tractability. While previous results generally indicated the intractability of cost-based semantics, this paper demonstrates that for DL-LiteHbool ontologies and a fixed cost bound, certain answers for instance queries and possible answers for conjunctive queries can be computed with the lowest possible data complexity (AC0). This remarkable efficiency is achieved through a technique called first-order rewriting, which transforms the complex query into a simpler first-order query that can be evaluated directly on the data.
The core of these positive results lies in a “small interpretation property.” This property states that if an interpretation satisfies the desired query behavior within a fixed cost, then there exists another interpretation that is trivial except for a small, constant-sized domain. This allows for the complex reasoning to be “rewritten” into a first-order query, making it highly efficient.
Also Read:
- Enhancing Decision-Focused Learning with Dual-Guided Surrogates for Scalable AI
- Improving AI Reliability: Predicting When Models Lack Sufficient Data
This research significantly improves our comprehension of query entailment under cost-based semantics, offering tight complexity bounds for a broad spectrum of Description Logics. The surprising tractability results for DL-LiteHbool under fixed-cost scenarios open new avenues for practical implementations of inconsistency-tolerant query answering. For more technical details, you can refer to the full research paper: Data Complexity of Querying Description Logic Knowledge Bases under Cost-Based Semantics.
