Enhancing Datalog Reasoning with Hypertree Decompositions
- URL: http://arxiv.org/abs/2305.06854v2
- Date: Mon, 15 May 2023 12:57:50 GMT
- Title: Enhancing Datalog Reasoning with Hypertree Decompositions
- Authors: Xinyue Zhang, Pan Hu, Yavor Nenov, Ian Horrocks
- Abstract summary: We provide algorithms that exploit hypertree decompositions for the materialisation and incremental evaluation of Datalog programs.
We combine this approach with standard Datalog reasoning algorithms in a modular fashion so that the overhead caused by the decompositions is reduced.
- Score: 17.868595375154506
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Datalog reasoning based on the semina\"ive evaluation strategy evaluates
rules using traditional join plans, which often leads to redundancy and
inefficiency in practice, especially when the rules are complex. Hypertree
decompositions help identify efficient query plans and reduce similar
redundancy in query answering. However, it is unclear how this can be applied
to materialisation and incremental reasoning with recursive Datalog programs.
Moreover, hypertree decompositions require additional data structures and thus
introduce nonnegligible overhead in both runtime and memory consumption. In
this paper, we provide algorithms that exploit hypertree decompositions for the
materialisation and incremental evaluation of Datalog programs. Furthermore, we
combine this approach with standard Datalog reasoning algorithms in a modular
fashion so that the overhead caused by the decompositions is reduced. Our
empirical evaluation shows that, when the program contains complex rules, the
combined approach is usually significantly faster than the baseline approach,
sometimes by orders of magnitude.
Related papers
- Adaptive Graph of Thoughts: Test-Time Adaptive Reasoning Unifying Chain, Tree, and Graph Structures [0.0]
We introduce Adaptive Graph of Thoughts (AGoT), a dynamic, graph-based inference framework.
AGoT enhances Large Language Models (LLMs) reasoning solely at test time.
We validate our approach on diverse benchmarks spanning multi-hop retrieval, scientific reasoning, and mathematical problem-solving.
arXiv Detail & Related papers (2025-02-07T16:54:19Z) - Score-matching-based Structure Learning for Temporal Data on Networks [17.166362605356074]
Causal discovery is a crucial initial step in establishing causality from empirical data and background knowledge.
Current score-matching-based algorithms are primarily designed to analyze independent and identically distributed (i.i.d.) data.
We have developed a new parent-finding subroutine for leaf nodes in DAGs, significantly accelerating the most time-consuming part of the process: the pruning step.
arXiv Detail & Related papers (2024-12-10T12:36:35Z) - Fuzzy Datalog$^\exists$ over Arbitrary t-Norms [5.464669506214195]
One of the main challenges in the area of Neuro-Symbolic AI is to perform logical reasoning in the presence of both neural and symbolic data.
This requires combining heterogeneous data sources such as knowledge graphs, neural model predictions, structured databases, crowd-sourced data, and many more.
We generalise the standard rule-based language Datalog with existential rules to the setting, by allowing for arbitrary t-norms in the place of classical conjunctions in rule bodies.
The resulting formalism allows us to perform reasoning about associated data with degrees of uncertainty while preserving computational complexity results and the applicability of reasoning techniques established for
arXiv Detail & Related papers (2024-03-05T12:51:40Z) - ZodiacEdge: a Datalog Engine With Incremental Rule Set Maintenance [0.0]
We tackle the incremental maintenance of Datalog inference materialisation when the rule set can be updated.
This is particularly relevant in the context of the Internet of Things and Edge computing where smart devices may need to reason over newly acquired knowledge represented as Datalog rules.
Our solution is based on an adaptation of a stratification strategy applied to a dependency hypergraph whose nodes correspond to rule sets in a Datalog program.
arXiv Detail & Related papers (2023-12-22T08:53:48Z) - When Do Program-of-Thoughts Work for Reasoning? [51.2699797837818]
We propose complexity-impacted reasoning score (CIRS) to measure correlation between code and reasoning abilities.
Specifically, we use the abstract syntax tree to encode the structural information and calculate logical complexity.
Code will be integrated into the EasyInstruct framework at https://github.com/zjunlp/EasyInstruct.
arXiv Detail & Related papers (2023-08-29T17:22:39Z) - Modeling Hierarchical Reasoning Chains by Linking Discourse Units and
Key Phrases for Reading Comprehension [80.99865844249106]
We propose a holistic graph network (HGN) which deals with context at both discourse level and word level, as the basis for logical reasoning.
Specifically, node-level and type-level relations, which can be interpreted as bridges in the reasoning process, are modeled by a hierarchical interaction mechanism.
arXiv Detail & Related papers (2023-06-21T07:34:27Z) - Hierarchical clustering with dot products recovers hidden tree structure [53.68551192799585]
In this paper we offer a new perspective on the well established agglomerative clustering algorithm, focusing on recovery of hierarchical structure.
We recommend a simple variant of the standard algorithm, in which clusters are merged by maximum average dot product and not, for example, by minimum distance or within-cluster variance.
We demonstrate that the tree output by this algorithm provides a bona fide estimate of generative hierarchical structure in data, under a generic probabilistic graphical model.
arXiv Detail & Related papers (2023-05-24T11:05:12Z) - Seminaive Materialisation in DatalogMTL [10.850687097496373]
DatalogMTL is an extension of Datalog with metric temporal operators.
We propose a materialisation-based procedure to minimise redundant computation.
Our experiments show that our optimised seminaive strategy for DatalogMTL is able to significantly reduce materialisation times.
arXiv Detail & Related papers (2022-08-15T10:04:44Z) - Deep Equilibrium Assisted Block Sparse Coding of Inter-dependent
Signals: Application to Hyperspectral Imaging [71.57324258813675]
A dataset of inter-dependent signals is defined as a matrix whose columns demonstrate strong dependencies.
A neural network is employed to act as structure prior and reveal the underlying signal interdependencies.
Deep unrolling and Deep equilibrium based algorithms are developed, forming highly interpretable and concise deep-learning-based architectures.
arXiv Detail & Related papers (2022-03-29T21:00:39Z) - Reinforcement Learning Based Query Vertex Ordering Model for Subgraph
Matching [58.39970828272366]
Subgraph matching algorithms enumerate all is embeddings of a query graph in a data graph G.
matching order plays a critical role in time efficiency of these backtracking based subgraph matching algorithms.
In this paper, for the first time we apply the Reinforcement Learning (RL) and Graph Neural Networks (GNNs) techniques to generate the high-quality matching order for subgraph matching algorithms.
arXiv Detail & Related papers (2022-01-25T00:10:03Z) - 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)
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.