Tractable Fragments of Datalog with Metric Temporal Operators

Tractable Fragments of Datalog with Metric Temporal Operators

Przemysław A. Wałęga, Bernardo Cuenca Grau, Mark Kaminski, Egor V. Kostylev

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Main track. Pages 1919-1925. https://doi.org/10.24963/ijcai.2020/266

We study the data complexity of reasoning for several fragments of MTL - an extension of Datalog with metric temporal operators over the rational numbers. Reasoning in the full MTL language is PSPACE-complete, which handicaps its application in practice. To achieve tractability we first study the core fragment, which disallows conjunction in rule bodies, and show that reasoning remains PSPACE-hard. Intractability prompts us to also limit the kinds of temporal operators allowed in rules, and we propose a practical core fragment for which reasoning becomes TC0-complete. Finally, we show that this fragment can be extended by allowing linear conjunctions in rule bodies, where at most one atom can be intensional (IDB); we show that the resulting fragment is NL-complete, and hence no harder than plain linear Datalog.
Keywords:
Knowledge Representation and Reasoning: Qualitative, Geometric, Spatial, Temporal Reasoning
Knowledge Representation and Reasoning: Computational Complexity of Reasoning
Knowledge Representation and Reasoning: Logics for Knowledge Representation