Link traversal querying for a diverse Web of Data

Abstract

Traditional approaches for querying the Web of Data often involve centralised warehouses that replicate remote data. Conversely, Linked Data principles allow for answering queries live over the Web by dereferencing URIs to traverse remote data sources at runtime. A number of authors have looked at answering SPARQL queries in such a manner; these link-traversal based query execution (LTBQE) approaches for Linked Data offer up-to-date results and decentralised (i.e., client-side) execution, but must operate over incomplete dereferenceable knowledge available in remote documents, thus affecting response times and “recall” for query answers. In this paper, we study the recall and effectiveness of LTBQE, in practice, for the Web of Data. Furthermore, to integrate data from diverse sources, we propose lightweight reasoning extensions to help find additional answers. From the state-of-the-art which (1) considers only dereferenceable information and (2) follows rdfs:seeAlso links, we propose extensions to consider (3) owl:sameAs links and reasoning, and (4) lightweight RDFS reasoning. We then estimate the recall of link-traversal query techniques in practice: we analyse a large crawl of the Web of Data (the BTC’11 dataset), looking at the ratio of raw data contained in dereferenceable documents vs. the corpus as a whole and determining how much more raw data our extensions make available for query answering. We then stress-test LTBQE (and our extensions) in real-world settings using the FedBench and DBpedia SPARQL Benchmark frameworks, and propose a novel benchmark called QWalk based on random walks through diverse data. We show that link-traversal query approaches often work well in uncontrolled environments for simple queries, but need to retrieve an unfeasible number of sources for more complex queries. We also show that our reasoning extensions increase recall at the cost of slower execution, often increasing the rate at which results return; conversely, we show that reasoning aggravates performance issues for complex queries.

1. Introduction

A rich collection of RDF data has been published on the Web as Linked Data, by governments, academia, industry, communities and individuals alike [39]. The resulting collective of interlinked contributions from a wide variety of Linked Data publishers has been dubbed the “Web of (Linked) Data”: a novel corpus of structured data distributed across the entire Web, described using the Semantic Web standards and made available under the Linked Data principles.

An open challenge is how to query this novel Web of Data in an effective manner [6]. SPARQL [54]—the W3C standardised RDF query language—provides a powerful declarative means to formulate structured queries over RDF data. However, processing SPARQL queries over the Web of Data broaches many technical challenges. Traditional centralised approaches cache information from the Web of Data in local optimised indexes, executing queries over the replicated content. However, maintaining up-to-date coverage of a broad selection of the Web of Data is exceptionally costly; centralised caches of the Web of Data must settle for either limited coverage and/or for indexing some out-of-date information [43,63,66]. Users of centralised query engines will thus often encounter stale or missing results with respect to the current Web of Data [66].

Conversely, per Linked Data principles, the URIs that name resources (often) map through HTTP to the physical location of structured data about them (called dereferencing). The Web of Data itself can thus be viewed as a scale-free, decentralised database, consisting of millions of Web documents indexing structured data [37,39]. Furthermore, agents can traverse and navigate the Web of Data through typed “RDF links” to discover related information [39, § 4.5].

This perspective suggests that queries can be answered directly over the Web of Data using HTTP, where a number of live querying approaches have recently been proposed that take a (SPARQL) query, find query-relevant sources on the Web of Data, and dynamically retrieve data from these sources for runtime query processing. In one such approach, Hartig et al. [34] followed the view of the Web of Data as a global database and proposed to rely on dereferenceable URIs and RDF links for discovering sources relevant to answer a SPARQL query. Later work by Hartig [32] calls this idea “Link Traversal Based Query Execution” (which we abbreviate to LTBQE).

However, in the LTBQE approach, each HTTP lookup can take seconds to yield content, many such lookups may be required, and subsequent lookups to the same remote server may need to be artificially delayed to ensure “polite” access (i.e., to avoid inadvertent denial-of-service attacks). In the live querying scenario, remote sources are accessed while a user is waiting for answers to their queries: thus response times are often (necessarily) much slower when compared with centralised query engines operating over locally replicated content. Thus, a core challenge for LTBQE is to retrieve a minimal number of relevant sources while maximising the number of answers returned. Relatedly, the success of LTBQE is premised on the assumption that query relevant data about a resource can be found in its dereferenced document; as we show later, this assumption only partially holds.

Herein, we look at the performance and recall of LTBQE in practice. We also propose that lightweight reasoning extensions—specifically relating to owl: sameAs and RDFS semantics—can help to “squeeze” additional answers from sources and to find additional query-relevant sources on the diverse Web of Data. We apply analysis over a large sample of the Web of Data to get insights into what ratio of raw data is available to LTBQE through dereferenceable principles vs. raw data in the entire corpus; we also analyse to what extent our proposed extensions make additional query-relevant data available. We then apply LTBQE and our extensions to three different SPARQL query benchmarks to stress-test how the approaches work in real-world, uncontrolled settings. In general, we find that LTBQE works best for simple queries that require traversing a handful ( $\sim ⩽100$ ) sources. We also show that our reasoning extensions often help to find additional answers at the cost of increased query time, but can run into trouble when accessing data from domains such as DBpedia (which has a high fan-out of owl:sameAs and schema level links) and can exacerbate performance issues with complex queries.

Paper contributions and structure  This paper extends previous work [64] where we first introduced our reasoning extensions. Herein, we propose new mechanisms for collecting schema data, test additional benchmarks, and greatly extend discussion throughout. This paper is then structured as follows:

We first present some background work in the area of Linked Data querying and reasoning.

We present some formal preliminaries for RDF, Linked Data, SPARQL, RDFS and OWL.

We reintroduce the LTBQE approach using concrete HTTP-level methods.

We introduce LiDaQ (Linked Data Query engine): our implementation of LTBQE with novel reasoning extensions and optimisations.

We analyse a crawl of ∼7.4 m RDF/XML documents from the Web of Data (BTC’11), looking at issues of dereferenceability.

We survey SPARQL benchmarks and how live-querying papers have evaluated their works. We then propose a new benchmark called QWalk.

We test LTBQE and our reasoning extensions for three query benchmarks in native Web settings.

We conclude with a summary of contributions and remarks on future directions.

2. Background and related work

Our work relates to research on querying over RDF data; more precisely, we focus on executing SPARQL queries over the Web of Data in a manner adhering to the Linked Data principles. A comprehensive and recent overview of existing approaches to query Linked Data was published by Hose et al. [42]. We similarly classify relevant query approaches into three categories (1) materialised systems and data warehouses, (2) systems that federate SPARQL engines and (3) live query approaches. Although our own work falls into the third category, in order to provide a broader background, in this section we also summarise developments in the first two categories. Additionally, we briefly remark on “hybrid” proposals that combine different methods, as well as proposals for new languages (aside from SPARQL) to query/navigate the Web of Data. Finally, since our extensions for LTBQE further relate to research on reasoning over Linked Data, we also cover some background in this area.

2.1. Materialised systems

Materialised query-engines use a crawler or other data-acquisition methods to replicate (i.e., materalise) remote Web of Data content into a local quad store over which queries are executed. Such services include “FactForge” [13]1

¹

http://factforge.net/sparql

(which uses BigOWLIM [12]), “LOD Cache”2 ²

http://lod.openlinksw.com/sparql

and Sindice’s “Semantic Web Index” [50]3 ³

http://sparql.sindice.com/

(which both use Virtuoso [22]).

The typical goals of such materialised engines are to maintain broad and up-to-date coverage of the Web of Data and to process SPARQL queries efficiently. These objectives are (partially) met using distribution techniques, replication, optimised indexes, compression techniques, data synchronisation strategies, and so on [12,22,30,50]. Still, given that such services often index millions of documents, they require large amounts of resources to run. In particular, maintaining a local, optimal, up-to-date index with good coverage of the Web of Data is a Sisyphean task.

Unlike these materialised approaches, the LTBQE approach and our extensions do not require all content to be indexed locally prior to query execution.

2.2. SPARQL federation

Given the recent spread of independently operated SPARQL endpoints on the Web of Data hosting various closed datasets with varying degrees of overlap,4

⁴

http://www4.wiwiss.fu-berlin.de/lodcloud/state/

federated SPARQL querying is enjoying growing attention in the research community. The core idea is to execute queries over a federation of endpoints: to split an input query, send the relevant sub-queries to individual (and possibly remote) endpoints in situ, and subsequently merge and process the final result set.

A primary challenge for federated SPARQL engines is to decide which parts of a query are best routed to which endpoint. Many such engines rely on “service descriptions” or “catalogues”, which describe the contents of remote endpoints. One of the earliest such works (predating SPARQL by over three years) was by Stuckenschmidt et al. [60], who proposed summarising the content of distributed RDF repositories using schema paths (non-empty property chains). More recently, a variety of proposals have looked at using service descriptions or catalogues to enable routing in a federated scenario, including DARQ [55], SemWIQ [46], SPLENDID [25], ANAPSID [1], etc. Instead of relying (solely) on pre-computed service descriptions or catalogues, FedX [59] and SPLENDID (also) probe SPARQL endpoints with ASK sub-queries to test if they have relevant information.

New federation features were also introduced with SPARQL 1.1: the SERVICE feature invokes remote endpoints and the VALUES feature can be used to “ship” batches of intermediate bindings to an endpoint [28]. The SPARQL-DQP system [4] has investigated use of these SPARQL 1.1 federated features.

However, in recent work, we analysed a broad range of SPARQL endpoints available on the Web [5]. We found that half of the endpoints listed in the public datahub.io catalogue are no longer up, and that many endpoints have reliability issues. This work thus calls into question the current practicality of federation as a solution for querying the open Web.

Like the LTBQE approach and our proposed extensions, federated SPARQL engines may involve retrieving content from remote sources at runtime. However, unlike federated SPARQL, LTBQE operates over raw data sources on the level of HTTP, and does not require the availability of SPARQL interfaces.

2.3. Live Linked Data querying

Live querying approaches access raw data sources at runtime to dynamically select, retrieve and build a dataset over which SPARQL queries can be evaluated. Ladwig & Tran [44] identify three categories of such query evaluation approaches: (1) top-down, (2) bottom-up, and (3) mixed strategy.

Top-down evaluation determines the query relevant sources before the actual query execution using knowledge about the available sources stored in a “source-selection index”. These source-selection indexes can vary from simple inverted-index structures [47,50], to query-routing indexes [61], schema-level indexes [60], and lightweight hash-based structures [65].

The bottom-up query evaluation strategy involves discovering query-relevant sources on-the-fly during the evaluation of queries. The LTBQE approach [17,29,33–35] we extend herein falls into this category (we define LTBQE in Section 4). The unique challenges for such an approach are (1) to find as many query-relevant sources as possible to improve recall of answers; (2) to conversely minimise the amount of sources accessed to avoid traffic and slow query-response times; (3) to optimise query execution in the absence of typical selectivity estimates, etc. [32,34]. In this paper, we focus on the first two challenges.

As its name suggests, the third strategy, the mixed approach, combines top-down and bottom-up techniques. This strategy uses (in a top-down fashion) some knowledge about sources to map query terms or query sub-goals to sources which can contribute answers, then discovering additional query relevant sources using a bottom-up approach [44].

2.4. Hybrid and navigational query engines

A mature Linked Data query service could require a hybrid strategy that combines complementary approaches: for example to use a materialised approach for static datasets, a federated approach for dynamic datasets where a first-party SPARQL endpoint is available, or a live approach for dynamic datasets that have no SPARQL endpoint [43]. A number of works have investigated such combinations on a variety of levels (see, e.g., [37,45,66]). In previous works we combined LTBQE with a materialised approach for getting fresher SPARQL query answers from the Web than the materialised indexes could offer but at a fraction of the runtime of pure LTBQE [66]. We believe that live query approaches, such as LTBQE, are most useful in combination with other query paradigms.

Some authors have also questioned whether or not SPARQL is the only language needed to query the Web of Data [6]. There have also been a number of proposals to extend SPARQL with regular expressions that capture navigational patterns,5

⁵

SPARQL 1.1 includes a similar notion called property paths [28].

including work by Alkhateeb et al. [2], Perez et al.’s nSPARQL language [53], and Fionda et al.’s NautiLOD proposal [23]. Such work goes beyond pure SPARQL querying, but perhaps touches upon some of the broader potential of querying and consuming the Web of Data in a declarative manner.

2.5. Reasoning over Web data

In this paper, we propose lightweight reasoning extensions for LTBQE, which leverage (some of) the semantics of the RDFS and OWL standards to perform inferencing and find additional answer and query relevant sources. We now cover some related works in the area of RDFS/OWL reasoning over the Web of Data.

We investigate a terse profile of reasoning targeted for Web data. Similarly, Glimm et al. [24] surveyed the use of RDFS and OWL features in a large crawl of the Web of Data (viz., BTC’11), applying PageRank over documents and summating the rank of all documents using each feature. They found that RDF(S) features were the most prominently used. From OWL, owl:sameAs occurred most frequently, though features like owl:FunctionalProperty had higher ranks.

With respect to scalable rule-based reasoning over RDFS (and OWL), a number of authors have proposed separating schema data (aka. terminological data or T-Box) from instance data (aka. assertional data or A-Box) during inferencing [40,67,68]. The core assumptions are that the volume of schema data is much smaller than instance data, that schema data are frequently accessed during reasoning, that schema data are more static than instance data, and that schema-level inferences do not depend on instance data. Where these assumptions hold, the schema data can be separated from the main body of data and “compiled” into an optimised form in preparation for reasoning over the bulk of instance data. We use similar techniques herein when computing RDFS inferences: we consider schema data separately from instance data.

Aside from scalability, the freedom of the Web—where anyone can say anything (almost) anywhere—raises concerns about the trustworthiness of data for automated inferencing. On a schema level, for example, various obscure documents on the Web of Data make nonsensical definitions that would (naïvely) affect reasoning across all other documents [16]. Numerous authors have proposed mechanisms to incorporate notions of provenance for schema data into the inferencing process. One such procedure, called authoritative reasoning, only considers the schema definitions for a class or property term that are given in its respectively dereferenceable document [16,18,40]. We later use authoritative reasoning to avoid the unwanted effects of third-party schema contributions during RDFS reasoning. Delbru et al. [20] propose another solution called context-dependent reasoning (or quarantined reasoning), where a closed scope is defined for each document being reasoned over, incorporating only the document itself and other documents it (recursively) imports or links, thus excluding the claims of arbitrary Web documents. We later use a similar import mechanism to dynamically collect schemata from the Web during RDFS reasoning.

Our extensions involving owl:sameAs semantics do not directly involve schema data, but rather look at resolving coreferent resources in the corpus. Various authors have looked specifically at the use and the quality of use of owl:sameAs on the Web of Data [21,27,41]. Halpin et al. [27] look at the semantics and quality of owl:sameAs links in Linked Data. Manually inspecting five hundred owl:sameAs relations sampled from the Web of Data, they estimated an accuracy for owl:sameAs links—where sameness could be confidently asserted for the sampled relations—at around 51% ( $\pm 21\mathrm{\%}$ ), but found that judges often disagreed. We later conducted a similar manual inspection of one thousand owl:sameAs relations, where we asked a different question—is there any difference between these two resources to confirm that they are not the same?—and where we estimated a respective (and much more optimistic) precision of 97.2% [41]. We do not tackle issues pertaining to the quality of owl:sameAs relations in this particular work, but acknowledge this as an orthogonal challenge for Linked Data [27,41].

Finally, we are not the first work to look at incorporating reasoning into SPARQL querying over the Web of Data. Various materialised approaches for querying Linked Data have incorporated forward-chaining rule-based reasoners to find additional answers, including the SAOR reasoner [40] for YARS2 (which we use later), Sindice’s context-dependent reasoning [20], Factforge [13], etc. In terms of reasoning for top-down querying systems, Li and Heflin [47] also use reasoning techniques to find additional results through query rewriting and bottom-up inferencing.

2.6. Novelty of present work

