Temporal Datalog with Existential Quantification
Matthias Lanzinger, Markus Nissl, Emanuel Sallinger, Przemysław A. Wałęga
Abstract
Existential rules, also known as tuple-generating dependencies (TGDs) or Datalog+/- rules, are heavily studied in the communities of Knowledge Representation and Reasoning, Semantic Web, and Databases, due to their rich modelling capabilities. In this paper we consider TGDs in the temporal setting, by introducing and studying DatalogMTLE---an extension of metric temporal Datalog (DatalogMTL) obtained by allowing for existential rules in programs. We show that DatalogMTLE is undecidable even in the restricted cases of guarded and weakly-acyclic programs. To address this issue we introduce uniform semantics which, on the one hand, is well-suited for modelling temporal knowledge as it prevents from unintended value invention and, on the other hand, provides decidability of reasoning; in particular, it becomes 2-EXPSPACE-complete for weakly-acyclic programs but remains undecidable for guarded programs. We provide an implementation for the decidable case and demonstrate its practical feasibility. Thus we obtain an expressive, yet decidable, rule-language and a system which is suitable for complex temporal reasoning with existential rules.
BibTeX
@inproceedings{ijcai2023p365,
title = {Temporal Datalog with Existential Quantification},
author = {Lanzinger, Matthias and Nissl, Markus and Sallinger, Emanuel and Wałęga, Przemysław A.},
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 = {3277--3285},
year = {2023},
month = {8},
note = {Main Track},
doi = {10.24963/ijcai.2023/365},
url = {https://doi.org/10.24963/ijcai.2023/365},
}