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 forwardpropagating 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