We briefly highlight our novelty. First and foremost, we evaluate the bottom-up LTBQE approach using various benchmarks—all in an uncontrolled, real-world setting—to see what kinds of practical expectations one can have for answering queries directly over the Web of Data. Second, we propose and evaluate reasoning extensions for LTBQE to find additional sources on-the-fly and to generate further answers. To the best of our knowledge, no other work has looked at evaluating live querying approaches over diverse sources live on the Web, nor has any other work looked at the benefits of incorporating reasoning techniques into link-traversal querying techniques for the Web of Data.

3. Preliminaries

In this section, we cover some necessary preliminaries and notation relating to RDF (Section 3.2), Linked Data (Section 3.3), SPARQL (Section 3.4) and RDFS & OWL (Section 3.5). Before we continue, however, we introduce a running example used to explain later concepts.

3.1. Running Example

Fig. 1.

Snippets taken from five documents on the Web of Data. Individual documents are associated with individual background panes. The URI of each document is attached to its pane with a shaded tab. The same resources appearing in different documents are joined using “bridges”. Links from URIs to the documents they dereference to are denoted with dashed links. RDF triples are denoted following usual conventions within their respective document.

Fig. 2.

Snippet from the Friend Of A Friend (FOAF) Ontology: a schema document on the Web of Data. External terms have dashed lines.

Figure 1 illustrates an RDF (sub-)graph taken from five real-world interlinked documents on the Web of Data.6 ⁶

As last accessed on 2013-07-02.

Prefixes for the abbreviated CURIE names used in this section, and throughout the paper, are available in Appendix C. The graph models information about two real-world persons and a paper that they coauthored together. One author is identified by the URIs oh:olaf and dblpA:Olaf_Hartig and the other by cb:chris and dblpA:Christian_Bizer. The URI dblpP:HartigBF09 refers to the publication both authors share. The five documents are as follows: ohDoc:, cbDoc:

refer to the personal FOAF profile documents that each author created for themselves;

dblpADoc:Olaf..., dblpADoc:Chris...

refer to information exported from the “DBLP Computer Science Bibliography”7 ⁷

http://www.informatik.uni-trier.de/~ley/db/

for each author, including a publication list;

dblpPDoc:HartigBF09

provides information about the co-authored paper exported from DBLP.

Each document is available as RDF/XML on the Web. Dereferenceable relationships between resources and documents are highlighted in Fig. 1. Excluding cbDoc: (which must be looked up directly), the other four documents can be retrieved by dereferencing the URI of their main resource; for example, dereferencing oh:olaf over HTTP returns the document ohDoc: describing said resource.

In addition, Fig. 2 illustrates a subset of RDFS definitions in a “schema document” extracted from the real-world FOAF ontology. Although left implicit, all terms in the foaf: namespace (including the predicates and values for rdf:type represented in Fig. 1) dereference to this document. The relations between classes and properties shown in this document are well defined (using model-theoretic semantics) by the RDFS standard and can be used for automated inference [38].

3.2. RDF

In order to define our methods later, we must first provide notation for RDF [38].

Definition 1 (RDF Term, Triple and Graph).

The set of RDF terms consists of the set of URIs U, the blank-nodes B and literals L. An RDF triple $\mathit{t}:=\mathrm{(}\mathit{s}\mathrm{,}\mathit{p}\mathrm{,}\mathit{o}\mathrm{)}$ is an element of the set $\mathbf{G}:=\mathbf{U}\mathbf{B}\times \mathbf{U}\times \mathbf{U}\mathbf{B}\mathbf{L}$ (where, e.g., $\mathbf{U}\mathbf{B}$ is a shortcut for $\mathbf{U}\cup \mathbf{B}$ ). Here s is called subject, p predicate, and o object. An RDF graph $\mathit{G}\subset \mathbf{G}$ is a finite set of RDF triples. We use the functions $\mathsf{subj}\mathrm{(}\mathit{G}\mathrm{)}$ , $\mathsf{pred}\mathrm{(}\mathit{G}\mathrm{)}$ , $\mathsf{obj}\mathrm{(}\mathit{G}\mathrm{)}$ , $\mathsf{terms}\mathrm{(}\mathit{G}\mathrm{)}$ to resp. denote the set of all terms appearing in the subject, predicate, object and all positions of triples in G.

3.3. Linked Data

The four Linked Data principles [10] are as follows:

LDP1:

URIs are used to identify things

LDP2:

URIs should be dereferenceable through HTTP

LDP3:

Useful RDF content should be provided when URIs are dereferenced

LDP4:

Links should be offered within that content

We now provide some (time-invariant) Linked Data notation that we use later for defining our methods. This notation encapsulates the idea of the Web of Data as a database, where dereferencing URIs acts as a lookup that returns RDF data about those URIs.

Definition 2 (Data Source and Linked Dataset).

We define the http-download function $\mathsf{get}:\mathbf{U}\to 2^{\mathbf{G}}$ as the mapping from URIs to RDF graphs provided by means of HTTP lookups which directly return status code 200 OK and data in a suitable RDF format. We define the set of (RDF) data sources $\mathbf{S}\subset \mathbf{U}$ as the set of URIs $\mathbf{S}:=\{\mathit{s}\in \mathbf{U}:\mathsf{get}\mathrm{(}\mathit{s}\mathrm{)}\ne \varnothing \}$ (i.e., URIs that return RDF content with 200 Okay). We define a Linked Dataset as $\mathrm{\Gamma }\subset \mathsf{get}$ (i.e., a finite set of pairs $\mathrm{(}\mathit{s}\mathrm{,}\mathsf{get}\mathrm{(}\mathit{s}\mathrm{)}\mathrm{)}$ such that $\mathit{s}\in \mathbf{S}$ ). The “global” RDF graph presented by a Linked Dataset is denoted as $$\mathsf{merge}\mathrm{(}\mathrm{\Gamma }\mathrm{)}:=\underset{\mathrm{(}\mathit{u}\mathrm{,}\mathit{G}\mathrm{)}\in \mathrm{\Gamma }}{{\displaystyle ⨄}}\mathit{G}$$ where the operator ‘⊎’ denotes the RDF merge of RDF graphs, which ensures that blank node labels in the input graphs are kept distinct in the merged graph [38].

Example 1.

Taking Fig. 1, e.g., $\mathsf{get}\mathrm{(}\mathtt{ohDoc:}\mathrm{)}=\{\mathrm{(}\mathtt{oh:olaf:}\mathrm{,}\mathtt{foaf:name}\mathrm{,}\mathtt{"Olaf\; Hartig"}\mathrm{)}\mathrm{,}\dots \}$ , an RDF graph containing the five triples in that document. However, $\mathsf{get}\mathrm{(}\mathtt{oh:olaf}\mathrm{)}=\varnothing$ since it does not return a 200 Okay (redirects are supported in the next step). Thus, $\mathtt{ohDoc:}\in \mathbf{S}$ whereas $\mathtt{oh:olaf}\notin \mathbf{S}$ . If we denote Fig. 1 as the Linked Dataset Γ, we can say that $\mathrm{\Gamma }=\{\mathrm{(}\mathtt{ohDoc:}\mathrm{,}\mathsf{get}\mathrm{(}\mathtt{ohDoc:}\mathrm{)}\mathrm{,}\dots \}$ , containing five $\mathrm{(}\mathit{URI}\mathrm{,}\mathit{RDF-graph}\mathrm{)}$ pairs. Then, $\mathsf{merge}\mathrm{(}\mathrm{\Gamma }\mathrm{)}$ is the set of all 17 RDF triples shown in Fig. 1.

Definition 3 (Dereferencing RDF).

A URI may redirect to another URI with a 30x response code. We denote this function as $\mathsf{redir}:\mathbf{U}\to \mathbf{U}$ , which first strips the fragment identifier of a URI (if present) and would then map a URI to its redirect target or to itself in the case of failure (e.g., where no redirect exists). We denote the fixpoint of $\mathsf{redir}$ as $\mathsf{redirs}$ , denoting traversal of a number of redirects (a limit may be imposed to avoid cycles). We then denote dereferencing by the composition $\mathsf{deref}:=\mathsf{get}\circ \mathsf{redirs}$ , which maps a URI to an RDF graph retrieved with status code 200 OK after following redirects, or which maps a URI to the empty set in the case of failure. We denote the set of dereferenceable URIs as $\mathbf{D}:=\{\mathit{d}\in \mathbf{U}:\mathsf{deref}\mathrm{(}\mathit{d}\mathrm{)}\ne \varnothing \}$ , where $\mathbf{S}\subset \mathbf{D}$ and we place no expectations on what $\mathsf{deref}\mathrm{(}\mathit{d}\mathrm{)}$ returns, other than returning some valid RDF. As a shortcut, we denote by $\mathsf{derefs}:2^{\mathbf{U}}\to 2^{\mathbf{U}\times 2^{\mathbf{G}}}$ ; $\mathit{U}\mapsto \{\mathrm{(}\mathsf{redirs}\mathrm{(}\mathit{u}\mathrm{)}\mathrm{,}\mathsf{deref}\mathrm{(}\mathit{u}\mathrm{)}\mathrm{)}\mid \mathit{u}\in \mathit{U}\cap \mathbf{D}\mathrm{)}\}$ the mapping from a set of URIs to the Linked Dataset it represents by dereferencing all URIs (only including those in D which return some RDF).

In relation to the formal model of Hartig [33], we favour concrete HTTP-level methods used for Linked Data. He models the Web of Linked Data as a triple $\mathit{W}=\mathrm{(}\mathit{D}\mathrm{,}\mathit{data}\mathrm{,}\mathit{adoc}\mathrm{)}$ , where our set S is equivalent to his set D of document IDs, our function $\mathsf{get}\mathrm{(}.\mathrm{)}$ instantiates his (more general) function $\mathit{data}\mathrm{(}.\mathrm{)}$ for mapping document IDs to RDF graphs, and our function $\mathsf{redirs}\mathrm{(}.\mathrm{)}$ instantiates his function $\mathit{adoc}\mathrm{(}.\mathrm{)}$ for partially mapping URI names to document IDs.

Example 2.

Taking Fig. 1, oh:olaf redirects to ohDoc:, denoted $\mathsf{redir}\mathrm{(}\mathtt{oh:olaf}\mathrm{)}=\mathtt{ohDoc:}$ . No further redirects are possible, and thus $\mathsf{redirs}\mathrm{(}\mathtt{oh:olaf}\mathrm{)}=\mathtt{ohDoc:}$ . Dereferencing oh:olaf gives the RDF graph in the document ohDoc:, where $\mathsf{deref}\mathrm{(}\mathtt{oh:olaf}\mathrm{)}=\mathsf{get}\mathrm{(}\mathsf{redirs}\mathrm{(}\mathtt{oh:olaf}\mathrm{)}\mathrm{)}=\mathsf{get}\mathrm{(}\mathtt{ohDoc:}\mathrm{)}$ . Instead taking the URI $\mathtt{cb:chris}$ , $\mathsf{redir}\mathrm{(}\mathtt{cb:chris}\mathrm{)}=\mathtt{cb:chris}$ and $\mathsf{get}\mathrm{(}\mathtt{cb:chris}\mathrm{)}=\varnothing$ ; this URI is not dereferenceable. Thus we can say that $\mathtt{oh:olaf}\in \mathbf{D}$ and $\mathtt{ohDoc:}\in \mathbf{D}$ whereas $\mathtt{cb:chris}\notin \mathbf{D}$ .

3.4. SPARQL

We now introduce some concepts relating to the query language SPARQL [52,54]. We herein focus on evaluating simple, conjunctive, basic graph patterns (BGPs), where although supported by our implementation, we do not formally consider more expressive parts of the SPARQL language, which—with the exception of non-monotonic features that assume a closed dataset like OPTIONAL in SPARQL and MINUS/(NOT) EXISTS in SPARQL 1.1—can be layered on top [52]. In addition, we consider URIs and not IRIs for convenience with the RDF preliminaries.

Definition 4 (Variables, Triple Patterns & BGPs).

Let V be the set of variables ranging over $\mathbf{U}\mathbf{B}\mathbf{L}$ . A triple pattern $\mathit{tp}:=\mathrm{(}\mathit{s}\mathrm{,}\mathit{p}\mathrm{,}\mathit{o}\mathrm{)}$ is an element of the set $\mathbf{Q}:=\mathbf{V}\mathbf{U}\mathbf{L}\times \mathbf{V}\mathbf{U}\times \mathbf{V}\mathbf{U}\mathbf{L}$ .8

⁸

SPARQL allows literals in the subject position [54], though such patterns cannot match RDF triples as currently defined.

For simplicity, we do not consider blank-nodes in triple patterns (they could be roughly emulated by an injective mapping from B to V). A finite (herein, non-empty) set of triple patterns $\mathit{Q}\subset \mathbf{Q}$ is called a Basic Graph Pattern, or herein, simply a query. We use $\mathsf{vars}\mathrm{(}\mathit{Q}\mathrm{)}\subset \mathbf{V}$ to denote the set of variables in Q. Finally, we may overload graph notation for queries, where, e.g., $\mathsf{terms}\mathrm{(}\mathit{Q}\mathrm{)}$ returns all elements of $\mathbf{V}\mathbf{U}\mathbf{L}$ in Q.

In this paper, we only look at evaluating queries representing BGPs. We denote the answers to a query Q with respect to a Linked Dataset as ${[[\mathit{Q}]]}_{\mathrm{\Gamma }}$ . We now formally define this notion, where ${[[\mathit{Q}]]}_{\mathrm{\Gamma }}$ is a set of solutions generated by Q over the merge of graphs in Γ. Definition 5 (SPARQL solutions).

Call the partial function $\mathit{\mu }:\mathrm{dom}\mathrm{(}\mathit{\mu }\mathrm{)}\cup \mathbf{U}\mathbf{L}\to \mathbf{U}\mathbf{B}\mathbf{L}$ a solution mapping with a domain $\mathrm{dom}\mathrm{(}\mathit{\mu }\mathrm{)}\subset \mathbf{V}$ . A solution mapping binds variables in $\mathrm{dom}\mathrm{(}\mathit{\mu }\mathrm{)}$ to $\mathbf{U}\mathbf{B}\mathbf{L}$ and is the identify function for $\mathbf{U}\mathbf{L}$ . Overloading notation, let $\mathit{\mu }:\mathbf{Q}\to \mathbf{G}$ and $\mathit{\mu }:2^{\mathbf{Q}}\to 2^{\mathbf{G}}$ also resp. denote a solution mapping from triple patterns to RDF triples, and basic graph patterns to RDF graphs such that $\mathit{\mu }\mathrm{(}\mathit{tp}\mathrm{)}:=\mathrm{(}\mathit{\mu }\mathrm{(}\mathit{s}\mathrm{)}\mathrm{,}\mathit{\mu }\mathrm{(}\mathit{p}\mathrm{)}\mathrm{,}\mathit{\mu }\mathrm{(}\mathit{o}\mathrm{)}\mathrm{)}$ and $\mathit{\mu }\mathrm{(}\mathit{Q}\mathrm{)}:=\{\mathit{\mu }\mathrm{(}\mathit{tp}\mathrm{)}\mid \mathit{tp}\in \mathit{Q}\}$ . We now define the set of SPARQL solutions for a query Q over a (Linked) Dataset Γ as $$\begin{array}{llll}\hfill {[[\mathit{Q}]]}_{\mathrm{\Gamma }}:=& \{\mathit{\mu }\mid \mathit{\mu }\mathrm{(}\mathit{Q}\mathrm{)}\subseteq \mathsf{merge}\mathrm{(}\mathrm{\Gamma }\mathrm{)}\wedge \mathrm{dom}\mathrm{(}\mathit{\mu }\mathrm{)}& \hfill & \\ \hfill & =\mathsf{vars}\mathrm{(}\mathit{Q}\mathrm{)}\}.& \hfill & \end{array}$$ For brevity, and unlike SPARQL, solutions are herein given as sets (not multi-sets), implying a default DISTINCT semantics for queries, and we assume that answers are given over the default graph consisting of the merge of RDF graphs in the dataset.

Example 3.

Taking Γ from Fig. 1, let Q be:

Then ${[[\mathit{Q}]]}_{\mathrm{\Gamma }}$ would be:

