Parallelisable Existential Rules: a Story of Pieces

• URL: http://arxiv.org/abs/2107.06054v1
• Date: Tue, 13 Jul 2021 13:09:14 GMT
• Title: Parallelisable Existential Rules: a Story of Pieces
• Authors: Maxime Buron, Marie-Laure Mugnier, Micha\"el Thomazo
• Abstract summary: 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.
• Score: 2.20439695290991
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we consider existential rules, an expressive formalism well suited to the representation of ontological knowledge and data-to-ontology mappings in the context of ontology-based data integration. The chase is a fundamental tool to do reasoning with existential rules as it computes all the facts entailed by the rules from a database instance. We introduce parallelisable sets of existential rules, for which the chase can be computed in a single breadth-first step from any instance. The question we investigate is the characterization of such rule sets. 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. The pieceful class includes in particular frontier-guarded existential rules and (plain) datalog. We also give another characterization of parallelisable rule sets in terms of rule composition based on rewriting.

Related papers

• Seqret: Mining Rule Sets from Event Sequences [29.69265042723031]
  We study the problem of discovering conditional and unconditional dependencies from event sequence data.<n>We do so by discovering rules of the form $X rightarrow Y$ where $X$ and $Y$ are sequential patterns.<n>We propose the Seqret method to discover high-quality rule sets in practice.
  arXiv  Detail & Related papers  (2025-05-09T13:44:15Z)
• Rule Extrapolation in Language Models: A Study of Compositional Generalization on OOD Prompts [14.76420070558434]
  Rule extrapolation describes OOD scenarios, where the prompt violates at least one rule. We focus on formal languages, which are defined by the intersection of rules. We lay the first stones of a normative theory of rule extrapolation, inspired by the Solomonoff prior in algorithmic information theory.
  arXiv  Detail & Related papers  (2024-09-09T22:36:35Z)
• Symbolic Working Memory Enhances Language Models for Complex Rule Application [87.34281749422756]
  Large Language Models (LLMs) have shown remarkable reasoning performance but struggle with multi-step deductive reasoning. We propose augmenting LLMs with external working memory and introduce a neurosymbolic framework for rule application. Our framework iteratively performs symbolic rule grounding and LLM-based rule implementation.
  arXiv  Detail & Related papers  (2024-08-24T19:11:54Z)
• 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)
• Neuro-Symbolic Temporal Point Processes [13.72758658973969]
  We introduce a neural-symbolic rule induction framework within the temporal point process model. The negative log-likelihood is the loss that guides the learning, where the explanatory logic rules and their weights are learned end-to-end. Our approach showcases notable efficiency and accuracy across synthetic and real datasets.
  arXiv  Detail & Related papers  (2024-06-06T09:52:56Z)
• Can LLMs Reason with Rules? Logic Scaffolding for Stress-Testing and Improving LLMs [87.34281749422756]
  Large language models (LLMs) have achieved impressive human-like performance across various reasoning tasks. However, their mastery of underlying inferential rules still falls short of human capabilities. We propose a logic scaffolding inferential rule generation framework, to construct an inferential rule base, ULogic.
  arXiv  Detail & Related papers  (2024-02-18T03:38:51Z)
• RulE: Knowledge Graph Reasoning with Rule Embedding [69.31451649090661]
  We propose a principled framework called textbfRulE (stands for Rule Embedding) to leverage logical rules to enhance KG reasoning. RulE learns rule embeddings from existing triplets and first-order rules by jointly representing textbfentities, textbfrelations and textbflogical rules in a unified embedding space. Results on multiple benchmarks reveal that our model outperforms the majority of existing embedding-based and rule-based approaches.
  arXiv  Detail & Related papers  (2022-10-24T06:47:13Z)
• Truly Unordered Probabilistic Rule Sets for Multi-class Classification [0.0]
  We propose TURS, for Truly Unordered Rule Sets. We first formalise the problem of learning truly unordered rule sets. We then develop a two-phase algorithm that learns rule sets by carefully growing rules.
  arXiv  Detail & Related papers  (2022-06-17T14:34:35Z)
• 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)
• Automating Defeasible Reasoning in Law [0.0]
  We study defeasible reasoning in rule-based systems, in particular about legal norms and contracts. We identify rule modifier that specify how rules interact and how they can be overridden. We then define rule transformations that eliminate these modifier, leading to a translation of rules to formulas.
  arXiv  Detail & Related papers  (2022-05-15T17:14:15Z)
• Learning Symbolic Rules for Reasoning in Quasi-Natural Language [74.96601852906328]
  We build a rule-based system that can reason with natural language input but without the manual construction of rules. We propose MetaQNL, a "Quasi-Natural" language that can express both formal logic and natural language sentences. Our approach achieves state-of-the-art accuracy on multiple reasoning benchmarks.
  arXiv  Detail & Related papers  (2021-11-23T17:49:00Z)
• 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)
• Theoretical Rule-based Knowledge Graph Reasoning by Connectivity Dependency Discovery [2.945948598480997]
  We present a theory for rule-based knowledge graph reasoning, based on which the connectivity dependencies in the graph are captured via multiple rule types. Results show that our RuleDict model not only provides precise rules to interpret new triples, but also achieves state-of-the-art performances on one benchmark knowledge graph completion task.
  arXiv  Detail & Related papers  (2020-11-12T03:00:20Z)
• 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)

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.