From Conjunctive Queries to Instance Queries in Ontology-Mediated Querying

• URL: http://arxiv.org/abs/2010.11848v1
• Date: Thu, 22 Oct 2020 16:40:59 GMT
• Title: From Conjunctive Queries to Instance Queries in Ontology-Mediated Querying
• Authors: Cristina Feier, Carsten Lutz, Frank Wolter
• Abstract summary: 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.
• Score: 17.79631575141597
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider ontology-mediated queries (OMQs) based on expressive description logics of the ALC family and (unions) of conjunctive queries, studying the rewritability into OMQs based on instance queries (IQs). Our results include exact characterizations of when such a rewriting is possible and tight complexity bounds for deciding rewritability. We also give a tight complexity bound for the related problem of deciding whether a given MMSNP sentence is equivalent to a CSP.

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)
• Seek and Solve Reasoning for Table Question Answering [49.006950918895306]
  This paper improves Table-based Question Answering (TQA) performance by leveraging Large Language Models' reasoning capabilities. Inspired by how humans solve TQA tasks, we propose a Seek-and-seek pipeline that instructs the LLM to first seek relevant information and then answer questions. We present a compact single-stage TQA-solving prompt distilled from the pipeline.
  arXiv  Detail & Related papers  (2024-09-09T02:41:00Z)
• Controlled Query Evaluation through Epistemic Dependencies [7.502796412126707]
  We show the expressive abilities of our framework and study the data complexity of CQE for (unions of) conjunctive queries. We prove tractability for the case of acyclic dependencies by providing a suitable query algorithm.
  arXiv  Detail & Related papers  (2024-05-03T19:48:07Z)
• Modeling Hierarchical Reasoning Chains by Linking Discourse Units and Key Phrases for Reading Comprehension [80.99865844249106]
  We propose a holistic graph network (HGN) which deals with context at both discourse level and word level, as the basis for logical reasoning. Specifically, node-level and type-level relations, which can be interpreted as bridges in the reasoning process, are modeled by a hierarchical interaction mechanism.
  arXiv  Detail & Related papers  (2023-06-21T07:34:27Z)
• 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)
• Containment in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics [17.17606390337468]
  We study query containment in three closely related formalisms: monadic disjunctive Datalog (MDDLog), MMSNP (a logical generalization of constraint satisfaction problems) and Ontology-mediated queries (OMQs) We prove 2NEXPTIME-completeness and extend this result to monadic disjunctive Datalog and to OMQs.
  arXiv  Detail & Related papers  (2020-10-22T16:25:00Z)
• 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)
• Query Focused Multi-Document Summarization with Distant Supervision [88.39032981994535]
  Existing work relies heavily on retrieval-style methods for estimating the relevance between queries and text segments. We propose a coarse-to-fine modeling framework which introduces separate modules for estimating whether segments are relevant to the query. We demonstrate that our framework outperforms strong comparison systems on standard QFS benchmarks.
  arXiv  Detail & Related papers  (2020-04-06T22:35:19Z)
• 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)
• 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)
• Conditional Self-Attention for Query-based Summarization [49.616774159367516]
  We propose textitconditional self-attention (CSA), a neural network module designed for conditional dependency modeling. Experiments on Debatepedia and HotpotQA benchmark datasets show CSA consistently outperforms vanilla Transformer.
  arXiv  Detail & Related papers  (2020-02-18T02:22:31Z)

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.