?maker	?issued
dblpA:Christian_Bizer	"2009"^^xsd:gYear
dblpA:Olaf_Hartig	"2009"^^xsd:gYear

3.5. RDFS and OWL

In preparation for defining our reasoning extensions to LTBQE, we now give some preliminaries relating to RDFS and OWL. Our RDFS rules are the subset of the ρDF rules proposed by Muñoz et al. [49] that deal with instance data entailments (as opposed to schema-level entailments).9

⁹

We drop implicit typing [49] rules as we allow generalised RDF in intermediate inferences.

For supporting owl:sameAs, we use a small subset of OWL 2 RL/RDF rules, given in Table 1, which constitute a partial axiomatisation of the OWL RDF-Based Semantics relating to ground equality. Our selection of rules thus support a small subset of standard RDFS/OWL semantics that we argue to be important for answering queries over the Web of Data, and our approach could be generalised to support, e.g., OWL 2 RL/RDF rules with some adaptations.

For a ruleset R and dataset Γ, we denote by $\mathrm{\Gamma }\bullet \mathit{R}$ the fixpoint of applying R against Γ such that applying R over $\mathrm{\Gamma }\bullet \mathit{R}$ yields no new inferences. We now define $\mathrm{\Gamma }\bullet \mathit{R}$ formally in terms of an immediate consequence operator (reusing some SPARQL notation for brevity).

Table 1

RDFS (ρDF subset) and owl:sameAs (OWL 2 RL/RDF subset) rules

	ID	Body	Head
RDFS	prp-spo1	?p ${}_1$ rdfs:subPropertyOf ?p ${}_2$ . ?s ?p ${}_1$ ?o .	?s ?p ${}_2$ ?o .
	prp-dom	?p rdfs:domain ?c . ?s ?p ?o .	?p a ?c .
	prp-rng	?p rdfs:range ?c . ?s ?p ?o .	?o a ?c .
	cax-sco	?c ${}_1$ rdfs:subClassOf ?c ${}_2$ . ?s a ?c ${}_1$ .	?s a ?c ${}_2$ .
Same-As	eq-sym	?x owl:sameAs ?y .	?y owl:sameAs ?x .
	eq-trans	?x owl:sameAs ?y . ?y owl:sameAs ?z .	?x owl:sameAs ?z .
	eq-rep-s	?s owl:sameAs ?s′ . ?s ?p ?o .	?s′ ?p ?o .
	eq-rep-p	?p owl:sameAs ?p′ . ?s ?p ?o .	?s ?p′ ?o .
	eq-rep-o	?o owl:sameAs ?o′ . ?s ?p ?o .	?s ?p ?o′ .

Definition 6 (Entailment Rules & Least Model).

An entailment rule is a pair $\mathit{r}=\mathrm{(}\mathit{Body}\mathrm{,}\mathit{Head}\mathrm{)}$ (cf. Table 1) such that $\mathit{Body}$ , $\mathit{Head}\subset \mathbf{Q}$ ; and $\mathsf{vars}\mathrm{(}\mathit{Head}\mathrm{)}\subseteq \mathsf{vars}\mathrm{(}\mathit{Body}\mathrm{)}$ . The immediate consequences of r for a Linked Dataset Γ are given as: $$\begin{array}{llll}\hfill {\mathfrak{T}}_{\mathit{r}}\mathrm{(}\mathrm{\Gamma }\mathrm{)}:=& \{\mathit{\mu }\mathrm{(}\mathit{Head}\mathrm{)}\mid \mathit{\mu }\in {[[\mathit{Body}]]}_{\mathrm{\Gamma }}\}& \hfill & \\ \hfill & \setminus \mathsf{merge}\mathrm{(}\mathrm{\Gamma }\mathrm{)}.& \hfill & \end{array}$$ In other words, ${\mathfrak{T}}_{\mathit{r}}\mathrm{(}\mathrm{\Gamma }\mathrm{)}$ denotes the direct unique inferences from a single application of a rule r against the merge of RDF data contained in Γ. Let R denote a finite set of entailment rules. The immediate consequences of R over Γ are given analogously as: $$\begin{array}{rcll}{\mathfrak{T}}_{\mathit{R}}\mathrm{(}\mathrm{\Gamma }\mathrm{)}& :=& {\displaystyle \bigcup }_{\mathit{r}\in \mathit{R}}{\mathfrak{T}}_{\mathit{r}}\mathrm{(}\mathrm{\Gamma }\mathrm{)}.& \end{array}$$ This is the union of a single application of all rules in R over the data applied to the (raw) data in Γ. Furthermore, let $\mathit{\delta }\in \mathbf{U}$ denote a fresh URI which names the graph ${\mathit{G}}_{}^{\mathit{R}}$ of data inferred by R, and let ${\mathit{G}}_0^{\mathit{R}}=\varnothing$ . Now, for $\mathit{i}\in \mathbb{N}$ , define: $$\begin{array}{rcll}{\mathrm{\Gamma }}_{\mathit{i}}^{\mathit{R}}& :=& \mathrm{\Gamma }\cup \{\mathrm{(}\mathit{\delta }\mathrm{,}{\mathit{G}}_{\mathit{i}}^{\mathit{R}}\mathrm{)}\}& \\ {\mathit{G}}_{\mathit{i}+1}^{\mathit{R}}& :=& {\mathfrak{T}}_{\mathit{R}}\mathrm{(}{\mathrm{\Gamma }}_{\mathit{i}}^{\mathit{R}}\mathrm{)}\cup {\mathit{G}}_{\mathit{i}}^{\mathit{R}}& \end{array}$$ The least model of Γ with respect to R is ${\mathrm{\Gamma }}_{\mathit{n}}^{\mathit{R}}$ for the least n such that ${\mathrm{\Gamma }}_{\mathit{n}}^{\mathit{R}}={\mathrm{\Gamma }}_{\mathit{n}+1}^{\mathit{R}}$ ; at this stage the closure is reached and nothing new can be inferred.10

¹⁰

Since our rules are a syntactic subset of Datalog, there is a unique and finite least model (assuming finite inputs).

Henceforth, we denote this least model with $\mathrm{\Gamma }\bullet \mathit{R}$ . Query answers including entailments are given by ${[[\mathit{Q}]]}_{\mathrm{\Gamma }\bullet \mathit{R}}$ .

Example 4.

Let R denote the set of rules in Table 1. Also, consider Γ as the Linked Dataset comprising of $\mathrm{(}\mathtt{ohDoc:}\mathrm{,}\mathsf{get}\mathrm{(}\mathtt{ohDoc:}\mathrm{)}\mathrm{)}$ from Fig. 1 and a second named graph called foafSpec: with the following subset of triples from Fig. 2:

These (real-world) triples can be retrieved by dereferencing a FOAF term; e.g., $\mathsf{deref}\mathrm{(}\mathtt{foaf:img}\mathrm{)}$ . Now, given Γ and R, then ${\mathit{G}}_0^{\mathit{R}}=\varnothing$ , ${\mathit{G}}_1^{\mathit{R}}={\mathit{G}}_0^{\mathit{R}}\cup {\mathfrak{T}}_{\mathit{R}}\mathrm{(}{\mathrm{\Gamma }}_0^{\mathit{R}}\mathrm{)}$ where, by applying each rule in R over Γ once, ${\mathfrak{T}}_{\mathit{R}}\mathrm{(}{\mathrm{\Gamma }}_0^{\mathit{R}}\mathrm{)}$ contains the following triples (abbreviating CURIEs slightly):

Subsequently, ${\mathrm{\Gamma }}_1^{\mathit{R}}=\mathrm{\Gamma }\cup \{\mathrm{(}\mathit{\delta }\mathrm{,}{\mathit{G}}_1^{\mathit{R}}\mathrm{)}\}$ , where δ is any built-in URI used to identify the graph of inferences and where ${\mathit{G}}_1^{\mathit{R}}$ contains the unique inferences thus far (listed above). Thereafter, ${\mathit{G}}_2^{\mathit{R}}={\mathit{G}}_1^{\mathit{R}}\cup {\mathfrak{T}}_{\mathit{R}}\mathrm{(}{\mathrm{\Gamma }}_1^{\mathit{R}}\mathrm{)}$ , where ${\mathfrak{T}}_{\mathit{R}}\mathrm{(}{\mathrm{\Gamma }}_1^{\mathit{R}}\mathrm{)}$ contains:

As before, ${\mathrm{\Gamma }}_2^{\mathit{R}}=\mathrm{\Gamma }\cup \{\mathrm{(}\mathit{\delta }\mathrm{,}{\mathit{G}}_2^{\mathit{R}}\mathrm{)}\}$ , where ${\mathit{G}}_2^{\mathit{R}}$ contains all inferences collected thus far, and ${\mathit{G}}_3^{\mathit{R}}={\mathit{G}}_2^{\mathit{R}}\cup {\mathfrak{T}}_{\mathit{R}}\mathrm{(}{\mathrm{\Gamma }}_2^{\mathit{R}}\mathrm{)}$ , where ${\mathfrak{T}}_{\mathit{R}}\mathrm{(}{\mathrm{\Gamma }}_2^{\mathit{R}}\mathrm{)}$ contains:

This is then the closure since ${\mathfrak{T}}_{\mathit{R}}\mathrm{(}{\mathrm{\Gamma }}_3^{\mathit{R}}\mathrm{)}=\varnothing$ ; nothing new can be inferred, and so ${\mathrm{\Gamma }}_3^{\mathit{R}}={\mathrm{\Gamma }}_4^{\mathit{R}}$ . And thus we can say that $\mathrm{\Gamma }\bullet \mathit{R}={\mathrm{\Gamma }}_3^{\mathit{R}}=\mathrm{\Gamma }\cup \mathrm{(}\mathit{\delta }\mathrm{,}{\mathit{G}}_3^{\mathit{R}}\mathrm{)}$ .

4. Link Traversal Based Query Execution

Having covered some necessary preliminaries, in the following section, we cover the Link Traversal Based Query Execution (LTBQE) approach first proposed by Hartig et al. [33,34] for executing SPARQL queries over the Web of Data (Section 4.1).

4.1. Overview of baseline LTBQE

Given a SPARQL query, the core operation of LTBQE is to identify and retrieve a focused set of query-relevant RDF documents from the Web of Data from which answers can be extracted. The approach begins by dereferencing URIs found in the query itself. The documents that are returned are parsed, and triples matching patterns of the query are processed; the URIs in these triples are also dereferenced to look for further information, and so forth. The process is recursive up to a fixpoint wherein no new query-relevant sources are found. New answers for the query can be computed on-the-fly as new sources arrive. We now formally define an idea of query-relevant documents in the context of LTBQE. This is similar in principle to the generic notion of reachability introduced previously [33,35], but relies here on concrete HTTP specific operations:

Definition 7 (Query Relevant Sources & Answers).

First let $\mathsf{uris}\mathrm{(}\mathit{\mu }\mathrm{)}:=\{\mathit{u}\in \mathbf{U}\mid \exists \mathit{v}\mathrm{s}.\mathrm{t}.\mathrm{(}\mathit{v}\mathrm{,}\mathit{u}\mathrm{)}\in \mathit{\mu }\}$ denote the set of URIs in a solution mapping μ. Given a query Q and an intermediate dataset Γ, we define the function $\mathsf{qrel}$ , which extracts from Γ a set of URIs that can (potentially) be dereferenced to find further sources deemed relevant for Q: $$\mathsf{qrel}\mathrm{(}\mathit{Q}\mathrm{,}\mathrm{\Gamma }\mathrm{)}:={\displaystyle \bigcup }_{\mathit{tp}\in \mathit{Q}}{\displaystyle \bigcup }_{\mathit{\mu }\in {[[\{\mathit{tp}\}]]}_{\mathrm{\Gamma }}}\mathsf{uris}\mathrm{(}\mathit{\mu }\mathrm{)}$$ To begin the recursive process of finding query-relevant sources, LTBQE takes URIs in the query—denoted with ${\mathit{U}}_{\mathit{Q}}:=\mathsf{terms}\mathrm{(}\mathit{Q}\mathrm{)}\cap \mathbf{U}$ —as “seeds”, and builds an initial dataset by dereferencing these URIs: ${\mathrm{\Gamma }}_0^{\mathit{Q}}:=\mathsf{derefs}\mathrm{(}{\mathit{U}}_{\mathit{Q}}\mathrm{)}$ . Thereafter, for $\mathit{i}\in \mathbb{N}$ , define:11

¹¹

In practice, URIs need only be dereferenced once; i.e., only URIs in $\mathsf{qrel}\mathrm{(}\mathit{Q}\mathrm{,}{\mathrm{\Gamma }}_{\mathit{i}}^{\mathit{Q}}\mathrm{)}\setminus \mathrm{(}\mathsf{qrel}\mathrm{(}\mathit{Q}\mathrm{,}{\mathrm{\Gamma }}_{\mathit{i}-1}^{\mathit{Q}}\mathrm{)}\cup {\mathit{U}}_{\mathit{Q}}\mathrm{)}$ need be dereferenced at each stage.

$${\mathrm{\Gamma }}_{\mathit{i}+1}^{\mathit{Q}}:=\mathsf{derefs}\mathrm{(}\mathsf{qrel}\mathrm{(}\mathit{Q}\mathrm{,}{\mathrm{\Gamma }}_{\mathit{i}}^{\mathit{Q}}\mathrm{)}\mathrm{)}\cup {\mathrm{\Gamma }}_{\mathit{i}}^{\mathit{Q}}$$ The set of LTBQE query relevant sources for Q is given as the least n such that ${\mathrm{\Gamma }}_{\mathit{n}}^{\mathit{Q}}={\mathrm{\Gamma }}_{\mathit{n}+1}^{\mathit{Q}}$ , denoted simply ${\mathrm{\Gamma }}^{\mathit{Q}}$ . The set of LTBQE query answers for Q is given as ${[[\mathit{Q}]]}_{{\mathrm{\Gamma }}^{\mathit{Q}}}$ , or simply denoted $\lfloor \lfloor \mathit{Q}\rfloor \rfloor$ .

Example 5.

Taking Fig. 1, let Q be the following query looking for the author-names of a given paper:

First, the process extracts all raw query URIs: ${\mathit{U}}_{\mathit{Q}}=\{\mathtt{dblpP:HartigBF09}\mathrm{,}\mathtt{foaf:name}\mathrm{,}\mathtt{foaf:maker}\}$ . In the next stage, the engine dereferences these URIs. Given that $\mathsf{redirs}\mathrm{(}\mathtt{dblpP:HartigBF09}\mathrm{)}=\mathtt{dblpPDoc:HartigBF09}$ & $\mathsf{redirs}\mathrm{(}\mathtt{foaf:maker}\mathrm{)}=\mathsf{redirs}\mathrm{(}\mathtt{foaf:made}\mathrm{)}=\mathtt{foafSpec:}$ , dereferencing ${\mathit{U}}_{\mathit{Q}}$ gives two unique named graphs, viz.: $\mathrm{(}\mathtt{dblpPDoc:}\mathtt{HartigBF09}\mathrm{,}\mathsf{get}\mathrm{(}\mathtt{dblpPDoc:HartigBF09}\mathrm{)}\mathrm{)}$ and $\mathrm{(}\mathtt{foafSpec:}\mathrm{,}\mathsf{get}\mathrm{(}\mathtt{foafSpec:}\mathrm{)}\mathrm{)}$ . These two named-graphs comprise ${\mathrm{\Gamma }}_0^{\mathit{Q}}$ . (In fact, only the former graph will ultimately contribute answers.)

Second, LTBQE looks to extract additional query relevant URIs by seeing if any query patterns are matched in the current dataset. By reference to the graph dblpPDoc:HartigBF09 in Fig. 1, we see that for the pattern “dblpP:HartigBF09 foaf:maker ?author .”, the variable ?author is matched by two unique URIs, namely dblpA:Christian_Bizer and dblpA:Olaf_Hartig, which are added to $\mathsf{qrel}\mathrm{(}\mathit{Q}\mathrm{,}{\mathrm{\Gamma }}_0^{\mathit{Q}}\mathrm{)}$ . Nothing else is matched. Hence, these two URIs are dereferenced and the results added to ${\mathrm{\Gamma }}_0^{\mathit{Q}}$ to form ${\mathrm{\Gamma }}_1^{\mathit{Q}}$ .

