SPARQL property path queries provide a concise way to write complex navigational queries over RDF knowledge graphs. However, the evaluation of these queries over online knowledge graphs such as DBPedia or Wikidata are often interrupted by quotas, returning no results or partial results. Decomposing SPARQL property path queries into triple pattern subqueries allows to get complete results. However, such decomposition generates a high number of subqueries, a large data transfer and finally delivers poor performances. In this paper, we propose an algorithm able to decompose SPARQL property path queries into Basic Graph Pattern (BGP) subqueries. As BGP queries are guaranteed to terminate on preemptable SPARQL servers, property path queries always deliver complete results. Experimental results demonstrate that our approach outperforms existing approaches in terms of HTTP calls, data transfer and query execution time.
Context and motivation: Property path queries provide a concise way to
write sophisticated navigational queries in Knowledge Graphs (KGs). SPARQL
queries with property paths are largely used. They represent a total of 38% of
the entire log of wikidata [
Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). s e l e c t ? oeuvre ? i n s p i r a t i o n where { ? oeuvre wdt : P144 ? i n s p i r a t i o n . ? oeuvre wdt : P31/wdt : P279∗ wd : Q17537576 .
? i n s p i r a t i o n wdt : P136 wd : Q8253 } (a) Q1: Creative works and the list of fiction works that inspired it on Wikidata @ p r e f i x owl : <http ://www. w3 . org /2002/07/ owl#> @seplreecfti x ?xf o?a of : w<hhetretp {:// xmlns . com/ f o a f /0.1/> ?x f o a f : name ?n .
?x owl : sameAs∗ ?o . } (b) Q2: list of similar entities on
DBPedia a set of triple patterns. Unlike TPF servers, Preemptable servers support BGPs.
Unfortunately, there is currently no algorithm to decompose a property path query into BGP subqueries.
Approach and Contributions: In this paper, we propose an algorithm able to decompose a SPARQL property path query into BGP subqueries with filters and unions. As the generated subqueries are guaranteed to terminate when processed by a preemptable SPARQL server, the property path queries are executed online and always return complete results.
The contributions of the paper are the following: (i) We define an algorithm that computes a compressed automaton for SPARQL property path queries.
The algorithm allows to decompose the SPARQL property path queries into BGP subqueries. (ii) We compare the performance of our approach with existing approaches (TPF and SaGe). Experimental results demonstrate that the compressed automata approach outperforms existing approaches by several orders of magnitude in terms of HTTP calls, execution time and data transfer.
This paper is organized as follows. Section 2 reviews related works. Section 3 introduces SPARQL property path queries and automata as property path expressions models. Sections 4 presents the automata compression approach in the context of the web preemption. Section 5 presents our experimental results.
Finally, the conclusion is outlined in Section 6. 2
Property paths were introduced in SPARQL 1.1 2 to add extensive navigational
capabilities to the SPARQL query language. Property paths closely correspond
to regular expressions and are crucial to perform non-trivial navigation in
knowledge graphs. Regular expressions involve operators such as ’ * ’ (zero or more
occurrences-kleene star), ’ | ’ (OR operator), ’ / ’ (sequence operator), ’ ^ ’
(inverse operator), ’ ! ’ (NOT operator) that allow to describe complex paths of
arbitrary length. For instance, the query SELECT ?x ?y WHERE ?x foaf:knows*
?y require to compute the transitive closure of the relation f oaf : knows over
all pairs x; y present in the KG. Many techniques [
Breadth First Search or Depth First Search algorithms compute transitive
closures with a time complexity in O(jEj + jV j) and a space complexity in O(jV j2),
with E and V the finite set of KG edges and vertices, respectively. Even if
different optimisations have been proposed [
This makes the evaluation of property path queries challenging on online
Knowledge Graphs such as DBPedia or Wikidata. To ensure a fair usage policy of
resources, public SPARQL endpoints enforce quotas [
To overcome quotas limitations, KG providers publish dumps of their data. However, re-ingesting billions of triples on local resources to compute SPARQL property path queries is extremely costly and raises issues with freshness. Moreover, it is an offline approach, and in this paper we want to execute property path queries online and get complete results.
To overcome quota limitations, it is also possible to decompose SPARQL queries
into subqueries that may terminate under quotas [
The TPF client [
respectively, at August 5 2020.
SaGe implements the web preemption [
A BGP decomposition is much more efficient than a triple pattern
decomposition, as it generates less subqueries and transfers less intermediate results.
Unfortunately, there is no algorithm able to decompose property path into BGP
queries. In this paper, we propose an algorithm of decomposition based on
automaton compression. Similar automaton compression techniques have been
already used in other domains, but not related to query processing [
We recall briefly definitions related to the proposal of the paper. 3.1
SPARQL Queries : We follow the notation from [
A SPARQL graph pattern expression P is defined recursively as follows.
1. A tuple from (I [ L [ V ) (I [ V ) (I [ L [ V ) is a triple pattern.
2. If P 1 and P 2 are graph patterns, then expressions (P1 AND P2), (P1 OPT
P2), and (P1 UNION P2) are graph patterns (a conjunction graph pattern,
an optional graph pattern, and a union graph pattern, respectively).
3. If P is a graph pattern and R is a SPARQL built-in condition, then the
expression (P FILTER R) is a graph pattern (a filter graph pattern).
SPARQL Property Path Queries: The SPARQL 1.1 language [
q0 :A a d a q1 q4
(a) :B b a d e b d q2 q5 c
q3 :C c :D (c) path expressions, i.e. the inverse path is denoted by e e1 + e2 4.
Property path expressions are defined by the grammar: and alternative path e := a j e
j e1 e2 j e1 + e2 j e+ j e j e? j !a1; : : : ; ak j !a1 ; : : : ; ak ; where a; a1; : : : ; ak are properties, i.e. IRIs in I. A single property is called a predicate path expression. It is the smallest path expression and it can only match paths of length one, i.e. triple patterns. Expressions of the forms (e1 e2), (e1 + e2), (e+ ) and (e?) are respectively called sequence, alternative, transitive and optional path expressions. Expressions of the last two forms (i.e. starting with !) are called negated property sets. The set of all property paths expressions is denoted by P P .
Definition 2 (Property Path [
Property path patterns are incompatible with triple patterns, because they allow property path expressions in predicate positions but forbid variables in these positions. 3.2
A finite automaton is often used to represent a property path expression [
To evaluate the query Q=select * where {:A P ?y} over the graph G1 in
Figure 2c, an automaton-based approach [
The mono-predicate automaton in Figure 2a is equivalent to the automaton presented in Figure 2b, i.e. they both recognize the same language. Compared to the mono-predicate automaton, transitions in the second automaton are labeled with more complex expressions such as sequences and alternatives. We call this automaton a multi-predicate automaton.
If both automata are equivalent, evaluating the path expression with the multipredicate automaton generates BGP subqueries with union, which is much more efficient than evaluating triple pattern subqueries. Obviously, the second automaton is a compressed version of the first one. The scientific problem is to write an algorithm able to transform any mono-predicate automaton into an equivalent minimal multi-predicate automaton according to servers capabilities. A multi-predicate automaton is said to be minimal if it does not exist another equivalent multi-predicate automaton with less states and transitions, according to a set of operators supported by a server, i.e. server capabilities. For example, a mono-predicate automaton is a minimal multi-predicate automaton for a TPF server, as TPF only supports triple pattern queries. For a server supporting BGP and union such as SaGe, the multi-predicate automaton of Figure 2b is minimal, while the multi-predicate automaton presented in Figure 3d is not.
In this paper, we only consider predicate, sequence, alternative and transitive path expressions. Optionals are ignored as they are naturally rewritten as alternatives when a property path expression is converted into a finite automaton. Concerning negated property sets and inverse path expressions, they can be treated as special cases of predicate path expressions. An inverse path expression can be rewritten as a triple pattern whose subject and object have been reversed, while a negated property set can be rewritten as a triple pattern whose predicate is a variable that is associated to a "not in" filter condition to exclude unwanted properties. 4.1
In this section, we describe an algorithm to transform a mono-predicate automaton into a multi-predicate automaton. The algorithm is composed of two parts: 1. We first build an automaton for sequence path expressions, i.e. not considering alternatives. This produces a first compressed automaton that may be not minimal. 2. Second, we compress the automaton produced by the previous step considering alternatives to produce a minimal compressed automaton. 4.1.1
When a property path expression is converted into a mono-predicate automaton, sequences without transitive closures are converted into paths of mono-predicate transitions, such that (1) consecutive transitions are connected together by an intermediate state, (2) paths start from a non-intermediate state, (3) paths go to a non-intermediate state.
Definition 3 (Intermediate state). A state is called an intermediate state if and only if (1) it is not a start state, (2) it is not a final state, (3) it has no self transition.
For example, in the mono-predicate automaton of the property path P = ((a b c)+(d e))+, the sequence (a b c) corresponds to the paths <(q0; a; q1); (q1; b; q2), (q2; c; q3)>, <(q3; a; q1); (q1; b; q2); (q2; c; q3)>, <(q5; a; q1); (q1; b; q2); (q2; c; q3)> where q0, q3 and q5 are non-intermediate states, while q1 and q2 are intermediate states.
Consequently, the first step to build a minimal multi-predicate automaton is to replace these paths by single transitions that are labeled with the corresponding sequence path expressions. As only paths extremities are non-intermediate a d q1 q4 b d e a=b=c q0 d=e a=b c q3
a=b=c a=b=c a=b=c d=e q3
a=b=c a=b=c start d=e a=b=c start q0 a d a d start q0 a=b a d a=b start q0 a=b a d a=b (a) Replacing paths that go through q1 (b) Replacing paths that go through q2 q1 q4 q1 q4
a=b=c a=b a d=e b d e b d e a=b c
q3 a q2 q5 a q2 a=b c d ab d=e q5 d=e a q2 q5 q3 q5 (c) Replacing paths that go through q4 (d) Result of replacing paths between non-intermediate states by the shortest paths states, a simple solution to achieve this is to compute the shortest paths between the non-intermediate states, before removing the intermediate states and all transitions that are connected to one of them. Algorithm 1 follows this procedure by using a Floyd-Warshall based approach to compute the shortest paths between the non-intermediate states.
To illustrate, consider the automaton in Figure 2a. Algorithm 1 starts by considering all intermediate states. In this example q1, q2 and q4. For each of them, the algorithm searches all pairs of transitions that are consecutive through it. Two consecutive transitions can be seen as the two operands of a join operator, where the label of the first transition is the right operand, while the label of the second transition is the left operand. Consequently, the two transitions can be merged together into a new transition, labeled with the concatenation of the two operands. A delimiter (=) is used to be able to parse the expression, in order to convert it into a BGP query, during the evaluation of the property path expression. Figure 3a presents the automaton obtained after considering the intermedi13 14 end end remove the original transitions for which the source or the destination is an intermediate state remove intermediate states ate state q1. At this step, paths that go through state q1 are found and replaced. For example, the two consecutive transitions (q0; a; q1); (q1; b; q2), where predicate path expressions a and b are the operands of the sequence (a b), are replaced by the transition (q0; a=b; q2). In Figure 3b it is paths that go through state q2 that are found and replaced. Of course, transitions introduced in the previous steps are considered. Thus, the two consecutive transitions (q0; a=b; q2); (q2; c; q3) are replaced by the transition (q0; a=b=c; q3). At this step, we can see that the expression (a b c) is now complete. No more transition is labeled with a subexpression of (a b c). Finally, Figure 3c presents the automaton obtained after considering the last intermediate state q4. At the end, all paths that go through states q1, q2 or q4 have been found and replaced by single transitions labeled with the corresponding sequence expressions. After removing the intermediate states, we obtain the automaton described in Figure 3d. This multi-predicate automaton is minimal if we consider a server that only supports triple patterns and BGPs. 4.1.2
Although, evaluating alternative expressions on the server-side does not improve the data transfer, it can significantly reduce the number of subqueries. To illustrate, if the property path P = (a1 + ::: + an) is evaluated on the client, then it requires to send n subqueries to the server. However, only one call is required to evaluate this expression on the server.
Definition 4 (Equivalent states). Two states in a finite automaton M are equivalent if and only if for every string x, if M is started in either state with x as input, it either accepts in both cases or rejects in both cases.
start
q0
a=b=c
d=e
q35
d=e
When sequences have been processed, the n clauses of a same alternative
expression are represented by n transitions, such as they start from the same state
and go to the same or equivalent states. For example, in Figure 3d the two
transitions (q0; a=b=c; q3) and (q0; d=e; q3) are the two clauses of the expression
(a b c) + (d e). Consequently, the last step to build a multi-predicate
automaton is just to merge transitions that share the same sources and equivalent
destinations. This also requires to merge equivalent states. A simple solution
is to merge equivalent states by using a minimization algorithm such as [
To illustrate, consider the automaton in Figure 2a and imagine that sequences have already been processed, resulting in the automaton in Figure 3d. To perform the second transformation, i.e. merge the equivalent states, first, the automaton should be minimized. In Figure 4a, the two equivalent states q3 and q5 are merged into a new state q35. Then, transitions that share the same sources and destinations are merged together. For example, the two transitions (q0; abc; q35), (q0; de; q35) are part of the same alternative expression ((a b c) + (d e)), consequently, they are merged into a new transition (q0; (a=b=c+d=e); q35). Here, we use the delimiter (+) to be able to rewrite this expression as an union of BGPs. Finally, the resulting automaton in Figure 4b is the corresponding minimal multipredicate automaton of the property path ((a b c) + (d e))+. The decomposition defines by this automaton is effectively minimal in the context of a server that supports triple patterns, joins and unions. 5
We want to empirically answer the following questions: Does compressed automata approach follow the W3C semantics of SPARQL property paths? Does compressed automata approach outperform mono-predicate automata approach in terms of query execution time, number of HTTP calls and data transfer? Does compressed automata approach outperform existing client-side approaches in terms of query execution time, number of HTTP calls and data transfer? We implemented our multi-predicate automata compression approach as an extension of the SaGe query engine framework. All extensions and experimental results are available at https://github.com/JulienDavat. 5.1
Dataset and Queries: We used BeSEPPI benchmark and gMark framework.
We used BeSEPPI benchmark to study the compliance of our approach with
the W3C semantics. BeSEPPI [
Approaches: We compare the following approaches: (1) SaGe-AC : implements the automata compression approach on the SaGe smart client. (2) SaGe-A: for comparison, implements a traditional automaton-based approach with a monopredicate automaton on the SaGe smart client. (3) SaGe-Jena: is implemented as an extension of Apache Jena5, consequently, property path expressions are evaluated as defined in Jena, i.e. property path expressions are decomposed into sequences of triple patterns. (4) Comunica: a TPF smart client. Servers configurations: We run the experimentations on a machine with a Processor Intel® Core™ i7-6700HQ CPU @ 2.60GHz x 8 and 16GB of RAM. To be able to run SaGe-Jena and our approach, we run a SaGe server with a time quantum of 75ms, a page-size of 2000 mappings and HDT files as backend. For Communica (version 1.12.1), we run a TPF server (version 2.2.5) with HDT files as backend and the same settings as SaGe.
Evaluation Metrics: (1) Compliance with W3C semantics : check whether the
236 return complete and correct results as defined in [
time between starting query execution and the production of the final results by the client. Presented results correspond to the average obtained of three successive execution of the queries workloads. We fixed a time out of 30 minutes. Does compressed automata approach follow the W3C semantics? We run the BeSEPPI benchmark with SaGe-AC, Comunica and SaGe-Jena clients. Table 1 presents the results for the different approaches.
SaGe-AC follows the W3C semantics of SPARQL property paths, it returns complete and correct results for the 242 queries. SaGe-Jena is just as compliant as Jena, i.e. it follows the semantics. However, Comunica is unable to compute the transitive path expressions when paths have longer more than one, or reflexive closure must be computed.
Does compressed automata approach outperform mono-predicate automata? We run the 30 queries of gMark workload with the SaGe-A and SaGe-AC approaches. Figure 5 shows the execution time, the number of HTTP calls and the data transfer for each query in the workload for both approaches. Dashed lines represent incomplete queries after an execution time of 30 minutes. As expected, when it is possible to improve the decomposition of property path queries, SaGe-AC outperforms SaGe-A in terms of HTTP calls, data transfer and execution time. However, when mono-predicate automata cannot be compressed, then both approaches are equivalent. Queries 12 and 20 are examples of property path queries for which mono-predicate automata and multi-predicate automat have similar performance.
Does compressed automata approach existing client-side approaches We run the 30 queries of gMark workload with the SaGe-AC, communica and SaGe-Jena clients. Figure 6 shows the execution time, the number of HTTP calls and the data transfer for each query in the workload for three approaches. As Comunica does not support gMark transitive queries, we split the query workloads into two groups: transitive queries and non-transitive queries. The transitive queries regroupes queries that have at least one transitive closure expression. The non-transitive queries regroupes other queries.
Figure 6b presents the results of transitive queries with only SaGe-AC and SaGe-Jena, as these queries cannot be executed by Communica. As we can see, SaGe-AC outperforms SaGe-Jena in terms of execution time, number of HTTP calls and data transfer for all queries. Moreover, SaGe-AC provides complete result for all queries (20 queries) except the query Q30, while SaGe-Jena provides complete results for only three queries (Q12, Q20 and Q22).
Figure 6a presents results for the non-transitive queries with SaGe-AC, SaGeJena and Comunica. SaGe-AC outperforms SaGe-Jena and Comunica in term of the execution time, the number of HTTP calls and the data transfer. These results demonstrate empirically the performance of automata compression approach compared to Communica and SaGe-Jena decomposition of property path (a) Queries without transitive closure expressions (b) Queries with at least one transitive closure expression Fig. 6: gMark queries using SaGe-A, SaGe-AC, SaGe-Jena (logarithmic scale). queries. These results demonstrate also the advantage of using the web preemption instead of TPF. The web preemption ensures queries completeness, as TPF, while providing a more expressive interface. Therefore, operations that could be costly to compute on the client-side are supported directly by the server-side. Consequently, communication costs are significantly decreased and only final results are transferred to the client. Obviously, the more operators supported by the server, the better the performance will be.
Of course, it is possible to optimize queries evaluation with TPF [
In this paper, we proposed an algorithm to decompose property path queries into BGPs subqueries. As BGP subqueries are guaranteed to terminate under the web preemption model, this ensures that property path queries are processed online and return complete answers. Compared to the state of art, decomposing into BGPs subqueries is much more efficient than decomposing into Triple Pattern queries. It finally achieves better execution time. We modeled property path expressions as an automaton, and we demonstrated that generating BGPs subqueries instead of triple pattern subqueries can be seen as compressing of the automaton. We implemented our approach in smart client for a preemptable SPARQL server. We demonstrated that our approach outperforms existing approach in term of generated subqueries, data transfer and execution time while supporting full SPARQL 1.1 property path expressions.
The current approach has several limitations. First, in case of simple transitive closure such as ?x sameas* ?y, then there is no room for BGP optimisation. Second, when property path expressions are included inside a BGP, i.e. ?x rdf:type Person . ?x sameas* ?y, then joins have to processed in the smart client, generating high data transfer. Such limitations are the consequences of the lack of support for property path expressions on restricted SPARQL servers. Improving performances for property path expressions requires to find a way to process fairly property path expressions on server-side. This is clearly challenging as property paths may explore a large part of the knowledge graph while remembering visited nodes.