Navigating Streams: A Survey on 15 Years of Advances in Stream Reasoning Formalisms

This survey provides a systematic overview of Stream Reasoning (SR) formalisms, with a focus on deductive reasoning. To analyze and compare these formalisms, the authors define ten evaluation dimensions that cover theoretical aspects, like stream representation, static vs. temporal reasoning, or uncertainty, among others, as well as practical criteria, like citation count or applications, for example. Around forty formalisms are discussed that build upon description logics, temporal logics, ASP, Datalog, SPARQL and other foundations.
The general result is that formalisms often focus on either stream querying, reasoning over time, or reasoning about time, while no formalism excels at each of these objectives at the same time. In addition, topics like uncertainty and complexity analysis are usually neglected by many formalisms.

-----
(1) Suitability as introductory text:
The paper serves as a good starting point to look for available SR formalisms and the various characteristics they can possess. However, some of the theoretical bases, like DL, SPARQL and especially Event Calculus, might benefit from a more detailed description.

(2) How comprehensive and how balanced is the presentation and coverage:
The method for conducting the literature review is described well and the stated research questions and evaluation dimensions seem reasonable. The discussion of certain topics, however, is a bit unbalanced at some places. For example, ASP is described in much more details than DL in the preliminaries. In addition, it is not clear why ASP is introduced as a subsubsection, while Datalog and RDF, for example, have their own subsection. Besides, research question Q5 is not mentioned in the Discussion section. Even though the survey already captures a large amount of different SR formalisms based on various theoretical bases, it does not explicitly consider the usage of incremental reasoning approaches for deductive SR. It might be worth to take a look at the following works:
- Barbieri et al. - Incremental Reasoning on Streams and Rich Background Knowledge - 2010
- Ren and Pan - Optimising Ontology Stream Reasoning with TMS - 2011
- Terdjimi et al. - Web Reasoning Using Fact Tagging - 2018
- Budiu et al. - DBSP - 2022

(3) Readability and clarity of the presentation:
Most of the time, the text is clear and understandable. The various illustrations and tables further contribute to that. Nevertheless, there are many writing errors, like missing or duplicate punctuation, whitespaces, symbols or words, repeated sentences with slightly changed formulations, inconsistent spelling of words (British vs. American), missing capitalization of titles and names, as well as grammar and spelling errors. In addition, Figures 1 and 3 would benefit from a larger font.

(4) Importance of the covered material to the broader Semantic Web community:
The survey shows how different Semantic Web technologies contribute to the relevant topic of dynamic data processing. Thus, it may serve as motivation for further research directions to tackle the limitations of current formalisms.

-----
Further comments:
- p2: Section 4 is not mentioned during the description of the paper's structure
- p6: "while [phi] stays true until psi holds" (?)
- p6: "For example, [phi]@_[5] states that the formula phi" (?)
- p9: the three usage dimensions are not introduced at the beginning of Section 5, unlike the seven theoretical ones
- p17: "Since it only considers logical entailment and a correct order of the stream, it does [not] account for uncertainty in the data or the stream (T5)." (?)
- p22: "indicating at which time points a given grounded event predicate"; this sentence is not comprehensible & how can a predicate be grounded?

OVERALL
This paper presents a comprehensive literature review of formalisms for Stream Reasoning, evaluating them across ten dimensions. Particularly noteworthy are the attention given to the expressive power of each formalism, the breadth of the survey, and the effort invested in assessing real-world adoption through implementations and application-oriented publications.

The paper has several strengths. First, it is remarkably thorough, providing a broad overview of the field and covering a wide range of approaches, from query-oriented languages to reasoning-oriented languages. Second, Sections 2 and 3 offer a clear motivation and introduction that serve as an excellent entry point for readers new to Stream Reasoning. Third, the paper's systematic comparison framework makes it a valuable reference resource for researchers seeking to position their work within the existing landscape.

