Optimised Storage for Datalog Reasoning

• URL: http://arxiv.org/abs/2312.11297v2
• Date: Tue, 19 Dec 2023 16:11:33 GMT
• Title: Optimised Storage for Datalog Reasoning
• Authors: Xinyue Zhang, Pan Hu, Yavor Nenov, Ian Horrocks
• Abstract summary: Materialisation facilitates Datalog reasoning by precomputing all consequences of the facts and the rules so that queries can be directly answered over the materialised facts. storing all materialised facts may be infeasible in practice, especially when the rules are complex and the given set of facts is large. We present a general framework that allows for the integration of such optimised storage schemes with standard materialisation algorithms.
• Score: 8.305527776204178
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Materialisation facilitates Datalog reasoning by precomputing all consequences of the facts and the rules so that queries can be directly answered over the materialised facts. However, storing all materialised facts may be infeasible in practice, especially when the rules are complex and the given set of facts is large. We observe that for certain combinations of rules, there exist data structures that compactly represent the reasoning result and can be efficiently queried when necessary. In this paper, we present a general framework that allows for the integration of such optimised storage schemes with standard materialisation algorithms. Moreover, we devise optimised storage schemes targeting at transitive rules and union rules, two types of (combination of) rules that commonly occur in practice. Our experimental evaluation shows that our approach significantly improves memory consumption, sometimes by orders of magnitude, while remaining competitive in terms of query answering time.

Related papers

• Data reification in a concurrent rely-guarantee algebra [0.0]
  Data reification (or "refinement") techniques for sequential programs are well established. A version of the Galler-Fischer equivalence relation data structure is used as an example.
  arXiv  Detail & Related papers  (2024-05-09T05:09:37Z)
• Mutual information and the encoding of contingency tables [0.4779196219827508]
  Mutual information is commonly used as a measure of similarity between labelings of a given set of objects. As argued recently, the mutual information as conventionally defined can return biased results because it neglects the information cost of the so-called contingency table. In this paper we describe an improved method for encoding contingency tables that gives a substantially better bound in typical use cases.
  arXiv  Detail & Related papers  (2024-05-08T19:49:39Z)
• Obtaining Explainable Classification Models using Distributionally Robust Optimization [12.511155426574563]
  We study generalized linear models constructed using sets of feature value rules. An inherent trade-off exists between rule set sparsity and its prediction accuracy. We propose a new formulation to learn an ensemble of rule sets that simultaneously addresses these competing factors.
  arXiv  Detail & Related papers  (2023-11-03T15:45:34Z)
• Rethinking Complex Queries on Knowledge Graphs with Neural Link Predictors [58.340159346749964]
  We propose a new neural-symbolic method to support end-to-end learning using complex queries with provable reasoning capability. We develop a new dataset containing ten new types of queries with features that have never been considered. Our method outperforms previous methods significantly in the new dataset and also surpasses previous methods in the existing dataset at the same time.
  arXiv  Detail & Related papers  (2023-04-14T11:35:35Z)
• Relational Proxies: Emergent Relationships as Fine-Grained Discriminators [52.17542855760418]
  We propose a novel approach that leverages information between the global and local part of an object for encoding its label. We design Proxies based on our theoretical findings and evaluate it on seven challenging fine-grained benchmark datasets. We also experimentally validate our theory and obtain consistent results across multiple benchmarks.
  arXiv  Detail & Related papers  (2022-10-05T11:08:04Z)
• Relational Action Bases: Formalization, Effective Safety Verification, and Invariants (Extended Version) [67.99023219822564]
  We introduce the general framework of relational action bases (RABs) RABs generalize existing models by lifting both restrictions. We demonstrate the effectiveness of this approach on a benchmark of data-aware business processes.
  arXiv  Detail & Related papers  (2022-08-12T17:03:50Z)
• Structural Learning of Probabilistic Sentential Decision Diagrams under Partial Closed-World Assumption [127.439030701253]
  Probabilistic sentential decision diagrams are a class of structured-decomposable circuits. We propose a new scheme based on a partial closed-world assumption: data implicitly provide the logical base of the circuit. Preliminary experiments show that the proposed approach might properly fit training data, and generalize well to test data, provided that these remain consistent with the underlying logical base.
  arXiv  Detail & Related papers  (2021-07-26T12:01:56Z)
• String Theories involving Regular Membership Predicates: From Practice to Theory and Back [12.98284167710378]
  An algorithm for the satisfiability problem for systems of string constraints requires a thorough understanding of the structure of constraints present in the targeted cases. In this paper, we investigate benchmarks presented in the literature containing regular expression membership predicates, extract different first order logic theories, and prove their decidability undecidability. Notably, the most common theories in real-world benchmarks are PSPACE-complete and directly lead to the implementation of a more efficient algorithm to solving string constraints.
  arXiv  Detail & Related papers  (2021-05-15T13:13:50Z)
• Parsimonious Inference [0.0]
  Parsimonious inference is an information-theoretic formulation of inference over arbitrary architectures. Our approaches combine efficient encodings with prudent sampling strategies to construct predictive ensembles without cross-validation.
  arXiv  Detail & Related papers  (2021-03-03T04:13:14Z)
• Learning Implicitly with Noisy Data in Linear Arithmetic [94.66549436482306]
  We extend implicit learning in PAC-Semantics to handle intervals and threshold uncertainty in the language of linear arithmetic. We show that our implicit approach to learning optimal linear programming objective constraints significantly outperforms an explicit approach in practice.
  arXiv  Detail & Related papers  (2020-10-23T19:08:46Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  We present a general framework for mining constraints from data. In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem. We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
  arXiv  Detail & Related papers  (2020-06-18T20:09:53Z)

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.