First Order-Rewritability and Containment of Conjunctive Queries in Horn Description Logics

• URL: http://arxiv.org/abs/2011.09836v1
• Date: Thu, 19 Nov 2020 14:24:02 GMT
• Title: First Order-Rewritability and Containment of Conjunctive Queries in Horn Description Logics
• Authors: Meghyn Bienvenu, Peter Hansen, Carsten Lutz, Frank Wolter
• Abstract summary: We show that FO-rewriting is more complex for conjunctive queries than for atomic queries when inverse roles are present, but not otherwise. In particular, FO-rewriting is more complex for conjunctive queries than for atomic queries when inverse roles are present, but not otherwise.
• Score: 22.32075802508239
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study FO-rewritability of conjunctive queries in the presence of ontologies formulated in a description logic between EL and Horn-SHIF, along with related query containment problems. Apart from providing characterizations, we establish complexity results ranging from ExpTime via NExpTime to 2ExpTime, pointing out several interesting effects. In particular, FO-rewriting is more complex for conjunctive queries than for atomic queries when inverse roles are present, but not otherwise.

Related papers

• GRSQA -- Graph Reasoning-Structured Question Answering Dataset [50.223851616680754]
  We introduce the Graph Reasoning-Structured Question Answering dataset (GRS-QA), which includes both semantic contexts and reasoning structures for QA pairs. Unlike existing M-QA datasets, GRS-QA explicitly captures intricate reasoning pathways by constructing reasoning graphs. Our empirical analysis reveals that LLMs perform differently when handling questions with varying reasoning structures.
  arXiv  Detail & Related papers  (2024-11-01T05:14:03Z)
• Unlocking Temporal Question Answering for Large Language Models with Tailor-Made Reasoning Logic [84.59255070520673]
  Large language models (LLMs) face a challenge when engaging in temporal reasoning. We propose TempLogic, a novel framework designed specifically for temporal question-answering tasks.
  arXiv  Detail & Related papers  (2023-05-24T10:57:53Z)
• 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)
• Finite Entailment of UCRPQs over ALC Ontologies [0.82179684645881]
  We consider the query language, unions of conjunctive regular path queries (UCRPQs) We show a tight 2EXP bound for entailment of UCRPQs using the description logic ALC. There is a novel automata-based technique introducing a stratification of interpretations induced by the deterministic finite automaton underlying the input automaton.
  arXiv  Detail & Related papers  (2022-04-29T17:38:13Z)
• Query2Particles: Knowledge Graph Reasoning with Particle Embeddings [49.64006979045662]
  We propose a query embedding method to answer complex logical queries on knowledge graphs with missing edges. The answer entities are selected according to the similarities between the entity embeddings and the query embedding. A complex KG query answering method, Q2P, is proposed to retrieve diverse answers from different areas over the embedding space.
  arXiv  Detail & Related papers  (2022-04-27T11:16:08Z)
• The Price of Selfishness: Conjunctive Query Entailment for ALCSelf is 2ExpTime-hard [11.193504036335503]
  In logic-based knowledge representation, query answering has essentially replaced mere satisfiability checking. For knowledge bases in the basic description logic ALC, the computational complexity of conjunctive query (CQ) answering is well known to be ExpTime-complete. We show that even extending ALC by just the Self operator increases the complexity of CQ entailment to 2ExpTime.
  arXiv  Detail & Related papers  (2021-06-29T08:12:03Z)
• 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)
• Generation-Augmented Retrieval for Open-domain Question Answering [134.27768711201202]
  Generation-Augmented Retrieval (GAR) for answering open-domain questions. We show that generating diverse contexts for a query is beneficial as fusing their results consistently yields better retrieval accuracy. GAR achieves state-of-the-art performance on Natural Questions and TriviaQA datasets under the extractive QA setup when equipped with an extractive reader.
  arXiv  Detail & Related papers  (2020-09-17T23:08:01Z)
• On Finite Entailment of Non-Local Queries in Description Logics [1.3192452635990861]
  We focus on the logic descriptions ALCOIQ and ALCO, extended with transitive closure. For both logics, we show 2EXPTIME upper bounds for finite entailment of conjunctive queries with transitive closure.
  arXiv  Detail & Related papers  (2020-06-30T14:57:12Z)
• 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)
• VQA-LOL: Visual Question Answering under the Lens of Logic [58.30291671877342]
  We investigate whether visual question answering systems trained to answer a question about an image, are able to answer the logical composition of multiple such questions. We construct an augmentation of the VQA dataset as a benchmark, with questions containing logical compositions and linguistic transformations. We propose our Lens of Logic (LOL) model which uses question-attention and logic-attention to understand logical connectives in the question, and a novel Fr'echet-Compatibility Loss.
  arXiv  Detail & Related papers  (2020-02-19T17:57:46Z)

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.