LTBQE repeats the above process until no new sources are found. At the current stage, ${\mathrm{\Gamma }}_1^{\mathit{Q}}$ now also contains the two sources dblpADoc:Christian_Bizer and dblpADoc:Olaf_Hartig needed to return:

?authorName

"Christian Bizer"

"Olaf Hartig"

Furthermore, no other query-relevant URIs are found and so a fixpoint is reached and the process terminates: $\lfloor \lfloor \mathit{Q}\rfloor \rfloor$ contains the above results.

4.2. Decidability and completeness

The decidability of LTBQE—and indeed the decidability of the more general problem of evaluating a SPARQL query over the Web of Data—depends on how one scopes the sources of data considered for evaluation and which features of SPARQL are used.

If one considers an infinite Web of Data—aiming for what Hartig calls “Web completeness” [33]—then the evaluation of a SPARQL query is not finitely computable in the general case, even if one considers only the monotonic features of SPARQL [33]: there are (countably) infinite documents that may contain relevant data but that cannot be processed in finite steps. If non-monotonic features of SPARQL—such as OPTIONAL, MINUS, etc.—are used in the query, then evaluation is not even “eventually computable” by a non-terminating procedure [33] since, in the general case, all documents need to be processed before a single sound solution can be given, making the computation of each individual solution infinitary.

If one rather considers a reachability condition—whereby, for example, only the query-relevant sources in an LTBQE sense are considered in-scope—for similar reasons, Hartig [33] shows that queries are still not finitely computable unless it can be proven that the number of reachable sources is finite under the given conditions. This does not hold for the set of query relevant sources given in Definition 7.

Example 6.

The following query asks for a general description of people known by oh:olaf:

The initial query-relevant sources (per Definition 7) are the documents dereferenced from oh:olaf and foaf:maker. Thereafter, all triples in these documents will match the open pattern, and thus all URIs in these documents will be considered as potential query-relevant links. This will continue recursively, crawling the entire, potentially infinite Web of Data as reachable from the query URIs. The problem is not limited to open patterns; take the following query:

This would end up crawling the connected Web of FOAF documents, as are linked together by dereferenceable foaf:knows links.

Partly addressing this problem, Hartig et al. [34] defined an iterator-based execution model for LTBQE, which rather approximates the answers provided by Definition 7. This execution model defines an ordering of triple patterns in the query, similar to standard nested-loop join evaluation. The most selective patterns (those expected to return the fewest bindings) are executed first and initial bindings are propagated to bindings further up the tree. Crucially, later triple patterns are partially bound when looking for query-relevant sources. Thus, taking the previous example, the pattern “?s foaf:knows ?o .” will never be used to find query-relevant sources, but rather partially-bound patterns like “cb:chris foaf:knows ?o .” will be used. As such, instead of retrieving all possible query-relevant sources, the iterator-based execution model uses interim results to apply a more focused traversal of the Web of Data. This also makes the iterator-based implementation order-dependent: results may vary depending on which patterns are executed first and thus answers may be missed. However, it does solve the problem of traversing too many sources when low-selectivity patterns are present in the query.

Relatedly, Harth and Speiser [29] also consider an order-dependent version of LTBQE. Similar to Hartig [34], they remark that although the Web-completeness of SPARQL evaluation is useful as a theoretical notion, since the Web of Data cannot be materialised, more practical but weaker notions of completeness are also necessary. They propose another two completeness conditions: seed-complete considers answers from the set of documents that are within a fixed-length traversal path from the seed URIs in the query (the authors propose using the number of query patterns to decide the maximum hops) and query-reachable-complete considers a closed dataset of documents reachable through the LTBQE process under some ordering of the query patterns. The authors then demonstrate how Web-complete and query-reachable-complete conditions coincide if only certain authoritative triples—triples containing URIs that dereference to the container document—are considered.

We now give some practical examples as to why LTBQE (be it order-dependent or order-independent) cannot be Web-complete in the general case.

No dereferenceable query URIs  The LTBQE approach cannot return results in cases where the query does not contain dereferenceable URIs. For example, consider posing the following query against Fig. 1:

As previously explained, the URI cb:chris is not dereferenceable ( $\mathsf{deref}\mathrm{(}\mathtt{cb:chris}\mathrm{)}=\varnothing$ ) so the query has no place to start its traversal from.

Unconnected query-relevant documents  Relating to reachability, results can be missed where documents are “connected” by a join on literals, blank-nodes or non-dereferenceable URIs. The following query illustrates such a case:

Answers (other than oh:olaf) cannot be reached from the starting URI oh:olaf because the relevant documents are connected by the literal "Olaf Hartig".

Dereferencing partial information  In the general case, the effectiveness of LTBQE is heavily dependent on the amount of data returned by the $\mathsf{deref}\mathrm{(}\mathit{u}\mathrm{)}$ function. In an ideal case, dereferencing a URI u would return all triples mentioning u on the Web of Data. However, this is not always the case; for example:

This simple query cannot be answered since the triple “oh:olaf owl:sameAs dblpA:Olaf_Hartig .” is not accessible by dereferencing dblpA:Olaf_Hartig. The assumption that all RDF available on the Web of Data about a URI u can be collected by dereferencing u is clearly idealised; hence, later in Section 6 we will empirically analyse how much the assumption holds in practice, giving insights into the potential recall of LTBQE on an infrastructural level.

5. LiDaQ: Extending LTBQE with reasoning

We now present the details of LiDaQ: our proposal to extend the baseline LTBQE approach with components that leverage lightweight RDFS and owl:sameAs reasoning in order to improve recall. We first describe the extensions we propose (Section 5.1), and then describe our implementation of the system (Section 5.2).

5.1. LTBQE extensions

Partly addressing some of the shortcomings of the LTBQE approach in terms of “recall”, Hartig et al. [34] proposed extending the set of query relevant sources to consider rdfs:seeAlso links, which sometimes overcomes the issue of URIs not being dereferenceable. In the LiDaQ system, we include this extension and further propose novel extensions that apply reasoning over query-relevant sources to squeeze additional answers from these sources, which in turn may lead to recursively finding additional query-relevant sources.

We now describe, formally define and provide motivating examples for each of the three extensions: following rdfs:seeAlso links, following owl:sameAs links and applying equivalence inferencing, and collecting schema information for applying RDFS reasoning.

5.1.1. Following rdfs:seeAlso links

We first motivate the legacy rdfs:seeAlso extension with a simple example.

Example 7.

Consider executing the following simple query, asking for images of the friends of oh:olaf, against the data in Fig. 1 using baseline LTBQE:

LTBQE first dereferences the content of the query URI oh:olaf, and then follows and dereferences all URI bindings for the variable ?f, matching the second query pattern “?f foaf:depiction ?d .” over the retrieved content to find pictures. However, the query processor needs to follow the rdfs:seeAlso link from cb:chris (bound to ?f) to cbDoc: since the URI cb:chris is not dereferenceable (recall that a dashed arrow in Fig. 1 denotes dereferenceability).

Hartig et al. [34] thus proposed to extend LTBQE to consider rdfs:seeAlso links as follows. Definition 8 (LTBQE Extension 1: rdfs:seeAlso).

Given a dataset Γ, a set of URIs U and a predicate URI p, first define: $$\begin{array}{llll}\hfill \mathsf{link}\mathrm{(}\mathrm{\Gamma }\mathrm{,}\mathit{U}\mathrm{,}\mathit{p}\mathrm{)}:=& \{\mathit{v}\in \mathbf{U}\mid \exists \mathit{u}\in \mathit{U}\mathrm{s}.\mathrm{t}.& \hfill & \\ \hfill & \mathrm{(}\mathit{u}\mathrm{,}\mathit{p}\mathrm{,}\mathit{v}\mathrm{)}\in \mathsf{merge}\mathrm{(}\mathrm{\Gamma }\mathrm{)}\}& \hfill & \end{array}$$ which gives the target of links from URIs in U with the property p in the data of Γ. Next we extend the $\mathsf{qrel}\mathrm{(}\mathrm{\Gamma }\mathrm{,}\mathit{U}\mathrm{)}$ function from Definition 7 to allow for considering links through a predicate p as follows: $$\mathsf{qrel}\mathrm{(}\mathit{Q}\mathrm{,}\mathrm{\Gamma }\mathrm{,}\mathit{p}\mathrm{)}:=\mathsf{qrel}\mathrm{(}\mathit{Q}\mathrm{,}\mathrm{\Gamma }\mathrm{)}\cup \mathsf{link}\mathrm{(}\mathrm{\Gamma }\mathrm{,}\mathsf{qrel}\mathrm{(}\mathit{Q}\mathrm{,}\mathrm{\Gamma }\mathrm{)}\mathrm{,}\mathit{p}\mathrm{)}$$

Note that $\mathsf{qrel}\mathrm{(}\mathit{Q}\mathrm{,}\mathrm{\Gamma }\mathrm{)}\subseteq \mathsf{qrel}\mathrm{(}\mathit{Q}\mathrm{,}\mathrm{\Gamma }\mathrm{,}\mathit{p}\mathrm{)}$ . The extension to follow rdfs:seeAlso links then follows from Definition 7 by replacing $\mathsf{qrel}\mathrm{(}\mathrm{\Gamma }\mathrm{,}\mathit{U}\mathrm{)}$ with the extended function $\mathsf{qrel}\mathrm{(}\mathrm{\Gamma }\mathrm{,}\mathit{U}\mathrm{,}\mathtt{rdfs:seeAlso}\mathrm{)}$ .

5.1.2. Following and reasoning over owl:sameAs links

We now motivate the need for owl:sameAs traversal and reasoning with an example:

Example 8.

Consider the following query for Fig. 1 asking for friends of oh:olaf that are also co-authors.

Baseline LTBQE returns no answers: LTBQE requires owl:sameAs support to return Chris as an answer (given by the equivalences for oh:olaf/dblpA:Olaf_Hartig and cb:chris/dblpA:Christian_Bizer).

We now formalise the details of our extension. Definition 9 (LTBQE Extension 2: owl:sameAs).

We define an extension of LTBQE to consider owl:sameAs links and inferences. As before, from Definition 7, replace $\mathsf{qrel}\mathrm{(}\mathrm{\Gamma }\mathrm{,}\mathit{U}\mathrm{)}$ with $\mathsf{qrel}\mathrm{(}\mathrm{\Gamma }\mathrm{,}\mathit{U}\mathrm{,}\mathtt{owl:sameAs}\mathrm{)}$ , which follows owl:sameAs links. Next, let ${\mathit{R}}^{=}$ denote the set of rules of the form eq-* in Table 1. Finally, from Definition 7, replace ${\mathrm{\Gamma }}_{\mathit{i}}^{\mathit{Q}}$ with ${\mathrm{\Gamma }}_{\mathit{i}}^{\mathit{Q}}\bullet {\mathit{R}}^{=}$ , such that the owl:sameAs inferences are applied at each step.

5.1.3. Incorporating RDFS schemata and reasoning

Finally, we cover our novel extension for RDFS inferencing, starting with a motivating example.

Example 9.

Take the following query over Fig. 1 asking for the images(s) depicting oh:olaf:

From Fig. 2, we know that foaf:depiction is a sub-property of foaf:img, and we would thus hope to get the answer <http://...> from ohDoc:. However, returning this answer requires two thing: (i) retrieving the RDFS definitions of the FOAF vocabulary; and (ii) performing reasoning using the first four rules in Table 1. In this case, finding the relevant schema information (the first step) is quite straightforward and can be done dynamically since the relevant terms (foaf:img and foaf:depiction) are within the same namespace and are described by the same dereferenceable document. However, consider instead:

In this case, we know from the FOAF schema that foaf:name is a sub-property of rdfs:label, and so "Olaf Hartig" should be an answer. However, no FOAF vocabulary term is mentioned in the query, and so the FOAF schema will not be in the query-relevant scope. To overcome this, we can provide a static set of schema information to the query engine as input, or we can dereference property and class terms mentioned in the query-relevant data to dynamically retrieve the relevant definitions at runtime.

Definition 10 (LTBQE Extension 3: RDFS).

We define an extension of LTBQE to consider RDFS schema data and a subset of RDFS inferences. Let ${\mathit{R}}^{\mathit{\rho }}$ denote rules $\{\mathrm{PRP}\mathrm{-}\mathrm{SPO}\mathrm{1}\mathrm{,}\mathrm{PRP}\mathrm{-}\mathrm{DOM}\mathrm{,}\mathrm{PRP}\mathrm{-}\mathrm{RNG}\mathrm{,}\mathrm{CAX}\mathrm{-}\mathrm{SCO}\}$ in Table 1 (other rules could be added as necessary). From Definition 7, replace ${\mathrm{\Gamma }}_{\mathit{i}}^{\mathit{Q}}$ with $\mathrm{(}{\mathrm{\Gamma }}_{\mathit{i}}^{\mathit{Q}}\cup {\mathrm{\Psi }}_{\mathit{i}}\mathrm{)}\bullet {\mathit{R}}^{\mathit{\rho }}$ , such that inferences are applied at each step. We use ${\mathrm{\Psi }}_{\mathit{i}}$ to denote an auxiliary Linked Dataset containing schema data at step i.

We are then left to define how ${\mathrm{\Psi }}_{\mathit{i}}$ may be acquired, where we provide three options ( ${\mathrm{\Psi }}_{\mathit{i}}^{\mathit{a}\text{–}\mathit{c}}$ ).

A static corpus of schema data Ψ can be provided as input, such that ${\mathrm{\Psi }}_{\mathit{i}}^{\mathit{a}}:=\mathrm{\Psi }$ .

The class and property terms used in ${\mathrm{\Gamma }}_{\mathit{i}}^{\mathit{Q}}$ can be dereferenced. Letting $\mathsf{preds}\mathrm{(}\mathrm{\Gamma }\mathrm{)}$ and $\mathsf{o}\text{-}\mathsf{type}\mathrm{(}\mathrm{\Gamma }\mathrm{)}$ denote, respectively, the set of all URIs appearing as a predicate, and the set of all URIs appearing as a value for rdf:type (class instance) in Γ, we can define ${\mathrm{\Psi }}_{\mathit{i}}^{\mathit{b}}$ as: $${\mathrm{\Psi }}_{\mathit{i}}^{\mathit{b}}:=\mathsf{derefs}\mathrm{(}\mathsf{preds}\mathrm{(}{\mathrm{\Gamma }}_{\mathit{i}}^{\mathit{Q}}\mathrm{)}\cup \mathsf{o}\text{-}\mathsf{type}\mathrm{(}{\mathrm{\Gamma }}_{\mathit{i}}^{\mathit{Q}}\mathrm{)}\mathrm{)}$$

Class and property terms can be dereferenced and schema-level links followed. For a Linked Dataset Γ, let $\mathsf{imports}\mathrm{(}\mathrm{\Gamma }\mathrm{)}$ denote all URIs appearing as the subject or object of a triple in Γ with predicate rdfs:subPropertyOf, rdfs:domain, rdfs:range or rdfs:subClassOf; or appearing as the object of owl:imports. Extending ${\mathrm{\Psi }}_{\mathit{i}}^{\mathit{b}}$ as above, let ${\mathrm{\Psi }}_{\mathit{i}\mathrm{,}0}^{\mathit{c}}:={\mathrm{\Psi }}_{\mathit{i}}^{\mathit{b}}$ , and thereafter, for $\mathit{j}\in \mathbb{N}$ define: $${\mathrm{\Psi }}_{\mathit{i}\mathrm{,}\mathit{j}+1}^{\mathit{c}}:=\mathsf{derefs}\mathrm{(}\mathsf{imports}\mathrm{(}{\mathrm{\Psi }}_{\mathit{i}\mathrm{,}\mathit{j}}^{\mathit{c}}\mathrm{)}\mathrm{)}\cup {\mathrm{\Psi }}_{\mathit{i}\mathrm{,}\mathit{j}}^{\mathit{c}}$$ such that links are recursively followed up to a fixpoint: the least j such that ${\mathrm{\Psi }}_{\mathit{i}\mathrm{,}\mathit{j}}^{\mathit{c}}={\mathrm{\Psi }}_{\mathit{i}\mathrm{,}\mathit{j}+1}^{\mathit{c}}$ . We define ${\mathrm{\Psi }}_{\mathit{i}}^{\mathit{c}}$ as this fixpoint of recursive imports.

