Counting Query Answers over a DL-Lite Knowledge Base (extended version)

• URL: http://arxiv.org/abs/2005.05886v3
• Date: Fri, 17 Jul 2020 05:23:03 GMT
• Title: Counting Query Answers over a DL-Lite Knowledge Base (extended version)
• Authors: Diego Calvanese and Julien Corman and Davide Lanti and Simon Razniewski
• Abstract summary: 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.
• Score: 14.504450881786214
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: Counting answers to a query is an operation supported by virtually all database management systems. In this paper we focus on counting answers over a Knowledge Base (KB), which may be viewed as a database enriched with background knowledge about the domain under consideration. In particular, we place our work in the context of Ontology-Mediated Query Answering/Ontology-based Data Access (OMQA/OBDA), where the language used for the ontology is a member of the DL-Lite family and the data is a (usually virtual) set of assertions. We study the data complexity of query answering, for different members of the DL-Lite family that include number restrictions, and for variants of conjunctive queries with counting that differ with respect to their shape (connected, branching, rooted). We improve upon existing results by providing a PTIME and coNP lower bounds, and upper bounds in PTIME and LOGSPACE. For the latter case, we define a novel query rewriting technique into first-order logic with counting.

Related papers

• DAGE: DAG Query Answering via Relational Combinator with Logical Constraints [24.60431781360608]
  We propose a query embedding method for DAG queries called DAGE. DAGE combines the possibly multiple paths between two nodes into a single path with a trainable operator. We show that it is possible to implement DAGE on top of existing query embedding methods.
  arXiv  Detail & Related papers  (2024-10-29T15:02:48Z)
• Text2SQL is Not Enough: Unifying AI and Databases with TAG [47.45480855418987]
  Table-Augmented Generation (TAG) is a paradigm for answering natural language questions over databases. We develop benchmarks to study the TAG problem and find that standard methods answer no more than 20% of queries correctly.
  arXiv  Detail & Related papers  (2024-08-27T00:50:14Z)
• UQE: A Query Engine for Unstructured Databases [71.49289088592842]
  We investigate the potential of Large Language Models to enable unstructured data analytics. We propose a new Universal Query Engine (UQE) that directly interrogates and draws insights from unstructured data collections.
  arXiv  Detail & Related papers  (2024-06-23T06:58:55Z)
• 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)
• Consistent Query Answering for Existential Rules with Closed Predicates [2.559168320734115]
  Consistent Query Answering (CQA) is an inconsistency-tolerant approach to data access in databases. We study CQA in databases with data dependencies expressed by existential rules.
  arXiv  Detail & Related papers  (2024-01-11T08:48:40Z)
• Uni-Parser: Unified Semantic Parser for Question Answering on Knowledge Base and Database [86.03294330305097]
  We propose a unified semantic element for question answering (QA) on both knowledge bases (KB) and databases (DB) We introduce the primitive (relation and entity in KB, table name, column name and cell value in DB) as an essential element in our framework. We leverage the generator to predict final logical forms by altering and composing topranked primitives with different operations.
  arXiv  Detail & Related papers  (2022-11-09T19:33:27Z)
• A Benchmark for Generalizable and Interpretable Temporal Question Answering over Knowledge Bases [67.33560134350427]
  TempQA-WD is a benchmark dataset for temporal reasoning. It is based on Wikidata, which is the most frequently curated, openly available knowledge base.
  arXiv  Detail & Related papers  (2022-01-15T08:49:09Z)
• Dual Reader-Parser on Hybrid Textual and Tabular Evidence for Open Domain Question Answering [78.9863753810787]
  A large amount of world's knowledge is stored in structured databases. query languages can answer questions that require complex reasoning, as well as offering full explainability.
  arXiv  Detail & Related papers  (2021-08-05T22:04:13Z)
• 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)
• 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.