The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs

• URL: http://arxiv.org/abs/1912.12442v1
• Date: Sat, 28 Dec 2019 11:08:33 GMT
• Title: The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs
• Authors: Pablo Barcelo, Victor Dalmau, Cristina Feier, Carsten Lutz, Andreas Pieris
• Abstract summary: Ontology-mediated querying and querying in the presence of constraints are two key database problems. We study the limits of efficient query evaluation in the context of guarded and frontier-guarded TGDs and on UCQs as the actual queries.
• Score: 10.042878093985458
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Ontology-mediated querying and querying in the presence of constraints are two key database problems where tuple-generating dependencies (TGDs) play a central role. In ontology-mediated querying, TGDs can formalize the ontology and thus derive additional facts from the given data, while in querying in the presence of constraints, they restrict the set of admissible databases. In this work, we study the limits of efficient query evaluation in the context of the above two problems, focussing on guarded and frontier-guarded TGDs and on UCQs as the actual queries. We show that a class of ontology-mediated queries (OMQs) based on guarded TGDs can be evaluated in FPT iff the OMQs in the class are equivalent to OMQs in which the actual query has bounded treewidth, up to some reasonable assumptions. For querying in the presence of constraints, we consider classes of constraint-query specifications (CQSs) that bundle a set of constraints with an actual query. We show a dichotomy result for CQSs based on guarded TGDs that parallels the one for OMQs except that, additionally, FPT coincides with PTime combined complexity. The proof is based on a novel connection between OMQ and CQS evaluation. Using a direct proof, we also show a similar dichotomy result, again up to some reasonable assumptions, for CQSs based on frontier-guarded TGDs with a bounded number of atoms in TGD heads. Our results on CQSs can be viewed as extensions of Grohe's well-known characterization of the tractable classes of CQs (without constraints). Like Grohe's characterization, all the above results assume that the arity of relation symbols is bounded by a constant. We also study the associated meta problems, i.e., whether a given OMQ or CQS is equivalent to one in which the actual query has bounded treewidth.

Related papers

• 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)
• IfQA: A Dataset for Open-domain Question Answering under Counterfactual Presuppositions [54.23087908182134]
  We introduce the first large-scale counterfactual open-domain question-answering (QA) benchmarks, named IfQA. The IfQA dataset contains over 3,800 questions that were annotated by crowdworkers on relevant Wikipedia passages. The unique challenges posed by the IfQA benchmark will push open-domain QA research on both retrieval and counterfactual reasoning fronts.
  arXiv  Detail & Related papers  (2023-05-23T12:43:19Z)
• Toward Unsupervised Realistic Visual Question Answering [70.67698100148414]
  We study the problem of realistic VQA (RVQA), where a model has to reject unanswerable questions (UQs) and answer answerable ones (AQs) We first point out 2 drawbacks in current RVQA research, where (1) datasets contain too many unchallenging UQs and (2) a large number of annotated UQs are required for training. We propose a new testing dataset, RGQA, which combines AQs from an existing VQA dataset with around 29K human-annotated UQs. This combines pseudo UQs obtained by randomly pairing images and questions, with an
  arXiv  Detail & Related papers  (2023-03-09T06:58:29Z)
• RoMQA: A Benchmark for Robust, Multi-evidence, Multi-answer Question Answering [87.18962441714976]
  We introduce RoMQA, the first benchmark for robust, multi-evidence, multi-answer question answering (QA) We evaluate state-of-the-art large language models in zero-shot, few-shot, and fine-tuning settings, and find that RoMQA is challenging. Our results show that RoMQA is a challenging benchmark for large language models, and provides a quantifiable test to build more robust QA methods.
  arXiv  Detail & Related papers  (2022-10-25T21:39:36Z)
• Semantic Framework based Query Generation for Temporal Question Answering over Knowledge Graphs [19.851986862305623]
  We propose a temporal question answering method, SF-TQA, which generates query graphs by exploring the relevant facts of mentioned entities. Our evaluations show that SF-TQA significantly outperforms existing methods on two benchmarks over different knowledge graphs.
  arXiv  Detail & Related papers  (2022-10-10T08:40:28Z)
• Ontology-Mediated Querying on Databases of Bounded Cliquewidth [10.880181451789262]
  We study the evaluation of ontology-mediated queries (OMQs) on databases of bounded cliquewidth. Our main contribution is a detailed analysis of the dependence of the running time on the parameter, exhibiting several interesting effects.
  arXiv  Detail & Related papers  (2022-05-04T17:13:08Z)
• Knowledge Base Question Answering by Case-based Reasoning over Subgraphs [81.22050011503933]
  We show that our model answers queries requiring complex reasoning patterns more effectively than existing KG completion algorithms. The proposed model outperforms or performs competitively with state-of-the-art models on several KBQA benchmarks.
  arXiv  Detail & Related papers  (2022-02-22T01:34:35Z)
• Efficiency of Query Evaluation Under Guarded TGDs: The Unbounded Arity Case [1.370633147306388]
  The paper analyzes the parameterized complexity of evaluating Ontology Mediated Queries (OMQs) based on Guarded TGDs (GTGDs) and Unions of Conjunctive Queries (UCQs)
  arXiv  Detail & Related papers  (2021-01-27T22:32:16Z)
• 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)
• 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.