Tractable Responsibility Measures for Ontology-Mediated Query Answering

• URL: http://arxiv.org/abs/2507.23191v1
• Date: Thu, 31 Jul 2025 02:08:12 GMT
• Title: Tractable Responsibility Measures for Ontology-Mediated Query Answering
• Authors: Meghyn Bienvenu, Diego Figueira, Pierre Lafourcade,
• Abstract summary: We study the complexity of computing responsibility scores in the setting of ontology-mediated query answering.<n>We show that such measures enjoy minimal data complexity for classes of first-order-rewritable queries.<n>We prove that intractability applies already to atomic queries if the language supports conjunction.
• Score: 3.1952340441132474
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent work on quantitative approaches to explaining query answers employs responsibility measures to assign scores to facts in order to quantify their respective contributions to obtaining a given answer. In this paper, we study the complexity of computing such responsibility scores in the setting of ontology-mediated query answering, focusing on a very recently introduced family of Shapley-value-based responsibility measures defined in terms of weighted sums of minimal supports (WSMS). By exploiting results from the database setting, we can show that such measures enjoy polynomial data complexity for classes of ontology-mediated queries that are first-order-rewritable, whereas the problem becomes "shP"-hard when the ontology language can encode reachability queries (via axioms like $\exists R. A \sqsubseteq A$). To better understand the tractability frontier, we next explore the combined complexity of WSMS computation. We prove that intractability applies already to atomic queries if the ontology language supports conjunction, as well as to unions of `well-behaved' conjunctive queries, even in the absence of an ontology. By contrast, our study yields positive results for common DL-Lite dialects: by means of careful analysis, we identify classes of structurally restricted conjunctive queries (which intuitively disallow undesirable interactions between query atoms) that admit tractable WSMS computation.

Related papers

• Neuro-Symbolic Query Compiler [57.78201019000895]
  This paper presents QCompiler, a neuro-symbolic framework inspired by linguistic grammar rules and compiler design, to bridge this gap.<n>It theoretically designs a minimal yet sufficient Backus-Naur Form (BNF) grammar $G[q]$ to formalize complex queries.<n>The atomicity of the sub-queries in the leaf ensures more precise document retrieval and response generation, significantly improving the RAG system's ability to address complex queries.
  arXiv  Detail & Related papers  (2025-05-17T09:36:03Z)
• Shapley Revisited: Tractable Responsibility Measures for Query Answers [3.1952340441132474]
  We introduce a new family of responsibility measures -- weighted sums of minimal supports (WSMS)<n>We prove that every WSMS measure can be equivalently seen as the Shapley value of a suitably defined cooperative game.<n>We also explore the combined complexity of WSMS and establish (in)tractability results for various subclasses of conjunctive queries.
  arXiv  Detail & Related papers  (2025-03-28T11:52:26Z)
• 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)
• Adaptive-RAG: Learning to Adapt Retrieval-Augmented Large Language Models through Question Complexity [59.57065228857247]
  Retrieval-augmented Large Language Models (LLMs) have emerged as a promising approach to enhancing response accuracy in several tasks, such as Question-Answering (QA) We propose a novel adaptive QA framework, that can dynamically select the most suitable strategy for (retrieval-augmented) LLMs based on the query complexity. We validate our model on a set of open-domain QA datasets, covering multiple query complexities, and show that ours enhances the overall efficiency and accuracy of QA systems.
  arXiv  Detail & Related papers  (2024-03-21T13:52:30Z)
• Rethinking Complex Queries on Knowledge Graphs with Neural Link Predictors [58.340159346749964]
  We propose a new neural-symbolic method to support end-to-end learning using complex queries with provable reasoning capability. We develop a new dataset containing ten new types of queries with features that have never been considered. Our method outperforms previous methods significantly in the new dataset and also surpasses previous methods in the existing dataset at the same time.
  arXiv  Detail & Related papers  (2023-04-14T11:35:35Z)
• Logical Message Passing Networks with One-hop Inference on Atomic Formulas [57.47174363091452]
  We propose a framework for complex query answering that decomposes the Knowledge Graph embeddings from neural set operators. On top of the query graph, we propose the Logical Message Passing Neural Network (LMPNN) that connects the local one-hop inferences on atomic formulas to the global logical reasoning. Our approach yields the new state-of-the-art neural CQA model.
  arXiv  Detail & Related papers  (2023-01-21T02:34:06Z)
• Successive Prompting for Decomposing Complex Questions [50.00659445976735]
  Recent works leverage the capabilities of large language models (LMs) to perform complex question answering in a few-shot setting. We introduce Successive Prompting'', where we iteratively break down a complex task into a simple task, solve it, and then repeat the process until we get the final solution. Our best model (with successive prompting) achieves an improvement of 5% absolute F1 on a few-shot version of the DROP dataset.
  arXiv  Detail & Related papers  (2022-12-08T06:03:38Z)
• From Conjunctive Queries to Instance Queries in Ontology-Mediated Querying [17.79631575141597]
  We consider ontology-mediated queries based on expressive description logics of the ALC family and (unions) of conjunctive queries. Our results include exact characterizations of when such a rewriting is possible and tight complexity bounds for deciding rewritability.
  arXiv  Detail & Related papers  (2020-10-22T16:40:59Z)
• Answering Counting Queries over DL-Lite Ontologies [0.0]
  We introduce a general form of counting query, relate it to previous proposals, and study the complexity of answering such queries. We consider some practically relevant restrictions, for which we establish improved complexity bounds.
  arXiv  Detail & Related papers  (2020-09-02T11:10:21Z)
• 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)
• When is Ontology-Mediated Querying Efficient? [10.971122842236024]
  We study the evaluation of ontology-mediated queries over relational databases. We provide a characterization of the classes of OMQs that are tractable in combined complexity. We also study the complexity of deciding whether a given OMQ is equivalent to an OMQ of bounded tree width.
  arXiv  Detail & Related papers  (2020-03-17T16:32:00Z)

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.