One of the advantages that Linked Data o ers over the classical database setting is the ability to connect and navigate through di erent datasets. At the moment the standard mechanism for exploring navigational properties of the Semantic Web data are SPARQL property paths. However, the semantics of property paths is only de ned assuming one evaluates them over a single local database, and it is still not clear what is the correct way to implement them over the Web of Linked Data, nor if this is even feasible. In this paper we explore this topic in more depth and gauge the merits of di erent approaches of executing property paths over Linked Data. To this end we test how property paths perform if the Linked Data is assumed to be available locally, through endpoints, or if it is accessed directly through dereferencing IRIs.
The Web of Linked Data comprises a wide variety of datasets that have been
published under a set of best practices and standards that aim to improve the
interconnection of these datasets and allow computers to search for information
the way humans do with webpages (see e.g. [
In order to express queries, the recommendation is to use SPARQL, the
default language for querying RDF datasets. Unfortunately, the o cial semantics
of SPARQL assumes that we are dealing with a single dataset, and there is still
no standard semantics for SPARQL queries over the Web of Linked Data. The
main problem is that the open-world nature of the Web does not couple well with
some fragments of SPARQL, as the answers to certain queries may be invalidated
when dereferencing additional tuples. For this reason, most previous work has
focused on simple, monotonic fragments of SPARQL (see e.g. [
On the other hand, one of the more interesting features of Linked Data is
the ability to traverse RDF datasets by navigating from one node to another
using the properties connecting them inside an RDF triple, and to cross
between di erent datasets utilizing these types of links. The standard mechanism
for exploring navigational properties of RDF data are Property Paths, a new
feature made available in SPARQL 1.1 [
To this end, we identi ed the following four initial approaches for evaluating
property path queries over the LOD cloud:
1. Through endpoints: The rst option we have is to nd an appropriate
SPARQL endpoint and execute our property path query there. To illustrate
this by an example, suppose that we want to nd a list of actors with a
nite Bacon number1. If we decide to use the SPARQL endpoint of the
YAGO dataset [
the intuition is that actors are connected with movies via the yago:actedIn
property, and thus a co-actor of Kevin Bacon is someone that witnesses
the pattern {?x yago:actedIn/^yago:actedIn yago:Kevin_Bacon}. The
star is then use to retrieve co-actors of a co-actor of Kevin Bacon, and the
co-actors of them, and so on.
2. Keeping a local copy of the data: When endpoints fail, there is also
an option of simply keeping an (updated) copy of the LOD cloud locally
and ask the desired query over this dataset using a SPARQL engine. In the
example above we might dispense with the \whole LOD cloud" and simply
use YAGO, or another dataset we consider to contain su cient information
to answer our query.
3. Live querying: On the other hand, we can rely instead on the Linked Data
infrastructure, and perform a search by dereferencing IRIs. In this paper
we implement this approach using breadth- rst search to evaluate property
paths (when at least one end of the path is known, such as in the example
above). This approximates the semantics for property paths on Linked Data
given in [
to YAGO's public endpoint, which gives us all the information about
actors and movies where they acted, and then load this database into a
SPARQL engine to run the query.
{ Live querying + endpoints: When running queries live over Linked
Data one immediately observes some issues with dereferencing. This is
most notable when working with inverses, since it is well known that
publishers include only about a half of the triples where the requested
IRI appears as the object [
In this paper we do a detailed comparison on the 4 approaches, and based on empirical evidence discuss their strengths and limitations when evaluating property path queries in the context of Linked Data.
Preliminaries: Let I, L, and B be countably in nite disjoint sets of IRIs,
literals, and blank nodes, respectively. The set of RDF terms T is I [ L [ B.
An RDF triple is a triple (s; p; o) from T I T , where s is called subject,
p predicate, and o object. An (RDF) graph is a nite set of RDF triples. We
assume familiarity with SPARQL queries and specially with Property Paths, as
de ned in [
Here we describe the queries used in evaluating the four approaches discussed above, and also describe how each approach is executed. 2.1
To test the functionalities of property paths over Linked Data we selected three
queries. The number is low on purpose: mainly for brevity, but also because most
property path queries fall into these categories, thus exhibiting similar behaviour
in the evaluation scenarios we present (for an extensive list of navigational queries
which are relevant in this context please see [
Notice that in order to execute a property path query in the context of
Linked Data we have to have the starting point (or the ending point) of the
path (see e.g. [
Our rst query, Q1, is the one we mentioned in the introduction, that nds all
the actors with a nite Bacon number. The intention of this query is to test how
property paths work over a single well-known dataset, using a single property,
but going in both directions. In the case of YAGO the query is as follows (for
the DBpedia and WikiData versions see the online appendix [
We draw the second query (Q2) from previous work in benchmarking
property path implementations [
Our nal query (Q3) is intended to push the evaluation of property paths into the (true) realm of Linked Data by allowing them to utilize more than one dataset to obtain the answer. To this end, we modify the query (Q1) to nd the actors with a nite Bacon number in either YAGO or DBpedia2. In order to jump between datasets, we take advantage of the owl:sameAs triples in them, assuming that two resources connected by this triples are actually the same entity (in this case an actor). This query is important because it can retrieve actors which are not stored YAGO, but are in DBPedia. The query is given below (assuming standard YAGO and DBpedia pre xes):
Note also that we take into the account the fact that the property names change (e.g. actedIn becomes starring in DBpedia), as well as the direction (actedIn links movies to their actors, but starring links in the opposite direction, from actors to movies). 2 On can easily add WikiData to this mix, but since WikiData does not support Linked
Data through dereferencing we exclude it from this comparison. 2.2
The four di erent evaluation approaches are set up as follows: Using endpoints. For Q1 and Q2 we test a version of each query on the appropriate endpoint. In particular: { For YAGO we use: https://linkeddata1.calcul.u-psud.fr/sparql; { For DBpedia: http://dbpedia.org/sparql; and { For WikiData: https://query.wikidata.org/.
In order to execute the query Q3 we need to use the SERVICE functionality of SPARQL, but unfortunately mixing SERVICE with the star operator is not supported.
Local testing. For local testing we set up the Virtuoso 7.20.321 RDF datastore on two di erent servers: { Server 1: This machine has 4GB of main memory and a Intel i5-4670 CPU processor running up to date Manjaro Linux { Server 2: Is a machine with 192GB memory and 4 AMD Opteron(tm) 6366 H processors running Ubuntu 14 LTS.
To keep the presentation manageable, we ran local experiments only over the YAGO dataset (experiments over DBpedia and WikiData will be available in the journal version of the paper). To this end, we loaded a piece of the YAGO database of size 4.1GB containing the properties used in the tested queries. Live querying: Our next option obtains the answers by dereferencing IRIs, thus computing them using only the linked data infrastructure (without endpoints).
To compute property paths, we view the Web of Linked Data as an edge
labelled graphs, where IRIs are the nodes, and whenever a triple (u; p; v) appears in
some dataset, we say that there is a p-labelled edge between u and v (for a full
formalisation see e.g. [
For example, in YAGO version of query Q1 we start by dereferencing the IRI yago:Kevin Bacon, obtaining a document which contains a number of triples of the form (yago:Kevin Bacon; yago:actedIn; u) (and many other triples); each of these IRIs u is a movie in which Kevin Bacon acted. Since we do BFS, we rst list all such movies, say fu1; : : : ; ung. One by one, we dereference each ui, obtaining documents which contain triples of the form (a; yago:actedIn; ui), telling us that a is a co-star of Kevin Bacon, and thus we can output it as part of our answer. The BFS algorithm continues, dereferencing now each new actor a that is found, obtaining new movies, new actors, and so on.
Note that, unless we are assured to obtain all relevant triples when
dereferencing (as happens with e.g. DBpedia, but not YAGO), this procedure is not
guaranteed to obtain all the answers for the query, and thus in a sense our BFS
algorithm is simply an approximation of the query. This is especially the case
when we consider the inverse links (such as the ^yago:actedIn in Q1 above),
as it is well known that publishers include only about a half of the triples where
the requested IRI appears as the object [
We implement the BFS-based evaluation in Python using the RDFlib library to dereference IRIs. All the experiments using this approach were ran on Server 1, but since the resources needed here are very low, similar results can be obtained on a much weaker machine.
large amount of data which will not be used and then computing our queries over an unnecessarily big database, we use endpoints to obtain only the data needed in our queries. More precisely, if a property path uses the set fp1; : : : ; png of properties, we issue the following query (including of course the relevant prexes): CONSTRUCT {?x1 p1 ?y1 . .... . ?xn pn ?yn}
The endpoint will give us a turtle le with the constructed triples. These are then loaded into Virtuoso on Server 1 and Server 2 and queries Q1, Q2 and Q3 are executed using a database containing only this data and nothing more. As in the case of local testing, we only consider the YAGO version of the queries.
incomplete information resulting when the dereferenced IRI does not contain all inverses in the BFS-based implementation, we can use endpoints. More precisely, while running the BFS algorithm above, if we are processing the label ^p (that is, we want to follow p in the reverse direction), each time we dereference an IRI u we do not consider only the triples obtained by dereferencing, but also the answers to the SPARQL query SELECT ?s WHERE f?s p ug posed over YAGO and/or DBPedia endpoint (depending on the query). For instance in the YAGO version of Q1 we add the answer to SELECT ?s WHERE f?s yago:actedIn ug to the triples obtained by dereferencing u, each time we want to traverse this property in reverse (from u). In our extended BFS implementation this is hardcoded into the queries so that they consult the appropriate endpoint each time we need to process an inverse edge and the tests are run on Server 2.
We would like to note that the community is already building an
infrastructure that would eliminate this mismatch: the Linked Data Fragments initiative
[
In this section we report on our ndings when experiments from Section 2 were executed according the strategies described in the introduction. We report (when possible) the amount of memory used, total execution time, and the number of triples received while executing the data. Next, we discuss the merits and shortcomings of each approach in more detail. We would like to stress once again that this analysis applies only to property path queries (using the star operator ), and not to general SPARQL queries. 3.1
The results of our endpoints run are given in Table 1. As we see, our experiments show that property path queries are often not supported on current implementations of SPARQL endpoints. For both DBpedia and YAGO, the execution of Q1 does not complete due to an exceeded memory limit (1GB), and on WikiData due to an exceeded time limit. Further experimentation shows that the implementation of the star operator is the likely culprit3; namely, when one rewrites this query into a union of patters which obtain actors with a Bacon number 1, 2, 3, all the way up to 7, the resulting pattern4 executes with no substantial problems5. Next, the query Q3 is not supported, since querying two datasets inside a single property path is not possible, even using the SERVICE operator. On the other hand, the query Q2 runs very well on Yago and Wikidata, and the execution is almost instantaneous, which suggests that when there are not that many intermediate results, current SPARQL implementations can handle property paths without problem.
Overall, it seems that running property paths on endpoints is costly in terms of the memory used (although we could not measure the exact amount of memory and processor time), and full use of Linked Data is not really supported. On the other hand, when queries do run, they execute almost instantaneously, so using endpoints seems to be a good alternative for property path queries which are based in a single dataset and have relatively few intermediate results. In summary, we can describe the pros and cons of this approach as follows: Pros: Easy to use, virtually free for the user (in terms of required resources), when it works it works well.
Cons: Unreliable, often not fully supported, based on a single dataset.
3 An alternative interpretation related to the semantics of property paths is given in
the online appendix [
Endpoint
Yago
Yago DBpedia DBpedia Wikidata Wikidata nishes no yes ( < 1 sec) no no no yes ( < 1 sec) Even before executing the queries we can see that this approach to evaluating property paths is extremely costly in terms of the resources required, since at the very minimum one needs a dedicated machine. Next comes the cost of storage and data transfer. The most complete option would be to keep an updated copy of the entire LOD cloud and run the experiments on this dataset. Of course, if Linked Data is to become a success, this solution would simply not be feasible for a single user because of the sheer volume of the data available, and might be supported only by a big centralised service provider. Next, even if we settle for a single dataset this can provide costly since e.g. YAGO weighs around 100GB, so downloading it on a regular basis is time consuming. Even the small part of YAGO we used in our testing (parts of core, taxonomy and geonames) takes around 4.1GB, which is not a trivial amount of data to transfer over the Web. This is also one of the reasons we decided to run the tests only on the YAGO dataset, and leave the other two sources for future work.
The behaviour is consistent to what we saw in the endpoints: the systems cannot cope with neither Q1 nor Q3, while Q2 runs only on the high level server (in our commodity server (Server 1) we could not even load the database). The memory cost when computing Q2 was approximately 6GB, while the running time was almost instantaneous (less than 1 second).
Overall, we can conclude that having Virtuoso locally with all the data necessary to answer the queries basically simulates what is happening in endpoints, but it does allow us a higher degree of control, and the ability to make use of additional data. On the other hand, the total cost of maintaining this solution is quite high even if we only want to execute simple queries such as the ones we propose, as the total amount of transmitted data is rather big, and the computational power needed to make this approach run substantial. Despite of this, once SPARQL engines are capable to run transitive closure e ciently (or use more memory for intermediate results), the solution might have some merits for a big service trying to centralise Linked Data. We summarise the pros and cons of this approach as follows: Pros: Full control over query execution, reliable, when it works it works well. Cons: Requires a lot of resources, costly to keep it updated, performance seems to su er the same issues as endpoints do. 3.3
Here we run the BFS-based algorithm for evaluating property paths by fetching
the required documents by dereferencing IRIs. However, as we have discussed,
the main shortcoming is the fact that the answers we obtain are rather
incomplete (even if we wait for all possible answers), mainly due to the fact that
dereferencing an IRI does not give us all the triples where it occurs as an
object (this fact is well documented over Linked Data, see e.g. [
On the other hand, DBpedia returns much more complete data (see Table 2); and the system memory usage, the amount of transmitted data and total query execution time are very low, indicating that this solution can be quite e cient to answer our queries, and one of the advantages it has over a SPARQL engine is that once a single answer is found it can be returned immediately.
Starting Dataset query
DBPedia Q1 DBPedia Q2 DBPedia Q3 system memory 77MB 57MB 80MB
Overall, we can see that this is a lightweight solution requiring very few triples to be transmitted, and not a lot of system memory, but the query answer times can be rather long, since they largely depend on internet tra c and server response times. We summarise the pros and cons of this approach as follows: Pros: E cient, cheap, up-to-date, supports multiple datasets, incremental results.
Cons: Incomplete answers (dependent on the triples published as Linked Data), performance depends on Internet tra c. 3.4
Using a CONSTRUCT query over an endpoint to retrieve only the data needed to answer the query seems to completely avoid the huge download cost factor as opposed to having all the data locally. One would also expect that computing over such a small database would result in more e cient evaluation, but here is where things get more complex.
First, Q1 returns the same error (1GB limit of temp memory exceeded) as when ran over a much bigger piece of YAGO (on both servers), which is quite surprising taking into the account the fact that the size of the loaded dataset is less than 1MB. On the other hand, Q2 runs the same as before, taking less than a second on both the laptop and the high level server. As before, since Q1 did not run, we also do not execute Q3.
Overall, we see that not much is gained compared to having the data locally, although less resources are needed, and the amount of transmitted data is substantial increased. The main problem of this approach, however, is that query answers are again incomplete: the CONSTRUCT query form in endpoints has a maximum of 10.000 triples, and anything above that is simply not returned, without any warnings, so it is not easy to realise when a statement delivers all triples or when is it just a fraction of them. In summary, we have: Pros: Reliable, more control over execution than BFS-based approaches, amount of transmitted data is reasonable.
Cons: A lot of computational power is still needed, same issues as having the data locally, reliant on endpoints and Internet tra c, potentially incomplete answers. 3.5
As discussed in Subsection 3.3, when computing inverses in property paths, most answers we get are incomplete, since dereferencing an IRI does not give us all the triples where it appears as the object. One workaround to solve this problem is described in Section 2, where we obtain reverse links is done by consulting the appropriate endpoint.
The results of this approach are presented in Table 3. In particular, since we can now use YAGO's inverses (retrieved with the endpoint), we obtain much more answers that with the vanilla BFS algorithm. We do, however, keep the 1000 answers limit in order to avoid overloading YAGO's infrastructure. Note that it does not make sense to run these algorithms over DBpedia, because it already gives all the inverses when dereferencing. Furthermore, once again we leave Wikidata out since it does not support live querying in this way.
In summary, we can obtain many more answers at a slightly higher cost, thus allowing us to keep the advantages of the BFS-based approach, but also retrieve more answers than in that case. Pros and cons are classi ed as follows: Pros: E cient, cheap, up-to-date, supports multiple datasets, more complete answers than pure BFS.
Cons: Still incomplete answers, performance depends on Internet tra c, extra overhead for contacting endpoints, usage of endpoints has to be hard-coded. Starting Dataset
Yago Yago Yago query Q1 Q2 Q3 system memory 62MB
62MB In this paper we tested out several possible options of evaluating property path queries over Linked Data. Overall, we can see that there are no clear winners when it comes to selecting a single approach. On the one hand, the endpoint infrastructure does not support mixing data from di erent datasets inside a single property path, and the current SPARQL implementations still seem to be having some issues when executing the star operator, possibly because the way they interpret the semantics of property paths. On the other hand, ad-hoc approaches such as live querying seem to be quite cost e ective, but they su er from incomplete answers. Finally, hybrid approaches seem to run better, but also partially su er from the same issues as their base counterparts.
Although no one-solution- ts-all seems to be available, it seems that once algorithms for evaluating the star operator are improved, running a dedicated server with a SPARQL engine might be a good solution for a high end user wishing to provide centralised support for property paths, especially when they are meant to be executed over a single dataset. Similarly, for a user requiring a more lightweight solution and is not concerned in obtaining only partial answers, using live querying might be a good option.
Therefore, we plan to purse future work on two fronts. First, we wish to look
into improving the current algorithms for evaluating the star operator in existing
systems, which would allow us to have an out-of-the-box solution for a broad
range of uses of property paths. A good way to do this is to use the automata
theoretic approach for evaluation of the star operator, which would avoid the
exhaustive search which seems to take place in current implementations (see [
Acknowledgements. Work funded by the Millennium Nucleus Center for Semantic Web Research under Grant NC120004.