Data streams occur in a variety of modern applications. Specialized Stream Database Management Systems proved to be an optimal solution for on the y analysis of data streams, but they cannot perform complex reasoning tasks that requires to combine the streaming data with less time variant knowledge. At the same time, while reasoners are year after year scaling up in the classical, time invariant domain of ontological knowledge, reasoning upon rapidly changing information has been neglected or forgotten. We hereby propose stream reasoning - an unexplored, yet high impact, research area - as the new multi-disciplinary approach which will provide the abstractions, foundations, methods, and tools required to integrate data streams and reasoning systems. In particular the focus of this paper is to sketch the research chapters of Stream Reasoning.
\Is a tra c jam going to happen in this highway? And is then convenient to reallocate travelers based upon the forecast?" \By looking at the click stream coming from a given IP, can we notice the shifts of interest of the person behind the computer?" \Which contents of the news Web portal are attracting more attention? Which navigation pattern would lead readers to other news related to those contents?" \Are trends in medical records indicative of any new disease spreading in given parts of the world?" \Where are all my friends meeting?" \In the nancial context, can we detect any intraday correlation clusters among stock exchange?" Although the information is often available, there's no software system capable of computing the answers - indeed, no system enables users even to issue such queries.
Data streams occur in a variety of modern applications, such as network monitoring, tra c engineering, sensor networks, RFID tags applications, telecom call records, medical records, nancial applications, Web logs, click-streams. Specialized Stream Database Management Systems exist. While such systems proved to be an optimal solution for on the y analysis of data streams, they cannot perform complex reasoning tasks, such as the ones required for computing the answers to the above queries. At the same time, while reasoners are year after year scaling up in the classical, time invariant domain of ontological knowledge, reasoning upon rapidly changing information has been neglected or forgotten. Reasoning systems assume static knowledge, and do not manage \changing worlds" - at most, one can update the ontological knowledge and then repeat the reasoning tasks. We hereby propose stream reasoning - an unexplored, yet high impact, research area - as the new multi-disciplinary approach which will provide the abstractions, foundations, methods, and tools required to integrate data streams and reasoning systems, thus giving answer to the above and innumerable other questions. The idea is simple, yet pervasive.
In order to understand the research chapters that are currently under investigation, we organized the Stream Reasoning 2009 (SR2009) workshop5 co-located with the European Semantic Web Conference 20096. The main objective of this paper is to provide readers with key to systematically read the paper accepted to SR2009 workshop[1{5] and few others in the eld [6{8].
The rest of the paper is organized as follows. We rst present, in Section 2, two concrete examples of Stream Reasoning applications. Then, in Section 3, we introduces the problem Stream Reasoning research aim at solving. Section 4 is the central part of this paper and presents a list of research chapters that we believe should be investigated in order to turn Stream Reasoning into a solid reality. With Section 5 and 6, we present a simple, yet e ective, approach to measure progress in the area and we draw some conclusions. 2
We begin this paper with a list of questions in disparate domains that can be easily answered applying methods and tools resulting from investigation in the area of Stream Reasoning. Hereafter, we provide more details about two concrete examples of Stream Reasoning applications. 2.1
Today we live in a world where mobility is a core and always present concept that permeates our lives. Technology comes into place to support and accompany our mobility in several ways, with portable devices, both for business and entertainment. Mobile phones have become so popular and widespread that several applications for mobile phones are being developed in very di erent areas and with various purposes.
Mobile applications are therefore quite a generic and suitable case for the concept of Stream Reasoning. Being immersed in our everyday life, within our 5 http://streamreasoning.org/events/SR2009 6 http://www.eswc2009.org/ experience, those mobile applications must ful ll real time requirements, especially if they are used to take short-term decisions (like where to go, which means of transportation to choose, which restaurant to select, ...). Using data from sensors, which are likely to come in streams, those mobile applications must nd an answer to the problems of reasoning with streams: coping with noise data, dealing with errors, computing the \heavy" reasoning on the server rather that on the mobile devices, etc. Dealing with the \stream of experience" of users, those mobile applications must reason on what part of the streaming information is relevant and what's its \meaning" (e.g. abstracting from quantitative information about latitude and longitude to qualitative information about common places like home, o ce, gym, etc.). Using mobile phone users as \sensors", those mobile applications could be used also to understand the urban environment and its structure. 2.2
Early detection of potentially threatening public health events such as outbreaks and epidemics is a major priority of national and international health related organizations. Examples from the recent past are new infections such as SARS or the H5N1 \bird u". Dealing with this priority requires the advancement of early detection capabilities, by enabling more timely and thorough acquisition of relevant data and by advancing technologies associated with near real-time reporting and automated outbreak identi cation. This requires an integrated public health event detection platform that monitors a large variety of heterogeneous distributed data streams for detecting events and situations that might, when interpreted in the appropriate context, signify a potential threat for public health. Such a dynamic platform must identify, integrate and interpret heterogeneous distributed data streams, with information owing from these data sources automatically analysed and expressed on the basis of rich background knowledge. In the event that the outcome of this process is an increased estimated probability of a threat, noti cations to public health bodies will have to be streamlined over various communication channels (e.g. email, mobile phones) and will have to deliver traces of the reasoning process and data that lead to the calculation of the increased threat probability, in order to be evaluated and utilized appropriately. Existing systems such as Google's by now classical \ utrends" do indeed process high volume streams of data, but all semantic processing of this data is done either a priori (integration of streams) or a posteriori (interpretation of results). The challenge is to make the transition from such handcrafted systems to automatic reasoning over data-streams of similar magnitudes. 3
The areas that can be positively impacted by Stream Reasoning are numerous. Finance, energy supply management, attention mining for Web 2.0 application, tra c management, real-time social-networking, healthcare are just a few of those areas. Some years ago, proposing to develop a system to answer questions like the one above would have looked like a Sci-Fi idea due to the lack of data. Nowadays, a large amount of the required information are already available in digital format and can be access at almost no cost: maps with the commercial activities and meeting places, events scheduled in the city and their locations, average speed in highways, positions and speed of public transportation vehicles, parking availabilities in speci c parking areas, geo-positioned twitter posts, user generated media of any kind, web logs, click streams, epidemiological data, as so on and so forth. The problem is that current technologies are not up to the challenges to reason upon all this rapidly changing information. To do so, a system requires coping with: 1. heterogeneity both in data stream sources and in static information sources at syntactic, structural and semantic level; 2. time dependencies, since the very nature of stream, data is valuable only when it is actually presented; if it is not captured and immediately summarized, then reconstructing the value is impossible - of course, all the information is also subject to change through classical update mechanisms; 3. window dependencies, since data are observed trough a window, which can span in time or in number of elements it can contain, information about individuals in a given time window can be either incomplete (e.g., some sensors did not provide data) or over constrained (e.g., di erent sensors observing the same event); 4. noisy and uncertain data, i.e. data coming from a sensor network in a given moment may be faulty due to faults in some sensors or in part of the network; 5. scale, i.e., both the presence of huge data throughputs and the need to link streaming data with static knowledge, where perhaps only very limited amount data and knowledge are su cient for a given reasoning tasks and the data should therefore be identi ed, sampled, abstracted and approximated; 6. real-time constraints, i.e., an answer should be provided before it becomes useless, which leads to the need for incremental query answering and reasoning; 7. continuous processing, applications are either interested into fresh data thus, if they lose the data stream, they totally lose their relevance - or into summary data - but again, once that summarization is needed, it is much more rationale doing it once and for all by optimizing the continuous data processing than doing independent summarization upon masses of persistent data. Thus, continuous query processing performs the optimization by combining summarization requirements all at once, and then lets the irrelevant data (perhaps 99.99%) to get lost; and 8. distribution of computational units, which also means modularizing the reasoning, minimizing the transmission data among the units and being able to control the reasoning process.
By systematically analyzing the problems presented in Section 3, we were able to divide the Stream Reasoning research in 5 chapters. 4.1
Stream Reasoning research de nitely need new theoretical investigations that
go beyond Data Stream Management Systems [
Examples of important theoretical problems that need investigations are:
{ Dealing with incomplete or over constrained information about individuals
as proposed in [
Investigations about which logic language is appropriate for stream reasoning is an important theoretical aspect; therefore we dedicate to it a separate research chapter.
The paper submitted to SR2009 adopt a variety of di erent logics. A
Constructive Description Logic [
A rst step toward Stream Reasoning is certainly trying to combine the power of
existing Data Stream Management Systems and existing reasoning techniques.
The key idea is to keep streaming data in relational format as long as possible
and bring them at the reasoning level as aggregated events [
However, more investigation is need for Query Execution and Optimization. Interesting research topics appear to be:
{ cost metrics to measure query plan cost, { continuous query plan adaptation to the bursty nature of data streams, { parallel processing of multiple queries to exploit inter-query optimization opportunities, and { distributed query processing. 4.4
Combining Stream Data Management and reasoning at data model and query
language level is only a rst step toward Stream Reasoning, a deeper merge
can be investigated. From di erent view points, part of this research has been
conducted in Arti cial Intelligence under the name of belief revision [
The central research question is: can the idea of continuous semantics introduced in Data Stream Management System be extended to reasoners? For instance, can materializations be incrementally maintained? But even more basically, do the current materialization hold? How long will it? Can an updated materialization be computed before it will be outdated? Last but not least, can Stream Reasoning bene t from distribution and parallelization?
We nd very interesting the attempts to answer this questions the
incremental evaluation of complex temporal formula described in [
Engineering of Stream Reasoning is clearly in its infancy. Several implemented
systems exists (e.g., [
Moreover, all the research problems listed in the chapter above need some degree of engineering. Hereafter we list the key engineering activities needed to develop a solid implementation of Stream Reasoning: { Integration of data streams with reasoning systems, { Optimization methods for Stream Reasoning, { Scalability issues in stream reasoning, { Real time reasoning, { Approximate stream reasoning, { Distribution issues in stream reasoning, and { Evaluation of stream reasoners.
Application of Stream Reasoning deserve a research chapters on their own,
because the idea of Stream Reasoning does not arise as a theoretical research
topic, even if requires major theoretical researches, but as a potential solution
to real problems. Tra c Monitoring and tra c pattern detection appears to be
a very natural area, since it was independently studied in [1{3, 18]. Other area
of interest are nancial transaction continuous auditing [
Although the problem may appear intractable at rst glance, a roadmap for Stream Reasoning can be sketch as follows. Once one accepts that no Stream Reasoning is possible in the space of the onetime semantics of standard reasoning and thus it is only possible when thinking in terms of continuous semantics, then the system must have the notion of observation period, de ned as the period when the system is subject to querying. In current reasoners, all forms of knowledge are invariable and data can be updated, but they are not allowed to change too frequently. The notion of observation period together with a classi cation of what kind of knowledge and data is allow to change allow ordering progressively more complex form of stream reasoning. The table below presents our intuition and it can be used to measure progress.
All the researches, which we have been discussing in this paper and which prototyped a working system [1, 2, 6{8], ground the stream reasoning core model upon known database and reasoning methods. It's clear that the adoption of o the-shelf stream database and reasoning tools provide both a solid framework and a fast way for prototyping.
While the works discussed in this paper serve to ground stream reasoning and to give an intuition that the task is not impossible, a huge amount of innovation is required in order to cover the queries that we have initially set as our ambitious target and thus covering the gap between the current state-of-the-art to bring stream reasoning into life.
Starting from lesson learned in the database community (e.g., the ability to e ciently abstract and aggregate information out of multiple, high-throughput streams) a new foundational theory of stream reasoning is needed, capable to associate reasoning tasks to time windows describing data validity and to therefore to produce time-varying inferences. From these foundations, new paradigms for knowledge representation and query languages design must be derived, and the consequent computational frameworks for stream reasoning oriented software architectures and their instrumentation must be deployed.
The work described in this paper is has been partially supported by the European project LarKC (FP7-215535).