Answering Counting Queries over DL-Lite Ontologies

• URL: http://arxiv.org/abs/2009.09801v1
• Date: Wed, 2 Sep 2020 11:10:21 GMT
• Title: Answering Counting Queries over DL-Lite Ontologies
• Authors: Meghyn Bienvenu (UB, CNRS, Bordeaux INP, LaBRI), Quentin Mani\`ere (UB, CNRS, Bordeaux INP, LaBRI), Micha\"el Thomazo (VALDA )
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Ontology-mediated query answering (OMQA) is a promising approach to data access and integration that has been actively studied in the knowledge representation and database communities for more than a decade. The vast majority of work on OMQA focuses on conjunctive queries, whereas more expressive queries that feature counting or other forms of aggregation remain largely unex-plored. In this paper, we introduce a general form of counting query, relate it to previous proposals, and study the complexity of answering such queries in the presence of DL-Lite ontologies. As it follows from existing work that query answering is intractable and often of high complexity, we consider some practically relevant restrictions, for which we establish improved complexity bounds.

Related papers

• Database-Augmented Query Representation for Information Retrieval [59.57065228857247]
  We present a novel retrieval framework called Database-Augmented Query representation (DAQu) DAQu augments the original query with various (query-related) metadata across multiple tables. We validate DAQu in diverse retrieval scenarios that can incorporate metadata from the relational database.
  arXiv  Detail & Related papers  (2024-06-23T05:02:21Z)
• QFMTS: Generating Query-Focused Summaries over Multi-Table Inputs [63.98556480088152]
  Table summarization is a crucial task aimed at condensing information into concise and comprehensible textual summaries. We propose a novel method to address these limitations by introducing query-focused multi-table summarization. Our approach, which comprises a table serialization module, a summarization controller, and a large language model, generates query-dependent table summaries tailored to users' information needs.
  arXiv  Detail & Related papers  (2024-05-08T15:05:55Z)
• 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)
• Meta Operator for Complex Query Answering on Knowledge Graphs [58.340159346749964]
  We argue that different logical operator types, rather than the different complex query types, are the key to improving generalizability. We propose a meta-learning algorithm to learn the meta-operators with limited data and adapt them to different instances of operators under various complex queries. Empirical results show that learning meta-operators is more effective than learning original CQA or meta-CQA models.
  arXiv  Detail & Related papers  (2024-03-15T08:54:25Z)
• 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)
• Query Embedding on Hyper-relational Knowledge Graphs [0.4779196219827507]
  Multi-hop logical reasoning is an established problem in the field of representation learning on knowledge graphs. We extend the multi-hop reasoning problem to hyper-relational KGs allowing to tackle this new type of complex queries.
  arXiv  Detail & Related papers  (2021-06-15T14:08:50Z)
• Counting Query Answers over a DL-Lite Knowledge Base (extended version) [14.504450881786214]
  We study the data complexity of query answering over a Knowledge Base (KB) We improve upon existing results by providing a PTIME and coNP lower bounds, and upper bounds in PTIME and LOGSPACE.
  arXiv  Detail & Related papers  (2020-05-12T16:01:09Z)
• 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)
• Containment of Simple Regular Path Queries [1.869065967043578]
  Testing containment of queries is a fundamental reasoning task in knowledge representation. We focus here on severely restricted fragments, which are known to be highly relevant in practice. We obtain a detailed overview of the complexity of the containment problem, depending on the features used in the regular expressions of the queries, with completeness results for np, pitwo, pspace or expspace.
  arXiv  Detail & Related papers  (2020-03-09T21:05:29Z)

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.