# Enhancing Datalog Reasoning with Hypertree Decompositions

arXiv: https://arxiv.org/abs/2305.06854 · HTML: https://mlsanity.com/paper/2305.06854/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 55 references that are in the map.
- First posted on arXiv 11 May 2023.

## Builds on (most cited first, 9 of 9)

- [The Vadalog System: Datalog-based Reasoning for Knowledge Graphs](https://mlsanity.com/paper/1807.08709/) (2018)
- [An Analytical Study of Large SPARQL Query Logs](https://mlsanity.com/paper/1708.00363/) (2017)
- [Optimizing Answer Set Computation via Heuristic-Based Decomposition](https://mlsanity.com/paper/1812.09718/) (2018)
- [lpopt: A Rule Optimization Tool for Answer Set Programming](https://mlsanity.com/paper/1608.05675/) (2016)
- [Optimised Maintenance of Datalog Materialisations](https://mlsanity.com/paper/1711.03987/) (2017)
- [Estimating the Cardinality of Conjunctive Queries over RDF Data Using Graph Summarisation](https://mlsanity.com/paper/1801.09619/) (2018)
- [Modular Materialisation of Datalog Programs](https://mlsanity.com/paper/1811.02304/) (2018)
- [Skew Strikes Back: New Developments in the Theory of Join Algorithms](https://mlsanity.com/paper/1310.3314/) (2013)
- [Old Techniques for New Join Algorithms: A Case Study in RDF Processing](https://mlsanity.com/paper/1602.03557/) (2016)

## Abstract (arXiv)

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.