Oblivious and Semi-Oblivious Boundedness for Existential Rules

• URL: http://arxiv.org/abs/2006.08467v1
• Date: Mon, 15 Jun 2020 15:18:57 GMT
• Title: Oblivious and Semi-Oblivious Boundedness for Existential Rules
• Authors: Pierre Bourhis and Michel Lecl\`ere and Marie-Laure Mugnier and Sophie Tison and Federico Ulliana and Lily Galois
• Abstract summary: We study the notion of boundedness in the context of positive existential rules. By focussing our attention on the oblivious and the semi-oblivious chase variants, we give a characterization of boundedness. We show that it is decidable to recognize if a set of rules is bounded for several classes and outline the complexity of the problem.
• Score: 5.875276459237496
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the notion of boundedness in the context of positive existential rules, that is, whether there exists an upper bound to the depth of the chase procedure, that is independent from the initial instance. By focussing our attention on the oblivious and the semi-oblivious chase variants, we give a characterization of boundedness in terms of FO-rewritability and chase termination. We show that it is decidable to recognize if a set of rules is bounded for several classes and outline the complexity of the problem. This report contains the paper published at IJCAI 2019 and an appendix with full proofs.

Related papers

• Polynomial-Time Relational Probabilistic Inference in Open Universes [14.312814866832804]
  We introduce a method of first-order probabilistic inference that satisfies both the expressive power of the language used and the tractability of the computational problem posed by reasoning.<n> Specifically, we extend sum-of-squares logic of expectation to relational settings.<n>We are able to derive the tightest bounds provable by proofs of a given degree and size and establish completeness in our sum-of-squares refutations for fixed degrees.
  arXiv  Detail & Related papers  (2025-05-07T04:14:03Z)
• Greedy Algorithm for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure [51.4953549382486]
  We study the greedy (exploitation-only) algorithm in bandit problems with a known reward structure.<n>Our characterization extends to contextual bandits and interactive decision-making with arbitrary feedback.
  arXiv  Detail & Related papers  (2025-03-06T01:51:11Z)
• Fair Exploration and Exploitation [4.368185344922342]
  We consider the fully adversarial problem in which, apart from bounded losses, there are no assumptions whatsoever on the generation of the contexts and losses. In our problem we assume that the context set is partitioned into a set of protected groups. We develop an algorithm FexEx for this problem which has remarkable efficiency.
  arXiv  Detail & Related papers  (2024-11-06T22:25:56Z)
• Unified framework for continuity of sandwiched R\'enyi divergences [0.27309692684728604]
  We prove continuity bounds for entropic quantities related to sandwiched R'enyi divergences. In a separate contribution, we use the ALAAF method, developed by some of the authors, to study the stability of approximate quantum Markov chains.
  arXiv  Detail & Related papers  (2023-08-23T21:09:54Z)
• A Measure-Theoretic Axiomatisation of Causality [55.6970314129444]
  We argue in favour of taking Kolmogorov's measure-theoretic axiomatisation of probability as the starting point towards an axiomatisation of causality. Our proposed framework is rigorously grounded in measure theory, but it also sheds light on long-standing limitations of existing frameworks.
  arXiv  Detail & Related papers  (2023-05-19T13:15:48Z)
• Normalisations of Existential Rules: Not so Innocuous! [7.260554897161947]
  We study the impact of Existential Rules on chase variants with respect to chase (non-)termination and FO-rewritability. This also leads us to study open problems related to chase termination of independent interest.
  arXiv  Detail & Related papers  (2022-06-07T09:01:56Z)
• Revisiting the General Identifiability Problem [22.201414668050123]
  We revisit the problem of general identifiability originally introduced in [Lee et al., 2019] for causal inference. We show that without such an assumption the rules of do-calculus and consequently the proposed algorithm in [Lee et al., 2019] are not sound.
  arXiv  Detail & Related papers  (2022-06-02T15:07:25Z)
• Emergence of Fermi's Golden Rule [55.73970798291771]
  Fermi's Golden Rule (FGR) applies in the limit where an initial quantum state is weakly coupled to a continuum of other final states overlapping its energy. Here we investigate what happens away from this limit, where the set of final states is discrete, with a nonzero mean level spacing.
  arXiv  Detail & Related papers  (2022-06-01T18:35:21Z)
• Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective [49.17352150219212]
  Federated AveragingFedAvg, also known as Local SGD, is one of the most popular algorithms in Federated Learning (FL) We show how to analyze this quantity from the Differential Equation (SDE) perspective.
  arXiv  Detail & Related papers  (2021-11-05T22:16:11Z)
• Discovering Useful Compact Sets of Sequential Rules in a Long Sequence [57.684967309375274]
  COSSU is an algorithm to mine small and meaningful sets of sequential rules. We show that COSSU can successfully retrieve relevant sets of closed sequential rules from a long sequence.
  arXiv  Detail & Related papers  (2021-09-15T18:25:18Z)
• A Unifying Theory of Thompson Sampling for Continuous Risk-Averse Bandits [91.3755431537592]
  This paper unifies the analysis of risk-averse Thompson sampling algorithms for the multi-armed bandit problem. Using the contraction principle in the theory of large deviations, we prove novel concentration bounds for continuous risk functionals. We show that a wide class of risk functionals as well as "nice" functions of them satisfy the continuity condition.
  arXiv  Detail & Related papers  (2021-08-25T17:09:01Z)
• Parallelisable Existential Rules: a Story of Pieces [2.20439695290991]
  We introduce parallelisable sets of existential rules, for which the chase can be computed in a single breadth-first step from any instance. We show that parallelisable rule sets are exactly those rule sets both bounded for the chase and belonging to a novel class of rules, called pieceful.
  arXiv  Detail & Related papers  (2021-07-13T13:09:14Z)
• A Weaker Faithfulness Assumption based on Triple Interactions [89.59955143854556]
  We propose a weaker assumption that we call $2$-adjacency faithfulness. We propose a sound orientation rule for causal discovery that applies under weaker assumptions.
  arXiv  Detail & Related papers  (2020-10-27T13:04:08Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  We consider algorithm-independent lower bounds for the problem of black-box optimization of functions having a bounded norm. We provide a novel proof technique for deriving lower bounds on the regret, with benefits including simplicity, versatility, and an improved dependence on the error probability.
  arXiv  Detail & Related papers  (2020-08-20T03:48:14Z)
• Characterizing Boundedness in Chase Variants [1.7033055327465234]
  We investigate the decidability of the k-boundedness problem, which asks whether the depth of the chase for a given set of rules is bounded by an integer k. We show that the main chase variants satisfy this property, namely the oblivious, semi-oblivious, and restricted chase, as well as their breadth-first versions.
  arXiv  Detail & Related papers  (2020-04-21T14:07:10Z)

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.