Materialisation-Based Reasoning in DatalogMTL with Bounded Intervals

Authors

  • Przemysław A. Wałęga University of Oxford
  • Michał Zawidzki University of Oxford
  • Dingmin Wang University of Oxford
  • Bernardo Cuenca Grau University of Oxford

DOI:

https://doi.org/10.1609/aaai.v37i5.25807

Keywords:

KRR: Geometric, Spatial, and Temporal Reasoning, KRR: Automated Reasoning and Theorem Proving

Abstract

DatalogMTL is a powerful extension of Datalog with operators from metric temporal logic (MTL), which has received significant attention in recent years. In this paper, we investigate materialisation-based reasoning (a.k.a. forward chaining) in the context of DatalogMTL programs and datasets with bounded intervals, where partial representations of the canonical model are obtained through successive rounds of rule applications. Although materialisation does not naturally terminate in this setting, it is known that the structure of canonical models is ultimately periodic. Our first contribution in this paper is a detailed analysis of the periodic structure of canonical models; in particular, we formulate saturation conditions whose satisfaction by a partial materialisation implies an ability to recover the full canonical model via unfolding; this allows us to compute the actual periods describing the repeating parts of the canonical model as well as to establish concrete bounds on the number of rounds of rule applications required to achieve saturation. Based on these theoretical results, we propose a practical reasoning algorithm where saturation can be efficiently detected as materialisation progresses, and where the relevant periods used to evaluate entailment of queries via unfolding are efficiently computed. We have implemented our algorithm and our experiments suggest that our approach is both scalable and robust.

Downloads

Published

2023-06-26

How to Cite

Wałęga, P. A., Zawidzki, M., Wang, D., & Cuenca Grau, B. (2023). Materialisation-Based Reasoning in DatalogMTL with Bounded Intervals. Proceedings of the AAAI Conference on Artificial Intelligence, 37(5), 6566-6574. https://doi.org/10.1609/aaai.v37i5.25807

Issue

Section

AAAI Technical Track on Knowledge Representation and Reasoning