The main weakness is that the paper is largely descriptive rather than analytical. As a reference survey, it is highly useful. Indeed, when I was developing a Stream Reasoning formalism, a resource like this would have been extremely helpful in identifying the most relevant existing approaches for comparison. However, I believe the paper misses an opportunity to extract broader lessons from the surveyed material.
For example, in Section 8, T1, rather than simply noting the diversity of formalisms considered, it would be valuable to discuss why researchers have resorted to different formalisms and whether any patterns emerge regarding their suitability for particular applications or problem settings. More generally, the paper excels at cataloguing and comparing existing work, but it is less effective at identifying trends, research gaps, or overarching principles. Many survey papers conclude with a discussion of key challenges and future directions for the field. While this paper touches on such issues toward the end of Section 9, the discussion is relatively brief and arrives too late in the narrative.

Overall, I believe the paper has sufficient merit and utility to warrant acceptance. My preferred outcome, however, would be acceptance conditional on revisions that reduce some of the repetition throughout the manuscript and add a dedicated section towards the end, synthesising the main trends, open challenges, and future research directions in the field.

DETAILED COMMENTS
The classification framework introduced in this work, based on ten analytical dimensions, is a valuable contribution. As the authors note, it provides a structured way to position future contributions relative to the state of the art and may also help identify underexplored areas within the field. I found the attention paid to expressive power particularly useful, including the analysis of which logical connectives and LTL-inspired constructs are supported by different formalisms.

I also appreciate that the survey methodology and classification process are explained and justified in considerable detail. This transparency increases confidence in the comprehensiveness and reproducibility of the review.

Page 8 (Section 4): The discussion of related surveys feels somewhat disjointed. The presentation moves back and forth between different prior surveys, and the connection to the classification of topics introduced in Section 3 is not always clear. I would encourage the authors to reorganise this section in a more systematic way, with a stronger emphasis on how the present survey differs from and extends previous work. Furthermore, rather than discussing prior surveys primarily through the lens of the Bonte et al. [5] classification, it may be more helpful to relate them directly to the structure and dimensions introduced in Section 3.

Section 6.3: I was surprised that the complexity of query answering is not considered among the analysed dimensions. Depending on the expressiveness of the query language, query answering can involve highly non-trivial reasoning tasks and may have a substantial impact on practical applicability. Additional justification for excluding this aspect, or a discussion of its relevance, would be appreciated.

Section 7: The analysis of usage focuses primarily on citation counts, implementations, and applications, but pays less attention to their scale and impact. Did the survey identify any formalisms that have seen particularly large-scale deployments, for example in terms of data volume, industrial adoption, or integration within widely used systems? Such information would provide a richer picture of practical uptake than citation counts.
It may also be worthwhile to consider citation and application trends over time, rather than only cumulative counts. Examining growth rates could help identify approaches that are gaining or losing momentum within the community. More generally, I found the repeated discussion of citation counts somewhat redundant, as the information is already presented in tabular form. The most informative parts of this section were the descriptions of implementations and applications. I believe the section would be strengthened by reducing the emphasis on citation numbers and devoting more space to implementation-related observations, such as whether systems are research prototypes or production-ready tools, and whether they are actively maintained or no longer developed.

Section 8: The beginning of this section feels somewhat repetitive, as it largely revisits the ten analytical dimensions and their relationship to the research questions. At this stage of the paper, I was expecting a deeper synthesis of the reviewed literature, including broader observations, emerging patterns, or lessons that can be drawn across different approaches.

Sections 8–9: The paper notes that query-based formalisms exhibit higher usage statistics. However, it is unclear whether this comparison accounts for the age of the respective approaches. As the paper itself observes, query-based formalisms tend to be older than several alternative paradigms. Without some form of temporal normalisation, the reported differences in usage may not accurately reflect current levels of interest or adoption.

MINOR COMMENTS
Page 3: it isn't very clear how the initial selection of 14 papers relates to the procedure discussed afterwards.
Page 6: it might be worth mentioning that these intervals can be unbounded e.g. a can be -infinity, and/or b can be +infinity
The start of Section 5 and Section 5.1 seem to repeat a considerable amount of information. This could likely be simplified.

