How to improve existing RDF stream engine benchmarks with functional tests that verify result correctness before stressing the compared systems.
Since 2008 different research groups have studied the problem of query answering
over streams of RDF data [
One common problem of those two benchmarks is that they do not consider the output of the RDF stream engines. SRBench performs only functional tests in order to determine the features supported by the RDF stream engines; LSBench does not verify the correctness of the answers: it limits the analysis to the number of outputs, but this is not enough to determine if the answer is correct. In other words, both benchmarks make two assumptions: 1) the tested systems work correctly, and 2) the tested systems have the same operational semantics. If any of the two assumptions does not hold, the benchmarks supply misleading information on the performance of the compared RDF stream engines.
In this paper, we report our experience about the analysis of three RDF stream engines: C-SPARQL, CQELS and SPARQLstream1. We show that the two assumptions do not always hold, and consequently the results of the benchmark are not enough to make a comparison of the systems. We also supply guidelines for designing an improved benchmark for RDF stream engines: we propose the addition of a set of functional tests to verify the correctness of the results, in order to obtain more accurate benchmarks. In particular, we provide the following contributions: – considerations on benchmark principles: in order to the define a benchmark for RDF stream engines it is necessary to deeply understand the operational semantics of these systems (see bold-faced text in Section 3); 1 We used the last version available at March 14 on the public Web sites. For more information visit http://www.streamreasoning.org/bersys2013/ – propose guidelines to define functional tests to verify that the RDF stream engines behave correctly (see bold-faced text in Section 4); – a discussion on the results proposed by SRBench and LSBench.
In Section 2, we briefly introduce the RDF stream engines and the existent benchmarks for evaluating their performance. Then, in Section 3, we focus on the models at the basis of the RDF stream engines, explaining why their operational semantics should be well-defined, while in 4, we discuss the need to verify that the system implements correctly the operational semantics defined by its model. Finally, Section 5 concludes with considerations about the tests and guide lines for the improvements of the RDF stream benchmarks. 2
In the following, we provide the background information: we first briefly describe the behaviour of a generic RDF stream engines, then we provide information about the two benchmarks for these systems. 2.1
In its general definition, a RDF stream engine is a system able to continuously answer a query over a RDF stream. A RDF stream is an infinite sequence of timestamped RDF triples. A timestamped RDF triple is a RDF triple annotated with a time instant (also known as application timestamp); we represent a timestamped RDF triple as <s p o>:[τ ], where <s p o> is a well-defined RDF triple and τ is a natural number indicating the application time.
RDF stream engines are a particular case of stream engines; in these systems
the input is a generic stream, composed by a sequence of timestamped tuples [
One of the most used families of stream-to-relation operators is sliding windows: they allow to extract a continue portion of the stream. For the sake of brevity, we report only the definition of time-based sliding window. A timebased sliding window has an associate time range [to, tc) (known as scope) and it contains all the tuples of the stream having application time stamp in the scope. The scope is regularly updated to consider different blocks of the stream. The scope and its update are defined by two parameters, size and slide: the size (ω) defines the width of the window (ω = tc − to); the slide (β) defines the update rate and it is the time distance between two consecutive blocks of the window. A particular case of time-based sliding window is the one where the size equals to the slide. The name of this window is time-based tumbling window: it partitions the stream, ensuring that each timestamped tuple of the stream is in one and only one window block.
As relation-to-relation operators, those systems usually use well known transformations, such as algebras: RDF stream engines usually consider SPARQL and its algebra. It is worth to note that the relations are time-dependent relations and they changes over time (when the scope is updated).
Finally, relation-to-stream operators are used when the output of the query
engine should be a new stream. [
All the three systems we consider in this work implements time-based sliding windows and they all support (at least partially) SPARQL 1.1. As relation-tostream operators, C-SPARQL implements Rstream, CQELS implements Istream, while SPARQLstream implements all the three operators. 2.2
SRBench [
LSBench [
The first point, we want to focus on is related to the task of determining the correct answer of a RDF stream engine. Given an input data streams, an input query and the operational semantics of the engine, it should be possible to determine which is the expected answer of a RDF stream engine. The specifications of the RDF stream engines are usually available in the scientific articles and in the documentation available on their Web sites.
Let’s consider for example SPARQL engines: for SPARQL query answering engines, a test suite2 defined by W3C is available to verify the correctness of an 2 Cf. http://www.w3.org/2009/sparql/docs/tests/ implementation through a set of SPARQL queries. Each query is associated to its expected result. In that case, the SPARQL algebra is enough to explain how to determine which should be the output of a SPARQL engine implementation given an input and a query.
In the case of RDF stream engines, this process is more complex: the inputs (the stream and the query) and the SPARQL algebra are not enough to determine one correct answer. We set up the following experiment: we consider an input stream S1 and an input query Q1 defining a tumbling window W with size and slide of ten seconds. We registered the query in different (consecutive) time instants obtaining different outputs (details of the experiment can be found in Appendix A.1). It is worth noting that all the different results are correct.
This behaviour can be explained through an extended model of stream
engine, SECRET [
It becomes possible to determine which should be the correct answer given the inputs by extending operational semantics of a stream engine with the additional window parameters defined by SECRET. RDF stream benchmark designers should understand the differences in operational semantics of the systems they want to target. In particular, different behaviours of the S2R operators affect the outputs and the performance of those systems, and the explanation of the benchmarks results without considering this fact can be misleading. 4
In the previous sections, we explained that in order to benchmark RDF stream engines, their operational semantics should be complete and comparable. The last point we consider is the adherence of the RDF stream engines to their operational semantics: even if the specification is fine, if the implementation is wrong, the results of the benchmarking would be misleading. To verify it we exploit the correctness of the output. It may appear obvious, but, let us restate that given a RDF stream engine, an input query and a dataset, the result is correct if it conforms to the one defined by the system specification, better if in the form of a formal semantics.
The specifications of the RDF stream engines describe not only the operational semantics of the systems, but also the requirements at the basis of their design, the features they should implement and the use case scenarios with suites of functional and non-functional tests. It can happen that the test suite is badly defined – it is too strictly related to the use-case to elicitate all the requirements. Thus, the implemented RDF stream engine does not work correctly in general cases.
When designing tests to check that the RDF stream engines correctly implements the operational semantics, it is important to take into account both the whole RDF stream engine answering process and the single sub-processes that compose it. In fact, the query answering process would work in the right way if the three transformations that composes it are correct.
Before talking about the tests on the S2R operator (the main focus of this work), we explain how tests for the R2R and the R2S operators could be build. Regarding the R2R operator, an initial work is done by the two existent benchmarks. In their analysis these work check which are the limit of these operators, verifying which constructs are supported. The next step should be the verification of the correctness of the result of the R2R operators; the goal can be achieved exploiting the existent work on SPARQL query answering engines. The input data should be placed in one window (so the size has to be properly defined) and the output must be the same of the one defined by the
The correct implementation of the R2S operator can be verified with the following test: let’s consider as input stream a generic stream S. The input query Q uses as S2R operator a time-based sliding window W with size ω > 1 and slide β = 1; Q uses as the R2R operator the identity transformation. It is easy to verify that Rstream works correctly if the system outputs the current content of W ; Istream works correctly if the system outputs the new triples that enter W ; finally Dstream works correctly if the system outputs the triples that exit the W .
properly. Tests should verify that the window contains the correct elements and that its update is performed in the right way. To check the content of the window, if the tested RDF stream engine supports the Rstream S2R operator, it is easy to verify the behaviour of the window: it is enough to use a identity transformation as R2R operator (i.e. copy content of the input relation in the output relation) and the outputs would be the content of the window. If the RDF stream engine does not support Rstream, the test described above is not enough. If the system has the Istream operator and the test query uses the identity transformation, the output would allow to check only if the tuples are correctly inserted in the window, but not if they are correctly removed (a similar consideration is possible for systems supporting Dstream operator only). This problem can be fixed preparing the test with a different SPARQL query, exploiting the aggregate functions or the join operator. In Appendix A.2 we present an example of test of this kind.
The results of these tests on the systems we considered allowed us to verify that C-SPARQL and SPARQLstream correctly implements the window, while CQELS does not remove the elements in the window. In other words, CQELS ignores the window size and processes the whole data contained in S. It is not in the scope of this paper to report on the potential improvement in terms of input throughput of such a CQELS shortcoming; we intend to further inspect this behaviour checking memory allocation in the long run. A performing RDF Stream engine should not only maximize input throughput, but also minimize and keep as stable as possible memory allocation. 5
In this work, we analyzed the existing RDF stream engines and we showed that the absence of exhaustive functional testing hides anomalous behaviours of those systems. It is worth to note that both SRBench and LSBench do not detect S2R related problems, because they assume that the answer returned by the system is correct. Additionally, we illustrated how the operational semantics of actual RDF stream engines are not able to define a unique correct answer given an input stream and a query.
Both the benchmarks for RDF stream engines take into account different
dimensions in the definition of the experiments, such as: single and multiple input
streams; single and multiple windows over the input stream; optional presence of
static knowledge. However, they should take into account the variety of possible
systems outputs, in order to relate the performance to the correctness of the
results, as it happens in stream engine benchmarks such as the Linear Road
Benchmark [
In our future works, we intend to extend one of the RDF stream benchmark with correctness tests. This would allow the community to improve the existent systems and, potentially, to test new systems against a exhaustive set of tests. A.1
As scenario we use a simplified version of the scenario considered by CQELS
authors in [
Let’s set up the stream S1, depicted in Figure 1. S1 contains four triples describing the detections of the two individuals m1 and m2 in r1 first (respectively triples S1 and S2) and in r2 then (respectively triples S3 and S4).
We want to know when the two individuals m1 and m2 are in the same room. As window, we consider a time-based tumbling window of 10 seconds, the query returns the room where both m1 and m2 are detected, or empty-set otherwise. The query, expressed in the C-SPARQL syntax, is available in Listing 1.1.
Let’s now try to determine the correct answer the system should return. Looking at the stream S1, the expected answer is to have http://ex.org/r1 first, and http://ex.org/r2 then. But it is worth to note that it is not the only correct answer: all the results supplied in Table 1 are correct. The different results are consequence of the window operator: if it starts at t = 0 or t = 1 (windows W0 and W1 in Figure 1) the answer is the one presented above. If the window starts at t > 1 the output produced would be different: if t = 2 (window W2) the first answer of the window would be empty, because its content at 123 is S2 only; the second returned answer is http://ex.org/r2, because at 22 W2 contains both S3 and S4. The results are reported in Table 1. The outputs of the SPARQLstream and C-SPARQL engines are similar: the only difference is the second output of W6. It happens because C-SPARQL answers when the content of the window is not empty; looking at Figure 1 it easy to observe that the second block of W6 is empty.
A first observation on the results of CQELS is that when the system produces a result, it is always at τ = 3 and τ = 15. It happens because CQELS does not wait that the window closes (i.e., the size of the active window equals to ω). It is a possible behaviour of the S2R operator and we think it is correct. The second consideration is related to the fact that CQELS always output ex:r2 in each experiment. We are not able to explain if this behaviour is correct or not, because we are not able to control the t0 of the window as in the other systems4. We tried to probe, but on the one hand its source code is not available on the Web site; and on the other hand some bugs of CQELS (see Appendix A.2) do not allow us to investigate through additional experiments.
Finally, it is worth to note that in this experiment we considered a tumbling window, but it is easy to observe that there are multiple correct results every time the query defines a time-based sliding window with slide β > 1. In general, no one of the operational semantics of the RDF stream engines we considered can determine a unique correct answer given a stream and a query. 3 The scope of W2 at 12 is [2,12). 4 In C-SPARQL and SPARQLstream, the window W is created when the first query with W in its FROM STEAM clause is submitted to the system (i.e., t0 equals to the query registration time). We are not able to determine if it is true also for CQELS. A.2
As scenario we use the same of the first experiment: there are two connected rooms, r1 and r2; , r1 and r2; each room has a sensor able to detect the individuals (m1, m2, m3 and m4) when they are inside. The stream contains triples in the form: indicating that the individual mi has been detected in the room rj.
We set up the stream S2 depicted in Figure 2: it contains four triples Sk
(k ∈ [
Looking at the picture it is easy to observe that the query should return only empty answers or no answers if the engine only reports at content change: timestamped triples in S2 with the same room have a time difference of 10 seconds (respectively S1 and S3 for r1, S2 and S4 for r2). Additionally the minimum time-distance between two triples is of 5 seconds, which is greater than the window size ω: the window never contains two triples, so the WHERE clause of the query is never satisfied.
Listing 1.2. CQELS query used in Experiment 2
We performed this test on the three RDF stream engines we are considering, and while C-SPARQL and SPARQLstream behaved in the correct way, CQELS returned wrong answers in W4 and W5, as shown in Table 2.
SELECT ?p1 ?p2 ?room WHERE {
STREAM <http://ex.org/streams/test> [RANGE 3s SLIDE 3s] { ?p1 <http://ex.org/detectedAt> ?room .
?p2 <http://ex.org/detectedAt> ?room Listing 1.3. CQELS query used in Experiment 2 – without FILTER clause The new result is reported in Table 3. C-SPARQL and SPARQLstream returns the empty-result or mappings where ?p1 and ?p2 bind the same individual or empty result (in other words the join are performed on the same RDF triple). CQELS returns also performs the join over different RDF triples. We traced this CQELS behaviour to a possible incorrect removal ofthe triples from the window.
C-SPARQL Block ts ?p1 ?p2 ?room ts ?p1
CQELS SPARQLstream
?p2 ?room ts ?p1 ?p2 ?room 3 ex:m1 ex:m1 ex:r1 0 ex:m1 ex:m1 ex:r1 3 ex:m1 ex:m1 ex:r1 6 ex:m2 ex:m2 ex:r2 5 ex:m2 ex:m2 ex:r2 6 ex:m2 ex:m2 ex:r2 no result no result 9 – – – 12 ex:m3 ex:m3 ex:r1 10 ex:m1 ex:m3 ex:r1 12 ex:m3 ex:m3 ex:r1 ex:m3 ex:m3 ex:r1 no result no result 15 – – – 18 ex:m4 ex:m4 ex:r2 15 ex:m2 ex:m4 ex:r2 18 ex:m4 ex:m4 ex:r2 ex:m4 ex:m4 ex:r2