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

• URL: http://arxiv.org/abs/2511.07095v2
• Date: Fri, 14 Nov 2025 03:50:37 GMT
• Title: Data Complexity of Querying Description Logic Knowledge Bases under Cost-Based Semantics
• Authors: Meghyn Bienvenu, Quentin Manière,
• Abstract summary: We study the data complexity of querying inconsistent weighted description logic (DL) knowledge bases under cost-based semantics.<n>In a nutshell, the idea is to assign each interpretation a cost based upon the weights of the violated axioms and assertions.<n>We find that certain answers for instance queries and possible answers for conjunctive queries can be computed using first-order rewriting.
• Score: 4.511923587827302
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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$).

Related papers

• OrLog: Resolving Complex Queries with LLMs and Probabilistic Reasoning [51.58235452818926]
  We introduce OrLog, a neuro-symbolic retrieval framework that decouples predicate-level plausibility estimation from logical reasoning.<n>A large language model (LLM) provides plausibility scores for atomic predicates in one decoding-free forward pass, from which a probabilistic reasoning engine derives the posterior probability of query satisfaction.
  arXiv  Detail & Related papers  (2026-01-30T15:31:58Z)
• FLARE: Faithful Logic-Aided Reasoning and Exploration [47.46564769245296]
  We introduce a novel approach for traversing the problem space using task decompositions.<n>We use the Large Language Models to plan a solution, soft-formalise the query into facts and predicates using a logic programming code.<n>Our method allows us to compute the faithfulness of the reasoning process w.r.t. the generated code and analyse the steps of the multi-hop search without relying on external solvers.
  arXiv  Detail & Related papers  (2024-10-14T19:39:11Z)
• Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
  Motivated by crowdsourcing, we consider a problem where we partially observe the correctness of the answers of $n$ experts on $d$ questions. In this paper, we assume that the matrix $M$ containing the probability that expert $i$ answers correctly to question $j$ is bi-isotonic up to a permutation of it rows and columns. We construct an efficient-time algorithm that turns out to be minimax optimal for this classification problem.
  arXiv  Detail & Related papers  (2024-08-27T18:28:31Z)
• Queries With Exact Truth Values in Paraconsistent Description Logics [5.222978725954348]
  We present a novel approach to querying classical inconsistent description logic (DL) knowledge bases. We adopt aparaconsistent semantics with the four Belnapian values: exactly true ($mathbfT$), exactly false ($mathbfF$), both ($mathbfB$), and neither ($mathbfN$)
  arXiv  Detail & Related papers  (2024-08-01T08:11:50Z)
• Cost-Based Semantics for Querying Inconsistent Weighted Knowledge Bases [5.222978725954348]
  We consider weighted knowledge bases in which both axioms and assertions have (possibly infinite) weights. Two notions of certain and possible answer are defined by either considering interpretations whose cost does not exceed a given bound. Our main contribution is a comprehensive analysis of the combined and data complexity of bounded cost satisfiability and certain and possible answer recognition.
  arXiv  Detail & Related papers  (2024-07-30T11:56:02Z)
• Generating $SROI^-$ Ontologies via Knowledge Graph Query Embedding Learning [26.905431434167536]
  We propose a novel query embedding method, AConE, which explains the knowledge learned from the graph in the form of $SROI-$ description logic axioms. AConE achieves superior results over previous baselines with fewer parameters. We provide comprehensive analyses showing that the capability to represent axioms positively impacts the results of query answering.
  arXiv  Detail & Related papers  (2024-07-12T12:20:39Z)
• H-STAR: LLM-driven Hybrid SQL-Text Adaptive Reasoning on Tables [56.73919743039263]
  This paper introduces a novel algorithm that integrates both symbolic and semantic (textual) approaches in a two-stage process to address limitations.<n>Our experiments demonstrate that H-STAR significantly outperforms state-of-the-art methods across three question-answering (QA) and fact-verification datasets.
  arXiv  Detail & Related papers  (2024-06-29T21:24:19Z)
• A Theory of Interpretable Approximations [61.90216959710842]
  We study the idea of approximating a target concept $c$ by a small aggregation of concepts from some base class $mathcalH$. For any given pair of $mathcalH$ and $c$, exactly one of these cases holds: (i) $c$ cannot be approximated by $mathcalH$ with arbitrary accuracy. We show that, in the case of interpretable approximations, even a slightly nontrivial a-priori guarantee on the complexity of approximations implies approximations with constant (distribution-free and accuracy-
  arXiv  Detail & Related papers  (2024-06-15T06:43:45Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  The fuzzy or soft objective is a popular generalization of the well-known $k$-means problem. We show that by making few queries, the problem becomes easier to solve.
  arXiv  Detail & Related papers  (2021-06-04T02:32:26Z)
• A tetrachotomy of ontology-mediated queries with a covering axiom [1.749935196721634]
  Our concern is the problem of efficiently determining the data complexity of answering queries mediated by description and their optimal rewritings to standard database queries. We focus on Boolean conjunctive-mediated queries called disjunctive sirups (or d-sirups) Some d-sirups only have exponential-size resolution features, some only double-exponential-size positive existential existential-rewritings and single-exprecursive datalog rewritings.
  arXiv  Detail & Related papers  (2020-06-07T14:47:07Z)
• CQE in Description Logics Through Instance Indistinguishability (extended version) [0.0]
  We study privacy-preserving query answering in Description Logics (DLs) We derive data complexity results query answering over DL-Lite$_mathcal$$. We identify a semantically well-founded notion of approximated confidentiality answering for CQE.
  arXiv  Detail & Related papers  (2020-04-24T17:28:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.