DatalogMTL: computational complexity and expressive power

Conference item

We study the complexity and expressive power of DatalogMTL - a knowledge representation language that extends Datalog with operators from metric temporal logic (MTL) and which has found applications in ontology-based data access and stream reasoning. We establish tight PSpace data complexity bounds and also show that DatalogMTL extended with negation on input predicates can express all queries in PSpace; this implies that MTL operators add significant expressive power to Datalog. Furthermore, we provide tight combined complexity bounds for the forward-propagating fragment of DatalogMTL, which was proposed in the context of stream reasoning, and show that it is possible to express all PSpace queries in the fragment extended with the falsum predicate.

Authors: Walega, P; Cuenca Grau, B; Kaminski, M; Kostylev, E

• Alternative title: Conference paper
• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: International Joint Conferences on Artificial Intelligence
• Host title: Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
• Journal: Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
• Pages: 1886-1892
• Publication date: 2019-08-10
• Acceptance date: 2019-05-09
• DOI: 10.24963/ijcai.2019/261
• ISBN: 9780999241141
• Keywords: knowledge representation and reasoning: geometric, spatial, and temporal reasoning; knowledge representation and reasoning: non-classical logics for knowledge representation; knowledge representation and reasoning: logics for knowledge representation; knowledge representation and reasoning: computational complexity of reasoning