Abstract
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.
Keywords
- Knowledge Representation and Reasoning: Computational Complexity of Reasoning
- Knowledge Representation and Reasoning: Geometric, Spatial, and Temporal Reasoning
- Knowledge Representation and Reasoning: Logics for Knowledge Representation
- Knowledge Representation and Reasoning: Non-classical Logics for Knowledge Representation
