Recursion in SPARQL

3.1.A fixed point based recursive operator

We have decided to implement a different approach and define a more expressive recursive operator that allows us compute the fixed point of a wide range of SPARQL queries. This is based on the recursive operator that was added to SQL when considering similar challenges. We cannot define this type of operator for SPARQL SELECT queries, since these returns mappings and thus no query can be applied to the result of a previous query, but we can do it for CONSTRUCT queries, since these return RDF graphs. Following [31], we now define the language of Recursive Queries. Before proceeding with the formal definition we illustrate the idea behind such queries by means of an example.

Example 3.1.

Recall graph G from Fig. 1. In the Introduction we made a case for the need of a query that could compute all pairs of articles (A,A′) such that A is linked to A′ by a path of wasRevisionOf links and where all of the revisions along the way were made by the same user. We can compute this with the recursive query of the Fig. 3.

Fig. 3.

Example of a recursive query.

Let us explain how this query works. The second line specifies that a temporary graph named: http://db.ing.puc.cl/temp

will be constructed according to the query below which consists of a UNION of two subpatterns. The first pattern does not use the temporary graph and it simply extracts all triples (A,U,B) such that A was a revision of B and U is the user generating this revision. All these triples should be added to the temporary graph.

Then comes the recursive part: if (A,U,B) and (B,U,C) are triples in the temporary graph, then we also add (A,U,C) to the temporary graph.

We continue iterating until a fixed point is reached, and finally we obtain a graph that contains all the triples (A,U,A′) such that A is linked to A′ via a path of revisions of arbitrary length but always generated by the same user U. Finally, the SELECT query extracts all such pairs of articles from the constructed graph.

As hinted in the example, the following is the syntax for recursive queries:

Note that in this definition q1 is allowed to use the temporary graph t, which leads to recursive iterations. Furthermore, the query q2 could be recursive itself, which allows us to compose recursive definitions.

As usual with this type of queries, semantics is given via a fixed point iteration.

In this definition, D1 is the union of D with a temporary graph t that corresponds to the evaluation of q1 over D, D2 is the union of D with a temporary graph t that corresponds to the evaluation of q1 over D1, and so on until Di+1=Di. Note that the temporary graph is completely rewritten after each iteration. This definition suggests the pseudocode of Algorithm 1 for computing the answers of a recursive query q of the form (1) over a dataset D.44

Algorithm 1

Computing the answer for recursive c-queries of the form (1)

To clarify Definition 3.2, we show how the temporary graph <http://db.ing.puc.cl/temp> evolves during the execution of the query from Fig. 3, when evaluated the graph in Fig. 1. The different values of temporary graph are show in Fig. 4. Here we call GTempi the instance of GTemp at the ith iteration of the loop presented in the Algorithm 1. We have two things to note: (1) GTemp0 is an empty graph, and (2) since we are working with graphs, there are no duplicated triples. Finally, we have GTemp3=GTemp4, and thus we stop the loop at the fourth iteration.

Fig. 4.

The step-by-step evaluation of the recursive graph <http://db.ing.puc.cl/temp>.

Obviously, the semantics of recursive queries only makes sense as long as the required fixed point exists. Unfortunately, we show in the following section that there are queries for which this operator indeed does not have a fixed point. Thus, we need to restrict the language that can be applied to such inner queries.55 We also discuss other possibilities to allow us using any operator we want.

3.2.Ensuring fixed point of queries

If we want to guarantee the termination of Algorithm 1, we need to impose two conditions. The first, and most widely studied, is that query q1 must be monotone: a c-query q is monotone if for all pair of datasets D1, D2 where D1⊆D2 it holds that ans(q,D1)⊆ans(q,D2). However, we also need to impose that the recursive c-query q1 preserves the domain: we say that a c-query q preserves the domain if there is a finite set S of IRIs such that, for every dataset D, the IRIs in q(D) either come from S or are already present in D. Let us provide some insight about the need for these conditions.

