Expressive rule-based stream reasoning

Abstract

Modern stream processing tools offer various solutions for evaluating continuously streaming data. They typically come with query languages or programming interfaces that extend those for static data. However, model-based semantics are rarely given, which complicates the comparison and formal analysis of different approaches. The lack of theoretical underpinning makes them also less suitable for problem solving in Artificial Intelligence. While logical reasoning is at the core of Knowledge Representation (KR) paradigms like Answer Set Programming (ASP), streams have been considered only recently. So far, rule-based approaches in KR do not provide explicit controls for streams such as window mechanisms, which play a central role in stream processing. To fill this gap, we develop LARS, a Logic-based Framework for Analytic Reasoning over Streams. LARS formulas extend propositional logic with generic window operators to select recent data, and with modalities to control the temporal dimension of reasoning. On top of this, we define LARS programs which can be seen as an extension of ASP for streams. We study this formalism and relate it to selected methods from different lines of research. Towards optimizations of LARS programs, we introduce and characterize notions of equivalence that are in line with previous research for ASP. Furthermore, we tackle the trade-off between data throughput and expressiveness by developing incremental reasoning techniques for a practical fragment of LARS. Based on this, we present the Ticker engine, a prototypical stream reasoning system, along with an empirical evaluation.