article · 2023

Temporal Datalog with Existential Quantification

Matthias Lanzinger, Markus Nissl, Emanuel Sallinger, Przemysław Andrzej Wałęga

Cited by 0Open access

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.

Cite this paper

APA 7

Lanzinger, M., Nissl, M., Sallinger, E., & Wałęga, P. A. (2023). Temporal Datalog with Existential Quantification. https://doi.org/10.24963/ijcai.2023/365

MLA 9

Lanzinger, Matthias, et al. “Temporal Datalog with Existential Quantification.” 2023, pp. 3277–85, https://doi.org/10.24963/ijcai.2023/365.

Chicago

Lanzinger, Matthias, Markus Nissl, Emanuel Sallinger, and Przemysław Andrzej Wałęga. 2023. “Temporal Datalog with Existential Quantification.” https://doi.org/10.24963/ijcai.2023/365.

Harvard

Lanzinger, M. et al. (2023) ‘Temporal Datalog with Existential Quantification’. Available at: https://doi.org/10.24963/ijcai.2023/365.

BibTeX

@article{lanzinger2023temporal,
  title = {{Temporal Datalog with Existential Quantification}},
  author = {Lanzinger, Matthias and Nissl, Markus and Sallinger, Emanuel and Wałęga, Przemysław Andrzej},
  pages = {3277--3285},
  year = {2023},
  doi = {10.24963/ijcai.2023/365}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.