Abstract

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.

Code

We have implemented our approach based on an old version of RDFox. The linux executables are available here and are explained as follows.

standard: uses seminaive algorithm for materialisation and an optimised variant of DRed for incremental maintenance.
HD: uses our hypertree decomposition based algorithms.
Combined: applies HD algorithms to complex rules and the standard algorithms to the remaining rules.

The source code is available upon request at xinyue.zhang AT cs.ox.ac.uk.

Datasets and Datalog Programs

The test datasets and Datalog programs used in our paper are available here. The data description is shown below:

LUBM/ (containing the rules and data of LUBM)

LUBM-500-split* (the subsections of LUBM-500.nt.tar.bz2)
LUBM_L.dlog (LUBM L rules)
LUBM_L-C.dlog (LUBM L+C rules)

Expressions/ (containing the rules and data of Expression dataset)

exp300.nt.tar.bz2 (the data of Expressions)
exp-rules.dlog (the rules of Expressions)

YAGO/ (containing the rules of YAGO)

yago_rules.dlog (the rules of YAGO)
for the datasets of YAGO, please find it here. We use the GCARE-version of YAGO directly.

This repo also includes the instructions to reproduce the experiment results.

Paper and Supplementary Material

Xinyue Zhang, Pan Hu, Yavor Nenov, Ian Horrocks.
Enhancing Datalog Reasoning with Hypertree Decompositions.
In IJCAI, 2023.
proceedings

					@inproceedings{ijcai2023p0377, 

						  title     = {Enhancing Datalog Reasoning with Hypertree Decompositions}, 

						  author    = {Zhang, Xinyue and Hu, Pan and Nenov, Yavor and Horrocks, Ian},

						  booktitle = {Proceedings of the Thirty-Second International Joint Conference on
									 Artificial Intelligence, {IJCAI-23}},

						  publisher = {International Joint Conferences on Artificial Intelligence Organization},

						  editor    = {Edith Elkind},

						  pages     = {3383--3393},

						  year      = {2023},

						  month     = {8},

						  note      = {Main Track},

						  doi       = {10.24963/ijcai.2023/377},

						  url       = {https://doi.org/10.24963/ijcai.2023/377},

					  }

Acknowledgements: The design of this page was modified from the template made by Phillip Isola and Richard Zhang.