Second-Order Specifications and Quantifier Elimination for Consistent Query Answering in Databases

• URL: http://arxiv.org/abs/2108.08423v2
• Date: Fri, 20 Aug 2021 01:04:54 GMT
• Title: Second-Order Specifications and Quantifier Elimination for Consistent Query Answering in Databases
• Authors: Leopoldo Bertossi
• Abstract summary: We show how to use the repair programs to transform the problem of consistent query answering into a problem of reasoning w.r.t. It also investigated how a first-order theory can be obtained instead by applying second-order quantifier elimination techniques.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Consistent answers to a query from a possibly inconsistent database are answers that are simultaneously retrieved from every possible repair of the database. Repairs are consistent instances that minimally differ from the original inconsistent instance. It has been shown before that database repairs can be specified as the stable models of a disjunctive logic program. In this paper we show how to use the repair programs to transform the problem of consistent query answering into a problem of reasoning w.r.t. a theory written in second-order predicate logic. It also investigated how a first-order theory can be obtained instead by applying second-order quantifier elimination techniques.

Related papers

• Effective Instruction Parsing Plugin for Complex Logical Query Answering on Knowledge Graphs [51.33342412699939]
  Knowledge Graph Query Embedding (KGQE) aims to embed First-Order Logic (FOL) queries in a low-dimensional KG space for complex reasoning over incomplete KGs. Recent studies integrate various external information (such as entity types and relation context) to better capture the logical semantics of FOL queries. We propose an effective Query Instruction Parsing (QIPP) that captures latent query patterns from code-like query instructions.
  arXiv  Detail & Related papers  (2024-10-27T03:18:52Z)
• LLM-R2: A Large Language Model Enhanced Rule-based Rewrite System for Boosting Query Efficiency [65.01402723259098]
  We propose a novel method of query rewrite named LLM-R2, adopting a large language model (LLM) to propose possible rewrite rules for a database rewrite system. Experimental results have shown that our method can significantly improve the query execution efficiency and outperform the baseline methods.
  arXiv  Detail & Related papers  (2024-04-19T13:17:07Z)
• Computational Complexity of Preferred Subset Repairs on Data-Graphs [2.254434034390529]
  We study the problem of computing prioritized repairs over graph databases with data values. We present several preference criteria based on the standard subset repair semantics. We show that it is possible to maintain the same computational complexity as in the case where no preference criterion is available for exploitation.
  arXiv  Detail & Related papers  (2024-02-14T15:51:55Z)
• 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)
• Inconsistency Handling in Prioritized Databases with Universal Constraints: Complexity Analysis and Links with Active Integrity Constraints [5.87010466783654]
  This paper revisits the problem of repairing and querying inconsistent databases equipped with universal constraints. We adopt symmetric difference repairs, in which both deletions and additions of facts can be used to restore consistency. We show how existing notions of optimal repairs, defined for simpler denial constraints and repairs solely based on fact deletion, can be suitably extended to our richer setting.
  arXiv  Detail & Related papers  (2023-06-06T09:17:56Z)
• QUADRo: Dataset and Models for QUestion-Answer Database Retrieval [97.84448420852854]
  Given a database (DB) of question/answer (q/a) pairs, it is possible to answer a target question by scanning the DB for similar questions. We build a large scale DB of 6.3M q/a pairs, using public questions, and design a new system based on neural IR and a q/a pair reranker. We show that our DB-based approach is competitive with Web-based methods, i.e., a QA system built on top the BING search engine.
  arXiv  Detail & Related papers  (2023-03-30T00:42:07Z)
• Searching for Better Database Queries in the Outputs of Semantic Parsers [16.221439565760058]
  In this paper, we consider the case when, at the test time, the system has access to an external criterion that evaluates the generated queries. The criterion can vary from checking that a query executes without errors to verifying the query on a set of tests. We apply our approach to the state-of-the-art semantics and report that it allows us to find many queries passing all the tests on different datasets.
  arXiv  Detail & Related papers  (2022-10-13T17:20:45Z)
• LoL: A Comparative Regularization Loss over Query Reformulation Losses for Pseudo-Relevance Feedback [70.44530794897861]
  Pseudo-relevance feedback (PRF) has proven to be an effective query reformulation technique to improve retrieval accuracy. Existing PRF methods independently treat revised queries originating from the same query but using different numbers of feedback documents. We propose the Loss-over-Loss (LoL) framework to compare the reformulation losses between different revisions of the same query during training.
  arXiv  Detail & Related papers  (2022-04-25T10:42:50Z)
• Querying Inconsistent Prioritized Data with ORBITS: Algorithms, Implementation, and Experiments [12.952483242045366]
  We investigate practical algorithms for inconsistency-tolerant query answering over prioritized knowledge bases. We consider three well-known semantics (AR, IAR and brave) based upon two notions of optimal repairs (Pareto and completion)
  arXiv  Detail & Related papers  (2022-02-16T10:44:39Z)
• Logic Embeddings for Complex Query Answering [56.25151854231117]
  We propose Logic Embeddings, a new approach to embedding complex queries that uses Skolemisation to eliminate existential variables for efficient querying. We show that Logic Embeddings are competitively fast and accurate in query answering over large, incomplete knowledge graphs, outperform on negation queries, and in particular, provide improved modeling of answer uncertainty.
  arXiv  Detail & Related papers  (2021-02-28T07:52:37Z)
• Fact-aware Sentence Split and Rephrase with Permutation Invariant Training [93.66323661321113]
  Sentence Split and Rephrase aims to break down a complex sentence into several simple sentences with its meaning preserved. Previous studies tend to address the issue by seq2seq learning from parallel sentence pairs. We introduce Permutation Training to verifies the effects of order variance in seq2seq learning for this task.
  arXiv  Detail & Related papers  (2020-01-16T07:30:19Z)

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.