Monotonicity The most typical example of a problematic non-monotonic behaviour is when we use negation to alternate the presence of some triples in each iteration of the recursion, and therefore come up with recursive queries where the fixed point does not exists.

:s :p "b"

:s :p "a"

Similar examples can be obtained with other SPARQL operators that can simulate negation, such as MINUS or even arbitrary OPTIONAL [4,29].

Preserving the domain The BIND clause allows us to generate new values that were not in the domain of the database before executing a recursive query. Since completely new values may be generated for the temporary graph at each iteration, this may also imply that a (finite) fixed point may not exists, even if the query is monotone.

On the other hand, it is easy to verify that the query from Example 3.3 is monotone. By the Knaster–Tarski theorem [45], a monotone query always has a fixed point, however, such a fixed point need not be a finite dataset. Indeed, the fixed point for the query in Example 3.3 would have to contain triples linking each person in the original dataset with all the numbers larger than her or his initial age. This would make the fixed point infinite and thus not be a valid RDF graph.

One way to ensure that a fixed point of a monotone query is necessarily finite, is to make the underlying domain over which it operates finite. For instance, in Example 3.3, we are assuming that the domain over which queries operate is the set of all possible triple over I∪L, and not just the ones using IRIs and literals from the queried dataset. On the other hand, in the case of domain preserving queries, when considering the sequence (Di)i from Definition 3.2, our monotone queries can only construct triples over a finite set of IRIs and literals (the initial dataset, plus another finite set), thus making the fixed point necessarily finite.

Besides the BIND operator, we can also simulate the creation of new values by means of blanks in the construct templates, or even with blanks inside queries or subqueries.

Existence of a fixed point If we are working with queries that are both monotone and domain preserving, we can guarantee that the sequence (Di)i from Definition 3.2 always converges to a well defined RDF dataset. More precisely, as an immediate consequence of the Knaster-Tarski theorem [45], we can obtain the following:

It is important to note that the query q1 need not be monotone over the domain of all possible RDF datasets in order for q to converge over D. Indeed, in order to apply the Knaster–Tarski theorem, it suffices that q1 is monotone over the datasets that appear in the sequence (Di)i from Definition 3.2.

Next, we study which SPARQL queries are both domain preserving and monotone, in order to restrict the recursion to such queries.

3.3.Fragments where the recursion converges

We know that monotonicity and domain preservation allows us to define a class of recursive queries which will always have a least fixed point. The question then is: how to define a fragment of SPARQL that is both monotonic and domain preserving?

First, how can we guarantee that queries are monotonic? An easy option here is to simply disallow all the operators which can simulate negation such as OPTIONAL, MINUS, or negative FILTER conditions. Second, when it comes to guaranteeing that queries are domain preserving, we can simply prohibit them to use operators that can create new values such as BIND, or to use blanks in construct templates, queries or subqueries. This leads us to a first subclass of SPARQL queries for which can be used inside recursive queries.

Given that positive SPARQL queries are both monotone and domain preserving, as an easy corollary of Proposition 3.1, we obtain the following:

While positive queries do the trick, one might argue that they are quite restrictive. We can therefore wonder, whether it is possible to allow some form of negation, or the use of OPTIONAL?

In fact, literature has pointed out some more milder restrictions, that still do the trick. For instance, even though we disallow OPTIONAL, we note that our fragment of SPARQL is expressive enough to express rec-SPARQL queries in which q1 is given by positive SPARQL with well-designed optionals [40]. This is because for CONSTRUCT queries, the fragment we consider has been shown to contain queries defined by union of well designed graph patterns [31]).

The second, more expressive fragment to consider, loosens the restrictions we put on the use of negation. The idea is that bad behaviour of negation, such as the one shown in Example 3.2, only occurs when negation involves the same graph that is being constructed in the fixed point. Therefore, we will consider a fragment of rec-SPARQL queries which allow negation whenever it does not involve the graph being constructed in the recursive portion of the query.

