Efficiency of Query Evaluation Under Guarded TGDs: The Unbounded Arity Case

• URL: http://arxiv.org/abs/2101.11727v1
• Date: Wed, 27 Jan 2021 22:32:16 GMT
• Title: Efficiency of Query Evaluation Under Guarded TGDs: The Unbounded Arity Case
• Authors: Cristina Feier
• Abstract summary: The paper analyzes the parameterized complexity of evaluating Ontology Mediated Queries (OMQs) based on Guarded TGDs (GTGDs) and Unions of Conjunctive Queries (UCQs)
• Score: 1.370633147306388
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The paper analyzes the parameterized complexity of evaluating Ontology Mediated Queries (OMQs) based on Guarded TGDs (GTGDs) and Unions of Conjunctive Queries (UCQs), in the setting where relational symbols might have unbounded arity and where the parameter is the size of the OMQ. It establishes exact criteria for fixed-parameter tractability (fpt) evaluation of recursively enumerable classes of such OMQs (under the widely held Exponential Time Hypothesis). One of the main technical tools introduced in the paper is an fpt-reduction from deciding parameterized uniform CSPs to parameterized OMQ evaluation. A fundamental feature of the reduction is preservation of measures which are known to be essential for classifying classes of parameterized uniform CSPs: submodular width (according to the well known result of Marx for unbounded-arity schemas) and treewidth (according to the well known result of Grohe for bounded-arity schemas). As such, the reduction can be employed to obtain hardness results for evaluation of classes of parameterized OMQs both in the unbounded and in the bounded arity case. Previously, in the case of bounded arity schemas, this has been tackled using a technique requiring full introspection into the construction employed by Grohe.

Related papers

• How to Prune Your Language Model: Recovering Accuracy on the "Sparsity May Cry'' Benchmark [60.72725673114168]
  We revisit the question of accurate BERT-pruning during fine-tuning on downstream datasets. We propose a set of general guidelines for successful pruning, even on the challenging SMC benchmark.
  arXiv  Detail & Related papers  (2023-12-21T03:11:30Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  The sequential decision-making problem is statistically learnable if it admits a low-rank structure modeled by predictive state representations (PSRs) This paper proposes the first known UCB-type approach for PSRs, featuring a novel bonus term that upper bounds the total variation distance between the estimated and true models. In contrast to existing approaches for PSRs, our UCB-type algorithms enjoy computational tractability, last-iterate guaranteed near-optimal policy, and guaranteed model accuracy.
  arXiv  Detail & Related papers  (2023-07-01T18:35:21Z)
• MM Algorithms to Estimate Parameters in Continuous-time Markov Chains [0.0]
  We introduce the class parametric CTMCs, where transition rates are functions over a set of parameters. We present iterative likelihood estimation algorithms for parametric CTMCs covering two learning scenarios.
  arXiv  Detail & Related papers  (2023-02-16T21:25:27Z)
• GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyond [101.5329678997916]
  We study sample efficient reinforcement learning (RL) under the general framework of interactive decision making. We propose a novel complexity measure, generalized eluder coefficient (GEC), which characterizes the fundamental tradeoff between exploration and exploitation. We show that RL problems with low GEC form a remarkably rich class, which subsumes low Bellman eluder dimension problems, bilinear class, low witness rank problems, PO-bilinear class, and generalized regular PSR.
  arXiv  Detail & Related papers  (2022-11-03T16:42:40Z)
• Probabilistic Entity Representation Model for Chain Reasoning over Knowledge Graphs [18.92547855877845]
  We propose a Probabilistic Entity Representation Model (PERM) for logical reasoning over Knowledge Graphs. PERM encodes entities as a Multivariate Gaussian density with mean and covariance parameters to capture semantic position and smooth decision boundary. We demonstrate PERM's competence on a COVID-19 drug-repurposing case study and show that our proposed work is able to recommend drugs with substantially better F1 than current methods.
  arXiv  Detail & Related papers  (2021-10-26T09:26:10Z)
• A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
  Policy gradient (PG) is one of the most popular reinforcement learning (RL) problems. "vanilla" theoretical understanding of PG trajectory is one of the most popular methods for solving RL problems.
  arXiv  Detail & Related papers  (2021-07-23T19:38:17Z)
• Exact Recovery in the General Hypergraph Stochastic Block Model [92.28929858529679]
  This paper investigates fundamental limits of exact recovery in the general d-uniform hypergraph block model (d-HSBM) We show that there exists a sharp threshold such that exact recovery is achievable above the threshold and impossible below it.
  arXiv  Detail & Related papers  (2021-05-11T03:39:08Z)
• Autoregressive Hidden Markov Models with partial knowledge on latent space applied to aero-engines prognostics [2.179313476241343]
  This paper describes an Autoregressive Partially-hidden Markov model (ARPHMM) for fault detection and prognostics of equipments based on sensors' data. We show how to apply this model to estimate the remaining useful life based on health indicators.
  arXiv  Detail & Related papers  (2021-05-01T10:23:22Z)
• Lower bounds in multiple testing: A framework based on derandomized proxies [107.69746750639584]
  This paper introduces an analysis strategy based on derandomization, illustrated by applications to various concrete models. We provide numerical simulations of some of these lower bounds, and show a close relation to the actual performance of the Benjamini-Hochberg (BH) algorithm.
  arXiv  Detail & Related papers  (2020-05-07T19:59:51Z)
• 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)
• The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs [10.042878093985458]
  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.
  arXiv  Detail & Related papers  (2019-12-28T11:08:33Z)

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.