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

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 $\mathcal{EL}_\bot$ and $\mathcal{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 $\text{DL-Lite}^\mathcal{H}_\mathsf{bool}$ 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 ($\mathsf{TC}_0$).

• Publication year

  2025

• Venue

  arXiv.org

• Publication date

  2025-11-10

• Fields of study

  Computer Science

• Identifiers
  DOI 10.48550/arXiv.2511.07095arXiv 2511.07095
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Adding Circumscription to Decidable Fragments of First-Order Logic: A Complexity Rollercoaster

  2024cited by this paper
• Cost-Based Semantics for Querying Inconsistent Weighted Knowledge Bases

  2024influential reference
• Principles of KLM-style Defeasible Description Logics

  2020cited by this paper
• A Short Survey on Inconsistency Handling in Ontology-Mediated Query Answering

  2020cited by this paper
• Ontology-Based Data Access: A Survey

  2018cited by this paper
• Inconsistency-Tolerant Querying of Description Logic Knowledge Bases

  2016cited by this paper
• Generalized Consistent Query Answering under Existential Rules

  2016cited by this paper
• Inconsistency Handling in Ontology-Mediated Query Answering. (Gestion des incohérences pour l'accès aux données en présence d'ontologies)

  2016influential reference
• Ontology-Mediated Query Answering with Data-Tractable Description Logics

  2015cited by this paper
• The Complexity of Circumscription in DLs

  2014cited by this paper
• A non-monotonic Description Logic for reasoning about typicality

  2013cited by this paper
• Inconsistency-Tolerant Semantics for Description Logics

  2010cited by this paper
• Data Complexity of Query Answering in Expressive Description Logics via Tableaux

  2008cited by this paper
• Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-Lite Family

  2007cited by this paper
• The complexity of optimization problems

  1986cited by this paper

• No citing papers are available for this paper.