KR Conference 2012 Short Paper
- Martin Gebser
- Torsten Grote
- Roland Kaminski
- Philipp Obermeier
- Orkunt Sabuncu
- Torsten Schaub
To further illustrate this problem, consider a continuous character stream over alphabet {a, b} along with the task of continuously checking whether the stream at hand matches regular expression (a|b)∗ aa. We represent the stream via atoms of the form read(C, T), indicating that character C is at stream position T. As a first attempt, we may then encode the recognition of (a|b)∗ aa by the rule The advance of Internet and Sensor technology has brought about new challenges evoked by the emergence of continuous data streams. While existing data-stream management systems allow for high-throughput stream processing, they lack complex reasoning capacities. We address this shortcoming and elaborate upon an approach to knowledge-intense stream reasoning based on Answer Set Programming (ASP). The emphasis thus shifts from rapid data processing to complex reasoning. To accommodate this in ASP, we develop new techniques that allow us to formulate problem encodings dealing with emerging as well as expiring data in a seamless way. We thus propose novel language constructs and modeling techniques for specifying and reasoning with timedecaying logic programs. accept: - read(a, T-1), read(a, T). This rule can be seen as an “offline” encoding, which is correct for the initial segment of a stream of successive instances of predicate read, that is, up to the smallest i (if any) such that read(a, i−1) and read(a, i) hold. However, instances of read constitute an “online” data flow, and an accept decision has to be withdrawn when letter b is read, eg. in read(b, i+1). Clearly, solving such a problem with traditional ASP systems requires relaunching the system upon the arrival of each character. Although each time only the last two readings need to be taken into account, neither of the following ways to utilize standard ASP systems is satisfactory from a KRR viewpoint: (a) one may add further rules to explicitly identify outdated readings (in order not to reason about them) among the whole data; (b) an external component may filter readings and pass only the most recent ones on to the ASP system. Major drawbacks of (a) are the increasing size of input data over time and the more involved encoding, required for the sake of “garbage collection. ” Compared to this, (b) might appear tempting, but it relies on external filtering and thus fails to model the scenario at hand within the declarative realm of ASP. To overcome this problem, we propose an ASP-based approach to stream reasoning based on the sliding window model (cf. (Golab and Özsu 2010)). The idea is (i) to read an “offline” encoding just once and (ii) to keep only the n last entries of an “online” data stream. We accomplish this by extending our previous approach to reactive ASP (Gebser et al. 2011) by means for dealing with time-decaying program parts. In our example, this implies that instances of predicate read expire after two steps. Hence, when investigating the stream abba, only the atoms read(b, 3) and read(a, 4) are taken into account, while read(a, 1) and read(b, 2) have already expired and been disposed of. In fact, time-decaying data poses a major challenge to ASP given that fixed encodings must tolerate emerging as well