Stream reasoning is now emerging as a hot topic in the context of Semantic Web. As the number of data sources that continuously generates data streams emulating real-time events are increasing (and getting more diverse, i.e., from social networks to sensor networks), the task of exploiting the temporal aspects of these dynamic data becomes a real challenge. Stream reasoning is another form of the traditional reasoning, that works with streaming (dynamic, temporal) data over an underlying (static) ontology. There have been many existing reasoning systems (or newly proposed) trying to cope with the problems of stream reasoning but there is yet no standard to measure the performance and scalability of such systems. This paper proposes a benchmarking system, which is an extension to the well-known benchmark for traditional reasoning, Lehigh University Benchmark (LUBM), to make it work for stream-based experiments while retaining most of the LUBM's old standards.
RDF Data have been prevailing in the era of Semantic Web and now has
become a major part of the World Wide Web. Together with the growth in size of
RDF data, there appears a constant need of processing heterogeneous and noisy
RDF in a stream-based approach, as the problem is faced in many di erent
applications [
There are two main contributions of this paper. First, we introduce a benchmark that is speci cally designed for testing the performance of incremental reasoning engines. To the best of our knowledge, this is the rst benchmark that provides a practical measuring method for assessing the capabilities of such systems. Secondly, we conduct extensive experiments using our benchmark to measure the performance of a number of state-of-the-art reasoning engines of different types (i.e., OWL-DL, rule-based) which are streamable or can be adapted to process stream data. We are con dent this will aid the improvement of these tested engines toward the domain of stream reasoning. 2
Stuckenschmidt et al. [
There are plenty of di erent works that provide a benchmarking assessment
for RDF storage systems. We classify these systems into two di erent categories:
reasoning -based and SPARQL-based, since the semantics of RDF and RDFS are
omitted in the SPARQL speci cation [
LUBM [
2.2
SP2Bench [11], is a framework which measures the performance of triple stores in response to speci ed query language, SPARQL. The framework consists of two parts, the data generator, provide arbitrarily DBLP-like models in RDF format and the collection of 17 benchmark queries, designed to test all strengths and weaknesses of SPARQL engines. Berlin SPARQL benchmark (BSBM) [12], addresses the untapped part of SPARQL-to-SQL rewriting sytems of SP2Bench. It provides a set of measurements of which, deep comparisons between native RDF stores and systems rewriting SPARQL-to-SQL against its relational databases are carried out. BSBM emulates e-commerce scenarios in which the query mix is designed to follow a customer's search and navigation pattern while looking for a product. On the other hand, OpenRuleBench [13] provides a suite of benchmark for analyzing the performance and scalability of rule-based systems at Web scale. OpenRuleBench partitions rule-based systems into ve di erent categories: Prolog-based systems, Deductive databases, Rule engines for triples, Production and reactive rule systems, and Knowledge-base systems. The OpenRuleBench test suite includes a set of test derived from LUBM, adopting three out of its 14 queries. The three adopted queries are Query1, Query2 with high selectivity (i.e., each tuple of a join of 2 relation is joined with only a small number of tuples in the other relation) and Query3 with lower selectivity. Toward stream reasoning, Zang et al. [14] proposed SRBench, an RDF/SPARQL benchmark framework that covers dynamic reasoning in a stream-based context. However, the set of SRBench queries is restricted to sensor domain and is not clear to be easily and widely adapted like LUBM (e.g., to rule-based systems). 3
In this work, we select the state-of-the-art reasoning engines for testing. The engines are widely used in many applications, and they are either meant for or adaptable for stream-based reasoning. 3.1
Jena2 is the state-of-the-art Java framework for building Semantic Web applications. Jena provides functionalities for triplet store, RDFS/OWL processing, reasoning and querying using SPAQRL. Jena reasoning module provides an interface for easy plugging in of external inference engines. OWLAPI3 provides a high level application programming interface for creating and manipulating OWL Ontologies. Unlike Jena that support triple-based abstraction, OWLAPI focuses on a higher level of OWL abstraction syntax, the axioms. In this work, we study the two frameworks with an external reasoner component, Pellet.
3.2
Pellet4 is an open source OWL-DL reasoner that supports incremental reasoning via two di erent approaches: incremental classi cation for ABoxes and incremental consistency checking for TBoxes. Incremental classi cation is a reasoning technique in Description Logic, which is used for incremental subsumption checking. Whereas this approach incrementally checks for changes in relations between classes in the ontology hierarchy (i.e., A subClassOf B or not), it requires expensive computational cost that makes Pellet work ine ciently when it comes to processing with continuous streams of data. Incremental consistency checking is used to instantly detect the consistency between triples in the KB. With that, Pellet removes the old triple facts that cause con ict with the newer triple facts and continuously look for inconsistencies in the KB without running all reasoning steps from scratch. This feature makes Pellet a potential candidate for stream reasoning, where the reasoner needs to be robust against the upcoming facts into the dynamic KB. 3.3
C-SPARQL is a new query language designed for data stream processing, based
on the syntax of SPARQL with advanced features to support retrieving
continuous results at runtime. The query range is applied on a speci able sliding
time window, with respect to a data source of one or multiple registered data
streams combined with an optional static knowledge background. C-SPARQL
CONSTRUCT predicate, inherited from SPARQL syntax, allows query results
to be stored and registered as new streams on the y, hence making it
possible for C-SPARQL to describe production rules like inference rules. Figure 1
demonstrates the transitivity rule is constructed in C-SPARQL, the results are
contained in a newly de ned stream, namely, inf. Barbieri et al. [
Jess5, Java expert system shell, is a popular rule based inference engine, built upon the Rete network, provides support for both backward and forward chaining. Because it is built upon the Rete Network, Jess supports incremental reasoning for forward inference. The backward chaining method in Jess requires a special declarations to inform the Jess engine that a rule has to be red in order to acquire some facts. Facts in Jess are classi ed as ordered and unordered facts.
REGISTER STREAM inf COMPUTED EVERY
1s AS
PREFIX rdf:
<http://www.w3.org/1999/02/22-rdf-syntax-ns#>
PREFIX owl: <http://www.w3.org/2002/07/owl>
CONSTRUCT f?z ?p ?yg
FROM <static source>
FROM STREAM <some stream> [RANGE 1s STEP 1s]
WHERE f ?x ?p ?y .
?z ?p ?x.
?p rdf:type owl:TransitiveProperty
g
Data structure to describe unordered facts in Jess are de ned by templates.
E.g. a template for RDF triple in Jess is : (deftemplate triple (slot subject)(slot
predicate)(slot object)
BaseVISor [
LUBM provides an university ontology where 43 classes are de ned, of which
including department, course, student, professor etc. The benchmark generates
triple data regardless of time. We extend LUBM by plotting its static ontology
into a temporal semantic dimension, where we reconsider all possible triple data
with respect to time. RDF Streams [
... (< subji; predi; obji >; i) (< subji+1; predi+1; obji+1 >; i+1) ...
RDF Streams generated from our modi ed data generator of LUBM followed Barbieri et al.'s de nition. The only di erence we made is, as the KB is in a university domain, we choose a semester as the time granularity. This allows triples in the KB to retain their semantic meaning, adding the semester period when they are valid. By this, the timestamp of triple facts still follows a monotonic Object Property has a degree from has as a member has as a research project has as an alumnus is a TA for is about is a liated with is being advised by is taking publishes teaches was written by evolution and are semantically validated by academic semesters. As the consequence, there is a batch of facts corresponding to every semester. In this semester timespan, a semester can be considered as a time slice where facts in the newest time slice are all relevant. We dont use ner-grain time granularity to a semester (e.g., day or week) because this time slide length ensures a good proportion of dynamic data in a university data-generated context of LUBM.
... (<Department0.University0/GraduateStudent31, ub:takesCourse ,
Department1.University0/GraduateCourse1>, semester0 ) ...
As the time evolves, the benchmark re-generates university data recursively as complete batches (complete university data) of information. After each recursion, dynamic data in the KB of the previous semester are considered expired and must be retracted and replaced by newer data (of the new semester). In our system architecture described in Figure 2, the RDF Handler module only accepts triples (generated from LUBM ABox) with temporal annotation after the rst recursion. This mechanism guarantees the inference engine does not have to process duplicate static data (already there in the rst round). Table 1 provides a list of all object properties provided in the LUBM Ontology. The object properties are classi ed with regards to the change probability over time of the according objects in its range. We heuristically de ne three distinct predicate classes, namely static, near-dynamic and dynamic. Static is labeled for those predicates which re ect facts that are true for the whole timespan, while dynamic indicates those predicates that the fact validity changes constantly for every time slice or every window of time slices in the case of near-dynamic. For example, has a degree from refers to a constant fact where the object class of ub:University is labeled as static, while a subject instance with teaches has a more subject to change object instance (e.g., a teacher is assigned to teach di erent subjects in di erent semester). Therefore, with respect to the time dimension of semester unit, teaches is marked as dynamic. The temporal predicates (dynamic and neardynamic decides the proportion of dynamic data generated in each recursion, and hence, the complexity of the temporal data (towards reasoning engines).
Stuckenschmidt et al. [
In the communication module, we replace the original way of data transfering in traditional LUBM (which RDF data are serialized into les and the les then will be read by the reasoner), by a stream-based protocol. Here, LUBM data generator (the RDFWriter module in particular), is improved to establish a TCP/IP socket connection with experimented reasoners. To make it uniformly work, we introduce a data bu er that temporarily stores stream data from LUBM, RDFHandler, where RDF stream is parsed into RDF triples and these triples will be then fed into the tested reasoner via its API interface for processing.
For stream reasoning, inference rules for rule-based reasoning engines are redesigned. Table 2 contains a list of the most important inference rules and introduces a time-to-last 4t which describes the expiration time of the conclusions that derive from these rst-order rules. Time-to-last 4t has a lower bound of one semester, the time unit of the time dimension, and has no restriction in the upper bound as a derived fact can last for several semesters. In our extended LUBM, for consistency purpose, a time-to-last 4t of an inference rule is de ned as the minimum number of time units for facts that constitutes the rst part of Temporal Inference Rule transitive subclass-type transitive subproperty-type transitive symmetry inverse equivalent
Description (s0, p0, o0) (o0, p0,o1) (p0, rdf:type, owl:TransitiveProperty)) ) (assert ((s0, p0, o1), 4t)) (s0, rdfs:subClassOf, o0) (o0, rdf:type, o1) ) (assert ((s0, rdf:type, o1), 4t)) (p0, rdfs:subPropertyOf, p1) (s0, p0, o0) ) (assert ((s0, p1, o0), 4t)) (p0, rdf:type, owl:SymmetricProperty) (s0, p0, o0) ) (assert (o0, p0, s0), 4t)) (p0, owl:inverseOf, p1) (s0, p0, o0) ) (assert (o0, p1, s0), 4t)) (o0, owl:equivalentClass, o1) (s0, rdf:type, o0) ) (assert (s0, rdf:type, o1), 4t)) the inference rules stay in the system until one of them is removed out of the KB (so that, the outdated inferenced fact is also removed). 5
All experiments were conducted under Linux 2.6.x 64 bit, on top of a server
computer with an Intel(R) Xeon(R) E7520 1.87GHz processor and 80GB memory.
The Java engine was OpenJDK 1.6.0 24. We experimented with four di erent
reasoning engines, two of them are RETE-based (Jess, BaseVISOr), one
description logic-based (Pellet, together with Jena and OWLAPI) and one is the
engine of C-SPARQL. 14 LUBM queries are re-used to assess the engine
performances in a stream-based approach. We measured the loading time, query
response time and the completeness and soundness of the returned results from
the tested engines. For simplicity, we chose takescourse as the only temporal
predicate (adding other predicates does not signi cantly change the
complexity of the system). Hence, there is approximately 10% of the generated data
are dynamic (measured by the proportion between the numbers of facts with
takescourse predicate and the total number of facts). We rst experimented
with Jess engine for the load+inference (loading triple and inference on the y)
of Stream LUBM (1,0,5),which is LUBM (1,0) running over 5 semester. The
results surprisingly show that Jess engine, based on the RETE algorithm (ideal
for real-time pattern matching [
BaseVISor, Pellet+Jena and Pellet+OWLAPI are fed with data from di erent range. Figure 3 shows the response time on LUBM queries of BaseVISor for Query 5, Query 6, Query 13 and Query 14. In general, BaseVISor performed well in the incremental reason fashion as computation is reduced to minimal after the rst or second semester. We chose Query 14 for most of the test scenarios (although it has the lowest complexity among LUBM 14 queries) because the query guarantees a large result set that is in propositional to the size of the generated LUBM data. It can be seen that the accumulation of computation as the engine takes more time on the rst semester and takes signi cantly less time on the following semesters. Figure 4 indicates the time BaseVISor uses to response to Query 14, the longest query time among the LUBM queries for BaseVISor over the dataset range from LUBM (1,0,5) to (50,0,5) in 5 semesters. The chart shows the incremental behaviour of the RETE engine after semester 1, as the computation time needed for the next semesters are similar regardless of the size of the dataset, and is closed to zero. The results (detailed in Table 3) indicate BaseVISor's e ciency for stream reasoning.
Because Pellet+Jena and Pellet+OWLAPI are respectively founded on Jena and OWLAPI for RDF processing, RDF triples cannot be directly fed into both system. The statements of Jena and axioms of OWLAPI require elements of RDF triples to be pre-classi ed as resources and properties of the prede ned ontology. For example, (ub:GraduateStudent0 ub:takesCourse http://www.Dep artment0.University0.com/Course0) RDF triple, ub:GraduateStudent0 must be recognized as an instance of ub:GraduateStudent class, similarly for the predicate and object. Another medium module for triple classi cation is added for the pre-processing. Pellet+Jena and Pellet+OWLAPI, are based on the Description Logic reasoning engine of Pellet, show less signi cant gures than BaseVISor in query time required to answer the 14 LUBM queries, however both take much less time for data loading as tested with LUBM (5,0,5), (10,0,5), (20,0,5) and (50,0,5) in Figure 7. Pellet+Jena and Pellet+OWLAPI performance on incremental reasoning are measured as well as BaseVISor in Figure 5 and the results show that the BaseVISor outperforms the two DL-based engines. We also provide the numerical gures in Table 3 where the systems are experimented with Query 6, Query 13 and Query 14 and di erent settings for references.
We have also tested with the engine of C-SPARQL, an emerging and promising engine for stream RDF processing. With this engine, the data stream generated from our extended LUBM is registered as the only stream source. We have created the inference rule set (as described in Table 2) using CONSTRUCT predicate, in the same analogy to what we described in Figure 1. However, the released package of C-SPARQL6 does not yet fully support stream reasoning and as C-SPARQL returned results continuously over time, which requires a di erent approach of querytime measurement to the rest of the tested systems, thus we decided to present only the engine's loading time. As shown in Figure 7, C-SPARQL takes the least time to load in the data.
In this paper, we have introduced an extension of the well-known benchmark (LUBM) for reasoning engines over static dataset, to make it suitable for testing stream-based systems. The extension preserves the semantic of the LUBM ontology while adding a time dimension (of semester unit) to the KB. We run experiments on full and partial stream reasoning supported engines (i.e., BaseVISor, Pellet and C-SPARQL)using our benchmark. The results re ect the capabilities of each system in stream reasoning context, where BaseVISor outperforms other engines in most of the test cases.
For future work, we will focus on three improvements. First, our current approach is limited to control the complexity with time (e.g., increase the complexity the system must handle in the next semester time units). Secondly, we want to extend the benchmark to feature a more direct measurement of the time saved by incremental reasoning (e.g., how much computation is saved after one time unit). And lastly, we want to extend the benchmark to generate inconsistent facts (e.g., from di erent sources) with a parameterized rate, in order to closely simulate noisy real-world stream-based applications.
This work is funded by BMBF under the project ASEV. Query 6 ontology benchmark. In: Proceedings of the 3rd European conference on The formance of rule engines. In: Proceedings of the 18th international conference on out tted to process ruleml and r-entailment rules. In: Rules and Rule Markup Languages for the Semantic Web, Second International Conference on. (2006) 67{ match problem. Arti cial Intelligence 19(1) (1982) 17 { 37