Rule-Based Stream Reasoning [PhD Project]

Continuous processing of data streams is a key aspect of many applications. For instance, oil and gas companies continuously monitor and analyse data coming from their sites to detect equipment malfunction and predict maintenance needs. In recent years, there has been an increasing interest in extending stream processing engines with rule-based temporal reasoning capabilities.


To ensure correctness, such systems must be able to output results over the partial data received so far as if the entire (infinite) stream had been available; furthermore, these results must be streamed out as soon as the relevant data is received, thus incurring the minimum possible latency; finally, due to memory limitations, systems can only keep a limited history of previous facts in memory to perform further computations. These requirements pose significant theoretical and practical challenges since temporal rules can derive new information and propagate it both towards past and future time points; as a result, streamed answers can depend on data that has not yet been received, as well as on data that arrived far in the past.


Towards developing a solid foundation for practical rule-based stream reasoning, we proposed and studied in a suite of decision problems that can be exploited by stream reasoning algorithms to tackle the aforementioned challenges, and provide tight complexity bounds for a core temporal extension of Datalog. All the problems we considered can be solved at design time (under reasonable assumptions), prior to the processing of any data. Solving these problems enables the use of reasoning algorithms that process the input streams incrementally using a sliding window, while at the same time supporting an expressive rule-based knowledge representation language and minimising both latency and memory consumption.


We have proposed and studied a suite of decision problems which enable the use of incremental stream reasoning algorithms based on a sliding window, while ensuring correctness and minimising both latency and memory consumption. Although these problems are undecidable for Temporal Datalog, we have shown decidability and established tight complexity bounds under the assumption that the set of objects that may occur in an input stream is fixed. We believe that our results constitute a first step towards the development of robust and efficient stream reasoning engines with provable correctness guarantees.


Selected Publications

  • Alessandro Ronca, Mark Kaminski, Bernardo Cuenca Grau, and Ian Horrocks. The window validity problem in rule-based stream reasoning. In Proc. 16th International Conference on Principles of Knowledge Representation and Reasoning (KR 2018), pages 571–581. AAAI Press, 2018.
  • Alessandro Ronca, Mark Kaminski, Bernardo Cuenca Grau, Boris Motik, and Ian Horrocks. Stream reasoning in Temporal Datalog. In Proc. 32nd AAAI Conference on Artificial Intelligence (AAAI 2018), pages 1941–1948. AAAI Press, 2018.
  • Alessandro Ronca, Mark Kaminski, Bernardo Cuenca Grau, and Ian Horrocks. The delay and window size problems in rule-based stream reasoning. Artificial Intelligence, 306:103668, 2022.


Alessandro Ronca [PhD Candidate], Bernardo Cuenca Grau [Supervisor], Mark Kaminski [Supervisor]Ian Horrocks [Supervisor]



This work was supported by the SIRIUS Centre for Scalable Data Access (Research Council of Norway, project 237889).