text: The trade-off between language expressiveness and system scalability (E&S) is a well-known problem in RDF stream reasoning. Higher expressiveness supports more complex reasoning logic, however, it may also hinder system scalability. Current research mainly focuses on logical frameworks suitable for stream reasoning as well as the implementation and the evaluation of prototype systems. These systems are normally developed in a centralized setting which suffer from inherent limited scalability, while an in-depth study of applying distributed solutions to cover E&S is still missing. In this paper, we aim to explore the feasibility of applying modern distributed computing frameworks to meet E&S all together. To do so, we first propose BigSR, a technical demonstrator that supports a positive fragment of the LARS framework. For the sake of generality and to cover a wide variety of use cases, BigSR relies on the two main execution models adopted by major distributed execution frameworks: Bulk Synchronous Processing (BSP) and Record-at-A-Time (RAT). Accordingly, we implement BigSR on top of Apache Spark Streaming (BSP model) and Apache Flink (RAT model). In order to conclude on the impacts of BSP and RAT on E&S, we analyze the ability of the two models to support distributed stream reasoning and identify several types of use cases characterized by their levels of support. This classification allows for quantifying the E&S trade-off by assessing the scalability of each type of use case its level of expressiveness. Then, we conduct a series of experiments with 15 queries from 4 different datasets. Our experiments show that BigSR over both BSP and RAT generally scales up to high throughput beyond million-triples per second (with or without recursion), and RAT attains sub-millisecond delay for stateless query operators.
  @cite_7: In complex reasoning tasks, as expressible by Answer Set Programming (ASP), problems often permit for multiple solutions. In dynamic environments, where knowledge is continuously changing, the question arises how a given model can be incrementally adjusted relative to new and outdated information. This paper introduces Ticker, a prototypical engine for well-defined logical reasoning over streaming data. Ticker builds on a practical fragment of the recent rule-based language LARS which extends Answer Set Programming for streams by providing flexible expiration control and temporal modalities. We discuss Ticker's reasoning strategies: First, the repeated one-shot solving mode calls Clingo on an ASP encoding. We show how this translation can be incrementally updated when new data is streaming in or time passes by. Based on this, we build on Doyle's classic justification-based truth maintenance system (TMS) to update models of non-stratified programs. Finally, we empirically compare the obtained evaluation mechanisms. This paper is under consideration for acceptance in TPLP.
  @cite_29: Stream reasoning is an emerging research field focused on dynamic processing and continuous reasoning over huge volumes of streaming data. Finding the right trade-off between scalability and expressivity is a key challenge in this area. In this paper, we want to provide a baseline for exploring the applicability of complex reasoning to the Web of Data based on a solution that combines results and approaches from database research, stream processing, and nonmonotonic logic programming.
  @cite_12: An increasing number of use cases require a timely extraction of non-trivial knowledge from semantically annotated data streams, especially on the Web and for the Internet of Things (IoT). Often, this extraction requires expressive reasoning, which is challenging to compute on large streams. We propose Laser, a new reasoner that supports a pragmatic, non-trivial fragment of the logic LARS which extends Answer Set Programming (ASP) for streams. At its core, Laser implements a novel evaluation procedure which annotates formulae to avoid the re-computation of duplicates at multiple time points. This procedure, combined with a judicious implementation of the LARS operators, is responsible for significantly better runtimes than the ones of other state-of-the-art systems like C-SPARQL and CQELS, or an implementation of LARS which runs on the ASP solver Clingo. This enables the application of expressive logic-based reasoning to large streams and opens the door to a wider range of stream reasoning use cases.
  @cite_3: 
summary: Both StreamRule @cite_29 and its recent parallelized version StreamRule @math @cite_3 use a RSP engine for data stream pre-filtering and Clingo as the ASP solver. The expressiveness of BSP implementation in BigSR can fully cover StreamRule and StreamRule @math , since the implementation in these two reasoners stay on positive stratified Datalog program. Evaluation of StreamRule StreamRule @math showcases that the average throughput is around thousand-triples second with second-level delay. Comparatively, our BSP implementation has almost three orders of magnitude gains. Laser @cite_12 and Ticker @cite_7 are both stream processing systems based on the LARS framework but do not concentrate on scalability. Ticker concentrates incremental model maintenance and sacrifices performance by relying on an external ASP engine (Clingo). Laser also proposes an incremental model based on time interval annotations which can prevent unnecessary re-computations. Although Laser claims to represent a trade-off between expressiveness and data throughput, it cannot scale the way BigSR enables to. This is mainly due to Laser's inability to distribute stream processing.