Essentially, with stratified positive rec-SPARQL we allow some degree of negation, but we need to make sure this negation does not involve the temporal graph under construction.

While stratified positive rec-SPARQL need not be monotone with respect to the domain of all possible RDF datasets, they are monotone in the context of the sequence (Di)i from Definition 3.2. More precisely, any stratified positive rec-SPARQL of the form (2) is such that q1 is monotone with respect to the named graph t, meaning that, for datasets D and D′ that only differ in the named graph t, if ⟨t,G⟩ is the graph named t in D, ⟨t,G′⟩ is the graph t in D′, and G⊆G′, then ans(q1,D)⊆ans(q1,D′). We can then confirm that our semantics is well-defined for positive or stratified positive rec-SPARQL as an easy corollary of Proposition 3.1.

3.4.Expressive power

As a way to gauge the power of our language, we turn to the language datalog. Datalog (and ASP) has been used to pinpoint the expressive power of SPARQL (see e.g. [41]). For our case, it suffices to define positive Datalog, and Datalog with negation under stratified semantics.

A positive Datalog program Π consists of a finite set of rules of the form S(x¯)←R1(y¯1),…,Rm(y¯m), where S,R1,…,Rm are predicate symbols, y¯1,…,y¯m are tuples in V∪I and x¯ is a tuple of variables already appearing in y¯1,…,y¯m. In a rule of this form, S is said to appear in the head of the rule, and R1,…,Rm in the body of the rule. A predicate that occurs in the head of a rule is called intensional predicate. The rest of the predicates are called extensional predicates. Further, we assume that each program has a distinguished intensional predicate called the answer of Π, and denoted by Ans.

Let P be an intensional predicate of a positive Datalog program Π and I a set of predicates. For i⩾0, PΠi(I) denote the collection of facts about the intensional predicate P that can be deduced from I by at most i applications of the rules in Π. Let PΠ∞(I) be ⋃i⩾0PΠi(I). Then, the answer Π(I) of Π over I is AnsΠ∞(I).

Datalog programs with negation extend positive datalog with rules of the form

For positive datalog programs Π with stratified negation, we can compute the answer Π(I) of Π over a set I of predicates as follows. Let C1,…,Cℓ be a partition satisfying the conditions for stratified negation. We compute sets I1,…,Iℓ of predicates, as follows. Let I=I0. For each 1⩽k⩽ℓ, let Πk be the set of rules mentioning a predicate in Ck on their head. Notice that by definition of stratification, all predicates mentioned in the head or body of Πk must belong to some Ck′ with k′⩽k. Then Ik=Ik−1∪⋃P∈CkPΠk∞(Ik−1). Finally, the answer Π(I) is AnsΠℓ∞(I).

Since we are using Datalog to query RDF databases, we only focus on programs in which all extensional predicates are ternary predicates of the form Tg, with g an IRI. We can then represent each dataset D as a set I of predicates containing one ternary relation Tg per each graph in g. We can then treat datalog programs as c-queries: on input D, the constructed graph of a program Π contains all predicates in Π(I), where I is the representation of the dataset D we have just defined. Abusing the notation, we will write Π(D) to speak of this RDF graph.

In order to study the expressive power of rec-SPARQL, we first compare positive c-queries and stratified positive c-queries with datalog. It follows from Polleres and Wallner [41] (see Table 1) that our fragment of positive c-queries can be translated into positive datalog, in the following sense: For each c-query q one can construct a positive datalog program Π such that ans(q,D)=Π(D) for every dataset D. Moreover, by inspecting the construction by Polleres and Wallner, one also gets that stratified positive c-queries can be translated into datalog with stratified negation, in the same terms. From these results, we further obtain that any positive or stratified positive rec-SPARQL query can be translated as well into positive datalog or datalog with stratified negation, respectively.

