Reasoning over Streaming Data in Metric Temporal Datalog

Authors

  • Przemysław Andrzej Wałęga University of Oxford
  • Mark Kaminski University of Oxford
  • Bernardo Cuenca Grau University of Oxford

DOI:

https://doi.org/10.1609/aaai.v33i01.33013092

Abstract

We study stream reasoning in datalogMTL—an extension of Datalog with metric temporal operators. We propose a sound and complete stream reasoning algorithm that is applicable to a fragment datalogMTLFP of datalogMTL, in which propagation of derived information towards past time points is precluded. Memory consumption in our algorithm depends both on the properties of the rule set and the input data stream; in particular, it depends on the distances between timestamps occurring in data. This is undesirable since these distances can be very small, in which case the algorithm may require large amounts of memory. To address this issue, we propose a second algorithm, where the size of the required memory becomes independent on the timestamps in the data at the expense of disallowing punctual intervals in the rule set. Finally, we provide tight bounds to the data complexity of standard query answering in datalogMTLFP without punctual intervals in rules, which yield a new PSPACE lower bound to the data complexity of the full datalogMTL.

Downloads

Published

2019-07-17

How to Cite

Wałęga, P. A., Kaminski, M., & Grau, B. C. (2019). Reasoning over Streaming Data in Metric Temporal Datalog. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 3092-3099. https://doi.org/10.1609/aaai.v33i01.33013092

Issue

Section

AAAI Technical Track: Knowledge Representation and Reasoning