Characterizing Boundedness in Chase Variants

• URL: http://arxiv.org/abs/2004.10030v1
• Date: Tue, 21 Apr 2020 14:07:10 GMT
• Title: Characterizing Boundedness in Chase Variants
• Authors: Stathis Delivorias, Michel Lecl\`ere, Marie-Laure Mugnier, Federico Ulliana
• Abstract summary: 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.
• Score: 1.7033055327465234
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Existential rules are a positive fragment of first-order logic that generalizes function-free Horn rules by allowing existentially quantified variables in rule heads. This family of languages has recently attracted significant interest in the context of ontology-mediated query answering. Forward chaining, also known as the chase, is a fundamental tool for computing universal models of knowledge bases, which consist of existential rules and facts. Several chase variants have been defined, which differ on the way they handle redundancies. A set of existential rules is bounded if it ensures the existence of a bound on the depth of the chase, independently from any set of facts. Deciding if a set of rules is bounded is an undecidable problem for all chase variants. Nevertheless, when computing universal models, knowing that a set of rules is bounded for some chase variant does not help much in practice if the bound remains unknown or even very large. Hence, 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 identify a general property which, when satisfied by a chase variant, leads to the decidability of k-boundedness. We then show that the main chase variants satisfy this property, namely the oblivious, semi-oblivious (aka Skolem), and restricted chase, as well as their breadth-first versions. This paper is under consideration for publication in Theory and Practice of Logic Programming.

Related papers

• Faithful Differentiable Reasoning with Reshuffled Region-based Embeddings [62.93577376960498]
  Knowledge graph embedding methods learn geometric representations of entities and relations to predict plausible missing knowledge.<n>We propose RESHUFFLE, a model based on ordering constraints that can faithfully capture a much larger class of rule bases.<n>The entity embeddings in our framework can be learned by a Graph Neural Network (GNN), which effectively acts as a differentiable rule base.
  arXiv  Detail & Related papers  (2024-06-13T18:37:24Z)
• Contextual Multinomial Logit Bandits with General Value Functions [47.06746975822902]
  Contextual multinomial logit (MNL) bandits capture many real-world assortment recommendation problems such as online retailing/advertising. We consider contextual MNL bandits with a general value function class that contains the ground truth, borrowing ideas from a recent trend of studies on contextual bandits. Specifically, we consider both the computation and the adversarial settings, and propose a suite of algorithms, each with different-regret trade-off.
  arXiv  Detail & Related papers  (2024-02-12T23:50:44Z)
• ChatRule: Mining Logical Rules with Large Language Models for Knowledge Graph Reasoning [107.61997887260056]
  We propose a novel framework, ChatRule, unleashing the power of large language models for mining logical rules over knowledge graphs. Specifically, the framework is initiated with an LLM-based rule generator, leveraging both the semantic and structural information of KGs. To refine the generated rules, a rule ranking module estimates the rule quality by incorporating facts from existing KGs.
  arXiv  Detail & Related papers  (2023-09-04T11:38:02Z)
• Semi-Oblivious Chase Termination for Linear Existential Rules: An Experimental Study [5.936402320555635]
  The chase procedure is a fundamental algorithmic tool in databases that allows us to reason with constraints. It takes as input a database and a set of constraints, and iteratively completes the database as dictated by the constraints. A key challenge, though, is the fact that it may not terminate, which leads to the problem of checking whether it terminates given a database and a set of constraints.
  arXiv  Detail & Related papers  (2023-03-22T18:21:01Z)
• Machine Learning with Probabilistic Law Discovery: A Concise Introduction [77.34726150561087]
  Probabilistic Law Discovery (PLD) is a logic based Machine Learning method, which implements a variant of probabilistic rule learning. PLD is close to Decision Tree/Random Forest methods, but it differs significantly in how relevant rules are defined. This paper outlines the main principles of PLD, highlight its benefits and limitations and provide some application guidelines.
  arXiv  Detail & Related papers  (2022-12-22T17:40:13Z)
• 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)
• Non-Uniformly Terminating Chase: Size and Complexity [8.250374560598493]
  We focus on guarded-generating dependencies (TGDs), which form a robust rule-based termination. One of our main findings is that non-uniform semi-oblivious chase for guarded TGDs is feasible in time w.r.t the database. We show that basic techniques such as simplification and linearization, originally introduced in the context of ontological query answering, can be safely applied to the chase termination problem.
  arXiv  Detail & Related papers  (2022-04-22T09:07:08Z)
• 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)
• 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)
• Causal Expectation-Maximisation [70.45873402967297]
  We show that causal inference is NP-hard even in models characterised by polytree-shaped graphs. We introduce the causal EM algorithm to reconstruct the uncertainty about the latent variables from data about categorical manifest variables. We argue that there appears to be an unnoticed limitation to the trending idea that counterfactual bounds can often be computed without knowledge of the structural equations.
  arXiv  Detail & Related papers  (2020-11-04T10:25:13Z)
• RNNLogic: Learning Logic Rules for Reasoning on Knowledge Graphs [91.71504177786792]
  This paper studies learning logic rules for reasoning on knowledge graphs. Logic rules provide interpretable explanations when used for prediction as well as being able to generalize to other tasks. Existing methods either suffer from the problem of searching in a large search space or ineffective optimization due to sparse rewards.
  arXiv  Detail & Related papers  (2020-10-08T14:47:02Z)
• Oblivious and Semi-Oblivious Boundedness for Existential Rules [5.875276459237496]
  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.
  arXiv  Detail & Related papers  (2020-06-15T15:18:57Z)

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.