TYPOS
General comment: revise spacing around formulas; sometimes there are too many or too few white spaces within formulas.
Page 3: "barbieri" -> "Barbieri"?
Page 3: "are not taking" -> "are not taken"
Page 3: Figure 2 "paper" -> "papers"
Page 4: "asS" -> "as S"
Page 5: "b_m notc_1" -> "b_m, not c_1"
Page 5: the description of LTL operators is repeated.
Page 5: "while \psi stays true until \psi holds true" -> "while \phi stays true until \psi holds true"
Page 7: the alignment of the Datalog rules makes them very hard to read
Page 18 "(T5),nor" -> "(T5), nor" Similar typos afterwards; probably an issue with a macro?
Page 21: "adn the timestaps" -> "and the timestamps"
Page 21: "the timestamps stem form a linear timeline" -> this doesn't sound right
Page 21: ". keywords" -> ". Keywords"
Page 21: "this allowing to impose conditions [...] to be imposed" -> probably a typo
Page 22: "can ," -> "can, "
Page 22: mismatch "RDF Streams" and "RDF streams"
Page 23: "several limitation" -> "several limitations"
Page 23: ". eh exact" -> "An exact" ?
Page 23: data one form of" - this is not grammatical; there must be some typo
Page 23: "empplys" -> "employs" ?
Page 23: "independent" -> "independently" ?
Page 23: "at whihc" -> "at which"
Page 24: several formalism" -> formalisms
Page 24: "future work In" -> work. In
Page 24: "In the later works of" ... this sentence is not grammatical either, some word must be missing
Page 24 "Hpwever" -> "However"
Page 25 ". putting" -> "Putting"
Page 25 "Testing every SR formalisms" -> formalism, or "Testing the SR formalisms"

In this survey, the authors give an overview of the state of the art of the stream reasoning formalisms.

On the positive side, I find the topic relevant and timely. Moreover, the survey is properly focused and comprehensive.

On the negative side, I believe that the comparison between the formalisms is very shallow and, in general, unsatisfactory. Most importantly, the survey generally does not answer a most important question of a practitioner: Which of the formalisms/systems should I choose in my situation? Yes, some pieces of information is scattered here and there across the survey, but it nearly exclusively is about reporting the properties of each system, not on their comparison. The most interesting in such surveys is, however, not just a list of what exists, but what is common and what is different in what exists. I would expect, for each system, a motivating example of what are its selling points, something “the main motivating example is being able to do this, which is not possible to do at all/easily with other systems; however, this and that functionality is inherited from this and that system, while this and that is not covered for the sake of that”. Nearly none of such comparison/analysis is given. Of course, I understand that in some cases a separate research is needed to establish such comparisons. In these cases it is fine to say that it is an open question. But at least motivating examples and, in many cases, some basic comparison is given already in the papers, and this should be the focus of the survey.

Another negative side is that the paper is very badly written in terms of spelling and typos. In fact, sometimes it looks like no one even tried to give it a proofread (which is weird in the times of LLMs). Missing/extra blanks, repeated words and even sentences, random punctuation is common throughout the paper (I do not see a point to give examples, there are too many). This makes the reading unpleasant.

Concrete issues:

— Page 4: “First-Order Logic (FOL) [22] represents information as logical expressions, often called propositions, which evaluate to either true or false, making it a Boolean logic” is a weird statement: propositions are in propositional logic, while FOL operates predicates.

— Figure 3 is useless, it does not provide anything that makes the paper better in any sense

— Table 4:
- calling connectives “relations” is confusing and non-standard
- DL is a family, should be DL-Line in the first 4 entries

— Page 15, Column left, line 2 from the bottom: decidability of what?

— Page 16, Column left, line 4: the subscript of \cal A is weird

— Page 17: what is “cfr.”?

— Page 17: “Cucala et al.” should be “Tena Cucala et al.”

— Page 18: “PMLTL constructs expressions using static operators ¬, ∧, ∨ and by recursion, →” sounds odd: if you have conjunction and negation, implication is expressible, you do not need any recursion for this (similar question arises in several places later)

— Page 21: “As stream querying formalisms do not perform explicit reasoning, complexity and decidability results, when provided, are not comparable to other SR formalisms discussed. As such, we do not consider dimension T7 in the discussion of this category.” This does not look justified enough: why not to report complexity of query answering, which is relevant for comparing the formalisms in Section 6.3

— Page 25: “Fragments DatalogMTL¬ and DatalogMTL∃” these are not fragments, they are extensions

— Page 30: the right column is extremely repetitive and missing any point

Overall, the survey requires deep reworking both in content and presentation to be published