With the release of SPARQL 1.1 in 2013 property paths were introduced, which make it possible to describe queries that do not explicitly define the length of the path that is traversed within an RDF graph. Already existing RDF stores were adapted to support property paths. In order to give an insight on how well the current implementations of property paths in RDF stores work, we introduce a benchmark for evaluating the support of property paths. In order to support realistic RDF graphs as well as arbitrarily scalable synthetic RDF graphs as benchmark dataset, a query generator was developed that creates queries from query templates. Furthermore, we present the results of our benchmark for 4 RDF stores frequently used in academia and industry. These results indicate that many current implementations of property paths have several shortcomings.
The SPARQL Protocol And RDF Query Language (SPARQL) is used to query data
from RDF stores. In 2008 SPARQL 1.0 became an official World Wide Web
Consortium recommendation [
One limitation of SPARQL 1.0 was the missing possibility to formulate queries, which do not specify the length of traversed paths during their execution. Therefore, queries may become very complex, or it may even be impossible to retrieve complete results with one single query.
For example it is impossible to create a SPARQL 1.0 query that retrieves all friends of friends of a friend etc. from a social network. In order to make such complex queries more concise, or even possible, property paths were introduced with SPARQL 1.1 in 2013. The construct <foaf:knows>* could be used in a SPARQL 1.1 query to retrieve all direct or indirect friends of a friend.
After property paths had been introduced, already existing RDF stores have been
adapted to support this new feature. To give insights into the current state of the
integration of property paths and to detect possible shortcomings, the current implementations
of property paths needs to be evaluated. RDF store developers could use such an
evaluation of their own property path implementation to analyse the current state of their
implementation and as help for the further development of their RDF store. In order to
provide such an evaluation we offer two main contributions in this work:
1. In section 3 we introduce a benchmark, which makes it possible to evaluate the
? This paper is based on the findings in the bachelor thesis [
2. In section 4 we present benchmark results for Apache Jena, Virtuoso, Allegrograph and RDF4J. These results indicate that the current property path implementation of some stores have several shortcomings. Queries containing property paths partly have an execution time of over one hour and for some queries RDF stores return incomplete or even incorrect results. 2
In this section common definitions for RDF, SPARQL and property paths are given in order to define the terminology used in this work. 2.1
The Resource Description Framework [
two disjoint sets of all IRIs and literals, respectively and B is the set of all blank nodes.
Furthermore, s is called the subject, p the predicate and o the object of the triple. [
An RDF graph G is a finite set of RDF triples. [
A path P = (< v1; e1; v2 >; < v2; e2; v3 >; :::; < vn; en; vn+1 >) in an RDF graph G
is a sequence of triples such that (vi; ei; vi+1) 2 G. Furthermore the length of the path
is defined by the number of triples in the path. [
SPARQL can be used to query data from a stored RDF graph. In definition 4 basic graph patterns are defined, which are frequently used in queries.
Definition 4. Basic graph pattern (BGP)
A tuple t 2 (I [ L [ B [ V ) (I [ V ) (I [ L [ B [ V ) is a basic graph pattern, where
I, L, B and V are disjoint sets of IRIs, literals, blank nodes and variables respectively.
If P1 and P2 are basic graph patterns, then (P1 . P2) is a graph pattern.[
The semantics of graph patterns are defined in terms of mappings in definition 6.
Definition 6. Variable mappings
Mappings are partial functions from variables V to an RDF term T , which is defined
as I [ L.[
Definition 8. Join of mappings
Given two sets of mappings M1 and M2, the join of M1 and M2 is defined as:
M1 ./ M2 =) f 1 [ 2j 1 2 M1; 2 2 M2; ^ 1 2g [
Definition 9 Evaluation of graph pattern
if P 2 (I [L[V ) (I [V ) (I [L[V ), then [[P ]]G := f : var(P ) ! T j (P ) 2 Gg,
if P is P1:P2, then [[P ]]G := [[P1]]G ./ [[P2]]G [
Definition 10 Semantics of SELECT query
The evaluation [[Q]]G of a query Q of the form SELECT X WHERE P is the set of all
projections jX of mappings from [[P ]]G to X, where the projection of jX is the
mapping that coincides with on X and is undefined elsewhere.[
There are several different property path expressions, which denote different paths. These different expressions and their syntax are presented in definition 12. Definition 12. Property Path expression 1) p 2 I is a property path expression. 2) ˆP with property path expression P , is the inverse property path expression. 3) P1/P2, with property path expressions P1 and P2, is the sequence property path expression.
expression. 5) P *, with property path expression P , is the transitive reflexive closure property path expression. 6) P +, with property path expression P , is the transitive closure property path expression. A query containing the property path expression * is shown in listing 1. PREFIX snw : h t t p : / / www. s o c i a l nw . com / PREFIX f o a f : h t t p : / / x m l n s . com / f o a f / 0 . 1 / SELECT ? f r i e n d WHERE f <snw : Ann> < f o a f : knows >
? f r i e n d . g
Listing 1: Query containing the * operator of property paths [[sP o]]G := f = ?gjif (s; o) 2 [[P ]]G ?; otherwise The evaluation of a property path is presented in the following definition: Definition 13. Evaluation of property paths
property paths is defined as:
(
[[vP o]]G := f j( (v); o) 2 [[P ]]G ^ dom( ) = fvgg
[[sP v]]G := f j(s; (v)) 2 [[P ]]G ^ dom( ) = fvgg
[[v1P v2]]G := f j( (v1); (v2)) 2 [[P ]]G ^ dom( ) = fv1; v2gg
The semantics of the evaluation of property path expressions are defined in definition 14.
Definition 14. Evaluation of property path expressions
The evaluation [[P ]]G of a property path expression P over an RDF graph G is a set
of pairs of RDF terms from I [ L [ B [ V defined as follows:
[[p]]G := f(s,o) j (s,p,o) 2 Gg,
[[ ˆP ]]G := f(s,o) j (o,s) 2 [[P ]]Gg,
[[P1/P2]]G := [[P1]]G [[P2]]G,
[[P1jP2]]G := [[P1]]G [ [[P2]]G,
[[P +]]G := Si 1[[P i]]G,
[[P ]]G := [[P +]]G [ f(s,s) j(s; p; o) 2 Gg,
where is the usual composition of binary relations, and pi is the concatenation p/.../p
of i copies of p. [
When benchmarking the performance of RDF stores, different datasets might lead to
different results. As stated in [
To make it possible to use an arbitrary dataset as benchmark dataset, we provide query templates instead of fixed queries. These query templates are designed to test property path expressions. With the help of a query generator the query templates can be instantiated for the user-selected dataset (see section 3.1).
When evaluating the implementations of property paths, we see the testing of soundness and completeness of the returned query results as well as the querying time as the most important measures (see section 3.3 for their definitions). In order to test whether the returned results are complete and sound, we need a reference result set for each query. The creation of these reference result sets is described in section 3.2.
Since query result sets might contain different identifier for the same blank node,
the equality of two result sets containing blank nodes might become hard to check [
With our benchmark we want to evaluate how well the individual property path primitives are supported. Therefore, the benchmark comprises 8 query templates (see appendix A). Half of them test a single property path primitive. The only difference between the + and * operator is that in case of a query SELECT ?o WHERE fS P* ?og where S and P are IRIs, S is included in the result set, whereas it is not included in 3 Available as open source
Technologies/propertyPathBenchmark under https://github.com/Institute-Web-Science-andthe case of SELECT ?o WHERE fS P+ ?og . Thus we only test the * operator. The nesting of property path primitives may cause a higher degree on computational complexity. Therefore, the second half of the query templates test different nestings comprising templates with a high complexity containing nested * or + operators and templates with a low complexity containing, e.g., only alternative and sequence operators.
In order to generate queries that can be executed on the user-selected dataset each
query template contains query variables and template variables. The former remain
variables in the generated queries whereas the latter will be replaced by IRIs
existing in the dataset. An example for a query template is shown in listing 2. In this listing
the template variables S1 and P1 denote subject and predicate that are substituted with
constant IRIs during the query generation process. The query variable ?o1 remains a
variable in the actual generated query later on.
Basically the start, the end and all edge labels of a property path can be query variables
or template variables. As shown in [
RDF stores that are designed to process only SPARQL 1.0 queries regularly use SPO,
OSP and POS indices as described in [
In order to ensure that the generated queries return non-empty results set, our query generator searches for a substitution of the template variables such that the resulting property path matches with at least one path in the dataset. In case of property paths containing * and + operators, this path has to have a minimal length of n. To find such a substitution our query generator first generates so called grounding queries only consisting of SPARQL 1.0 features. These grounding queries are sent to an RDF store, which has loaded the dataset, to find actual IRIs as substitutions for the template variables. An example for such a grounding query is shown in listing 3. It checks if there exists a path of at least 4 edges labelled with ?p1. If this is the case ?s1 and thus the starting point of the query and ?p1, the property is returned. The substitutions found by the query generator are used to replace the template variables with concrete IRIs found in the dataset resulting in the final queries that can be executed to actually perform the benchmark. Listing 3: Grounding query for query template in listing 2 ensuring a path length of at least n = 4
Assuming the dataset shown in figure 1 and the query template in listing 2 the query generator executes the grounding query shown in listing 3 in order to fill the template variables in the respective template. Thus, ?s1 would be bound to snw:Ann and ?p1 to foaf:knows because there only exists a path from snw:Ann to snw:Eve that has a length of 4 and has the same IRI foaf:knows on each edge. The resulting query, which then can be executed on the dataset, is shown in listing 4.
PREFIX snw : h t t p : / / www. s o c i a l nw . com / PREFIX f o a f : h t t p : / / x m l n s . com / f o a f / 0 . 1 / SELECT ? o1 WHEREf <snw : Ann> < f o a f : knows >
? o1 . g
Listing 4: Benchmark query generated by query generator 3.2
Since we want to test for completeness and soundness of results, we need the correct and complete reference result sets for each generated query. These reference result sets are obtained with the help of a result set generator. This generator simulates queries that contain the inverse, sequence and alternative operator by executing one or more SPARQL1.0 queries that should return the same results as the property path queries. Furthermore, the generator can simulate the * and + property path expression by executing a breadth-first search. Thereby the data is retrieved with several SPARQL 1.0 queries4. We restrict these queries to SPARQL 1.0 since we assume that these features are implemented correctly for most RDF stores.
These queries are then send to all benchmarked RDF stores and the result sets are computed. For each query we compare the result sets of the different RDF stores. If the majority of the stores have the same result set we take this set as the correct result. If no majority can be found, we state that the result set is unknown. Thus, the completeness and soundness cannot be evaluated for this query.
Sometimes more than one query is needed to create the reference result set. In case of the prior created benchmark query in listing 4 the breadth-first search based result set generation works as follows: First a reference result set R is initialized with R = f(?o1; < snw : Ann >)g because the * operator also returns the starting point of the query. Then the query shown in listing 5 is executed that returns all vertices connected to snw:Ann by an edge labelled with foaf:knows and the results are added to R. After that the query is extended to reach all vertices that are connected to snw:Ann 4 The queries that are used to create the reference result set for each query template are listed in appendix A by a path containing two occurrences of foaf:knows. The query is shown in listing 6 and the results retrieved from executing this query are added to R. This is done until a query does not return any new results. Then R is enclosed and is defined as the final reference result set for the query.
PREFIX snw : h t t p : / / www. s o c i a l nw . com / PREFIX f o a f : h t t p : / / x m l n s . com / f o a f / 0 . 1 / SELECT ? o1 WHEREf
<snw : Ann> < f o a f : knows> ? o1 . g Listing 5: Query that retrieves vertices connected to snw:Ann by one occurrence of foaf:knows PREFIX snw : h t t p : / / www. s o c i a l nw . com / PREFIX f o a f : h t t p : / / x m l n s . com / f o a f / 0 . 1 / SELECT ? o1 WHEREf <snw : Ann> < f o a f : knows> ? r 1 .
? r 1 < f o a f : knows> ? o1 . g Listing 6: Query that retrieves vertices connected to snw:Ann by two occurrences of foaf:knows 3.3
The metrics of the new property path benchmark were chosen to focus on the completeness and soundness of results to ensure that the returned results are feasible and thus, the RDF store can be used with queries containing property paths.
Definition 15. Query soundness The percentage of right query results that are returned by each query. If Rq is the set of correct results for a query q and Rqs is the set of returned results of an executed query q where s is the name of the respective RDF store, then the query soundness is defined as s(q) = jRq \ Rqsj
jRqj c(q) = jRq \ Rqsj
jRqsj Definition 16. Query completeness The percentage of all possible query results of the query. If Rq is the set of correct results for a query q and Rqs is the set of returned results of an executed query q where s is the name of the respective RDF store then the query completeness On the other hand the execution time of queries is measured to compare the efficiency of query execution between the benchmarked stores.
Definition 17. Average execution time per query The arithmetic mean avexec(q) of the execution time t(q) of each query q. The average execution time per query is:
Pn avexec(q) = i=1 t(qi) where i is the ith execution of the query.
n Preparation phase: As first step of the benchmark execution, each blank node in the used dataset is replaced with an unique IRI. After that the dataset is loaded into the tested system. Then the query generator generates the queries from the query templates. After that the result queries are executed and thus, reference result sets are generated. Evaluation phase: In order to measure the query execution time of the benchmark on a warm store and thus, to evaluate how the tested system performs in an authentic setting, the query mix is executed twice before the actual metrics are measured. The queries of the query mix are executed one after another and not in parallel. The query mix is executed 10 times in order to have ample results. Queries that are not finished after one hour are aborted and counted as failed queries. From the results the highest and lowest execution times are deleted to prevent the effect of outliers. Query 1 to query 8 are all executed once, before query 1 is executed again to prevent caching of results. Finally the resulting metrics are returned in a human readable log file. 4
With the help of the property path benchmark defined in the previous section we benchmarked RDF stores frequently used in academia and industry. 4.1
Benchmarked stores: The benchmarked stores are Virtuoso 7.2.2 community edition5, RDF4J 2.0M1 formerly known as Sesame6, Apache Jena 3.0.17 and Allegrograph 6.0.2 free edition8.
Dataset: In [
The BTC 2014 dataset was crawled in 14 iterations called hops. In the first hop all
triples that contain a seed IRI as subject are crawled and added to the dataset. The
objects of these triples were used as the seed IRIs for the second hop. In these 14 hops
a dataset of about 4 billion quads was crawled [
Since the complete BTC 2014 dataset would consume a lot of time to be loaded without giving additional insight into the property path support of the RDF stores, we used only a subset of the complete dataset for our benchmark. This subset consists of the first three hops of the BTC dataset. This subset was preprocessed by iterating over all quads of the original dataset and deleting all syntactically incorrect quads. The remaining dataset consists of about 400 million quads.
The free edition of Allegrograph has a limit of 5 million triples [
Evaluation Environment: The RDF stores were benchmarked on a virtual machine with 8 GB RAM, 500 GB disk space, 4 2.9 Mhz processor cores and Ubuntu 14.04 running on it. The Java version on the machine has been 1.8.0.77. 4.2
While benchmarking Virtuoso, RDF4J and Allegrograph no errors or exceptions have occurred. During the benchmark process of Jena an OutOfMemoryError has been thrown whenever a query with the * operator was used. In order to identify the cause of the error, the amount of results the query should return has been limited to 100. The results that have been returned by a query of the form SELECT ?o WHERE fA B* ?o.g LIMIT 100 where A and B are valid IRIs, consisted of 100 times A. Due to this fact it is presumable that the query containing the * operator returns A recursively until the main memory was full. To ensure that this behaviour is not caused by cycles in the dataset a query of the same form but with a predicate IRI that did not exist in the dataset was executed. This query still returned 100 times A. This indicates, that the * operator is not implemented correctly.
Due to the problems with the * operator the queries 4, 7 and 8 could not be processed. Additionally query 3, 5, and 6 returned no results after 1 hour and thus, were aborted. Query 1 returned an empty and thus, incomplete result set. Only for query 2 a valid result was returned. Due to the lack of comparable results, Jena has been omitted in the comparison of triple stores.
As presented in table 1 the result sets of Virtuoso and RDF4J on the BTC dataset are different for almost all queries. For instance query 1 and 6 deliver completely different result sets, because for query 6 RDF4J returns 0 results and for query 1 Virtuoso returns 0 results. Due to the fact that 0 results were returned, nothing can be said about the soundness of results as it is depicted by - in the table. Only for query 5 Virtuoso and RDF4J returned the same result set.
RDF4J
Reference
Virtuoso
RqV irtuoso s(q) Query 1 = ˆP1 2 = P1/P2 3 = P1j P2 4 = P1* 5 = (P1j P2)/P3 6 = P1+/P2 7 = P1*j P2*j P3* 8 = P1+/P2* 9 http://wiki.dbpedia.org/Downloads2015-04 retrieved at 29.06.17
The soundness and completeness of the results of RDF4J is 100% for queries 1, 2, 3, 5, 7 and 8. For query 6 RDF4J returned an empty result set and for query 4 it only returns 1 out of 6 correct results. Thus, the soundness for the results is 100% for query 4 but the completeness is only 16.6%. On the other hand Virtuoso found the correct and complete result sets for queries 4, 5 and 6. For queries 7 and 8 Virtuoso returns correct but incomplete results. In case of query 1 Virtuoso returns none of the 4111 correct results. For query 2 Virtuoso misses 1 result and even returns a wrong result. Thus, it can be concluded that in our evaluation Virtuoso has problems with returning all results and in case of query 2 even correct results at all, whereas RDF4J seems to have problems only with the execution of * and + operators.
Due to this outcome we benchmarked only Allegrograph and RDF4J with the Polish DBpedia dump. In table 2 the amount of results in the reference dataset and the soundness and completeness of each store are displayed.
Query
Allegrograph
RDF4J The table shows that the result sets of Allegrograph and RDF4J are the same for each store and equal to the reference dataset. Thus, it can be concluded that the soundness and completeness of results is 100% for both stores.
Since RDF4J returned the correct result sets for the + and also for the * operators on the smaller Polish DBpedia dump but not on the larger BTC 2014 subset, RDF4J might ignore some intermediate results if the number of the intermediate results becomes to huge.
The execution times of Virtuoso and RDF4J can be compared only partly. Due to the fact that Virtuoso fails to return complete and sound results for most queries and RDF4J also fails to do so for some queries, the mere comparison of execution times of queries is not very meaningful. Only for query 5, where the result sets are complete and sound for Virtuoso and RDF4J, it can be said that RDF4J executed the query with 79ms faster than Virtuoso with 1122ms. Nothing can be said about the execution times for any of the other queries.
As shown in figure 2 the execution time for Allegrograph is higher for each query but query 5. Due to the fact that both stores return sound and complete result sets, it can be concluded that RDF4J evaluates queries with property path expressions more efficiently than Allegrograph. In our evaluation we evaluated the RDF stores Apache Jena, Virtuoso, RDF4J and Allegrograph, that are used frequently in academia and industry. Before performing the benchmark we expected that the RDF stores would process property path queries correctly. When performing our benchmark this expectation was not fulfilled. Jena could not return results for any query in under 1 hour besides query 2. Furthermore, the * operator could not be evaluated at all and the inverse operator returned empty result sets.
Virtuoso returned mostly incomplete results and in one case even a wrong result. RDF4J could handle most property path expressions but had problems with some queries containing the * and + operator when executed on the larger BTC 2014 subset. On the smaller Polish DBpedia dump RDF4J and Allegrograph could find the complete and correct result sets for all queries. All in all it can be said that our evaluation indicates that some RDF stores have shortcomings in the context of property paths. 5
When examining the already existing benchmarks for RDF stores, we found no benchmark that focused on evaluating the support of property paths. Nevertheless, we checked, whether the used queries could serve as a basis for property path queries.
The Berlin SPARQL Benchmark [
In [
The DBpedia SPARQL Benchmark [
The Semantic Publishing Benchmark [
To the best of our knowledge, no benchmark that evaluates the property path support of RDF stores in particular exists. Due to paths with a length of at most 3 traversed edges during query execution, none of the benchmarks provides queries that can be used as a basis for realizing queries testing the * or + operator support. 6
Property Paths that make it possible to define queries that match with an arbitrary amount of edges were introduced with SPARQL 1.1 in 2013. Already existing RDF stores were extended to make it possible to process queries containing such property paths. In order to evaluate how well these RDF stores handle property paths we introduced a novel benchmark. With our benchmark the RDF stores can be tested with several datasets. For each dataset queries are generated that test the implementation of the property path expressions. Beside the query execution time the benchmark also examines the completeness and soundness of the returned query results.
When benchmarking several RDF stores frequently used in academia and industry, especially the check of sound and complete query results lead to surprising results. Several tested RDF stores could not return complete result sets and in one case even incorrect results were returned. Furthermore, in our evaluation another RDF store needed over one hour to execute queries containing property paths. This long execution time indicates that queries with property paths are executed inefficiently.
In summary our evaluation indicates that the current implementations of property paths in frequently used RDF stores is not ready for practical usage. Thus, our novel property paths benchmark has shown to be a valuable tool to systematically evaluate the property path support of existing and future RDF stores.
A
In the following the query templates and the respective SPARQL 1.0 queries for the generation of the reference result set are presented. For query templates 1, 2, 3, 5 and 6 the reference result sets are obtained by simply executing the corresponding SPARQL 1.0 queries. Query 4 and 7 have an initial result set R = f(?o1; S1)g. These initial result sets are extended with results returned from SPARQL 1.0 queries that translate P1* into 1, 2, 3... matches of P1. This process stops if no new results can be added to the reference result set.
Query template 8 contains the sequence of P1+ and P2*. In this case we start with an empty result set and then systematically execute queries that first match P1 one or several times followed by zero, one or more matches of P2. We indicate this by showing intermediate reference result set creating queries, in which only P2* is translated. Each of these queries still contains P1+ that is then translated similar to the reference result set creating queries for query template 6. SELECT ? o1 WHEREf
? o1 ˆ P1 S1 . g SELECT ? o1 WHEREf
S1 P1 / P2 ? o1 . g SELECT ? o1 WHEREf
S1 P1 j P2 ? o1 . g
Query 1 Query 2
Query 3
Query 6 SELECT ? o1 WHEREf
S1 P1 j P2 j P3 ? o1 . g
Query 7 SELECT ? o1 WHEREf
S1 P1+/P2 ? o1 . g SELECT ? o1 WHEREf
S1 P1 ? r1 . ? r1 P1 ? r2 . ? r2 P2 ? o1 . g 8P 2 fP 1; P 2; P 3g SELECT ? o1 WHEREf
S1 P ? o1 . g SELECT ? o1 WHEREf
S1 P ? r1 . ? r1 P ? o1 . g SELECT ? o1 WHEREf
S1 P1+ ? o1 . g SELECT ? o1 WHEREf
S1 P1+/P2 ? o1 . g SELECT ? ( o1 ) WHEREf
S1 P1+/P2 / P2 ? o1 . g