Fig. 3.

LTBQE architecture diagram.

The second and third methods involve dynamically collecting schemata at runtime. The third method of schema-collection is potentially problematic in that it recursively follows links, and may end up collecting a large amount of schema documents (a behaviour we encounter in evaluation later). However, where, for example, class or property hierarchies are split across multiple schema documents, this recursive process is required to “recreate” the full hierarchy.

All three extensions—following rdfs:seeAlso links, following owl:sameAs links & applying owl: sameAs reasoning, retrieving RDFS data (using one of three approaches) & applying RDFS reasoning—can be combined in a straightforward manner. In fact, some answers may only be possible through the combination of all extensions. We will later explore the effects of combining all extensions in Section 8.

5.2. LiDaQ implementation

The LiDaQ prototype (implemented in Java) draws together a variety of techniques proposed in the literature [34,36,45] and has five main components, as depicted in Fig. 3.

Query Processor:

uses Jena ARQ to parse and process input SPARQL queries and format the output results.12

¹²

http://jena.apache.org/documentation/query/

We discuss query processing in further detail below.

Source Selector:

decides which query and solution URIs should be dereferenced and which links should be followed.

Source Lookup:

an adapted version of the LDSpider crawling framework performs the live Linked Data lookups required for LTBQE. LDSpider respects the robots.txt policy, blacklists typical non-RDF URI patterns (e.g., .jpeg) and enforces a half-second politeness delay between two consequential lookups for URIs hosted at the same pay-level-domain. A per-domain queue is implemented from which a pool of threads polls on a first-in-first-out basis.13 ¹³

http://code.google.com/p/ldspider/

Local Repository:

a custom implementation of an in-memory quad store (similar to [36]) is used to cache the content of all query relevant data (including inferences and schema data), as well as indexing triple patterns from the query to match against the data. Triple-pattern “listeners” match cached data in a continuous fashion, feeding the iterators.

Reasoner:

the Java-based SAOR reasoner is used to support rule-based reasoning extensions [16] and executes inferencing over the local repository.

The query processing algorithm is based on a nested-loop strategy. During LTBQE, retrieving certain sources may involve high latency. Thus rather than blocking while waiting for the result of a particular request, special non-blocking operators are required [34,45], where we adopt a strategy analogous to the symmetric-index-hash join [45]. When a data-access operator receives a lookup request, it: (i) registers the pattern in a hash-table, (ii) pulls all relevant data, currently found in the local repository, as bindings into the hash-table, (iii) co-ordinates with the source-selector to request remote accesses as necessary, and (iv) registers a listener with the local repository that will push new relevant data into the operator’s hash-table as they arrive. Join operators use these hash-tables to asynchronously concatenate compatible tuples and return them to higher operators. By caching intermediate bindings, this asynchronous model ensures that all relevant data are consumed—in a bottom-up, nested-loop sense—as they arrive, no matter when or from where they arrive [45].

We further investigate some practical optimisations to minimise the number of query-relevant sources retrieved while maximising results. First, we avoid dereferencing URIs that do not appear in join positions. We illustrate this with a simple example:

Example 10.

Consider the following query issued against the example graph of Fig. 1, asking for friends of oh:olaf that have some value defined for foaf: based_near:

Assuming the rdfs:seeAlso extension is enabled, LTBQE will visit ohDoc: binding cb:chris for ?f; and then visit cbDoc: binding "Chris Bizer" for ?fn and dbpedia:Berlin for ?b. However, dereferencing the latter URI would be pointless: we do not need any information about dbpedia:Berlin to answer the query. Our optimisation thus proposes to avoid wasting lookups by not dereferencing URIs bound to non-join variables such as ?b.

By reducing the amount of sources and raw data that are accessed—and given that anyone in principle can say anything, anywhere—we may also reduce the number of answers that are returned. Taking the previous example, for all we know, the document dereferenced through dbpedia:Berlin may contain people based near Berlin that Olaf knows, which would help to contribute other answers. However, we deem this to be unlikely in the general case, and note that it goes against the core LTBQE idea of using Linked Data principles to find query-relevant sources.

Aside from this optimisation to avoid dereferencing URIs bound to non-join variables, we note that URIs in certain positions of a triple pattern may not be worth dereferencing to look for matching information. For example, given the pattern “?s foaf:knows ?o .”, we would not expect to find (m)any triples matching this pattern in the document dereferenced by foaf:knows. In the next section, we investigate precisely this matter for different triple positions, and thereafter propose a further variation on LiDaQ’s source selection to prune remote lookups that are unlikely to contribute answers.

6. Empirical study

LTBQE relies on the assumption that relevant data are dereferenceable, which may not always hold in practice. In this section, we analyse a large sample of the Web of Data to see what ratio of information is available in dereferenceable documents versus the total information available in the entire sample. This provides insights as to what percentage of raw data is available to LTBQE versus, e.g., a materialised approach with a complete index over a large crawl of the Web of Data. We can also test how much additional raw information is made available by our extensions.

6.1. Empirical corpus

We take the dataset crawled for the Billion Triple Challenge 2011 (BTC’11) in mid-May 2011 as our corpus. The dataset consists of 7.4 million RDF/XML documents spanning 791 pay-level domains (data providers). URIs extracted from all RDF triples positions (excluding common non-RDF/XML extensions like .pdf, .jpg, .html, etc.) were considered for crawling. The resulting corpus contains 2.15 billion quadruples (1.97 billion unique triples) mentioning 538 million RDF terms, of which 52 million ( $\sim 10\mathrm{\%}$ ) are literals, 382 million ( $\sim 71\mathrm{\%}$ ) are blank nodes, and 103 million ( $\sim 19\mathrm{\%}$ ) are URIs. We denote the corpus as ${\mathrm{\Gamma }}_{\sim }$ . The core RDF data are serialised as N-Quads [19]: a syntax that extends N-Triples with a fourth element, used in this case to track which triple came from which source (following our notion of a Linked Dataset).

Alongside the RDF data, all relevant HTTP information, such as response codes, redirects, etc., are made available. However, being an incomplete crawl, not all URIs mentioned in the data were looked up. As such, we only have knowledge of $\mathsf{redir}$ and $\mathsf{deref}$ functions for 18.65 million URIs; all of these URIs are HTTP and do not have non-RDF file-extensions. We denote these URIs by ${\mathit{U}}_{\sim }$ . Of the 18.65 million, 8.37 million ( $\sim 45\mathrm{\%}$ ) dereferenced to RDF; we denote these by ${\mathit{D}}_{\sim }$ .

Again, this corpus is only a sample of the Web of Data: we can only analyse the HTTP lookups and the RDF data provided for the corpus. Indeed, a weakness of our analysis is that the BTC’11 dataset only considers dereferenceable RDF/XML documents and not other syntaxes like RDFa or Turtle. Thus, our estimate of what ratios of relevant data are dereferenceable should be considered as an upper bound since there are many documents on the Web of Data that we do not (or cannot [63]) know about.

6.2. Static schema data

For the purposes of this analysis, we extract a static set of schema data for the RDFS reasoning. As argued in [16], schema data on the Web is often noisy, where third-party publishers “redefine” popular terms outside of their namespace. Thus, we perform authoritative reasoning, which conservatively discards certain third-party schema axioms (cf. [16]). In effect, our schema data only includes triples of the following form:

prp-spo1	:  $\mathrm{(}\mathit{s}\mathrm{,}\mathtt{rdfs:subPropertyOf}\mathrm{,}\mathit{o}\mathrm{)}\in \mathsf{deref}\mathrm{(}\mathit{s}\mathrm{)}$
prp-dom	:  $\mathrm{(}\mathit{s}\mathrm{,}\mathtt{rdfs:domain}\mathrm{,}\mathit{o}\mathrm{)}\in \mathsf{deref}\mathrm{(}\mathit{s}\mathrm{)}$
prp-rng	:  $\mathrm{(}\mathit{s}\mathrm{,}\mathtt{rdfs:range}\mathrm{,}\mathit{o}\mathrm{)}\in \mathsf{deref}\mathrm{(}\mathit{s}\mathrm{)}$
cax-sco	:  $\mathrm{(}\mathit{s}\mathrm{,}\mathtt{rdfs:subClassOf}\mathrm{,}\mathit{o}\mathrm{)}\in \mathsf{deref}\mathrm{(}\mathit{s}\mathrm{)}$

We call these authoritative schema triples. Table 2 gives a breakdown of the counts of triples of this form extracted from the dataset, and how many domains (PLDs) they were sourced from: a total of 397 thousand triples were extracted from schema data provided by 98 PLDs. We denote this dataset as ${\mathrm{\Psi }}_{\sim }$ .

Table 2

Breakdown of authoritative schema triples extracted from the corpus

Category	Triples	PLDs
rdfs:subPropertyOf	10,902	67
rdfs:subClassOf	334,084	82
rdfs:domain	26,207	79
rdfs:range	26,204	77
total	397,397	98

6.3. Recall for baseline

We first measure the average dereferenceability of information in our sample. Let $\mathsf{data}\mathrm{(}\mathit{u}\mathrm{,}\mathit{G}\mathrm{)}$ give the triples mentioning a URI u in a graph G, and, for a dereferenceable URI d, let $\mathsf{ddata}\mathrm{(}\mathit{d}\mathrm{)}$ denote $\mathsf{data}\mathrm{(}\mathit{d}\mathrm{,}\mathsf{deref}\mathrm{(}\mathit{d}\mathrm{)}\mathrm{)}$ : triples dereferenceable through d mentioning d in some triple position. We then define the sample dereferencing recall for d w.r.t. G as: $$\mathsf{sdr}\mathrm{(}\mathit{d}\mathrm{,}\mathit{G}\mathrm{)}:={\displaystyle \frac{\mathsf{ddata}\mathrm{(}\mathit{d}\mathrm{)}}{\mathsf{data}\mathrm{(}\mathit{d}\mathrm{,}\mathit{G}\mathrm{)}}}$$ Letting ${\mathit{G}}_{\sim }:=\mathsf{merge}\mathrm{(}{\mathrm{\Gamma }}_{\sim }\mathrm{)}$ denote the merge of our corpus, we measure $\mathsf{sdr}\mathrm{(}\mathit{d}\mathrm{,}{\mathit{G}}_{\sim }\mathrm{)}$ , which gives the ratio of dereferenceable triples for d mentioning d vs. unique triples mentioning d across the corpus. For comparability, we do not dereference d live, but use the HTTP-level information of the crawl to emulate $\mathsf{deref}\mathrm{(}.\mathrm{)}$ at the time of the crawl. We denote by ${\mathsf{ddata}}_{\sim }$ the average of $\mathsf{ddata}\mathrm{(}\mathit{d}\mathrm{)}$ for all $\mathit{d}\in {\mathit{D}}_{\sim }$ , and by ${\mathsf{sdr}}_{\sim }$ the average of $\mathsf{sdr}\mathrm{(}\mathit{d}\mathrm{,}{\mathit{G}}_{\sim }\mathrm{)}$ for all $\mathit{d}\in {\mathit{D}}_{\sim }$ .

We also measure analogues of ${\mathsf{ddata}}_{\sim }$ and ${\mathsf{sdr}}_{\sim }$ where d must appear in specific triple positions: for example, if LTBQE dereferences a URI in the predicate position of a triple pattern, we wish to know how often relevant triples—i.e., triples with that URI as predicate—occur in the dereferenced document, how many, and what ratio compared with the whole corpus.

Table 3 presents the results, where for different triples positions we present:

$|{\mathit{U}}_{\sim }|$	: number of URIs in that position,
$|{\mathit{D}}_{\sim }|$	: number of which are dereferenceable,
${\displaystyle \frac{|{\mathit{D}}_{\sim }|}{|{\mathit{U}}_{\sim }|}}$	: ratio of dereferenceable URIs,
${\mathsf{sdr}}_{\sim }$	: as above, with std. deviation (σ),
${\mathsf{ddata}}_{\sim }$	: as above, with std. deviation (σ).

The row Type-Object only considers the object position of triples with the predicate rdf:type, and the row Object only considers object positions where the predicate is not rdf:type.

Table 3

Dereferenceability results for different triple positions

Position	$|{\mathit{U}}_{\sim }|$	$|{\mathit{D}}_{\sim }|$	${\displaystyle \frac{|{\mathit{D}}_{\sim }|}{|{\mathit{U}}_{\sim }|}}$	${\mathsf{sdr}}_{\sim }$		${\mathsf{ddata}}_{\sim }$
				avg.	σ	avg.	σ
Any	1.87 × 107	8.37 × 106	0.449	0.51	±0.5	17.26	±97.15
Subject	9.55 × 106	8.09 × 106	0.847	0.95	±0.19	14.11	±35.46
Predicate	4.77 × 104	745	0.016	0.00007	±0.008	0.14	±56.68
Object	9.73 × 106	4.50 × 106	0.216	0.44	±0.46	2.95	±60.64
Type-Object	2.13 × 105	2.11 × 104	0.099	0.002	±0.05	0.07	±29.13

A number of observations are directly relevant to LTBQE. Given a HTTP URI (without a common non-RDF/XML extension), we have a $\sim 45\mathrm{\%}$ success ratio to receive RDF/XML content regardless of the triple position; for subjects, the percentage increases to $\sim 85\mathrm{\%}$ , etc. If such a URI dereferences to RDF, we receive on average (at most) $\sim 51\mathrm{\%}$ of all triples in which it appears across the whole corpus. Given a triple pattern with a URI in the subject position, the dereferenceable ratio increases to $\sim 95\mathrm{\%}$ , such that LTBQE would work well for (possibly partly bound) query patterns with a URI in the subject position. For objects of non-type triples, the ratio drops to 44%. Further still, LTBQE would perform very poorly for triple patterns where it must rely on a URI in the predicate position or a class URI in an object position: the documents dereferenced from class and property terms rarely contain their respective extension, but instead often contain schema-level definitions.

Table 3 also features high standard-deviation values: these indicate that dereferenceability is often “all or nothing”. In relative terms, predicate and type-object deviations were the highest. Although most such terms return little or no relevant information—e.g., dereferencing the predicate in a triple pattern rarely yields triples where the dereferenced term appears as predicate—we observed a few predicates and values for rdf:type return a great many relevant triples in their dereferenced documents.14 ¹⁴

Many such examples for both classes and properties come from the SUMO ontology: see, e.g., http://www.ontologyportal.org/ SUMO.owl#subsumingRelation for a large extension of ontology terms provided by the ontology itself.

6.4. Recall for extensions

We now study how much additional data is made available for query answering by the three LTBQE extensions. Table 4 presents the average increase in raw triples made available to LTBQE by considering rdfs:seeAlso and owl:sameAs links, as well as knowledge materialised through owl:sameAs and RDFS reasoning. ${\mathit{D}}_{\sim }^{+}$ indicates the subset of URIs in ${\mathit{D}}_{\sim }$ that have some relation to the extension, respectively: the URI has rdfs:seeAlso link(s), has owl:sameAs link(s), or has non-empty RDFS inferences. Also, ${\mathsf{ddata}}_{\sim }^{+}$ indicates the analogous ${\mathsf{ddata}}_{\sim }$ measure after the extension has been applied; i.e., after relevant links are followed and/or inferences applied.

Table 4

Additional raw data made available through LTBQE extensions

Extension	$|{\mathit{D}}_{\sim }^{+}|$	${\displaystyle \frac{|{\mathit{D}}_{\sim }^{+}|}{|{\mathit{D}}_{\sim }|}}$	${\displaystyle \frac{{\mathsf{ddata}}_{\sim }^{+}}{{\mathsf{ddata}}_{\sim }}}$
			avg.	σ