We note that the other direction is currently open: we do not know if every stratified positive datalog program can be translated into stratified positive rec-SPARQL. On the surface, and given the result that SPARQL can express all stratified positive datalog queries (see e.g. [31], it would appear that we can. However, rules in datalog programs may incur in all sort of simultaneous fixed points, as the dependency graph in programs need not be a tree. In standard datalog one can always flatten these simultaneous rules so that the resulting dependency graph is tree-shaped, but the only constructions we are aware of must incur in predicates with more than three positions, that we don’t currently know how to store in the graphs constructed by rec-SPARQL.

On the other hand, when datalog programs disallow all sort of simultaneous fixed points, a translation is surely possible.

While this result may sound narrow, it already gives us a tool to compare again some other recursive languages proposed for graphs and RDF. For example, the language of regular queries [43] is a datalog program whose only cicles in its dependency graph are self loops, so we immedately have that rec-SPARQL can express any Regular Query. Another language with a similar recursion structure is TriAL [32], and we can also use that rec-SPARQL can express any TriAl query. On the other hand, it does not give us much in terms of more expressive languages such as [6], for which the comparison would require more work.

3.5.Complexity analysis

Since recursive queries can use either the SELECT or the CONSTRUCT result form, there are two decision problems we need to analyze. For SELECT queries, we define the problem SelectQueryAnswering, that receives as an input a recursive query q using the SELECT result form, a tuple a¯ of IRIs from I and a dataset D with default graph G0, and asks whether a¯ is in ans(q,D). For CONSTRUCT queries, the problem ConstructQueryAnswering receives a recursive query q using the CONSTRUCT result form, a triple (s,p,o) over I×I×I and a dataset D, and asks whether this triple is in ans(q,D).

Thus, at least from the point of view of computational complexity, our class of recursive queries are not more complex than standard select queries [39] or construct queries [31]. We also note that the complexity of similar recursive queries in most data models is typically complete for exponential time; what lowers our complexity is the fact that our temporary graphs are RDF graphs themselves, instead of arbitrary sets of mappings or relations.

For databases it is also common to study the data complexity of the query answering problem, that is, the same decision problems as above but considering the input query to be fixed. We denote this problems as SelectQueryAnswering(q) and ConstructQueryAnswering(q), for select and result queries, respectively. The following shows that the problem remains in polynomial time for data complexity, albeit in a higher class than for non recursive queries.

From a practical point of view, and even if theoretically the problems have the same combined complexity as queries without recursion and are polynomial in data complexity, any implementation of the Algorithm 1 is likely to run excessively slow due to a high demand on computational resources (computing the temporary graph over and over again) and would thus not be useful in practice. For this reason, instead of implementing full-fledged recursion, we decided to support a fragment of recursive queries based on what is commonly known as linear recursive queries [1,24]. This restriction is common when implementing recursive operators in other database languages, most notably in SQL [42], but also in graph databases [18], as it offers a wider option of evaluation algorithms while maintaining the ability of expressing almost any recursive query that one could come up with in practice. For instance, as demonstrated in the following section, linear recursion captures all the examples we have considered thus far and it can also define any query that uses property paths. Furthermore, it can be implemented in an efficient way on top of any existing SPARQL engine using a simple and easy to understand algorithm. All of this is defined in the following section.

4.1.Linear recursive queries

The concept of linear recursion is widely used as a restriction for fixed point operators in relational query languages, because it presents a good trade-off between the expressive power of recursive operators and their practical applicability.

Commonly defined for logic programs, the idea of linear queries is that each recursive construct can refer to the recursive graph or predicate being constructed only once. To achieve this, our queries are made from the union of a graph pattern that does not use the temporary IRI, denoted as pbase and a graph pattern prec that does mention the temporary IRI. Formally, a linear recursive query is an expression of the form

Notice that we enforce a syntactic separation between base and recursive query. This is done so that we can keep track of changes made in the temporary graph without the need of computing the difference of two graphs, as discussed in Section 4.2. This simple yet powerful syntax resembles the design choices taken in most SQL commercial systems supporting recursion,66 and is also present in graph databases [18].

To give an example of a linear query, we return to the query from Fig. 3. First, we notice that this query is not linear. Nevertheless, it can be restated as the query from Fig. 5 that uses one level of nesting (meaning that the query qout is again a linear recursive query). We note that the union in the first query can obviously be omitted, and is there only for clarity (our implementation supports queries where either pbase or prec is empty). The idea of this query is to first dump all meaningful triples from the original dataset into a new graph named http://db.ing.puc.cl/temp1, and then use this graph as a basis for computing the required reachability condition, that will be dumped into a second temporary graph http://db.ing.puc.cl/temp2.77

Fig. 5.

Example of a linear recursion.

4.2.Algorithm for linear recursive queries

The main reason why linear queries are widely used in practice is the fact that they can be computed piece by piece, without ever invoking the complete database being constructed. More precisely, if a query Q=WITHRECURSIVEtAS{q1}q2 is linear, then for every dataset D, the answer ans(Q,D) of the query can be computed as the least fixed point of the sequence given by

In other words, in order to compute the i+1-th iteration of the recursion, we only need the original dataset plus the tuples that were added to the temporary graph t in the i-th iteration. Considering that the temporary graph t might be of size comparable to the original dataset, linear queries save us from evaluating the query several times over an ever increasing dataset: instead we only need to take into account what was added in the previous iteration, which is generally much smaller.

Unfortunately, it is undecidable to check whether a given recursive query satisfies the property outlined above (under usual complexity-theoretic assumptions, see [23]), so this is why we must guarantee it with syntactic restrictions. We also note that most of the recursive extensions proposed for SPARLQ have the aforementioned property: from property paths [26] to nSPARQL [40], SPARQLeR [30], regular queries [43] or Trial [32], as well as our example.

As for the algorithm, we have decided to implement what is known as seminaive evaluation, although several other alternatives have been proposed for the evaluation of these types of queries (see [24] for a good survey). In order to describe our algorithm for evaluating a query of the shape (4), we abuse the notation and speak of qbase to denote the query CONSTRUCTHWHEREpbase and qrec to denote the query CONSTRUCTHWHEREprec. Our algorithm for query evaluation is presented in Algorithm 2.

Algorithm 2

Computing the answer for linear recursive c-queries of the form (4)

So what have we gained? By looking at Algorithm 2 one realizes that in each iteration we only evaluate the query over the union of the dataset and the intermediate graph Gtemp, instead of the previous algorithm where one needed the whole graph being constructed (in this case Gans). Furthermore, qbase is evaluated only once, using qrec in the rest of the iterations. Considering that the temporary graph may be large, and that no indexing scheme could be available, this often results in a considerable speedup for query computation.

Expressive power of linear queries In Section 3.4 we show that all stratified positive recursive SPARQL queries can be defined in datalog, but have no matching result in the other direction. When it comes to linear queries, we can mirror the same result. The definition of linear datalog is quite straightforward: a datalog rule is linear if there is at most one atom in the body of the rule that is recursive with the head. For example, the rule E(x,y):−R(x),E(x,y) is linear, while E(x,y):−R(x),E(x,z),E(z,y) is not, since it uses the head predicate recursively twice. A datalog program is linear if all of its rules are linear.

With this in mind, we can again show that every linear positive rec-SPARQL query can be transformed into linear positive datalog, and likewise for linear stratified positive rec-SPARQL and linear stratified datalog (note that the translation outlined in the proof of Proposition 3.4 preserves linearity). Unfortunately, for the other direction we have the same problem, as we are not sure whether our recursive languages can express every linear positive or stratified positive datalog program. Of course, we can also mirror Proposition 3.5 for linear queries. Thus, linear languages such as regular queries [43] or Trial [32] can be also translated into linear queries.

4.3.Supporting arbitrary queries in recursive clauses

Although we show in Section 3 that recursive queries which include some form of negation can be impossible to evaluate, there is no doubt that queries including negation are very useful in practice. In this section we briefly discuss how such queries can be mixed with linear recursion.

Limiting the recursion depth In practice it could happen that an user may not be interested in having all the answers for a recursive query. Instead, the user could prefer to have only the answers until a certain number of iterations are performed. We propose the following syntax for to restrict the depth of recursion to a user specified number k:

It is easy to see that this extension is useful for handling queries which include negation, or which create values by means of blanks or a BIND clause. Namely, if we fix the number of iterations of a recursive query, we can ensure that these queries terminate their execution, regardless of the existence of a fixed point.

Other ways of supporting negation Limiting the number of iterations can also give us a way of allowing more complex c-queries inside the recursive part of recursive queries. This is not an elegant solution, but can be made to work: since the number of iterations is bounded, we don’t longer need queries to ensure that our graph has a fixed point operator.

We also mention that there are other, more elegant solutions, but we do not investigate them further as they drive us out of what can be implemented on top of SPARQL systems, and is out of the scope of this paper. For example, a possible solution to support BIND and negation is to extend the semantics by borrowing the notion of stable models from logic programs (see e.g. [37]). Moreover, one could redefine rec-SPARQL to consider a partial fixed point in Definition 3.2 instead of the least-fixed point. This approach simply assumes a query that does not converge gives an empty result. It is a clean theoretical solution, but it is not a good approach for practice.

Studying these extensions to rec-SPARQL is an important topic for future work, and in particular the stable model semantics approach may require an interesting combination of techniques from both databases and logic programming.

5.1.Evaluating real use cases

The first thing we do is to test our implementation against realistic use cases. As we have mentioned, we do not aim to obtain the fastest possible algorithms for these particular use cases (this is out of the scope of this paper), but rather aim for an implementation whose execution times are reasonable. For this, we took the LMDB and the YAGO datasets, and built a series of queries asking for relationships between entities. Since YAGO also contains information about movies, we have the advantage of being able to test the same queries over different datasets (their ontology differs). The specifications for each database can be found in the Table 1. Note that the size is the one used by Jena TDB to store the datasets.

To the best of our knowledge, it is not possible to compare the full scope of our approach against other implementations. While it is true that our formalism is similar to the recursive part of SQL, all of the RDF systems that we checked were either running RDF natively, or running on top of a relational DBMS that did not support the recursion with common table expressions functionality, that is part of the SQL standard. OpenLink Virtuoso does have a transitive closure operator that can be used with its SQL engine, but this operator is quite limited in the sense that it can only compute transitivity when starting in a given IRI. Our queries were more general than this, and thus we could not compare them directly. For this reason, in this set of experiments we will only discuss about the practical applicability of the results.

Our round of experiments consists of three movie-related queries, which will be executed both on LMDB and YAGO, and two additional queries that are only run in YAGO, because LMDB does not contain this information. All of these queries are similar to that of Example 3.1 (precise queries are given in the Appendix). The queries executed in both datasets are the following:

The queries executed only in the YAGO dataset where the following:

Note that QA, QD and QE are also expressible as property paths. To fully test recursive capabilities of our implementation we use another two queries, QB and QC, that apply various tests along the paths computing the Bacon number. Recall that the structure of queries QB and QC is similar to the query from Example 3.1 and cannot be expressed in SPARQL 1.1 either.

Fig. 6.

Running times and the number of output tuples for the three datasets.

The results of the evaluation can be found in Figs 6(a) and 6(b). As we can see the running times, although high, are reasonable considering the size of the datasets and the number of output tuples (Figs 6(c) and 6(d)). The query QE is the only query with a small size in its output and a high time of execution. This fact can be explained because the query is a combination of 2 property paths that required to instantiate 2 recursive graphs before computing the answer.

5.2.Comparison with property paths using the GMark benchmark

As mentioned previously, since to the best of our knowledge no SPARQL engine implements general recursive queries, we cannot really compare the performance of our implementation with the existing systems. The only form of recursion mandated by the latest language standard are property paths, so in this section we show the results of comparing the execution of property paths queries in our implementation using our recursive language against the implementation of property paths in popular systems.

We used the GMark benchmark [9] to measure the running time of property paths queries using Recursive SPARQL, and to compare such times with respect to Apache Jena and Openlink Virtuoso.

The GMark benchmark allows generating queries and datasets to test property paths, and one of its advantages is that the size of the datasets and the patterns described by the queries are parametrized by the user. Using the benchmark we generated three different graphs of increasing size, named G1,G2 and G3. The specifications for each graph can be found in Table 2. We also generated 10 SPARQL queries that could have one or more property paths of different complexities. The queries can be found in the Appendix. The run times our queries are presented in the Fig. 7 for the graph G1, in Fig. 8 for G2, and in Fig. 9 for G3.

Fig. 7.

Times for G1.

Fig. 8.

Times for G2.

Fig. 9.

Times for G3.

Note first that every property path query is easily expressible using linear recursion. With this observation in mind we must also remark that we are comparing the performance of our more general recursive engine with property paths, which are a much less expressive language. For this reason highly efficient systems like Virtuoso should run property paths queries faster: they do not need to worry about being able to compute more recursive queries. Of course, it would also be interesting to compare our engine with specific ad-hoc techniques for computing property paths.

Comparison with Virtuoso Virtuoso cannot run queries 2, 6, 7 and 8, because the SPARQL engine requires an starting point for property paths queries, which was not possible to give for such queries. We can see that Virtuoso outperforms Jena and the Recursive implementation in almost all the queries that they can run, except for Query 1, where the running time goes beyond 25 seconds. As we will discuss later, this can be explained because of the semantic they use to evaluate property paths, which makes Virtuoso to have many duplicated answers. For the remaining queries, we can see that the execution time is almost equals.

Comparison with Jena Apache Jena can also answer all queries. However, our recursive implementation is only clearly outperformed in Query 2 and Query 6. This is mainly because those queries have patterns of the form:

?x <:p1|:p2>* ?z

and our system is not optimized for working with unions of predicates. Remarkably, and even though all of the generated queries are relatively simple, our implementation reports a faster running time in half of the queries we test. Note that Q7, Q8 and Q9 have an answer time considerably worse in Jena than in our recursive implementation, where the time goes beyond the 25 seconds. We can only speculate that this is because the property paths has many paths of short length and because Apache Jena cannot manage properly the queries with two or more star triple patterns.

When we increase the size of the graph, the results have the same behaviour. It is also more evident which queries are easier and harder to evaluate for the existing systems. The result for the increased size of the graph can be found in the Figs 8 and 9.

Number of outputs As we said before, one interesting thing that we note from the previous experiments is the time that Virtuoso took to answer the query Q1 in the three dataset. We suspect that this could occur because Virtuoso generates many duplicate results, thus the output should be higher with respect to rec-SPARQL and Jena. We count the number of outputs for the queries ran over the first graph. The results can be seen in Table 3.

The first thing to note is that we avoid duplicate answers in our language, mainly because of the UNION operator used in lineal recursion, which deletes the duplicates answers. Also we do not consider paths of length 0, because those results do not give us any relevant information about the answer. Then we can see that Apache Jena has always more results than us, this is mainly because they consider paths of length 0. We did not rewrite the queries because we wanted keep them as close as possible to the benchmark. In Virtuoso one needs a starting point for property path queries, so this system does not consider paths of length 0 and for that reason in some queries they have less outputs than Apache Jena. However, in most of the queries they give more results than Apache Jena and RecSPARQL, because they produce many duplicate answers and thus, the answer time becomes considerably worse. This happen mainly in the first query, which is the simplest one. The same effect happen for the 2 bigger graphs. The number of outputs for the bigger graphs can be found in the Appendix (Tables 5 and 6).

5.3.Tests over large datasets

We wanted to know how our recursive operator works when the queries are executed over large datasets. Thus, we decided to try our implementation with queries over the graph of Wikidata, so we load the “truthy” dump from 2018/11/15. This dump contains 3,303,288,386 triples. For this set of experiments we use a server Devuan GNU/Linux 3 (beowulf) with an Intel Xeon Silver 4110 CPU @ 2.10 GHz processor and 120 GB of memory.

We create property paths queries based on (1) the example queries showed at the Wikidata Endpoint and (2) the LMDB queries from Section 5.1. The queries are the following:

Queries Q1, and Q4 are simple star * queries, while Q3 is a star query where in each iteration only one triple is added to the recursive graph. Q2 is a query of the form (wdt:p1/wdt:p2*), while Q5 combines two properties within a star.

We rewrote the property paths as WITHRECURSIVE queries and we ran them on our server setup. We display the results in Table 4. As a reference, we also put the time that the queries took at the Wikidata endpoint https://query.wikidata.org/. We note that this is not an exact comparison as the endpoint dataset might slightly differ from the one we use, and the server running the endpoint is likely different from ours. The values are expressed in seconds.

As we see, the trend shown with the previous experiments is repeated again with a large dataset: Recursive SPARQL is competitive against existing solutions. Since the dataset of Wikidata is larger than previous datasets and our solution implies to do several joins, we expected easier queries to have better running times in the endpoint than in our implementation. However, the running times our solution displays are still competitive. Finally, we remark the result for Q5, where our implementation could answer the query in a reasonable time, and the endpoint times out.

5.4.Limiting the number of iterations

In Section 4.3 we presented a way of limiting the depth of the recursion. We argue that this functionality should find good practical uses, because users are often interested in running recursive queries only for a predefined number of iterations. For instance, very long paths between nodes are seldom of interest and in a wast majority of use cases we will be interested in using property paths only up to depth four or five.

It is straightforward to see that every query defined using recursion with predefined number of iterations can be rewritten in SPARQL by explicitly specifying each step of the recursion and joining them using the concatenation operator. The question then is, why is specifying the recursion depth beneficial?

One apparent reason is that it makes queries much easier to write and understand (as a reference we include the rewritings of the query QA, QB and QC from Section 5.1 using only SPARQL operators in the online Appendix). The second reason we would like to argue for is that, when implemented using Algorithm 2, recursive queries with a predetermined number of steps result in faster query evaluation times than evaluating an equivalent query with lots of joins. The intuitive reason behind this is that computing qbase, although expensive initially, acts as a sort of index to iterate upon, resulting in fast evaluation times as the number of iterations increases. On the other hand, for even a moderately complex query using lots of joins, the execution plan will seldom be optimal and will often resort to simply trying all the possible matchings to the variables, thus recomputing the same information several times.

We substantiate this claim by running two rounds of experiments on LMDB and YAGO datasets, using queries QA, QB and QC from Section 5.1 and running them for an increasing number of steps. We evaluate each of the queries using Algorithm 2 and run it for a fixed number of steps until the algorithm saturates. Then we use a SPARQL rewriting of a recursive query where the depth of recursion is fixed and evaluate it in Jena and Virtuoso.

Fig. 10.

Limiting the number of iterations for the evaluation of QA, QB and QC over LMDB.

Fig. 11.

Limiting the number of iterations for the evaluation of QA and QC over Yago.

Figure 10 shows the results over LMDB and Fig. 11 shows the results over YAGO. The time out here is again set to two minutes. As we can see, the initial cost is much higher if we are using recursive queries, however as the number of steps increases we can see that they show much better performance and in fact, the queries that use only SPARQL operators time out after a small number of iterations. Note that we did not run the second query over the YAGO dataset, because it ends in two iterations, and it would not show any trend. We also did not run queries QD and QE. Query QD was timing out also after two iterations on Jena and Virtuoso, and query QE is composed of two property paths, so there is no straightforward way to transform it in a query with unions.