# Data Complexity of Querying Description Logic Knowledge Bases under Cost-Based Semantics

arXiv: https://arxiv.org/abs/2511.07095 · HTML: https://mlsanity.com/paper/2511.07095/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 17 references that are in the map.
- First posted on arXiv 10 Nov 2025.

## Builds on (most cited first, 2 of 2)

- [Cost-Based Semantics for Querying Inconsistent Weighted Knowledge Bases](https://mlsanity.com/paper/2407.20754/) (2024)
- [Adding Circumscription to Decidable Fragments of First-Order Logic: A Complexity Rollercoaster](https://mlsanity.com/paper/2407.20822/) (2024)

## Built on by (most cited first, 1 of 1)

- [ABox Abduction for Inconsistent Knowledge Bases under Repair Semantics](https://mlsanity.com/paper/2605.01341/) (2026)

## Abstract (arXiv)

In this paper, we study the data complexity of querying inconsistent weighted description logic (DL) knowledge bases under recently-introduced cost-based semantics. In a nutshell, the idea is to assign each interpretation a cost based upon the weights of the violated axioms and assertions, and certain and possible query answers are determined by considering all (resp. some) interpretations having optimal or bounded cost. Whereas the initial study of cost-based semantics focused on DLs between EL_bot and ALCO, we consider DLs that may contain inverse roles and role inclusions, thus covering prominent DL-Lite dialects. Our data complexity analysis goes significantly beyond existing results by sharpening several lower bounds and pinpointing the precise complexity of optimal-cost certain answer semantics (no non-trivial upper bound was known). Moreover, while all existing results show the intractability of cost-based semantics, our most challenging and surprising result establishes that if we consider DL-LiteH_mathsfbool ontologies and a fixed cost bound, certain answers for instance queries and possible answers for conjunctive queries can be computed using first-order rewriting and thus enjoy the lowest possible data complexity (mathsfTC0).