SeeAlso	2.01 × 105	0.02	1.006	±0.04
SameAs	1.35 × 106	0.16	2.5	±36.23
RDFS	6.79 × 106	0.84	1.8	±0.76

6.4.1. Benefit of rdfs:seeAlso extension

The percentage of dereferenceable URIs in ${\mathit{D}}_{\sim }$ with at least one rdfs:seeAlso link in their dereferenced document was $\sim 2\mathrm{\%}$ (about 201 thousand URIs). Where such links exist, following them increases the amount of unique triples (involving the original URI) by a factor of $1.006\times$ versus the unique triples in the dereferenced document alone. We conclude that the rdfs:seeAlso extension will only marginally affect the recall increase of LTBQE in the general case.

6.4.2. Benefit of owl:sameAs extension

We measured the percentage of dereferenceable URIs in ${\mathit{D}}_{\sim }$ which have at least one owl:sameAs links in their dereferenced document to be $\sim 16\mathrm{\%}$ for our sample. Where such links exist, following them and applying the eq-* entailment rules over the resulting information increases the amount of unique triples (involving the original URI) by a factor of $2.5\times$ vs. the unique (explicit) triples in the dereferenced document alone. The very high standard deviation of ±36.23 shown in Table 4 is explained by the plot in Fig. 4 ( $\log \text{/}\log$ ), which shows the distribution of the ratio of increase by considering dereferenceable owl:sameAs links and inferences for individual entities: we again see that although the plurality of entities enjoy only a small increase in raw data (close to the x-axis), a few entities enjoy a very large increase (farther from the x-axis). In more detail, Fig. 5 gives a breakdown for URIs from individual domains, showing the number of URIs with an information increase above the indicated threshold due to owl:sameAs. The graph shows that, e.g., some URIs from nytimes.com and freebase.com had an information increase of over $4000\times$ (mostly due to DBpedia links); often the local descriptions were “stubs” with few triples.

Fig. 4.

Distribution of relative information increases by materialising owl:sameAs information ( $\log \text{/}\log$ ).

We conclude that owl:sameAs links are generally not so common for dereferenceable URIs, but where available, following them and applying the entailment rules generates significantly more (occasionally orders of magnitude more) data for generating answers.

6.4.3. Benefit of RDFS extension

With respect to our authoritative static schema data ${\mathrm{\Psi }}_{\sim }$ , we measured the percentage of dereferenceable URIs in ${\mathit{D}}_{\sim }$ whose dereferenced documents give non-empty entailments as $\sim 81\mathrm{\%}$ . Where such entailments are non-empty, they increase the amount of unique triples (involving the original URI) by a factor of $1.8\times$ vs. the unique (explicit) triples in the dereferenced document. We conclude that such reasoning often increases the amount of raw data available for LTBQE query answering, and by a significant amount.

6.5. Discussion

Before looking at specific queries, in this section we find that, in the general case, LTBQE works best when a subject URI is provided in a query-pattern, works adequately when only (non-class) object URIs are provided, but works poorly when it must rely on property URIs bound to the predicate position or class URIs bound to the object position. Furthermore, we see that rdfs:seeAlso links are not so common (found in 2% of cases) and do not significantly extend the raw data made available to LTBQE for query-answering. Conversely, owl:sameAs links are a bit more common (found in 16% of cases) and can increase the available raw data significantly ( $2.5\times$ ). Furthermore, RDFS reasoning often (81% of the time) increases the amount of available raw data by a significant amount ( $1.8\times$ ).

As discussed previously, we can use these results to justify a variant of LTBQE that tries to minimise wasted remote lookups: aside from skipping URIs bound to non-join variables, and unless collecting schema data dynamically, this variant skips dereferencing predicate URIs bound in triple patterns, or URIs bound to the objects of triples patterns where the predicate is bound to rdf:type, since we are unlikely to find data matching those patterns in the respectively dereferenced document (cf. Table 3).

7. Query benchmarks

Fig. 5.

Binning of relative information increases by materialising owl:sameAs information per domain ( $\log \text{/}\log$ ).

We wish to evaluate LiDaQ in a realistic, uncontrolled environment: answering SPARQL queries directly over a diverse set of Web of Data sources. To guide this evaluation, we first survey existing Linked Data SPARQL benchmarks and look at how other systems evaluate their approaches (Section 7.1). We conclude that no benchmark offers a large and diverse range of benchmark SPARQL queries and thus propose QWalk: a novel benchmark methodology tailored for testing LTBQE-style query-answering approaches over the broader Web of Data (Section 7.2). Final evaluation setup and results are presented later in Section 8.

7.1. Existing Linked Data SPARQL benchmarks

Since we aim to run our evaluation over Linked Data sources in situ, we ignore benchmarks designed to run over synthetic datasets such as LUBM [26], BSBM [15], or SP ${}^2$ Bench [57,58]. To the best of our knowledge, this leaves only two standard benchmarks:

FedBench [ 56 ]

offers three data collections for testing Linked Data querying scenarios:

a Life Science Data Collection, which includes datasets like KEGG, ChEBI, DrugBank and DBPedia;

a synthetic dataset from the SP ${}^2$ Bench framework [57,58]; and

a general Linking Open Data Collection, which includes datasets like DBpedia, GeoNames, Jamendo, LinkedMDB, The New York Times and Semantic Web Dog Food.

A query set is defined for each. The first query set focuses on features of particular interest for federated query engines, such as the number of involved sources, (interim) query results size, and so forth. The second query set consists of the original SP ${}^2$ Bench queries. The third set provides 11 Linked Data queries and is thus relevant to us.

DBSPB [ 48 ]

(the DBpedia SPARQL Benchmark) contains SPARQL queries distilled from real-world DBpedia logs, consisting of 31.5 million queries issued by various users and agents over a four-month time-frame in 2010. The raw set of queries is reduced to a total of 35 thousand queries after less frequently-occuring query shapes were removed. These 35 thousand queries are clustered to generate 25 templates that characterise the larger set. These templates can be “instantiated” to create new queries from DBpedia data. The core of the templates consist of Basic Graph Pattern queries with 1–5 triple patterns, but may also include various combinations of SPARQL query features (e.g., OPTIONAL–FILTER–DISTINCT, UNION–FILTER, and so forth).

A variety of Linked Data querying papers have also defined once-off evaluation frameworks. The methods used by a selection of papers are summarised in Table 5. We see that two approaches (FedX [59] and SPLENDID [25]) evaluate their methods using Fedbench, but do not run their queries live. Most papers simulate HTTP lookups or replicate SPARQL endpoints locally. We see that only two papers feature evaluation of queries that are run live over HTTP, both by Hartig [31,32], one involving six hand-crafted queries over real-world sources [32], the other proposing a “FOAF Letter” application to keep track of social connections where five query templates are instantiated for 23 people, giving a total of 115 queries.

In summary, there is much diversity in how Linked Data query proposals have been evaluated. Few benchmarks have been proposed for real-world Linked Data; perhaps the most agreed upon is FedBench. Most evaluations involve either a handful of custom queries designed to run over a small number of sources (FedBench), or a large number of (semi-)automatically generated queries tied to a specific domain (e.g., DBPSB) or vocabulary (e.g., FOAF Letter). Few engines run their queries live over remote resources, but instead replicate raw content or endpoints within a controlled environment. As such, no live Linked Data query engine has been evaluated in an uncontrolled, real-world setting for a large set of diverse queries: the closest such evaluation is probably FOAF Letter [31], but which only created queries over FOAF profiles.

Table 5

Summary of evaluation setups in the Linked Data querying literature

Reference	Queries			Measures			Live	Evaluation Setup
	count	type	published	time	results	sources
LTBQE1 a) [34]	4	Custom	X	✓	✓	✓	✓	Single run
LTBQE1 b) [34]	12	Custom	X	✓	X	X	X	BSBM query mixes, RAP Pubby setup
LTBQE2 [36]	200	Custom	✓	✓	X	✓	X	BSBM query mixes, RAP Pubby setup
LTBQE3 [31]	115	Custom	✓	✓	✓	✓	✓	3 runs per query
LTBQE4 [32]	3	Custom	✓	✓	✓	✓	✓	6 runs per query (1st run warmup)
LT10 [44]	8	Custom	✓	✓	✓	✓	X	Controlled with 2 second delay proxy
SIHJoin [45]	10	Custom	✓	✓	X	X	X	CumulusRDF Linked Data proxy
FedX [59]	11	FedBench	✓	✓	X	X	X	Local copies of SPARQL endpoints
LH10 [47]	390	Custom	X	✓	✓	✓	X	Simulated HTTP lookups
SPLENDID [25]	14	FedBench	✓	✓	X	✓	X	Local replication of SPARQL endpoints
SPARQL-DQP [4]	7	Custom	✓	✓	X	X	X	Amazon EC2 instance
QTree [65]	300	Auto-gen.	X	✓	✓	✓	X	Simulated HTTP lookups

7.2. QWalk: Random walk query generation

Given the shortcomings of existing benchmarks, we propose QWalk: a new benchmark framework that automatically builds a large set of queries that are answerable (e.g., by LTBQE) over a diverse set of real-world sources. The core idea is to take a large crawl of the Web of Data (in this case, the BTC’11 dataset) and to conduct random walks of different shapes and lengths through the corpus to generate Basic Graph Patterns. The walk is guided to ensure that it crosses documents through dereferenceable links: generated queries should thus be answerable by LTBQE.

7.2.1. Query shapes

To inform the types of queries we generate, we take observations from the work of Gallego et al. [7], who analyse the SPARQL queries logs of the DBPedia and Semantic Web Dog Food (SWDF) servers. They found that most queries contain a single triple pattern (66.41% in DBPedia, 97.25% in SWDF). The maximum number of patterns found was 15, but such complex queries occurred only rarely. The most common forms of joins involved subject–subject (59–61%), subject–object (32–36%) and object–object (4–5%); few joins involving predicate variables were found in general. As such, most queries with multiple patterns are star-shaped, with a few path shaped queries. Star-shaped joins typically had a low “fan-out”, where 27% of the DBpedia queries had a fan-out of three, and 3.7% had a fan-out of two; the bulk of the remaining queries were single-pattern with a trivial fan-out of one, but went up to a maximum of nine. The lengths of paths in the query were mostly one (98%) or two (1.8%); very few longer paths were found.

Along similar lines, for our benchmark we generate queries of elemental graph shapes as depicted in Fig. 6, viz., edge, star and path queries. We now describe these query types in more detail.

Fig. 6.

Visualisation of example query shapes (edge-s, edge-o, s-path-2, o-path-3, star-2-1); dotted nodes represent variables; solid nodes represent URIs.

Edge queries (edge-<s|o|so>)

fetch all triples (edges) for an entity. We generate three sub-types of edge queries, asking for triples where a URI appears as the subject (edge-s); as the object (edge-o); as the subject and object (edge-so). These types of queries are very common in Linked Data browsers or for dynamically serving dereferenceable Linked Data content. An example query for edge-so would be:

Star queries (star-<s3|o3|s2-o1|s1-o2>)

consist of three acyclic triple patterns that share exactly one URI (called the centre node). These queries are similar to edge queries but have only constant predicates, asking for specific attributes of a given entity. Each query has 4 constants and 3 variables. We generate four sub-types of star queries, differing in the number of triple patterns in which the centre node appears at the subject (s) or object (o). An example for star-s2-o1 would be:

Path queries (<s|o>-path-<2|3>)

consist of 2 or 3 triple patterns with constant predicates that form a path such that precisely two triple patterns share a given join variable. Precisely two patterns contain one join variable, and the remaining patterns contain two join variables. Precisely one triple pattern has a URI at either the subject or object position. We generate four different sub-types: path shaped queries of length 2 and 3 in which either the subject or object term of one of the triple patterns is a constant. An example for s-path-2 is:

Query generation  We generate queries from the aforementioned BTC’11 dataset. In total, we generate 100 SELECTDISTINCT queries for each of the above 11 query shapes using random walks in our corpus. To help ensure that queries return non-empty results (in case there are no HTTP connection errors or time outs) we consider dereferenceable information and generate queries as follows:

We randomly pick a pay-level-domain available in the set of confirmed dereferenceable URIs ${\mathit{D}}_{\sim }$ .

We then randomly select a URI from ${\mathit{D}}_{\sim }$ for that pay-level-domain.

We generate appropriate triple patterns from the dereferenceable document of the selected URI based on the query shape being generated.

• If path-shaped queries are being generated, the URI for the next triple pattern is selected from the dereferenceable URIs connected to the previous URI, as per a random walk.

One variable is randomly chosen as distinguished (returned in the SELECT clause) and other variables are made distinguished with a probability of $0.5$ .

By randomly selecting a pay-level-domain first (as opposed to randomly selecting a URI directly), we achieve a greater spread of URIs across different datasets. The result of the QWalk process is a large set of diverse queries with different elemental shapes that—according to the sampled data—should be answerable through LTBQE methods over real-world data in a realistic scenario (accessing remote sources).

8. Query benchmark results & discussion

When running queries directly over remote sources, various challenges come to the fore, including slow HTTP lookups, unpredictable remote server behaviour, high fan-out of links to traverse, the need for polite access (in terms of delays between lookups and respecting robots.txt policies), and so forth. As discussed, most works have evaluated LTBQE-style approaches in controlled environments using proxies or only for a small number of queries or sources in uncontrolled environments. Conversely, we now wish to investigate the feasibility of LTBQE—and our proposed reasoning extensions—for a broad range of diverse queries in uncontrolled environments so as to characterise how these methods cope with real-world challenges.

Based on the discussion of the previous section, we select three complementary benchmarks to run with LiDaQ, where we execute all queries directly over the Linked Data Web:

1. DBpedia SPARQL Benchmark (DBPSB), which generates many queries designed to run over one domain based on real-world query logs (we encountered difficulties running DBPSB with LTBQE as summarised later);

2. FedBench Linked Data Queries, which offers some manually crafted queries designed to run over a small selection of different domains;

3. QWalk, which offers a large selection of synthetic queries that can be run directly over a diverse set of sources.

We first discuss the experimental setup and measures (Section 8.1). Next we introduce the configurations of LiDaQ that we evaluate (Section 8.2). We then briefly summarise the problems we encountered when running DBPSB queries (Section 8.3). Finally, we present detailed results for FedBench (Section 8.4) and QWalk (Section 8.5).

8.1. Experimental setup and measures

All evaluation is run on one server: 4 GB RAM, Debian OS, 2.2 GHz single core. To ensure polite behaviour, we enforce a per-domain (specifically per-PLD) minimum delay of 500 ms between two sequential HTTP lookups on one domain. Furthermore, we use a (generous) query timeout of 2 hours.

When running queries live over HTTP, we often encounter some “non-deterministic” behaviour: a source may be readily accessible during some query runs, but may be unresponsive or not return at all in others. Different HTTP-level issues can occur at different times for the same source. During initial experiments, we thus encountered that result size and execution time can differ for the same query and setup between several benchmark runs. This “inconsistent” query behaviour is explained by the fact that we encountered various HTTP-level issues between different executions for the same query and setup. We thus define the straightforward notion of a benchmark stable query to help with comparability across different setups. We assume that a query has a core set of relevant documents, which are accessed in all configurations (introduced in the following section). A benchmark stable query is a query for which the response codes for each of the core URIs is the same across all setups runs.

For each query in each evaluation framework, we record the number of unique results returned and the total time taken for the query to execute and terminate. We also record the first result latency, where a query may begin to return results quickly but may take a long time to terminate due to a few slow accesses for the final results. We record the number of HTTP lookups performed; since individual lookups are slow and we additionally implement politeness policies, this will be a major factor for performance issues. We also look at the raw data processed and number of triples inferred, both expressed as number of unique triples.

In initial experiments, we found that raw counts of unique query results sometimes exhibit outliers due to redundancy caused by joins. We illustrate the problem with an example QWalk query:

Example 11.

Take the following QWalk query:

