Complete Approximations of Incomplete Queries

• URL: http://arxiv.org/abs/2407.20932v1
• Date: Tue, 30 Jul 2024 16:13:42 GMT
• Title: Complete Approximations of Incomplete Queries
• Authors: Julien Corman, Werner Nutt, Ognjen Savković,
• Abstract summary: We investigate whether a query can be fully answered, as if all data were available. If not, we explore reformulating the query into either Maximal Complete approximations (MCSs) or the Minimal Complete Generalization (MCG)
• Score: 0.9626666671366836
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper studies the completeness of conjunctive queries over a partially complete database and the approximation of incomplete queries. Given a query and a set of completeness rules (a special kind of tuple generating dependencies) that specify which parts of the database are complete, we investigate whether the query can be fully answered, as if all data were available. If not, we explore reformulating the query into either Maximal Complete Specializations (MCSs) or the (unique up to equivalence) Minimal Complete Generalization (MCG) that can be fully answered, that is, the best complete approximations of the query from below or above in the sense of query containment. We show that the MSG can be characterized as the least fixed-point of a monotonic operator in a preorder. Then, we show that an MCS can be computed by recursive backward application of completeness rules. We study the complexity of both problems and discuss implementation techniques that rely on an ASP and Prolog engines, respectively.

Related papers

• Can we Retrieve Everything All at Once? ARM: An Alignment-Oriented LLM-based Retrieval Method [48.14236175156835]
  ARM aims to better align the question with the organization of the data collection by exploring relationships among data objects. It outperforms standard RAG with query decomposition by up to 5.2 pt in execution accuracy and agentic RAG (ReAct) by up to 15.9 pt. It achieves up to 5.5 pt and 19.3 pt higher F1 match scores compared to these approaches.
  arXiv  Detail & Related papers  (2025-01-30T18:07:19Z)
• Reasoning-Aware Query-Focused Summarization over Multi-Table Data [1.325953054381901]
  We propose QueryTableSummarizer++, an end-to-end generative framework leveraging large language models (LLMs) Our method eliminates the need for intermediate serialization steps and directly generates query-relevant summaries. Experiments on a benchmark dataset demonstrate that QueryTableSummarizer++ significantly outperforms state-of-the-art baselines in terms of BLEU, ROUGE, and F1-score.
  arXiv  Detail & Related papers  (2024-12-12T06:04:31Z)
• 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)
• 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)
• Generalizing Level Ranking Constraints for Monotone and Convex Aggregates [0.0]
  In answer set programming (ASP), answer sets capture solutions to search problems of interest. One viable implementation strategy is provided by translation-based ASP. We take level ranking constraints into reconsideration, aiming at their generalizations to cover aggregate-based extensions of ASP.
  arXiv  Detail & Related papers  (2023-08-30T09:04:39Z)
• 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)
• 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)
• 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)
• Improving One-stage Visual Grounding by Recursive Sub-query Construction [102.47477888060801]
  We improve one-stage visual grounding by addressing current limitations on grounding long and complex queries. We show our new one-stage method obtains 5.0%, 4.5%, 7.5%, 12.8% absolute improvements over the state-of-the-art one-stage baseline.
  arXiv  Detail & Related papers  (2020-08-03T17:43:30Z)
• 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)

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.