Tractable Fragments of Datalog with Metric Temporal Operators
Abstract
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.
Cite
Text
Walega et al. "Tractable Fragments of Datalog with Metric Temporal Operators." International Joint Conference on Artificial Intelligence, 2020. doi:10.24963/IJCAI.2020/266Markdown
[Walega et al. "Tractable Fragments of Datalog with Metric Temporal Operators." International Joint Conference on Artificial Intelligence, 2020.](https://mlanthology.org/ijcai/2020/walega2020ijcai-tractable/) doi:10.24963/IJCAI.2020/266BibTeX
@inproceedings{walega2020ijcai-tractable,
title = {{Tractable Fragments of Datalog with Metric Temporal Operators}},
author = {Walega, Przemyslaw Andrzej and Grau, Bernardo Cuenca and Kaminski, Mark and Kostylev, Egor V.},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2020},
pages = {1919-1925},
doi = {10.24963/IJCAI.2020/266},
url = {https://mlanthology.org/ijcai/2020/walega2020ijcai-tractable/}
}