Without reasoning, upon dereferencing the ebiz: URI, we found 1 binding for ?o0, 2 bindings for ?s0 and 199 bindings for ?s1, yielding a total of $1\times 2\times 199=398$ results. However, with RDFS reasoning enabled, the schema document for RDFS (the so-called “rdfs.rdfs” document) authoritatively defines rdfs:isDefinedBy to be a sub-property of rdfs:seeAlso. Thus, the 199 bindings for ?s1 are added to ?s0, yielding 201 bindings, and a total of $1\times 201\times 199=39\mathrm{,}999$ results, giving a two orders of magnitude increase.

The query results in this example contain many repetitions of terms: each term bound to ?s0 or ?s1 would appear about 200 times with RDFS reasoning enabled. Hence we add another measure to help characterise the “redundancy-free content” of the results: we add the number of unique result terms found for each distinguished variable in the results. In the above example, this would give $1+2+199=202$ terms without reasoning, and $1+201+199=401$ terms with reasoning.

8.2. LiDaQ configurations evaluated

For LiDaQ, given the various extensions, various ways of collecting RDFS data, and the option to turn off/on our reduction of sources, we have thirty-two combinations of possible setups, where we choose the following ten configurations to evaluate:

Core ( Core ):

we dereference all URIs appearing in the query and during the query execution, independent from their triple position or role in joins. No extensions are included. This setup serves primarily as reference to the basic LTBQE profile.

Reduced Core ( Core ⁻ ):

Our reduced configuration uses our optimised source selection to decide which URIs are query relevant and should be dereferenced. We do not dereference URIs bound to non-join variables, or (unless dynamically retrieving schemata) URIs bound to predicates or values for rdf:type. In theory, we expect the smallest amount of results and also the fastest query time and the following extensions are built upon Core⁻, not Core.

With rdfs:seeAlso links ( seeAlso ):

this configuration extends the Core⁻ setup by following rdfs:seeAlso links. Based on our empirical analysis, we expect that only a small number of queries will be affected given that $\sim 2\mathrm{\%}$ of URIs have dereferenceable rdfs:seeAlso links and that following such links finds little relevant data.

With owl:sameAs links and inference ( sameAs ):

this benchmark setup extends the Core⁻ setup by considering owl:sameAs links and inference. We expect an increase in returned results and the number of lookups. Based on our empirical study, this should affect a moderate number of queries given that such links are available for $\sim 16\mathrm{\%}$ of resources, where, in such cases, inference makes on average $2.5\times$ more raw data available.

With RDFS inference $\mathrm{(}{\mathrm{RDFS}}_{[\mathit{s}|\mathit{d}|\mathit{e}]}\mathrm{)}$ :

this benchmark setup extends the Core⁻ setup by performing inferences for the RDFS ruleset relying on retrieved schema information. Based on static schema data, our empirical analysis suggested that RDFS reasoning affects $\sim 84\mathrm{\%}$ of resources for which it makes about $1.8\times$ more raw data available. However, we investigate three sub-configurations based on the methods described in Section 5.1.3: Static ( RDFS ${}_{\mathit{s}}$ ):

uses the static schema extracted earlier from the BTC’11 dataset;

Direct ( RDFS ${}_{\mathit{d}}$ ):

collects direct schemata by dynamically dereferencing predicates and values for rdf:type;

Extended ( RDFS ${}_{\mathit{e}}$ ):

collects extended schemata by dynamically following recursive links from the direct schemata.

Combined $\mathrm{(}{\mathrm{C}\mathrm{OMB}}_{[\mathit{s}|\mathit{d}|\mathit{e}]}\mathrm{)}$ :

this benchmark setup combines all extensions for the previously mentioned configurations of schema collection. With this configuration, we expect the highest number of results, query time and processed and inferred statements.

For reference, Table 6 summarises these test configurations and which features are enabled or disabled.

Table 6

Overview of the ten LiDaQ benchmark configurations

Label	reduced sources	rdfs:seeAlso	owl:sameAs	static RDFS	direct RDFS	extended RDFS
Core
Core −	✓
seeAlso	✓	✓
sameAs	✓		✓
RDFS ${}_{\mathit{s}}$	✓			✓
RDFS ${}_{\mathit{d}}$	✓				✓
RDFS ${}_{\mathit{e}}$	✓					✓
Comb ${}_{\mathit{s}}$	✓	✓	✓	✓
Comb ${}_{\mathit{d}}$	✓	✓	✓		✓
Comb ${}_{\mathit{e}}$	✓	✓	✓			✓

8.3. DBPSB Result Summary

We first briefly summarise our experiences in trying to use DBpedia SPARQL benchmark (DBPSB) to test LTBQE and our extensions. DBPSB involves 25 query templates generated from real-world DBpedia query logs, which are not designed specifically to be run with LTBQE. Our experiments had broadly negative results. Full details of the experiments are available in [62, § 4.5.2.2]. To summarise, of the 25 query templates, we identified that 16 could not be run by LTBQE, due to either containing an OPTIONAL clause15

¹⁵

In SPARQL, OPTIONAL can be combined with a !BOUND(.) filter to emulate negation-as-failure, which cannot be run over an open Web of Data (unless a closed-dataset semantics is considered [33]).

or only containing property/class URIs in the query (whose extension cannot be dereferenced in DBpedia).

Next we tried to generate 25 sample queries for each of the remaining 9 DBPSB templates. We ran the template queries provided for the benchmark against the public DBpedia SPARQL endpoint16 ¹⁶

http://dbpedia.org/sparql/

and generated up to 1000 results. From these, we randomly selected 25 results to generate the query instances. Of the 9 templates, we encountered problems instantiating another 3 where the endpoint either timed out or returned too few results. In running the queries generated by the remaining 6 templates,17 ¹⁷

All template instances are available online: http://code.google. com/p/lidaq/source/browse/queries/dbpsb.swj.25.tar.gz.

LTBQE could not return results for 3 templates due to (non-dereferenceable) RDF literals being generated in the queries.

The detailed discussion and results for the 3 remaining templates are available in [62, § 4.5.2.2]. To summarise, these three templates involved (1) listing the types of a given entity (DB1), (2) listing English comments and depictions or homepages for a given entity (DB13), and (3) a more complex query that asks for the French-language labels of French prefectures and German state capitals (DB17). The results for these three templates suggested that Core⁻ offers increased performance over Core with no loss of results, but we encountered performance issues with sameAs where there are many outgoing owl:sameAs links from DBpedia that did not contribute answers to the DBpedia-specific queries of DBPSB. Also, although using static RDFS schema contributed many additional answers to the first query template, the dynamic import of schema proved expensive for DBpedia, where classes and properties dereference to separate documents.

The observation that so few query templates (based on real-world user logs) could be run by LTBQE is in itself a negative result and also makes it difficult to meaningfully interpret the results of our DBPSB experiments. Acknowledging this, we now rather focus on the results of the FedBench and QWalk benchmarks, which are designed with LTBQE in mind.

8.4. FedBench results

We now use the FedBench Linked Data Queries (Section 7.1) to measure the potential benefit of our proposed extensions and optimisations. These 11 cross-domain queries (denoted LD1–11) are designed to return a non-empty result set if executed over the Web with an LTBQE-style approach. The queries (along with results and discussion) can be found in Appendix A. Our first observation is that 4 out of the 11 manually crafted FedBench queries contain explicit owl:sameAs query patterns. This fact ties back with our initial motivation that including owl:sameAs information is important to answer queries across diverse sources. In the case of FedBench, these owl:sameAs relations are included explicitly; for our extension this would not be necessary (though we leave them in for comparability across LiDaQ configurations that include/exclude owl:sameAs inference).

Query testing  We had to make some amendments to the original 11 FedBench queries. First, since we count results, we add the DISTINCT solution modifier to all queries to eliminate duplicates. Second, during initial tests, we identified that 3 queries were not up-to-date with the DBpedia knowledge-base. These queries (LD8–10) used the predicate skos:subject where DBpedia now uses dcterms:subject. We directly replaced these predicates in the query. In one such query (LD9), we also added a missing @en language tag to the literal "Luiz Felipe Scolari" to correspond with DBpedia data. Our updated queries are online.18

¹⁸

http://code.google.com/p/lidaq/source/browse/queries/ fedbench.txt

Other queries returned no results. Two queries (LD6–7) required data from the geonames.org domain, which failed because the the robots.txt file on the subdomain19 ¹⁹

See http://sws.geonames.org/robots.txt.

states that all agents are disallowed: we do not wish to contravene the Robots Exclusion Protocol. Query LD9 returns no results for any configuration (or any run) and query LD10 only sometimes returns results when owl:sameAs is considered: these are due to mismatches between the given queries and remote data that we could not easily fix without dramatically changing the original query (see Appendix A for details). Aside from LD7, which only involved the GeoNames domain, we run the other queries for timings, even if they do not return results.

Overview of experiments  For all benchmark configurations, we executed each FedBench query live over the Web once a week for four weeks. In Appendix A, for each individual query, we provide detailed results and discussion (selecting the best of the four runs). We also include per-query comparison to the existing SQUIN library for LTBQE [34], which we generally find to be considerably faster, but which, to the best of our knowledge, does not include politeness policies; we thus exclude it for later larger-scale experiments.

Table 7

Average result size and standard deviation across four query runs

Setup	LD1		LD2		LD3		LD4		LD5
	avg.	σ	avg.	σ	avg.	σ	avg.	σ	avg.	σ
Core	333	±0	185	±0	191	$\pm 0$	50	±0	21.5	±24.83
Core −	333	±0	185	±0	190.75	±0.5	50	±0	24	±22.32
seeAlso	333	±0	185	±0	190.75	±0.5	50	±0	21.5	±24.83
sameAs	527.25	±3.95	185	±0	908.25	±35.53	146	±0	67.75	±135.5
RDFS ${}_{\mathit{s}}$	380	±0	185	±0	246	±0	50	±0	17.5	±21.24
RDFS ${}_{\mathit{d}}$	380	±0	185	±0	246	±0	50	±0	20.25	±23.41
RDFS ${}_{\mathit{e}}$	380	±0	185	±0	246	±0	37.5	±25	8	±9.38
Comb ${}_{\mathit{s}}$	674.5	±14.15	185	±0	1385	±161.85	137	±92.57	0	±0
Comb ${}_{\mathit{d}}$	662.5	±14.71	185	±0	1428	±122.36	151.25	±100.85	3.5	±7
Comb ${}_{\mathit{e}}$	674.5	±14.15	185	±0	1428	±122.36	88.5	±59.29	—	—
Setup	LD6		LD8		LD9		LD10		LD11
	avg.	σ	avg.	σ	avg.	σ	avg.	σ	avg.	σ
Core	0	±0	9.5	±10.97	0	±0	0	±0	21,801.75	±6255.72
Core −	0	±0	9.5	±10.97	0	±0	0	±0	14,322	±12,237
seeAlso	0	±0	19	±0	0	±0	0	±0	19,096	±9373.88
sameAs	0	±0	10,535.5	±12,165.35	0	±0	2512.5	±2973.81	8466	±10,940.75
RDFS ${}_{\mathit{s}}$	0	±0	9.5	±10.97	0	±0	0	±0	1745.5	±3491
RDFS ${}_{\mathit{d}}$	0	±0	1	±2	0	±0	0	±0	2757.25	±3508.19
RDFS ${}_{\mathit{e}}$	0	±0	3	±6	0	±0	—	—	—	—
Comb ${}_{\mathit{s}}$	0	±0	14,096.75	±16,295.82	0	±0	812.25	±1624.5	71,438	±21,634.8
Comb ${}_{\mathit{d}}$	0	±0	—	—	0	±0	0	±0	177,596.5	±61,929.13
Comb ${}_{\mathit{e}}$	0	±0	—	—	—	—	—	—	50,660	±71,289.96

Detailed results  Given the number of queries (10), configurations (11) and measures (6), we leave detailed discussion of results for individual FedBench queries to Appendix A.

Summarising, we observe that LTBQE works well for some simpler FedBench queries, but struggles in an uncontrolled environment for complex queries that require accessing a lot of sources. For example, even in the baseline Core⁻ configuration, LD11 required performing 1125 lookups, and the most complex configuration—Comb ${}_{\mathit{e}}$ —attempted 17,996 lookups. Relatedly, we generally observe that LTBQE extensions perform well for simple queries, but exacerbate performance issues for complex queries. In fact, although RDFS and owl:sameAs extensions work well on domains like data.semanticweb.org, configurations that involve following same-as or schema links struggle for data-providers such as DBpedia, which offer many such links (both internal and external). On a more positive note, Core⁻ often offers significant time savings over Core with minimal effect on result sizes.

In addition, results sizes can become quite large (e.g., LD11 returns 196,448 results in one configuration): the given SPARQL queries often contain numerous result variables in the SELECT clause (e.g., 5 for LD11) and results can contain high redundancy. For example, DBpedia often contains a large number of labels for resources in different languages, where asking for the labels of result resources may multiply the raw result sizes by a factor of ten or more and where such behaviour has a cumulative effect.

In general, we would also expect that the results given by Core⁻ should be fewer or equal than for all other configurations, which are monotonic extensions; similarly, we would expect equal or more results in Comb ${}_{\mathit{x}}$ than RDFS ${}_{\mathit{x}}$ , sameAs and seeAlso (where x is one of the schema configurations). This expectation held true in practice for a number of the earlier queries (LD1–3), where for queries LD1 and LD3, the various extensions, including reasoning, found many more results. This monotonic increase also held true for certain other cases (e.g., with the exception of Comb ${}_{\mathit{e}}$ , LD4 shows this behaviour). However, it did not hold true in later queries: even selecting the best run from a span of four weeks, the unrepeatability of results played a major role in this evaluation. We thus now focus on characterising this issue.

Reliability results  Running complex queries live over networks of remote sources raises the question of reliability and repeatability. We now focus on how the results varied across the four runs to get a better idea of the repeatability of LTBQE/LiDaQ in a realistic setting. We summarise the average number of results and the corresponding standard deviation for each configuration and query across all four runs in Table 7.

LD11 in particular shows some unreliable behaviour across the four runs, where we estimated the absolute deviations to be between $\sim 28\text{–}140\mathrm{\%}$ of the mean, depending on the LiDaQ configuration: as aforementioned, this query required between 1103–17,996 lookups. With this exception aside, across all other queries, the Core, Core⁻ and seeAlso configurations access the fewest sources and produce reliable results across the four runs. The results for the other variations—which include reasoning extensions—are less reliable in general. LD5 and LD10 show high deviations in the number of results returned for sameAs, LD5 shows high deviations for dynamic schema configurations, and LD4 shows high deviations for configurations involving RDFS reasoning (though not for combined configurations). In terms of absolute deviation as a percentage of the mean, we computed that the results for the other setups vary somewhere between $\sim 2\text{–}11\mathrm{\%}$ for most of the queries.

Conclusions  When running the queries live over remote sources, we see complex and unpredictable behaviour across different configurations and across time: remote sources may give different responses at different times (e.g., may give 50x errors during high server load), and the failure of an important source may break traversal at that point. We also see that reasoning extensions, particular those involving dynamic schema collection, often make the query behaviour more unreliable by trying to access more sources.

The FedBench queries predominantly request data from a few central sites: the first four queries (LD1–4) are based around the data.semanticweb.org data provider, and provide generally stable results. Other queries also rely on the hosts www4.wiwiss.fu-berlin.de and dbpedia.org and generally demonstrate less stable behaviour. Taking the former domain, for example, owl:sameAs extensions can cause erratic behaviour, potentially due to errors in how the relation is used for the DailyMed and LinkedCT datasets. For DBpedia, the schema descriptions of class and property terms are hosted in individual documents and often interlink with related sources like YAGO and CYC, leading to unstable behaviour for dynamically retrieving schemata where many documents need to be recursively retrieved. Given that the queries are restricted to a few domains, the required politeness delays are a major factor for performance.

In summary, from the 11 original FedBench queries, which were designed to be run using LTBQE-style approaches, 4 queries show promising results, 3 return no results (2 involving access disallowed by robots.txt), and the remaining 4 queries show unpredictable behaviour across different runs and configurations. Some of the more complex queries involve accessing thousands and tens of thousands of sources at runtime. By requesting even more sources, our proposed reasoning extensions can aggravate reliability issues. This calls into question the practicality of the LTBQE approach (and our reasoning extensions) in uncontrolled environments for complex queries that span multiple sites and require many sources to answer.

