The research on optimization of top-k SPARQL query would largely benefit from the establishment of a benchmark that allows comparing different approaches. For such a benchmark to be meaningful, at least two requirements should hold: 1) the benchmark should resemble reality as much as possible, and 2) it should stress the features of the topk SPARQL queries both from a syntactic and performance perspective. In this paper we propose Top-k DBPSB: an extension of the DBpedia SPARQL benchmark (DBPSB), a benchmark known to resemble reality, with the capabilities required to compare SPARQL engines on top-k queries.
Top-k queries – queries returning the top k results ordered according to a
userdefined scoring function – are gaining attention in the Database [
Recent works [
Following well known principles of benchmarking [
In this poster, we describe our ongoing work on Top-k DBpedia SPARQL
Benchmark (Top-k DBPSB). It extends the methodology, proposed in DBPSB [
In order to present Top-k DBPSB, we need to introduce some terminology: – Definition 1: Rankable Data Property is a RDF property whose range is in xsd:int, xsd:long, xsd:float, xsd:integer, xsd:decimal, xsd:double, xsd:date, xsd:dateTime, xsd:time, or xsd:duration. – Definition 2: Rankable Triple Pattern is a triple pattern that has a Rankable Data Property in the property position of the pattern. – Definition 3: When a variable, in the object position of a Rankable Triple Pattern, appears in a scoring criteria of the scoring function, we call it Scoring Variable and we call Rankable Variable the one appearing in the subject position.
In the first step, Top-k DBPSB looks for all rankable variables, in each auxiliary query of each BDPSB query template, which could be used as part of a ranking criterion in a scoring function. For each DBPSB auxiliary query, Top-k DBPSB first checks if the variables in the query fit the definition of scoring variable. To find additional rankable variable Top-k DBPSB considers all variables in the query and tries also to find rankable triple pattern related to them.
For the sake of simplicity, Top-k DBPSB generates scoring function as a weighted sum of normalized ranking criteria, therefore, for each rankable variable, Top-k DBPSB needs to compute its maximum and minimum value. So, for each DBPSB auxiliary query and each rankable triple pattern identified in the previous step, Top-k DBPSB generates a query to find those values.
After having collected those values, for each rankable triple pattern, Top-k DBPSB creates a new top-k query template. For instance, Query 2 of Figure 1 shows such a query as generated by the Top-K DBPSB. In order to obtain an executable query, for each scoring variable that appears in scoring function Top-K DBPSB adds the related rankable triple pattern to the body of the query. 1. 3
Given that we extended DBPSB we give for positively answered the first part of our research question (i.e., Top-k DBPSB resembles reality). In this section, we provide preliminary evidence that the query variability feature of Top-k DBPSB positively answers also the second part of our research question. We do so by operationalising our research question in three hypotheses: H.1 The more are the number of the Rankable Variables, the longer is the average execution time.
H.2 The more are the number of the Scoring Variables in the scoring function, the longer is the average execution time.
H.3 The value of the LIMIT clause has not any significant impact on the average execution time.
In order to evaluate our hypothesis, we carry out our experiments by using the SPARQL engines Virtuoso, and Jena. After preparing the experimental environment, we load the DBpedia dataset with the scale factors of 10% on the SPARQL engines. In order to evaluate the performance of SPARQL engines, we use the DBpedia SPARQL Benchmark test driver and modify it for Top-k queries. We execute the generated Top-k SPARQL queries against these two SPARQL engines. The information gains from the execution of randomly generated query against the SPARQL engines is used to evaluate our hypotheses.
As a result we got that most of the queries templates generated by Top-k DBPSB are compatible with our hypotheses H.2 and H.3. On the contrary, Topk DBPSB does not generate adequate query templates to test the hypothesis H.1: only 6 queries templates out of the 25 in DBPSB can be use in validating H.1 while the others have only one rankable variable. Further investigation is needed to refine the hypothesis H.1 and better qualify the cases that stress SPARQL engines when answering top-k queries. 1 The implementation code is available //bitbucket.org/sh_zahmatkesh/top − k − dbpsb online at https :
In this work, we presented Top-k DBPSB, an extension of DBPSB [
In order to support the claim that we positively answered to the research question presented in Section 1, we experimentally showed that the query variability provided by Top-k DBPSB stresses the SPARQL engines. To this end, we formulated three hypothesis and we empirically demonstrated that when the number of scoring variables increases the average execution time also does (hypothesis H.2) and that the average execution time is independent from the value used in the LIMIT clause (hypothesis H.3). Counterintuitively, hypothesis H.1 is not confirmed by our experiments.