8.5. QWalk results

Having briefly looked at the DBPSB queries, which target only the DBpedia domain; and having looked in more detail at the FedBench queries, which target a handful of domains; we now look at the results of the QWalk benchmark (Section 7.2), which builds a large set of queries answerable over a wide range of real-world sources. Using random walk techniques over the BTC’11 corpus, we created 100 queries for each of the 11 elemental shapes of the QWalk benchmark, giving 1100 initial queries. We then ran these live over remote sources using various configurations of LiDaQ.

Query testing  We first wish to filter out queries that did not return any answers or that did not show benchmark stable behaviour. To begin, for the edge query classes, we look at how many queries return empty results, how many return stable non-empty results suitable for comparison, and how many return unstable non-empty results (see Section 8.1). Our notion of stability is measured across all ten configurations of LiDaQ, including the dynamic schema import extensions. We also looked at the breakdown of stable/unstable/empty results turning off the dynamic schema import (i.e., turning off RDFS ${}_{\mathit{d}}$ , RDFS ${}_{\mathit{e}}$ , Comb ${}_{\mathit{d}}$ , Comb ${}_{\mathit{e}}$ ). The results are shown in Table 8. Though the stability of edge-o and edge-so queries are not significantly affected, the number of stable queries for edge-s queries more than halves. Thus, due to these problems with instability and also long runtimes, and given the number of queries in the benchmark, we do not run the dynamic schema configurations for QWalk queries.

Table 8

Stable edge queries with and without dynamic schema extensions

Template	Total	Stable
		wo/dyn.	w/dyn.
edge-s	100	60	27
edge-o	100	57	53
edge-so	100	59	54

Considering Core⁻, Core, seeAlso, sameAs, RDFS ${}_{\mathit{s}}$ and Comb ${}_{\mathit{s}}$ configurations for each query shape, Table 9 provides a breakdown of the total number of queries that return some results and exhibit stable or unstable behaviour, as well as the number of queries with no results. Typewritten numbers correspond to categories for HTTP server response codes encountered for queries with no results; the column “mix” indicates at least two different response codes and the column “data” indicates that the missing results are not related to URI errors and we assume that the remote data changed. We select only non-empty and stable queries for our comparison.

Table 9

Summary of stable/unstable/empty queries for QWalk benchmark

Class	Non-Empty		Empty
	s.	uns.	all	4XX	5XX	6XX	mix	data
edge-o	57	7	36	18	2	11	0	5
edge-s	60	5	35	18	1	11	0	5
edge-so	59	9	32	17	2	8	1	4
o-path-2	62	4	34	16	5	8	1	4
o-path-3	35	25	40	19	3	18	0	0
s-path-2	66	2	32	17	2	11	0	2
s-path-3	51	7	42	18	1	20	0	3
star-0-3	67	6	27	14	0	10	0	3
star-1-2	62	2	36	21	2	12	0	1
star-2-1	70	5	25	11	3	9	1	1
star-3-0	66	15	19	12	0	4	0	3

Fig. 7.

Percentiles for ratio of increase in total runtimes, result latency and result sizes vs. Core⁻ for edge-query classes ( $\log$ ).

Fig. 8.

Percentiles for ratio of increase in total runtimes, result latency and result sizes vs. Core⁻ for star-query classes ( $\log$ ).

Detailed results  We now look at the average measures for results across all (non-empty stable) queries per query class: we begin with edge queries, then progress to star queries and eventually to path queries. Detailed results for each of our measures can be found for reference in Table 21 of Appendix B. Herein, we plot the total runtime, result latency and result sizes in bar plots, where we measure the ratio of the analogous figure for Core⁻ (which always returns the fewest results and should be the fastest). Absolute measures can be found in Table 21. We generally found a lot of variance and outliers in our results; hence we plot the 50th, 75th, 90th and 100th percentiles to help show how the measures varied in the median case (given by the 50th percentile) and for extremes/outliers (given by higher percentiles).

edge-*: Get all edges for a given resource

Edge queries have the most simple query shape and are used in a wide range of applications to gather all available information about a certain entity, e.g., for the user interfaces of entity search engines. They are also often (but not always) used as a simple mechanism to support SPARQL DESCRIBE queries. Figure 7a presents the increase in time over Core⁻ for all other configurations across the three classes of edge queries, broken down by percentiles, with the x-axis presented in $\log$ -scale, where the ${10}^0$ line indicates no change from Core⁻. Figure 7b analogously presents the increase in result latency (time taken to generate the first result) and Fig. 7c presents the increase in query results returned versus Core⁻.

We can see from the 50th percentile in Fig. 7a that the Core configuration—which dereferences predicates, values for rdf:type and URIs bound to non-join variables—often requires significantly more time to process queries than Core⁻ across all three edge query classes, with the most severe case (on the 100th percentile) taking almost eight times longer for edge-s. Conversely, Fig. 7c shows that Core almost never returns additional results beyond Core⁻.

We also see that seeAlso rarely affects performance, but very rarely finds additional answers (only for the 100th percentile are result increases visible). From the flat 75th percentiles in Fig. 7a, we can see that in the majority of cases, other extensions did not affect performance significantly, and the time taken to start returning results was only affected significantly in outlier cases. However, for total runtimes, the 90th and 100th percentiles with reasoning show occasional increases by a factor of ten, but these are offset by increased result sizes, where modest increases are already visible on the 50th percentile for RDFS ${}_{\mathit{s}}$ and Comb ${}_{\mathit{s}}$ in the edge-s and edge-so queries: all RDFS rules offer additional data for edge-s* queries, whereas only sub-property reasoning offers additional results for edge-o in the general case. The 75th–100th percentiles also show occasional but very large increases for results in the sameAs configuration. star-*: Retrieve values for specific predicates about a given resource

Fig. 9.

Percentiles for ratio of increase in total runtimes, result latency and result sizes vs. Core⁻ for path-query classes ( $\log$ ).

Star-shaped queries retrieve selected attributes of an entity. The results for star-shaped queries are presented in Fig. 8 following the same format as before.

Some similar conclusions can again be drawn as for edge queries. Again, the query time can often be reduced without a significant effect on query results by opting for Core⁻ over Core; in this case, since query predicates are set, the savings are made by not dereferencing values for rdf:type or URIs bound to non-join variables. The result latency remains relatively stable except for in the 100th percentile outlier. The notable total-runtime outlier for the query class star-1-2 in Core (on the 100th percentile) is due to one query which took around 1 hour to terminate because of the download and processing of a very large document from the ecowlim.tfri.gov.tw provider (such cases show the importance of also considering the result latency: this source contributed no results and was not accessed by configurations built on top of Core).

Again, we see that seeAlso had minimal effect on results returned, but did increase the time significantly for some of the query classes. RDFS and owl:sameAs reasoning had an occasional but significant effect on results size: however, we highlight that the baseline gave, on average, very few results for star-3-0 and star-0-3 (cf. Table 21), where a small absolute increase could account for a very large relative increase, as per the outliers on the 100th percentile. Also, the large RDFS-related results outlier for the class star-1-2 is due to the query mentioned in Example 11.

*-path-*: Retrieve terms that are two or three hops away from a central resource through a path of given predicates

Path-shaped queries allow for exploring recursive relations in the graph, or to get information about neighbouring nodes. When compared with edge and star queries, we would expect path queries to generally be more expensive for LTBQE to process since they explicitly require traversing a number of sources.

For path queries, we again show the analogous increases in runtimes for the five configurations in Fig. 9. Again, we see the savings in time for selecting Core⁻ over Core, particularly for the o-path-* classes of queries. We also see that result latencies are generally not affected by extensions, other than in the case of outliers. Across all extensions, the performance hit for o-path-* queries are not met with gains in results; in fact, the o-path-3 queries saw no significant gains for any extension, even for the 100th percentile. We see the first meaningful gain for seeAlso in the s-path-3 class, but only for a single outlier query. In this case, sameAs offers only minimal increases in some outlier cases. However, the RDFS ${}_{\mathit{s}}$ extension finds additional results for s-path-* queries, which are notable already on the 75th percentile; this extension performs particularly well for s-path-3 where large gains in results do not cost comparable increases in total runtimes. The Comb ${}_{\mathit{s}}$ configuration again offers the most results, but—with the exception of Core—at the cost of the highest runtimes.

Conclusion  Across the hundreds of queries run for the 11 query classes, we consistently find that compared with Core, the Core⁻ configuration saves significantly on total query runtimes with only minimal impact on result sizes. With the exception of one query, we find that seeAlso finds barely any additional results, but can sometimes cause a significant increase in runtime. Reasoning extensions also increase total runtimes, but regularly contribute additional answers: sameAs offers infrequent but very high increases in result sizes, where by comparison, RDFS ${}_{\mathit{s}}$ offers more frequent but more modest increases in results. These observations on result increases for the three extensions correspond well with the results of our analysis for the BTC’11 data in Section 6. Throughout, with the frequent exception of Core, the combined approach was indeed the slowest, but always offered the most results. Although the reasoning extensions often significantly increased the time taken for queries to terminate, the latency for retrieving the first results was not significantly increased except in extreme cases.

To help summarise these results, Table 10 presents the average throughput (results per second) achieved across all queries per query class.20 ²⁰

Given that there is a lot of variance in the raw figures, we acknowledge that average figures are a coarse way to present the results, but they do help to summarise overall trends.

We see that Core has uniformly the worst throughput of results across all query classes. We also see that Core⁻ generally performs slightly above average, but performs best for edge-o. With the sole exception of the s-path-3 class, seeAlso performs slightly worse than Core⁻. In terms of the reasoning extensions, of the 11 query classes, the highest throughput for 9 are split between the sameAs (4), RDFS ${}_{\mathit{s}}$ (4) and Comb ${}_{\mathit{s}}$ (1) configurations, where, for each configuration, the throughput of Comb ${}_{\mathit{s}}$ frequently sits between sameAs and RDFS ${}_{\mathit{s}}$ . However, aside from Core, these latter configurations also often perform the worst: they add significant overhead to the query execution, but may often find significantly many additional results: they offer high-risk but high-gain.

Table 10

Results per second for all query classes with configurations shaded from best (lightest) to worst (darkest) throughput

9. Conclusion

In theory, link-traversal query approaches for Linked Data have the benefit of up-to-date results and decentralised execution. However, a thorough evaluation of such methods in realistic uncontrolled environments—for a diverse Web of Data—had not yet been conducted. We have focused on evaluating LTBQE approaches in this manner and have investigated the possibility of combining lightweight reasoning methods with LTBQE to gather and integrate data from diverse sources during query-answering.

We have characterised what percentage of data is missed by only considering dereferenceable information, we have looked at what percentage of raw data is made available to LTBQE through various extensions, and we have tested LTBQE and various extensions in uncontrolled environments for three complimentary query benchmarks. Our results show that LTBQE works well for simple queries with a dereferenceable subject, but, in uncontrolled environments, struggles for more complex queries that involve accessing many remote sources at runtime. Furthermore, we showed that runtimes in uncontrolled environments are often a factor of politeness policies, since queries frequently access many documents from few domains.

In terms of the extensions, we have shown that the selection of sources can be successfully reduced by ignoring predicate URIs, object URIs for type-triples, and URIs bound to non-join positions. We have also shown that the rdfs:seeAlso extension offers little in terms of results, but occasionally introduces significant runtime costs. We also showed that owl:sameAs extensions can occasionally increase the number of results found by a great deal, but also comes at significant costs and introduces unstable behaviour when run live over domains such as DBpedia. Similarly, we showed that RDFS reasoning extensions increase results more frequently than owl:sameAs extensions (e.g., in lower percentiles of the QWalk experiments), but exhibits more moderate increases than the latter extensions (e.g., in the 100th percentiles of QWalk experiments). Through the FedBench experiments, we also showed that the dynamic import of RDFS data at runtime works well for simple queries on certain domains (e.g., data.semanticweb.org), but can introduce instability for domains such as DBpedia, where schemata are spread across multiple documents and link to other domains with similar decentralised schema.

Future directions  The combination of reasoning and LTBQE has shown the potential to find additional answers, and at a higher rate than without reasoning, but with the potential to make query-answering unstable. At the moment we focus on very lightweight reasoning, supporting an important subset of the semantics inherent in published Linked Data. Extending the inference rules to support a broader selection of OWL features—based on the observations of use by Glimm et al. [24]—would obviously help to find more answers. However, even for our lightweight reasoning, we already encounter practical problems. In particular, we showed that following owl:sameAs links caused problems for some queries that in baseline setups already involve many sources from the DBpedia domain, which offers a high density of owl:sameAs links from its local data. Furthermore, we noted that the dynamic import of RDFS data increased the complexity of remote access at runtime (esp. for DBpedia) and thus caused instability and inflated response times for more complex queries. Thus, we proposed to use static schema data where we assume that such data are infrequently updated. A better alternative—one that we did not investigate—is the use of lazy schema caching in combination with active refresh policies. We believe caching schema data would work well since a few (meta-)vocabularies (such as RDF, RDFS, OWL, FOAF, DC, DCTERMS, etc.) are used extremely frequently—something similar to a power-law driven by preferential attachment—and are generally quite static. Again, caching has obvious benefits for LTBQE in general (not just for schema), but herein we rather focus on query-at-a-time evaluation.

In general, due to various fundamental (e.g., no support for OPTIONAL, etc.) and practical issues (reliance on dereferenceability, assumptions that query-patterns connect relevant sources through dereferenceable URIs, slow access to remote sources, varying stablity of remote hosts) LTBQE cannot be considered a complete solution for running complex SPARQL queries over Linked Data: SPARQL is simply too complex a query language to be supported in its entirety and in a practical fashion by LTBQE. As such, one may consider a different language for navigational queries, along the lines of proposals by Fionda et al. [23]. In general, a query language that would allow for declaratively specifying navigational aspects of query execution—e.g., stick to the data.semanticweb.org domain, follow foaf:knows links, do not follow foaf:homepage links, etc.—would be interesting, and would allow users to better guide the query-engine than using a simple SPARQL query.

Taking an alternative view, although not a solution for SPARQL, LTBQE is an interesting technique for SPARQL and is complementary to other techniques for querying Linked Data, such as materialised or federated approaches. LTBQE offers the potential to get fresh answers when dynamic information is involved, or to get sensitive data when user-specific access-control is in place for some Linked Data source; this is not possible through centralised approaches. Furthermore, it does not rely on SPARQL interfaces like federated approaches; also, there are currently no mechanisms to discover endpoints in the same manner that LTBQE discovers sources. As such, the greatest potential for LTBQE is in combination with other querying techniques, for example to dynamically freshen-up results returned by a centralised SPARQL endpoint that replicates remote content. We have already begun to investigate this use of LTBQE—as a wrapper for the public LOD Cache and Sindice SPARQL endpoints–such that query patterns involving dynamic data are delegated to LTBQE rather than to replicated indexes, which are likely to be stale [66]. In such scenarios, LTBQE is required to deal with simple sub-queries, which we have shown to be feasible in this paper.

As the Web of Data continues to expand and diversify, and as it becomes more dynamic, new querying techniques will be required to keep up with its developments. Though various Web search engines have shown the power and potential of centralisation, even the preeminent Google machinery struggles to give up-to-date answers over dynamic sources. Linked Data presents new opportunities in this regard: URI names appearing in queries also correspond to addresses from which up-to-date data can be found. Although centralised approaches will always be relevant—a point of view which this paper partly confirms—exploring and combining complementary Linked Data querying techniques is an important area of research if we are to meet future challenges. In this paper, we have studied the realistic strengths and weaknesses of the LTBQE approach and various extensions. Next steps are to further explore how it can be combined with centralised query engines in an effective manner to freshen up answers over dynamic data, or to find answers from data-sources outside of the coverage of cached data.

Links  Our source code and queries are available at http://code.google.com/p/lidaq/wiki/Lidaq.