SPARQL with property paths on the Web

Abstract

Linked Data on the Web represents an immense source of knowledge suitable to be automatically processed and queried. In this respect, there are different approaches for Linked Data querying that differ on the degree of centralization adopted. On one hand, the SPARQL query language, originally defined for querying single datasets, has been enhanced with features to query federations of datasets; however, this attempt is not sufficient to cope with the distributed nature of data sources available as Linked Data. On the other hand, extensions or variations of SPARQL aim to find trade-offs between centralized and fully distributed querying. The idea is to partially move the computational load from the servers to the clients. Despite the variety and the relative merits of these approaches, as of today, there is no standard language for querying Linked Data on the Web. A specific requirement for such a language to capture the distributed, graph-like nature of Linked Data sources on the Web is a support of graph navigation. Recently, SPARQL has been extended with a navigational feature called property paths (PPs). However, the semantics of SPARQL restricts the scope of navigation via PPs to single RDF graphs. This restriction limits the applicability of PPs for querying distributed Linked Data sources on the Web. To fill this gap, in this paper we provide formal foundations for evaluating PPs on the Web, thus contributing to the definition of a query language for Linked Data. We first introduce a family of reachability-based query semantics for PPs that distinguish between navigation on the Web and navigation at the data level. Thereafter, we consider another, alternative query semantics that couples Web graph navigation and data level navigation; we call it context-based semantics. Given these semantics, we find that for some PP-based SPARQL queries a complete evaluation on the Web is not possible. To study this phenomenon we introduce a notion of Web-safeness of queries, and prove a decidable syntactic property that enables systems to identify queries that are Web-safe. In addition to establishing these formal foundations, we conducted an experimental comparison of the context-based semantics and a reachability-based semantics. Our experiments show that when evaluating a PP-based query under the context-based semantics one experiences a significantly smaller number of dereferencing operations, but the computed query result may contain less solutions.

1. Introduction

The increasing trend in sharing and interlinking pieces of structured data on the World Wide Web (WWW) is evolving the classical Web – which is focused on hypertext documents and syntactic links among them – into a Web of Linked Data. The Linked Data principles [5] present an approach to extend the scope of Uniform Resource Identifiers (URIs) to new types of resources (e.g., people, places) and represent their descriptions and interlinks by using the Resource Description Framework (RDF) [8] as standard data format. RDF adopts a graph-based data model, which can be queried by using the SPARQL query language [15]. When it comes to Linked Data on the WWW, the common way to provide query-based access is via SPARQL endpoints; that is, services that usually answer SPARQL queries over a single dataset. Recently, the original core of SPARQL has been extended with features supporting query federation; it is now possible, within a single query, to target multiple endpoints (via the SERVICE operator). However, such an extension is not enough to cope with an unbounded and a priori unknown space of data sources such as the WWW. Moreover, not all Linked Data on the WWW is accessible via SPARQL endpoints. More recent proposals are based on the idea of Linked Data Fragments [39,40] and aim at moving part of the computational load from Web servers to clients.

However, as of today, there exists no standard query language for Linked Data on the WWW, although SPARQL is clearly a candidate. A key feature that such a language should provide is navigation across the unbound, a priori unknown, graph-like environment represented by distributed Linked Data sources.

While earlier research on using SPARQL for Linked Data is limited to fragments of the first version of the language [6,16,18,38], the version 1.1 of SPARQL introduces a feature called property paths (PPs) that equips the language with navigational capabilities [15]. However, the standard definition of PPs is limited to single RDF graphs and, thus, not directly applicable to Linked Data that is distributed over the WWW.

Therefore, toward the definition of a language for accessing Linked Data live on the WWW, the following questions emerge naturally:

How can PPs be defined over the WWW?

and

What are the implications of such a definition?

Answering these questions is the broad objective of this paper. In particular, we focus on Linked Data on the WWW, by which we mean RDF data that is made available on the WWW as per the Linked Data principles [5] and, thus, can be accessed by looking up HTTP scheme based URIs. In this context we make the following main contributions:

1. We formalize a family of reachability-based query semantics of PP-based SPARQL queries that are meant to be evaluated over Linked Data on the WWW. This formalization approach treats navigation on the Web separate from navigation on the level of data.

2. We also formalize an alternative, context-based query semantics that intertwines Web graph navigation and data level navigation.

3. We study the feasibility of evaluating queries under these semantics. For this study we assume that query engines do not have complete information about the queried Web of Linked Data (as it is the case for the WWW). Our study shows that query evaluation under any reachability-based semantics is possible in practice and that a similarly general statement cannot be made for the context-based semantics; that is, there exist cases in which query evaluation under the context-based semantics is not possible.

4. We establish a decidable syntactic property of queries for which an evaluation under the context-based semantics is possible.

5. We provide an experimental comparison of the context-based and a reachability-based semantics. For this comparison we executed queries directly over the WWW. As its main result, our experiment shows that when evaluating a PP-based query under the context-based semantics, one experiences a significantly smaller number of dereferencing operations, but the computed query result may contain less solutions.

This article extends a preliminary version that appeared in the proceedings of the ESWC 2015 conference [21]. The extension includes: (i) the definition and analysis of a family of reachability-based query semantics for Property Paths on the Web; (ii) an experimental analysis and comparison of the different semantics; (iii) a more detailed description of the main technical results; (iv) further examples to better clarify the terminology and the main concepts of the paper; (v) a more comprehensive discussion of related work.

The paper is organized as follows. Section 2 provides an overview on related work. In Section 3 we introduce the formal framework for this paper, including a data model that captures the notion of Linked Data on the WWW. Section 4 focuses on PPs, isolated from other SPARQL operators. In Section 5 we broaden our view to define PP-based SPARQL graph patterns. In Section 6 we characterize a class of Web-safe patterns and prove their feasibility. Section 7 discusses the experimental evaluation. Finally, in Section 8 we conclude.

2. Related work

There is an extensive body of research on the foundations of querying RDF data. An important work in this context is the investigation of SPARQL provided by Peréz et al. [30]. Other authors focused on the foundations of SPARQL query optimization [26,34].

From the perspective of graphs, languages for the navigation and specification of vertices in graphs have a long tradition (see Wood’s survey [41]). For RDF, extensions of SPARQL such as PSPARQL [2], nSPARQL [31], and SPARQLeR [23] introduced navigational features since those were missing in the first version of SPARQL. Only recently, with the addition of property paths (PPs) in version 1.1 [15], SPARQL has been enhanced officially with such features. The final definition of PPs has been influenced by research that studied the computational complexity of an early draft version of PPs [3,27]. There also already exists a proposal to extend the expressive power of PPs [11]. Other strands of research focus on studying properties of PPs such as containment [25] or supporting recursion in SPARQL [32]. However, the main assumption of all these navigational extensions of SPARQL is to work on a single, centralized RDF graph.

The idea of querying the WWW as a database is not new (see Florescu et al.’s survey [13]). Perhaps the most notable early works in this context are by Konopnicki and Shmueli [24], Abiteboul and Vianu [1], and Mendelzon et al. [28], all of which tackled the problem of evaluating SQL-like queries on the hypertext Web. While such queries included navigational features, the focus was on retrieving specific Web pages, particular attributes of specific pages, or content within them.

Our departure point is different: We aim at defining semantics of SPARQL queries (including property paths) over Linked Data on the WWW; this involves dealing with two graphs of different type; namely, an RDF graph that is distributed over an unbounded number of documents on the WWW and the Web graph in which these documents are interlinked with each other.

To express queries over Linked Data on the WWW, two main strands of research can be identified. The first studies how to extend the scope of SPARQL queries to the WWW, with existing work focusing on basic graph patterns [6,16,38] or a more expressive fragment that includes AND, OPT, UNION and FILTER [18]. The second strand of research focuses on emphasizing navigational features, which resulted in new languages such as NautiLOD [10,12], LDPath [33], and LDQL [20].

These two strands have different departure points. The former employs navigation over the WWW to collect data for answering a given SPARQL query; here navigation is a means to discover query-relevant data. The latter provides explicit navigational features and uses querying capabilities to filter data sources of interest; here navigation (not querying) is the main focus. The context-based query semantics proposed in this paper combines both approaches.

Another line of research slightly related to our proposal is that of focused crawling. The idea is to enhance the behavior of classical Web crawlers, that consider all pages reachable from a given page, to be more selective; selectivity is obtained by considering e.g., a set of predefined topics [36] or meta data within HTML pages [29]. A more recent line of related research looks into building (domain-specific) knowledge graphs by exploiting semantic technologies to reconcile the data continuously crawled from diverse sources [35]. In a way, these approaches mimic the process of filtering performed by our approach but on a less expressive scale due to the limited expressiveness of the filtering mechanism as compared to our language. Nevertheless, our approach could be used to enable a finer-grained information filtering.

3. Formal framework

This section provides a formal framework for defining semantics of PPs over Linked Data. In particular, we first recall the definition of PPs as per the SPARQL standard [15]. Thereafter, we introduce a data model that captures the notion of Linked Data on the WWW.

3.1. Preliminaries

We assume four pairwise disjoint, countably infinite sets $\mathcal{I}$ (IRIs), $\mathcal{B}$ (blank nodes), $\mathcal{L}$ (literals), and $\mathcal{V}$ (variables, denoted by a leading ‘?’ symbol). An RDF triple (or simply triple) is a tuple from the set $\mathcal{T}=\mathrm{(}\mathcal{I}\cup \mathcal{B}\mathrm{)}\times \mathcal{I}\times \mathrm{(}\mathcal{I}\cup \mathcal{B}\cup \mathcal{L}\mathrm{)}$ . For any such triple $\mathit{t}=⟨\mathit{s}\mathrm{,}\mathit{p}\mathrm{,}\mathit{o}⟩$ we call s the subject, p the predicate, and o the object, and we write $\mathrm{iris}\mathrm{(}\mathit{t}\mathrm{)}$ to denote the set of all IRIs in the triple; i.e., $\mathrm{iris}\mathrm{(}\mathit{t}\mathrm{)}=\{\mathit{s}\mathrm{,}\mathit{p}\mathrm{,}\mathit{o}\}\cap \mathcal{I}$ . A set of triples is called an RDF graph.

A property path pattern (or PP pattern for short) is a tuple $\mathit{P}=⟨\mathit{\alpha }\mathrm{,}\mathtt{\text{path}}\mathrm{,}\mathit{\beta }⟩$ with $\mathit{\alpha }\in \mathrm{(}\mathcal{I}\cup \mathcal{L}\cup \mathcal{V}\mathrm{)}$ , $\mathit{\beta }\in \mathrm{(}\mathcal{I}\cup \mathcal{L}\cup \mathcal{V}\mathrm{)}$ , and $\mathtt{\text{path}}$ is a property path expression (PP expression) that is defined by the following grammar (where $\mathit{u}\mathrm{,}{\mathit{u}}_1\mathrm{,}\dots \mathrm{,}{\mathit{u}}_{\mathit{n}}\in \mathcal{I}$ ): $$\begin{array}{ll}\hfill \mathtt{\text{path}}=& \mathit{u}|!\mathrm{(}{\mathit{u}}_1|\dots |{\mathit{u}}_{\mathit{n}}\mathrm{)}|\mathtt{\text{path}}\mathrm{/}\mathtt{\text{path}}|\\ \hfill & \mathrm{(}\mathtt{\text{path}}|\mathtt{\text{path}}\mathrm{)}|{\mathrm{(}\mathtt{\text{path}}\mathrm{)}}^{\ast }|{}^{\wedge }\mathtt{\text{path}}\end{array}$$

Fig. 1.

SPARQL algebra operators over multisets of solution mappings, ${\mathit{M}}_1=⟨{\mathrm{\Omega }}_1\mathrm{,}{\mathit{card}}_1⟩$ and ${\mathit{M}}_2=⟨{\mathrm{\Omega }}_2\mathrm{,}{\mathit{card}}_2⟩$ .

As can be seen from this grammar, we have two base cases for PP expressions, namely, arbitrary IRIs and expressions of the form $!\mathrm{(}{\mathit{u}}_1|\dots |{\mathit{u}}_{\mathit{n}}\mathrm{)}$ . PP patterns based on the former are ordinary triple patterns, which, in the context of PPs, represent single navigation steps from the subject to the object of any triple whose predicate is the given IRI. The second base case captures a form of negation that represents a navigation step along any triple whose predicate is not among the IRIs listed. Given these base types of PP expressions, users may combine them via the classical regular expression operators: concatenation /, disjunction |, and recursive concatenation  ${\mathrm{(}·\mathrm{)}}^{\ast }$ ; additionally, ${}^{\wedge }\mathtt{\text{path}}$ represents the inverse of $\mathtt{\text{path}}$ (a formal semantics of PP patterns and PP expressions follows shortly).

The SPARQL standard introduces additional types of PP expressions [15]. Since these are merely syntactic sugar (they are defined in terms of expressions covered by the grammar given above), we ignore them in this paper. As another slight deviation from the standard, we do not permit blank nodes in PP patterns (i.e., $\mathit{\alpha }\mathrm{,}\mathit{\beta }\notin \mathcal{B}$ ). However, standard PP patterns with blank nodes can be simulated using fresh variables.

Example 1.

As an example of a PP pattern consider $⟨\mathsf{\text{Tim}}\mathrm{,}{\mathrm{(}\mathsf{\text{knows}}\mathrm{)}}^{\ast }\mathrm{/}\mathsf{\text{name}}\mathrm{,}?\mathit{n}⟩$ where $?\mathit{n}\in \mathcal{V}$ and $\mathsf{\text{Tim}}\mathrm{,}\mathsf{\text{knows}}\mathrm{,}\mathsf{\text{name}}\in \mathcal{I}$ . This pattern retrieves the names of persons that can be reached from $\mathsf{\text{Tim}}$ by an arbitrarily long path of $\mathsf{\text{knows}}$ relationships (which includes $\mathsf{\text{Tim}}$ ). Another example are the two PP patterns $⟨?\mathit{p}\mathrm{,}\mathsf{\text{knows}}\mathrm{,}\mathsf{\text{Tim}}⟩$ and $⟨\mathsf{\text{Tim}}\mathrm{,}{}^{\wedge }\mathsf{\text{knows}}\mathrm{,}?\mathit{p}⟩$ , both of which retrieve persons that know $\mathsf{\text{Tim}}$ . For further examples we refer to the SPARQL specification [15, Section 9.2].

In addition to a syntax for the queries of interest, we have to introduce the standard semantics of these queries. The SPARQL specification defines this semantics by an evaluation function (see below) that returns multisets of so called solution mappings; such a mapping is a partial function $\mathit{\mu }:\mathcal{V}\to \mathrm{(}\mathcal{I}\cup \mathcal{B}\cup \mathcal{L}\mathrm{)}$ .

To refer to the domain of a solution mapping μ (i.e., the set of variables for which μ is defined) we write $\mathrm{dom}\mathrm{(}\mathit{\mu }\mathrm{)}$ . If, for two solution mappings, say ${\mathit{\mu }}_1$ and ${\mathit{\mu }}_2$ , we have ${\mathit{\mu }}_1\mathrm{(}?\mathit{v}\mathrm{)}={\mathit{\mu }}_2\mathrm{(}?\mathit{v}\mathrm{)}$ for every variable $?\mathit{v}\in \mathrm{(}\mathrm{dom}\mathrm{(}{\mathit{\mu }}_1\mathrm{)}\cap \mathrm{dom}\mathrm{(}{\mathit{\mu }}_2\mathrm{)}\mathrm{)}$ , then we say that ${\mathit{\mu }}_1$ and ${\mathit{\mu }}_2$ are compatible ( ${\mathit{\mu }}_1\sim {\mathit{\mu }}_2$ ). In this case, ${\mathit{\mu }}_1$ and ${\mathit{\mu }}_2$ can be combined into a solution mapping $\mathit{\mu }={\mathit{\mu }}_1\cup {\mathit{\mu }}_2$ such that $\mathrm{dom}\mathrm{(}\mathit{\mu }\mathrm{)}=\mathrm{(}\mathrm{dom}\mathrm{(}{\mathit{\mu }}_1\mathrm{)}\cup \mathrm{dom}\mathrm{(}{\mathit{\mu }}_2\mathrm{)}\mathrm{)}$ , $\mathit{\mu }\sim {\mathit{\mu }}_1$ , and $\mathit{\mu }\sim {\mathit{\mu }}_2$ . Given a solution mapping μ and a PP pattern P, we write $\mathit{\mu }[\mathit{P}]$ to denote the PP pattern obtained by replacing the variables in P according to μ (where variables for which μ is not defined are not replaced).

We represent a multiset of solution mappings by a pair $\mathit{M}=⟨\mathrm{\Omega }\mathrm{,}\mathit{card}⟩$ where Ω is the underlying set (of solution mappings) and $\mathit{card}$ is the corresponding cardinality function; i.e., $\mathit{card}:\mathrm{\Omega }\to \{1\mathrm{,}2\mathrm{,}\dots \}$ . By abusing notation slightly, we write $\mathit{\mu }\in \mathit{M}$ for every $\mathit{\mu }\in \mathrm{\Omega }$ . Furthermore, to simplify the following definitions we introduce a family of special, parameterized cardinality functions for multisets in which every solution mapping has a cardinality of 1. That is, for any set of solution mappings Ω, let ${\mathsf{card}\mathsf{1}}^{\mathrm{(}\mathrm{\Omega }\mathrm{)}}:\mathrm{\Omega }\to \{1\mathrm{,}2\mathrm{,}\dots \}$ be the constant-1 cardinality function that is defined by ${\mathsf{card}\mathsf{1}}^{\mathrm{(}\mathrm{\Omega }\mathrm{)}}\mathrm{(}\mathit{\mu }\mathrm{)}=1$ for all $\mathit{\mu }\in \mathrm{\Omega }$ .

To define the aforementioned evaluation function we also need to introduce several operators of the SPARQL algebra, which is defined over multisets of solution mappings. That is, for two such multisets, ${\mathit{M}}_1=⟨{\mathrm{\Omega }}_1\mathrm{,}{\mathit{card}}_1⟩$ and ${\mathit{M}}_2=⟨{\mathrm{\Omega }}_2\mathrm{,}{\mathit{card}}_2⟩$ , we define the join (⋈), the difference (∖), the multiset union (⊔), and projection ( ${\mathit{\pi }}_{\mathit{V}}$ , where $\mathit{V}\subseteq \mathcal{V}$ is a finite set of variables) as given in Fig. 1. In addition to these algebra operators, the SPARQL standard introduces auxiliary functions to define the semantics of PP patterns of the form $⟨\mathit{\alpha }\mathrm{,}{\mathtt{\text{path}}}^{\ast }\mathrm{,}\mathit{\beta }⟩$ . Figure 2 provides these functions – which we call $\mathtt{ALP}\mathtt{1}$ and $\mathtt{ALP}\mathtt{2}$ – adapted to our formalism (we need a variable $?\mathit{x}$ in line 6 since PP patterns in our formalism do not have blank nodes).

Fig. 2.

Auxiliary functions used for defining the semantics of PP expressions of the form ${\mathtt{\text{path}}}^{\ast }$ .

Fig. 3.

Standard query semantics of SPARQL Property Paths, where $\mathit{\alpha }\mathrm{,}\mathit{\beta }\in \mathrm{(}\mathcal{I}\cup \mathcal{L}\cup \mathcal{V}\mathrm{)}$ ; $\mathit{u}\mathrm{,}{\mathit{u}}_1\mathrm{,}\dots \mathrm{,}{\mathit{u}}_{\mathit{n}}\in \mathcal{I}$ ; ${\mathit{x}}_{\mathrm{L}}\mathrm{,}{\mathit{x}}_{\mathrm{R}}\in \mathrm{(}\mathcal{I}\cup \mathcal{L}\mathrm{)}$ ; $?{\mathit{v}}_{\mathrm{L}}\mathrm{,}?{\mathit{v}}_{\mathrm{R}}\in \mathcal{V}$ ; $?\mathit{v}\in \mathcal{V}$ is a fresh variable; and ${\mathit{\mu }}_{\varnothing }$ is the empty solution mapping with $\mathrm{dom}\mathrm{(}{\mathit{\mu }}_{\varnothing }\mathrm{)}=\varnothing$ .

We are now ready to define the evaluation function that formalizes the standard semantics of PP patterns.

Definition 2.

Let P be a PP pattern and let G be an RDF graph. The evaluation of P over G, denoted by ${[[\mathit{P}]]}_{\mathit{G}}$ , is a multiset of solution mappings $⟨\mathrm{\Omega }\mathrm{,}\mathit{card}⟩$ that is defined recursively as given in Fig. 3.

Example 3.

Consider the following RDF graph: $$\begin{array}{ll}\hfill {\mathit{G}}_{\mathsf{ex}}=\{& ⟨\mathsf{\text{Suzi}}\mathrm{,}\mathsf{\text{knows}}\mathrm{,}\mathsf{\text{Eve}}⟩\mathrm{,}⟨\mathsf{\text{Eve}}\mathrm{,}\mathsf{\text{knows}}\mathrm{,}\mathsf{\text{Charlie}}⟩\mathrm{,}\\ \hfill & ⟨\mathsf{\text{Suzi}}\mathrm{,}\mathsf{\text{knows}}\mathrm{,}\mathsf{\text{Alice}}⟩\mathrm{,}⟨\mathsf{\text{Alice}}\mathrm{,}\mathsf{\text{knows}}\mathrm{,}\mathsf{\text{Charlie}}⟩\mathrm{,}\\ \hfill & ⟨\mathsf{\text{Alice}}\mathrm{,}\mathsf{\text{knows}}\mathrm{,}\mathsf{\text{Eve}}⟩\}.\end{array}$$ Then, for the PP pattern ${\mathit{P}}_{\mathit{a}}=⟨\mathsf{\text{Suzi}}\mathrm{,}\mathsf{\text{knows}}\mathrm{/}\mathsf{\text{knows}}\mathrm{,}?\mathit{x}⟩$ we have ${[[{\mathit{P}}_{\mathit{a}}]]}_{{\mathit{G}}_{\mathsf{ex}}}=⟨{\mathrm{\Omega }}_{\mathit{a}}\mathrm{,}{\mathit{card}}_{\mathit{a}}⟩$ with ${\mathrm{\Omega }}_{\mathit{a}}=\{{\mathit{\mu }}_{\mathit{a}1}\mathrm{,}{\mathit{\mu }}_{\mathit{a}2}\}$ , $$\begin{array}{ll}\hfill {\mathit{\mu }}_{\mathit{a}1}\mathrm{(}?\mathit{x}\mathrm{)}& =\mathsf{\text{Charlie}}\text{where }{\mathit{card}}_{\mathit{a}}\mathrm{(}{\mathit{\mu }}_{\mathit{a}1}\mathrm{)}=2\mathrm{,}\text{and}\\ \hfill {\mathit{\mu }}_{\mathit{a}2}\mathrm{(}?\mathit{x}\mathrm{)}& =\mathsf{\text{Eve}}\text{where }{\mathit{card}}_{\mathit{a}}\mathrm{(}{\mathit{\mu }}_{\mathit{a}2}\mathrm{)}=1.\end{array}$$ Note that the result contains the solution mapping ${\mathit{\mu }}_{\mathit{a}1}$ twice because $\mathsf{\text{Charlie}}$ can be reached from $\mathsf{\text{Suzi}}$ by two different paths that match the PP expression $\mathsf{\text{knows}}\mathrm{/}\mathsf{\text{knows}}$ (namely, one via $\mathsf{\text{Eve}}$ , the other via $\mathsf{\text{Alice}}$ ).

Example 4.

As another example, consider PP pattern ${\mathit{P}}_{\mathit{b}}=⟨\mathsf{\text{Suzi}}\mathrm{,}{\mathrm{(}\mathsf{\text{knows}}\mathrm{)}}^{\ast }\mathrm{,}?\mathit{x}⟩$ , for which we have: $$\begin{array}{ll}\hfill {[[{\mathit{P}}_{\mathit{b}}]]}_{{\mathit{G}}_{\mathsf{ex}}}& =⟨\{{\mathit{\mu }}_{\mathit{b}1}\mathrm{,}{\mathit{\mu }}_{\mathit{b}2}\mathrm{,}{\mathit{\mu }}_{\mathit{b}3}\mathrm{,}{\mathit{\mu }}_{\mathit{b}4}\}\mathrm{,}{\mathit{card}}_{\mathit{b}}⟩\mathrm{,}\text{where}\\ \hfill {\mathit{\mu }}_{\mathit{b}1}\mathrm{(}?\mathit{x}\mathrm{)}& =\mathsf{\text{Suzi}}\mathrm{,}{\mathit{\mu }}_{\mathit{b}2}\mathrm{(}?\mathit{x}\mathrm{)}=\mathsf{\text{Eve}}\mathrm{,}\\ \hfill {\mathit{\mu }}_{\mathit{b}3}\mathrm{(}?\mathit{x}\mathrm{)}& =\mathsf{\text{Alice}}\mathrm{,}{\mathit{\mu }}_{\mathit{b}4}\mathrm{(}?\mathit{x}\mathrm{)}=\mathsf{\text{Charlie}}\mathrm{,}\end{array}$$ and ${\mathit{card}}_{\mathit{b}}\mathrm{(}{\mathit{\mu }}_{\mathit{b}\mathit{i}}\mathrm{)}=1$ for all $\mathit{i}\in \{1\mathrm{,}2\mathrm{,}3\mathrm{,}4\}$ . The latter may be surprising at first. However, for the PP pattern ${\mathit{P}}_{\mathit{b}}$ , as for every PP pattern whose PP expression is of the form ${\mathrm{(}\mathtt{\text{path}}\mathrm{)}}^{\ast }$ , the SPARQL specification digresses from the standard bag semantics of other PP patterns to an existential semantics where every solution mapping is counted only once, even if there exist multiple matching paths with the same target node (the procedural definition represented by function $\mathtt{ALP}\mathtt{2}$ achieves this effect by ignoring already visited elements; cf. line 4 in Fig. 2).

Fig. 4.

The link graph of our example Web of Linked Data  ${\mathit{W}}_{\mathsf{ex}}$ (self-edges are omitted).

3.2. Data model

The standard query semantics of PP patterns – as introduced in the SPARQL specification and presented in the previous section – defines the result expected from evaluating such a pattern over a (single) RDF graph. Since the WWW is not an RDF graph, this standard definition is insufficient as a formal foundation for evaluating PP patterns over Linked Data on the WWW. As a basis for providing a suitable definition we need a data model that captures the notion of a Web of Linked Data. To this end, we adopt the data model introduced in our earlier work [18].

For this model we assume an infinite set $\mathcal{D}$ that is disjoint from the aforementioned sets $\mathcal{I}$ (IRIs), $\mathcal{B}$ (blank nodes), $\mathcal{L}$ (literals), and $\mathcal{V}$ (variables). Elements in this set $\mathcal{D}$ represent the concept of Web documents from which Linked Data can be extracted; hereafter, we call each $\mathit{d}\in \mathcal{D}$ a Linked Data document, or document for short. Moreover, we assume a function $\mathit{data}:\mathcal{D}\to 2^{\mathcal{T}}$ that maps every document  $\mathit{d}\in \mathcal{D}$ to a finite set of triples $\mathit{data}\mathrm{(}\mathit{d}\mathrm{)}\subseteq \mathcal{T}$ . As prescribed by the RDF data model [8], we require that the triples of each document use a unique set of blank nodes; i.e., for any pair of distinct documents  $\mathit{d}\mathrm{,}{\mathit{d}}^{\prime }\in \mathcal{D}$ , there does not exist two triples $\mathit{t}=⟨\mathit{s}\mathrm{,}\mathit{p}\mathrm{,}\mathit{o}⟩$ and ${\mathit{t}}^{\prime }=⟨{\mathit{s}}^{\prime }\mathrm{,}{\mathit{p}}^{\prime }\mathrm{,}{\mathit{o}}^{\prime }⟩$ such that $\mathit{t}\in \mathit{data}\mathrm{(}\mathit{d}\mathrm{)}$ , ${\mathit{t}}^{\prime }\in \mathit{data}\mathrm{(}{\mathit{d}}^{\prime }\mathrm{)}$ , and $\{\mathit{s}\mathrm{,}\mathit{p}\mathrm{,}\mathit{o}\}\cap \{{\mathit{s}}^{\prime }\mathrm{,}{\mathit{p}}^{\prime }\mathrm{,}{\mathit{o}}^{\prime }\}\cap \mathcal{B}\ne \varnothing$ . Given these preliminaries, we define a Web of Linked Data as follows.

Definition 5.

Assume a special symbol ⊥ such that $\perp \notin \mathrm{(}\mathcal{D}\cup \mathcal{I}\cup \mathcal{B}\cup \mathcal{L}\cup \mathcal{V}\mathrm{)}$ . A Web of Linked Data is a tuple  $\mathit{W}=⟨\mathit{D}\mathrm{,}\mathit{adoc}⟩$ with the following two elements:

$\mathit{D}\subseteq \mathcal{D}$ is a set of documents; and

$\mathit{adoc}$ is a function that maps every IRI $\mathit{u}\in \mathcal{I}$ either to a document in D or to the symbol ⊥ (i.e., $\mathit{adoc}:\mathcal{I}\to \mathit{D}\cup \{\perp \}$ ) such that for every $\mathit{d}\in \mathit{D}$ , there exists an IRI $\mathit{u}\in \mathcal{I}$ with $\mathit{adoc}\mathrm{(}\mathit{u}\mathrm{)}=\mathit{d}$ .

Observe that the function $\mathit{adoc}$ captures the concept of obtaining documents by looking up (HTTP) IRIs on the WWW (also referred to as dereferencing). IRIs that cannot be looked up, or whose look up does not result in retrieving a document (even after following HTTP-based redirection pointers) are mapped to the special symbol ⊥. In this paper we assume that in any Web of Linked Data  $\mathit{W}=⟨\mathit{D}\mathrm{,}\mathit{adoc}⟩$ the set of documents D is finite, in which case we say W is finite (for a discussion of infiniteness refer to our earlier work [18]).

For the subsequent discussion we introduce a few additional concepts: Given a Web of Linked Data  $\mathit{W}=⟨\mathit{D}\mathrm{,}\mathit{adoc}⟩$ , we write ${\mathrm{dom}}^{\perp ̸}\mathrm{(}\mathit{adoc}\mathrm{)}$ to denote the set of IRIs that function $\mathit{adoc}$ maps to a document; i.e., ${\mathrm{dom}}^{\perp ̸}\mathrm{(}\mathit{adoc}\mathrm{)}=\{\mathit{u}\in \mathcal{I}|\mathit{adoc}\mathrm{(}\mathit{u}\mathrm{)}\ne \perp \}$ (hence, this set corresponds to what is also referred to as “dereferencable IRIs”). Moreover, for any two documents $\mathit{d}\mathrm{,}{\mathit{d}}^{\prime }\in \mathit{D}$ in W, we say that document d has a data link to ${\mathit{d}}^{\prime }$ if there exists some triple $\mathit{t}=⟨\mathit{s}\mathrm{,}\mathit{p}\mathrm{,}\mathit{o}⟩$ in the data of d (i.e., $\mathit{t}\in \mathit{data}\mathrm{(}\mathit{d}\mathrm{)}$ ) such that t contains an IRI that can be used to obtain  ${\mathit{d}}^{\prime }$ , i.e., $\mathit{adoc}\mathrm{(}\mathit{u}\mathrm{)}={\mathit{d}}^{\prime }$ for some $\mathit{u}\in \{\mathit{s}\mathrm{,}\mathit{p}\mathrm{,}\mathit{o}\}$ . Such data links establish the link graph of the Web of Linked Data W, that is, a directed graph $⟨\mathit{D}\mathrm{,}\mathit{E}⟩$ in which the edges E are all pairs $⟨\mathit{d}\mathrm{,}{\mathit{d}}^{\prime }⟩\in \mathit{D}\times \mathit{D}$ for which d has a data link to  ${\mathit{d}}^{\prime }$ . We emphasize that the link graph of W is a different type of graph than the RDF “graph” whose triples are distributed over the documents in W.

Example 6.

As a running example for the remainder of this paper, we assume a small Web of Linked Data  ${\mathit{W}}_{\mathsf{ex}}=⟨{\mathit{D}}_{\mathsf{ex}}\mathrm{,}{\mathit{adoc}}_{\mathsf{ex}}⟩$ consisting of seven documents, ${\mathit{D}}_{\mathsf{ex}}=\{{\mathit{d}}_{\mathsf{A}}\mathrm{,}{\mathit{d}}_{\mathsf{B}}\mathrm{,}{\mathit{d}}_{\mathsf{C}}\mathrm{,}{\mathit{d}}_{\mathsf{D}}\mathrm{,}{\mathit{d}}_{\mathsf{E}}\mathrm{,}{\mathit{d}}_{\mathsf{S}}\mathrm{,}{\mathit{d}}_{\mathsf{P}}\}$ , with data that describes a project, denoted by IRI $\mathsf{\text{PrjX}}\in \mathcal{I}$ , and people, denoted by $\mathsf{\text{Alice}}\mathrm{,}\mathsf{\text{Bob}}\mathrm{,}\mathsf{\text{Charlie}}\mathrm{,}\mathsf{\text{Dody}}\mathrm{,}\mathsf{\text{Eve}}\mathrm{,}\mathsf{\text{Suzi}}\in \mathcal{I}$ . Figure 4 presents this data and illustrates the link graph of ${\mathit{W}}_{\mathsf{ex}}$ , assuming function ${\mathit{adoc}}_{\mathsf{ex}}$ is given as follows: $$\begin{array}{ll}\hfill {\mathit{adoc}}_{\mathsf{ex}}\mathrm{(}\mathsf{\text{Alice}}\mathrm{)}& ={\mathit{d}}_{\mathsf{A}}\mathrm{,}{\mathit{adoc}}_{\mathsf{ex}}\mathrm{(}\mathsf{\text{Eve}}\mathrm{)}={\mathit{d}}_{\mathsf{E}}\mathrm{,}\\ \hfill {\mathit{adoc}}_{\mathsf{ex}}\mathrm{(}\mathsf{\text{Bob}}\mathrm{)}& ={\mathit{d}}_{\mathsf{B}}\mathrm{,}{\mathit{adoc}}_{\mathsf{ex}}\mathrm{(}\mathsf{\text{Suzi}}\mathrm{)}={\mathit{d}}_{\mathsf{S}}\mathrm{,}\\ \hfill {\mathit{adoc}}_{\mathsf{ex}}\mathrm{(}\mathsf{\text{Charlie}}\mathrm{)}& ={\mathit{d}}_{\mathsf{C}}\mathrm{,}{\mathit{adoc}}_{\mathsf{ex}}\mathrm{(}\mathsf{\text{PrjX}}\mathrm{)}={\mathit{d}}_{\mathsf{P}}\mathrm{,}\\ \hfill {\mathit{adoc}}_{\mathsf{ex}}\mathrm{(}\mathsf{\text{Dody}}\mathrm{)}& ={\mathit{d}}_{\mathsf{D}}\mathrm{,}\text{and}{\mathit{adoc}}_{\mathsf{ex}}\mathrm{(}\mathit{u}\mathrm{)}=\perp \\ \hfill & \text{for every other IRI }\mathit{u}.\end{array}$$

We emphasize that the link graph, as well as the two elements D and $\mathit{adoc}$ , typically are not available directly to systems that aim to compute queries over the Web of Linked Data captured by $\mathit{W}=⟨\mathit{D}\mathrm{,}\mathit{adoc}⟩$ . In particular, the set ${\mathrm{dom}}^{\perp ̸}\mathrm{(}\mathit{adoc}\mathrm{)}$ – i.e., all IRIs that can be used to retrieve some document – is unknown to such systems and can only be disclosed partially (by trying to look up IRIs). This inherent lack of complete information about a queried Web of Linked Data has an impact on the feasibility of answering specific types of queries completely as we shall see in Section 6.

We are now ready to formalize query semantics that define PP patterns as queries over a Web of Linked Data (and, thus, over Linked Data on the WWW).

4. Web-aware semantics of property paths

This section introduces three alternative query semantics, each of which defines an expected query result for any PP pattern over any Web of Linked Data.

4.1. Full-web query semantics

As a first approach we may assume a semantics that is based on the standard evaluation function for PP patterns (cf. Definition 2) and defines expected query results in terms of all data in a queried Web of Linked Data. The following definition captures this approach, which we call a “full-Web query semantics” [18].

Definition 7.

Let P be a PP pattern, $\mathit{W}=⟨\mathit{D}\mathrm{,}\mathit{adoc}⟩$ be a Web of Linked Data, and ${\mathit{G}}_{\mathsf{all}}$ be the RDF graph for which it holds that ${\mathit{G}}_{\mathsf{all}}={\bigcup }_{\mathit{d}\in \mathit{D}}\mathit{data}\mathrm{(}\mathit{d}\mathrm{)}$ . The evaluation of P over W under full-Web semantics, denoted by $⟦\mathit{P}{⟧}_{\mathit{W}}^{\mathtt{\text{fw}}}$ , is defined by $⟦\mathit{P}{⟧}_{\mathit{W}}^{\mathtt{\text{fw}}}={[[\mathit{P}]]}_{{\mathit{G}}_{\mathsf{all}}}$ .

Example 8.

Recall our example Web ${\mathit{W}}_{\mathsf{ex}}$ (cf. Example 6 and Fig. 4). The expected result of evaluating PP pattern ${\mathit{P}}_{\mathit{a}}=⟨\mathsf{\text{Suzi}}\mathrm{,}\mathsf{\text{knows}}\mathrm{/}\mathsf{\text{knows}}\mathrm{,}?\mathit{x}⟩$ over ${\mathit{W}}_{\mathsf{ex}}$ under full-Web semantics is the multiset of solution mappings $⟦{\mathit{P}}_{\mathit{a}}{⟧}_{{\mathit{W}}_{\mathsf{ex}}}^{\mathtt{\text{fw}}}=⟨\{{\mathit{\mu }}_{\mathit{a}1}\mathrm{,}{\mathit{\mu }}_{\mathit{a}2}\mathrm{,}{\mathit{\mu }}_{\mathit{a}3}\mathrm{,}{\mathit{\mu }}_{\mathit{a}4}\mathrm{,}{\mathit{\mu }}_{\mathit{a}5}\}\mathrm{,}{\mathit{card}}_{\mathit{a}}^{\mathtt{\text{fw}}}⟩$ for which the following properties hold:

${\mathit{\mu }}_{\mathit{a}1}\mathrm{(}?\mathit{x}\mathrm{)}=\mathsf{\text{Charlie}}$ and ${\mathit{card}}_{\mathit{a}}^{\mathtt{\text{fw}}}\mathrm{(}{\mathit{\mu }}_{\mathit{a}1}\mathrm{)}=1$ (because $\mathsf{\text{Suzi}}$ has a “ $\mathsf{\text{knows}}\mathrm{/}\mathsf{\text{knows}}$ connection” to $\mathsf{\text{Charlie}}$ via $\mathsf{\text{Alice}}$ by using triples from documents  ${\mathit{d}}_{\mathsf{S}}$ and ${\mathit{d}}_{\mathsf{A}}$ );

${\mathit{\mu }}_{\mathit{a}2}\mathrm{(}?\mathit{x}\mathrm{)}=\mathsf{\text{Eve}}$ and ${\mathit{card}}_{\mathit{a}}^{\mathtt{\text{fw}}}\mathrm{(}{\mathit{\mu }}_{\mathit{a}2}\mathrm{)}=1$ (connection via $\mathsf{\text{Alice}}$ with triples from ${\mathit{d}}_{\mathsf{S}}$ and ${\mathit{d}}_{\mathsf{E}}$ );

${\mathit{\mu }}_{\mathit{a}3}\mathrm{(}?\mathit{x}\mathrm{)}=\mathsf{\text{Alice}}$ and ${\mathit{card}}_{\mathit{a}}^{\mathtt{\text{fw}}}\mathrm{(}{\mathit{\mu }}_{\mathit{a}3}\mathrm{)}=1$ (via $\mathsf{\text{Dody}}$ by using only triples from ${\mathit{d}}_{\mathsf{D}}$ );

${\mathit{\mu }}_{\mathit{a}4}\mathrm{(}?\mathit{x}\mathrm{)}=\mathsf{\text{Suzi}}$ and ${\mathit{card}}_{\mathit{a}}^{\mathtt{\text{fw}}}\mathrm{(}{\mathit{\mu }}_{\mathit{a}4}\mathrm{)}=2$ (connections via $\mathsf{\text{Dody}}$ , see ${\mathit{d}}_{\mathsf{D}}$ , and $\mathsf{\text{Bob}}$ , see ${\mathit{d}}_{\mathsf{B}}$ );

${\mathit{\mu }}_{\mathit{a}5}\mathrm{(}?\mathit{x}\mathrm{)}=\mathsf{\text{Dody}}$ and ${\mathit{card}}_{\mathit{a}}^{\mathtt{\text{fw}}}\mathrm{(}{\mathit{\mu }}_{\mathit{a}5}\mathrm{)}=1$  (via $\mathsf{\text{Bob}}$ ).

We emphasize that the full-Web query semantics is mostly of theoretical interest. In practice, that is, for a Web of Linked Data  ${\mathit{W}}^{\ast }=⟨{\mathit{D}}^{\ast }\mathrm{,}{\mathit{adoc}}^{\ast }⟩$ that represents the “real” WWW (as deployed on the Internet), there cannot exist any system that guarantees to compute the given evaluation function $⟦·{⟧}_{·}^{\mathtt{\text{fw}}}$ over ${\mathit{W}}^{\ast }$ using an algorithm that both terminates and returns complete query results. Our earlier work provides a formal proof of such a limitation of a full-Web query semantics for other types of SPARQL graph patterns, including triple patterns [18]. It is trivial to carry this result over to the full-Web semantics of PP patterns (i.e., Definition 7) because any PP pattern $\mathit{P}=⟨\mathit{\alpha }\mathrm{,}\mathtt{\text{path}}\mathrm{,}\mathit{\beta }⟩$ with PP expression $\mathtt{\text{path}}$ being an IRI $\mathit{u}\in \mathcal{I}$ is a triple pattern $⟨\mathit{\alpha }\mathrm{,}\mathit{u}\mathrm{,}\mathit{\beta }⟩$ . Informally, we explain this negative result by the fact that the two structures ${\mathit{D}}^{\ast }$ and ${\mathit{adoc}}^{\ast }$ that capture the queried Web formally, are not available for the WWW. Consequently, to enumerate the set of all triples in ${\mathit{W}}^{\ast }$  (denoted by ${\mathit{G}}_{\mathsf{all}}$  in Definition 7), a query execution system would have to discover all documents of the set ${\mathit{D}}^{\ast }$ ; given that mapping ${\mathit{adoc}}^{\ast }$ is not available to such a system (in particular, ${\mathrm{dom}}^{\perp ̸}\mathrm{(}{\mathit{adoc}}^{\ast }\mathrm{)}$  – the set of all IRIs whose lookup retrieves a document – is, at best, partially known), the only guarantee to discover all documents is to look up any possible (HTTP) IRI. Since these are infinitely many [9], the enumeration process cannot terminate.

4.2. Reachability-based query semantics

Given the limited practical applicability of the full-Web semantics, our earlier work introduces reachability-based semantics that restrict the scope of queries and expected results to “reachable” documents [18]. In the following, we adapt this idea for PP patterns.

Informally, a set of reachable documents of a Web of Linked Data W contains all the documents that can be reached by traversing recursively a well-defined set of data links in the link graph of W. To specify what data links belong to such a set, we introduce the notion of a reachability criterion [18], which we define formally as a function $\mathit{c}:\mathcal{T}\times \mathcal{I}\times \mathcal{P}\to \{\mathrm{true}\mathrm{,}\mathrm{false}\}$ where $\mathcal{P}$ denotes the infinite set of all PP patterns (and, as introduced before, $\mathcal{T}$ and $\mathcal{I}$ are the sets of all triples and all IRIs, respectively). Then, given such a reachability criterion, we define reachability of documents as follows.

Definition 9.

Let P be a PP pattern, let $\mathit{S}\subseteq \mathcal{I}$ be a finite set of IRIs (which serve as a seed), let c be a reachability criterion, and let $\mathit{W}=⟨\mathit{D}\mathrm{,}\mathit{adoc}⟩$ be a Web of Linked Data. A document $\mathit{d}\in \mathit{D}$ is ( $\mathit{S}\mathrm{,}\mathit{c}\mathrm{,}\mathit{P}$ )-reachable in W if any of the following two conditions holds:

There exists an IRI $\mathit{u}\in \mathit{S}$ such that $\mathit{adoc}\mathrm{(}\mathit{u}\mathrm{)}=\mathit{d}$ (in which case we call d a “seed document”); or

there exist (another) document ${\mathit{d}}^{\prime }\in \mathit{D}$ , a triple t, and an IRI u such that

• ${\mathit{d}}^{\prime }$ is $\mathrm{(}\mathit{S}\mathrm{,}\mathit{c}\mathrm{,}\mathit{P}\mathrm{)}$ -reachable in W,

• $\mathit{t}\in \mathit{data}\mathrm{(}{\mathit{d}}^{\prime }\mathrm{)}$ ,

• $\mathit{u}\in \mathrm{iris}\mathrm{(}\mathit{t}\mathrm{)}$ ,

• $\mathit{c}\mathrm{(}\mathit{t}\mathrm{,}\mathit{u}\mathrm{,}\mathit{P}\mathrm{)}=\mathrm{true}$ , and

• $\mathit{adoc}\mathrm{(}\mathit{u}\mathrm{)}=\mathit{d}$ .

Notice how the second condition restricts the notion of reachability by ignoring any data link that does not satisfy the given reachability criterion. In earlier work we define several concrete reachability criteria [18], including ${\mathit{c}}_{\mathsf{All}}$ that, for each tuple $⟨\mathit{t}\mathrm{,}\mathit{u}\mathrm{,}\mathit{P}⟩\in \mathcal{T}\times \mathcal{I}\times \mathcal{P}$ , is defined by ${\mathit{c}}_{\mathsf{All}}\mathrm{(}\mathit{t}\mathrm{,}\mathit{u}\mathrm{,}\mathit{P}\mathrm{)}=\mathrm{true}$ ; hence, ${\mathit{c}}_{\mathsf{All}}$ does not place any restrictions on data links.

Another, more restrictive criterion that is commonly used in practice [19,38], is ${\mathit{c}}_{\mathsf{Match}}$ [18]; this criterion ignores all data links that do not match any triple pattern contained in the given SPARQL query. While our earlier formal definition of ${\mathit{c}}_{\mathsf{Match}}$ assumes that SPARQL queries are constructed from triple patterns [18], we may adapt the idea of this criterion for the PP-based patterns in this paper and define a corresponding reachability criterion that we call ${\mathit{c}}_{\mathsf{PPMatch}}$ .

Definition 10.

For any triple $\mathit{t}=⟨\mathit{s}\mathrm{,}\mathit{p}\mathrm{,}\mathit{o}⟩$ , IRI u, and PP pattern P, ${\mathit{c}}_{\mathsf{PPMatch}}\mathrm{(}\mathit{t}\mathrm{,}\mathit{u}\mathrm{,}\mathit{P}\mathrm{)}=\mathrm{true}$ if and only if p is an IRI that is mentioned in the PP expression of PP pattern P except for those IRIs that appear only in subexpressions of the forms $!\mathrm{(}{\mathit{u}}_1|\dots |{\mathit{u}}_{\mathit{n}}\mathrm{)}$ .

Example 11.

By using our previous example pattern ${\mathit{P}}_{\mathit{a}}=⟨\mathsf{\text{Suzi}}\mathrm{,}\mathsf{\text{knows}}\mathrm{/}\mathsf{\text{knows}}\mathrm{,}?\mathit{x}⟩$ and ${\mathit{S}}_{\mathsf{ex}}=\{\mathsf{\text{Suzi}}\}$ , the following documents are ( ${\mathit{S}}_{\mathsf{ex}}\mathrm{,}{\mathit{c}}_{\mathsf{PPMatch}}\mathrm{,}{\mathit{P}}_{\mathit{a}}$ )-reachable in our example Web ${\mathit{W}}_{\mathsf{ex}}$ (cf. Example 6 and Fig. 4): ${\mathit{d}}_{\mathsf{S}}$ , ${\mathit{d}}_{\mathsf{A}}$ , ${\mathit{d}}_{\mathsf{C}}$ , and ${\mathit{d}}_{\mathsf{E}}$ . If we consider the less restrictive reachability criterion ${\mathit{c}}_{\mathsf{All}}$ instead, then we have these four documents and, additionally, ${\mathit{d}}_{\mathsf{P}}$ and ${\mathit{d}}_{\mathsf{D}}$ as being ( ${\mathit{S}}_{\mathsf{ex}}\mathrm{,}{\mathit{c}}_{\mathsf{All}}\mathrm{,}{\mathit{P}}_{\mathit{a}}$ )-reachable in ${\mathit{W}}_{\mathsf{ex}}$ (i.e., all but ${\mathit{d}}_{\mathsf{B}}$ ).

Given the notion of reachability criteria, we define a family of reachability-based semantics for PP patterns: Definition 12.

Let P be a PP pattern, let $\mathit{S}\subseteq \mathcal{I}$ be a finite set of IRIs, and let c be a reachability criterion. Furthermore, let W be a Web of Linked Data, let ${\mathit{D}}_{\mathsf{R}}$ be the set of all documents that are ( $\mathit{S}\mathrm{,}\mathit{c}\mathrm{,}\mathit{P}$ )-reachable in W, and let ${\mathit{G}}_{\mathsf{R}}$ be the RDF graph for which it holds that ${\mathit{G}}_{\mathsf{R}}={\bigcup }_{\mathit{d}\in {\mathit{D}}_{\mathsf{R}}}\mathit{data}\mathrm{(}\mathit{d}\mathrm{)}$ . Then, the S-seeded evaluation of P over W under c-semantics, denoted by $⟦\mathit{P}{⟧}_{\mathit{W}}^{\mathtt{\text{rw}}\mathrm{(}\mathit{c}\mathrm{,}\mathit{S}\mathrm{)}}$ , is defined by $⟦\mathit{P}{⟧}_{\mathit{W}}^{\mathtt{\text{rw}}\mathrm{(}\mathit{c}\mathrm{,}\mathit{S}\mathrm{)}}={[[\mathit{P}]]}_{{\mathit{G}}_{\mathsf{R}}}$ where ${[[\mathit{P}]]}_{{\mathit{G}}_{\mathsf{R}}}$ uses the standard evaluation function for PP patterns (cf. Definition 2).

Example 13.

Consider ${\mathit{P}}_{\mathit{a}}=⟨\mathsf{\text{Suzi}}\mathrm{,}\mathsf{\text{knows}}\mathrm{/}\mathsf{\text{knows}}\mathrm{,}?\mathit{x}⟩$ and ${\mathit{S}}_{\mathsf{ex}}=\{\mathsf{\text{Suzi}}\}$ , then, under ${\mathit{c}}_{\mathsf{All}}$ -semantics, we have $⟦{\mathit{P}}_{\mathit{a}}{⟧}_{{\mathit{W}}_{\mathsf{ex}}}^{\mathtt{\text{rw}}\mathrm{(}{\mathit{c}}_{\mathsf{All}}\mathrm{,}{\mathit{S}}_{\mathsf{ex}}\mathrm{)}}=⟨\{{\mathit{\mu }}_{\mathit{a}1}\mathrm{,}{\mathit{\mu }}_{\mathit{a}2}\mathrm{,}{\mathit{\mu }}_{\mathit{a}3}\mathrm{,}{\mathit{\mu }}_{\mathit{a}4}\}\mathrm{,}{\mathit{card}}_{\mathit{a}}^{\mathtt{\text{rw}}\mathrm{(}{\mathit{c}}_{\mathsf{All}}\mathrm{,}{\mathit{S}}_{\mathsf{ex}}\mathrm{)}}⟩$ with the solution mappings ${\mathit{\mu }}_{\mathit{a}1}$ – ${\mathit{\mu }}_{\mathit{a}4}$ as in Example 8 and ${\mathit{card}}_{\mathit{a}}^{\mathtt{\text{rw}}\mathrm{(}{\mathit{c}}_{\mathsf{All}}\mathrm{,}{\mathit{S}}_{\mathsf{ex}}\mathrm{)}}\mathrm{(}{\mathit{\mu }}_{\mathit{a}\mathit{i}}\mathrm{)}=1$ for all $\mathit{i}\in \{1\mathrm{,}2\mathrm{,}3\mathrm{,}4\}$ . Note that solution mapping ${\mathit{\mu }}_{\mathit{a}5}$ (cf. Example 8) is not a solution in this case because computing it requires triples from document  ${\mathit{d}}_{\mathsf{B}}$ , but ${\mathit{d}}_{\mathsf{B}}$ is not ( ${\mathit{S}}_{\mathsf{ex}}\mathrm{,}{\mathit{c}}_{\mathsf{All}}\mathrm{,}{\mathit{P}}_{\mathit{a}}$ )-reachable in ${\mathit{W}}_{\mathsf{ex}}$ (cf. Example 11); due to the same reason we have ${\mathit{card}}_{\mathit{a}}^{\mathtt{\text{rw}}\mathrm{(}{\mathit{c}}_{\mathsf{All}}\mathrm{,}{\mathit{S}}_{\mathsf{ex}}\mathrm{)}}\mathrm{(}{\mathit{\mu }}_{\mathit{a}4}\mathrm{)}=1$ (under full-Web semantics it is ${\mathit{card}}_{\mathit{a}}^{\mathtt{\text{fw}}}\mathrm{(}{\mathit{\mu }}_{\mathit{a}4}\mathrm{)}=2$ ; cf. Example 8).

Example 14.

Under ${\mathit{c}}_{\mathsf{PPMatch}}$ -semantics, we only expect the following result for ${\mathit{P}}_{\mathit{a}}$ (and ${\mathit{S}}_{\mathsf{ex}}$ ) over  ${\mathit{W}}_{\mathsf{ex}}$ : $⟦{\mathit{P}}_{\mathit{a}}{⟧}_{{\mathit{W}}_{\mathsf{ex}}}^{\mathtt{\text{rw}}\mathrm{(}{\mathit{c}}_{\mathsf{PPMatch}}\mathrm{,}{\mathit{S}}_{\mathsf{ex}}\mathrm{)}}=⟨\{{\mathit{\mu }}_{\mathit{a}1}\mathrm{,}{\mathit{\mu }}_{\mathit{a}2}\}\mathrm{,}{\mathit{card}}_{\mathit{a}}^{\mathtt{\text{rw}}\mathrm{(}{\mathit{c}}_{\mathsf{PPMatch}}\mathrm{,}{\mathit{S}}_{\mathsf{ex}}\mathrm{)}}⟩$ . As mentioned in Example 8, solution mapping ${\mathit{\mu }}_{\mathit{a}3}$ requires document  ${\mathit{d}}_{\mathsf{D}}$ , which is not ( ${\mathit{S}}_{\mathsf{ex}}\mathrm{,}{\mathit{c}}_{\mathsf{PPMatch}}\mathrm{,}{\mathit{P}}_{\mathit{a}}$ )-reachable in ${\mathit{W}}_{\mathsf{ex}}$ (cf. Example 11); similarly, for ${\mathit{\mu }}_{\mathit{a}4}$ .

4.3. Context-based query semantics

Reachability-based query semantics as introduced in the previous section impose a clear conceptual separation between navigation over the link graph of a queried Web of Linked Data – which serves the purpose of discovering and retrieving reachable documents – and standard PP-based navigation over the data obtained from all reachable documents. That is, there exists no correlation between paths of triples that match PP expressions and paths of data links that connect reachable documents to seed documents.

At this point it is interesting to also explore an alternative approach in which navigation on the link graph correlates with PP patterns in queries. To this end, we introduce another semantics that interprets PP patterns as a language for navigation over Linked Data on the WWW (i.e., along the lines of earlier navigational languages for Linked Data such as NautiLOD [10]). We refer to this semantics as context-based.

Fig. 5.

Context-based semantics of property paths over a Web of Linked Data;  $\mathit{\alpha }\mathrm{,}\mathit{\beta }\in \mathrm{(}\mathcal{I}\cup \mathcal{L}\cup \mathcal{V}\mathrm{)}$ ; ${\mathit{u}}_{\mathrm{L}}\mathrm{,}\mathit{p}\mathrm{,}{\mathit{u}}_1\mathrm{,}\dots \mathrm{,}{\mathit{u}}_{\mathit{n}}\in \mathcal{I}$ ; ${\mathit{x}}_{\mathrm{L}}\mathrm{,}{\mathit{x}}_{\mathrm{R}}\in \mathrm{(}\mathcal{I}\cup \mathcal{L}\mathrm{)}$ ; $?{\mathit{v}}_{\mathrm{L}}\mathrm{,}?{\mathit{v}}_{\mathrm{R}}\in \mathcal{V}$ ; $?\mathit{v}\in \mathcal{V}$ is a fresh variable; ${\mathit{\mu }}_{\varnothing }$ is the empty solution mapping with $\mathrm{dom}\mathrm{(}{\mathit{\mu }}_{\varnothing }\mathrm{)}=\varnothing$ ; and function $\mathtt{ALPW}\mathtt{1}$ is given in Fig. 6.

The main idea of this query semantics is to restrict the scope of searching for any next triple of a potentially matching path to specific data within specific documents on the queried Web of Linked Data.

To formalize these restrictions we introduce the notion of a context selector. Informally, for each IRI that can be used to retrieve a document, the context selector returns a specific subset of the data within that document; this subset contains only those triples that have the given IRI as their subject (such a subset of triples resembles Harth and Speiser’s notion of “subject authoritative triples” [16]). Formally, for any Web of Linked Data  $\mathit{W}=⟨\mathit{D}\mathrm{,}\mathit{adoc}⟩$ , the context selector of W is a function ${\mathrm{C}}^{\mathit{W}}:\mathrm{(}\mathcal{I}\cup \mathcal{B}\cup \mathcal{L}\cup \mathcal{V}\mathrm{)}\to 2^{\mathcal{T}}$ that, for every IRI $\mathit{u}\in \mathcal{I}$ with $\mathit{u}\in {\mathrm{dom}}^{\perp ̸}\mathrm{(}\mathit{adoc}\mathrm{)}$ , is defined by $$\begin{array}{c}{\mathrm{C}}^{\mathit{W}}\mathrm{(}\mathit{u}\mathrm{)}=\{⟨\mathit{s}\mathrm{,}\mathit{p}\mathrm{,}\mathit{o}⟩\in \mathit{data}\mathrm{(}\mathit{adoc}\mathrm{(}\mathit{u}\mathrm{)}\mathrm{\left)}\right|\mathit{u}=\mathit{s}\}\mathrm{,}\end{array}$$ and for any other $\mathit{\gamma }\in \mathrm{(}\mathcal{I}\cup \mathcal{B}\cup \mathcal{L}\cup \mathcal{V}\mathrm{)}\setminus {\mathrm{dom}}^{\perp ̸}\mathrm{(}\mathit{adoc}\mathrm{)}$ we have ${\mathrm{C}}^{\mathit{W}}\mathrm{(}\mathit{\gamma }\mathrm{)}=\varnothing$ (by extending the definition of ${\mathrm{C}}^{\mathit{W}}$ to handle any such γ, we can simplify the following formalization of the context-based query semantics).

Informally, the context-based semantics uses the notion of a context selector to restrict the scope of PP patterns over a Web of Linked Data as follows. Assume a sequence of triples $⟨{\mathit{s}}_1\mathrm{,}{\mathit{p}}_1\mathrm{,}{\mathit{o}}_1⟩\mathrm{,}\dots \mathrm{,}⟨{\mathit{s}}_{\mathit{k}}\mathrm{,}{\mathit{p}}_{\mathit{k}}\mathrm{,}{\mathit{o}}_{\mathit{k}}⟩$ that presents a path that already matches a sub-expression of a given PP expression. Under the previously defined reachability-based query semantics, the next triple for such a path can be searched for in any reachable document in the queried Web of Linked Data W. By contrast, under the context-based query semantics that we formalize in the following Definition 15, the next triple has to be searched for only in ${\mathrm{C}}^{\mathit{W}}\mathrm{(}{\mathit{o}}_{\mathit{k}}\mathrm{)}$ .

Definition 15.

Given a PP pattern P and a Web of Linked Data  $\mathit{W}=⟨\mathit{D}\mathrm{,}\mathit{adoc}⟩$ , the evaluation of P over W under context-based semantics, denoted by $⟦\mathit{P}{⟧}_{\mathit{W}}^{\mathtt{\text{ctx}}}$ , is a multiset of solution mappings $⟨\mathrm{\Omega }\mathrm{,}\mathit{card}⟩$ that is defined recursively as given in Fig. 5.

Fig. 6.

Auxiliary functions used for defining context-based query semantics.

Note how Definition 15 uses the context selector to restrict the data that has to be searched to find matching triples (e.g., consider the first line in Fig. 5).

Example 16.

Coming back to the example PP pattern ${\mathit{P}}_{\mathit{a}}=⟨\mathsf{\text{Suzi}}\mathrm{,}\mathsf{\text{knows}}\mathrm{/}\mathsf{\text{knows}}\mathrm{,}?\mathit{x}⟩$ , and ${\mathit{W}}_{\mathsf{ex}}$ (cf. Example 6 and Fig. 4), under the context-based semantics we obtain $⟦{\mathit{P}}_{\mathit{a}}{⟧}_{{\mathit{W}}_{\mathsf{ex}}}^{\mathtt{\text{ctx}}}=⟨\{{\mathit{\mu }}_{\mathit{a}1}\}\mathrm{,}{\mathit{card}}_{\mathit{a}}^{\mathtt{\text{ctx}}}⟩$ with ${\mathit{\mu }}_{\mathit{a}1}$ as before (cf. Example 8) and ${\mathit{card}}_{\mathit{a}}^{\mathtt{\text{ctx}}}\mathrm{(}{\mathit{\mu }}_{\mathit{a}1}\mathrm{)}=1$ .

There are two points worth emphasizing regarding Definition 15: First, we define the context-based semantics such that it resembles the standard semantics of PP patterns in Section 3.1 as close as possible. To this end, the part of our definition that covers PP patterns of the form $⟨\mathit{\alpha }\mathrm{,}{\mathtt{\text{path}}}^{\ast }\mathrm{,}\mathit{\beta }⟩$ also uses auxiliary functions, namely, $\mathtt{ALPW}\mathtt{1}$ and $\mathtt{ALPW}\mathtt{2}$ (cf. Fig. 6). These functions evaluate the sub-expression $\mathtt{\text{path}}$ recursively over the queried Web of Linked Data (instead of using a fixed RDF graph as done in the standard semantics in Fig. 2). Second, the two base cases with a variable in the subject position (i.e., the third and the sixth case in Fig. 5) require an enumeration of all IRIs. Such a requirement is necessary to both, remain consistent with the standard semantics and preserve commutativity of operators that can be defined on top of PP patterns (such as the AND operator in SPARQL; cf. Section 5).

However, due to this requirement, there exist PP patterns whose (complete) evaluation under context-based semantics is infeasible when querying the WWW. The following example describes such a case.

Example 17.

Consider the following PP pattern ${\mathit{P}}_{\mathsf{\text{E17}}}$ , which retrieves the IRIs of people that know Tim: $$\begin{array}{c}{\mathit{P}}_{\mathsf{\text{E17}}}=⟨?\mathit{v}\mathrm{,}\mathsf{\text{knows}}\mathrm{,}\mathsf{\text{Tim}}⟩.\end{array}$$ Under context-based semantics, any IRI  ${\mathit{u}}^{\prime }$ can be used to generate a correct solution mapping for the pattern as long as a lookup of that IRI results in retrieving a document whose data contains the triple $⟨{\mathit{u}}^{\prime }\mathrm{,}\mathsf{\text{knows}}\mathrm{,}\mathsf{\text{Tim}}⟩$ . While, for any Web of Linked Data that is finite, there exists only a finite number of such IRIs, determining these IRIs and guaranteeing completeness requires enumerating the infinite set of all possible IRIs and checking each of them – unless one knows the complete (and finite) subset of all IRIs that can be used to retrieve some document, which, due to the infiniteness of possible HTTP-scheme IRIs, cannot be achieved for the WWW.

It is not difficult to see that the issue illustrated in the example exists for any triple pattern that has a variable in the subject position. On the other hand, triple patterns whose subject is an IRI do not have this issue. However, having an IRI in the subject position is not a sufficient condition in general. For instance, the PP pattern $⟨\mathsf{\text{Tim}}\mathrm{,}{}^{\wedge }\mathsf{\text{knows}}\mathrm{,}?\mathit{v}⟩$ has the same issue as the pattern in Example 17 (in fact, both patterns are semantically equivalent under context-based semantics as can be observed from the seventh case in Fig. 5).

A question that arises is whether there exists a (decidable) property of PP patterns that can be used to distinguish between patterns that do not have this issue (i.e., evaluating them over any Web of Linked Data is feasible under the context-based semantics) and those that do. Another question is whether any of the aforementioned reachability-based semantics has a similar problem, and, more generally, how do these semantics compare to the context-based semantics?

We come back to these questions in Sections 6 and 7, after introducing the more general case of PP-based SPARQL queries in the next section.

5. PP-based SPARQL queries for the Web

After considering PP patterns in isolation, we now turn to a more expressive fragment of SPARQL that embeds PP patterns as the basic building block and uses additional operators on top. In this section, we define the resulting PP-based SPARQL queries; we specify their syntax and formalize Web-aware semantics that extend the above defined semantics of PP patterns.

By using the algebraic syntax of SPARQL [30], we define a graph pattern recursively as follows:1

¹

For this paper we leave out other types of SPARQL graph patterns such as filters, subqueries, assignments (BIND), aggregation. Adding them is an exercise that would not have any significant implication on the results in this paper.

• Any PP pattern $⟨\mathit{\alpha }\mathrm{,}\mathtt{\text{path}}\mathrm{,}\mathit{\beta }⟩$ is a graph pattern.

• If ${\mathit{P}}_1$ and ${\mathit{P}}_2$ are graph patterns, then so are $\mathrm{(}{\mathit{P}}_1\mathsf{\text{AND }}{\mathit{P}}_2\mathrm{)}$ , $\mathrm{(}{\mathit{P}}_1\mathsf{\text{UNION }}{\mathit{P}}_2\mathrm{)}$ , and $\mathrm{(}{\mathit{P}}_1\mathsf{\text{OPT }}{\mathit{P}}_2\mathrm{)}$ .

For any graph pattern P, we write $\mathrm{vars}\mathrm{(}\mathit{P}\mathrm{)}$ to denote the set of all variables in P; that is, if P is a PP pattern $⟨\mathit{\alpha }\mathrm{,}\mathtt{\text{path}}\mathrm{,}\mathit{\beta }⟩$ , we have $\mathrm{vars}\mathrm{(}\mathit{P}\mathrm{)}=\{\mathit{\alpha }\mathrm{,}\mathit{\beta }\}\cap \mathcal{V}$ , and if P is of the form $\mathrm{(}{\mathit{P}}_1\mathsf{\text{AND }}{\mathit{P}}_2\mathrm{)}$ , $\mathrm{(}{\mathit{P}}_1\mathsf{\text{UNION }}{\mathit{P}}_2\mathrm{)}$ , or $\mathrm{(}{\mathit{P}}_1\mathsf{\text{OPT }}{\mathit{P}}_2\mathrm{)}$ , we have $\mathrm{vars}\mathrm{(}\mathit{P}\mathrm{)}=\mathrm{vars}\mathrm{(}{\mathit{P}}_1\mathrm{)}\cup \mathrm{vars}\mathrm{(}{\mathit{P}}_2\mathrm{)}$ .

Example 18.

An example of a graph pattern that combines two PP patterns using the OPT operator is given as follows: $\mathrm{(}⟨\mathsf{\text{Tim}}\mathrm{,}\mathsf{\text{knows}}\mathrm{/}\mathsf{\text{knows}}\mathrm{,}?\mathit{p}⟩\mathsf{\text{OPT }}⟨?\mathit{p}\mathrm{,}\mathsf{\text{name}}\mathrm{,}?\mathit{n}⟩\mathrm{)}$ This pattern retrieves persons known by acquaintances of $\mathsf{\text{Tim}}$ and, if available, the names of these persons.

By using PP patterns as the basic building block of graph patterns, we can readily carry over any of the above defined query semantics to graph patterns. To this end, let $\mathcal{S}$ be a set of symbols that denote these semantics; in particular, we have $\mathtt{\text{fw}}\in \mathcal{S}$ that denotes the full-Web semantics (cf. Section 4.1), $\mathtt{\text{rw}}\mathrm{(}\mathit{c}\mathrm{,}\mathit{S}\mathrm{)}\in \mathcal{S}$ denotes the (reachability-based) c-semantics with a set S of seed IRIs (cf. Section 4.2), and $\mathtt{\text{ctx}}\in \mathcal{S}$ denotes the context-based semantics (cf. Section 4.3). We extend these semantics to cover graph patterns as follows. Definition 19.

Let P be a graph pattern and let W be a Web of Linked Data. For any $\mathit{\phi }\in \mathcal{S}$ , the evaluation of P over W under the semantics denoted by φ is a multiset of solution mappings, denoted by $⟦\mathit{P}{⟧}_{\mathit{W}}^{\mathit{\phi }}$ , that is defined recursively as follows:2 ²

Note that the definition uses the algebra defined in Fig. 1.

• If P is a PP pattern $⟨\mathit{\alpha }\mathrm{,}\mathtt{\text{path}}\mathrm{,}\mathit{\beta }⟩$ , then $⟦\mathit{P}{⟧}_{\mathit{W}}^{\mathit{\phi }}$ is defined in the φ-specific subsection of Section 4.

• If P is of the form $\mathrm{(}{\mathit{P}}_1\mathsf{\text{AND }}{\mathit{P}}_2\mathrm{)}$ , then $$\begin{array}{c}⟦\mathit{P}{⟧}_{\mathit{W}}^{\mathit{\phi }}=⟦{\mathit{P}}_1{⟧}_{\mathit{W}}^{\mathit{\phi }}\bowtie ⟦{\mathit{P}}_2{⟧}_{\mathit{W}}^{\mathit{\phi }}.\end{array}$$

• If P is of the form $\mathrm{(}{\mathit{P}}_1\mathsf{\text{UNION }}{\mathit{P}}_2\mathrm{)}$ , then $$\begin{array}{c}⟦\mathit{P}{⟧}_{\mathit{W}}^{\mathit{\phi }}=⟦{\mathit{P}}_1{⟧}_{\mathit{W}}^{\mathit{\phi }}\bigsqcup ⟦{\mathit{P}}_2{⟧}_{\mathit{W}}^{\mathit{\phi }}.\end{array}$$

• If P is of the form $\mathrm{(}{\mathit{P}}_1\mathsf{\text{OPT }}{\mathit{P}}_2\mathrm{)}$ , then $$\begin{array}{c}⟦\mathit{P}{⟧}_{\mathit{W}}^{\mathit{\phi }}=\mathrm{(}⟦{\mathit{P}}_1{⟧}_{\mathit{W}}^{\mathit{\phi }}\bowtie ⟦{\mathit{P}}_2{⟧}_{\mathit{W}}^{\mathit{\phi }}\mathrm{)}\bigsqcup \mathrm{(}⟦{\mathit{P}}_1{⟧}_{\mathit{W}}^{\mathit{\phi }}\setminus ⟦{\mathit{P}}_2{⟧}_{\mathit{W}}^{\mathit{\phi }}\mathrm{)}.\end{array}$$

6. Web-safeness

Given the different semantics for evaluating (PP-based) graph patterns over a Web of Linked Data, we now study formally whether such evaluations are possible in practice over Linked Data on the WWW.

To this end, we first recall from Section 4.1 that, under full-Web semantics, evaluating PP patterns over the WWW is not possible in practice because, for the tuple $\mathit{W}=⟨\mathit{D}\mathrm{,}\mathit{adoc}⟩$ with which we formalize the notion of Linked Data on the WWW, the sets D and ${\mathrm{dom}}^{\perp ̸}\mathrm{(}\mathit{adoc}\mathrm{)}$ cannot be assumed to be available completely to any algorithm [18]. Without complete knowledge of these two sets, an algorithm designed to answer PP patterns completely under full-Web semantics would have to enumerate the infinite set of all possible (HTTP-scheme) IRIs and look up each of them.

Based on this observation, we define a notion of Web-safeness of graph patterns; with this notion we capture whether it is possible for a graph pattern to be evaluated completely over Linked Data on the WWW under a given semantics.

Definition 20.

For any $\mathit{\phi }\in \mathcal{S}$ , a graph pattern P under the semantics denoted by φ is Web-safe if there exists an algorithm that, for any finite Web of Linked Data  $\mathit{W}=⟨\mathit{D}\mathrm{,}\mathit{adoc}⟩$ , has the following properties:

The algorithm computes $⟦\mathit{P}{⟧}_{\mathit{W}}^{\mathit{\phi }}$ .

During its execution, the algorithm looks up only a finite number of IRIs (that is, conceptually, the algorithm invokes function $\mathit{adoc}$ only a finite number of times).

Neither the set D nor the set ${\mathrm{dom}}^{\perp ̸}\mathrm{(}\mathit{adoc}\mathrm{)}$ is required as input for the algorithm (hence, the algorithm does not require any a priori information about W).

Unsurprisingly, as already discussed in Section 4.1, it follows from the results in our earlier work [18] that, under full-Web semantics, none of the graph patterns considered in this paper is Web-safe.

In the following, we study Web-safeness of graph patterns under the other Web-aware query semantics.

6.1. Web-safeness of reachability-based semantics

Independent of what reachability criterion (and seed IRIs) one chooses, for every reachability-based semantics we can show the following positive result.

Theorem 21.

Given an arbitrary reachability criterion c and any finite set $\mathit{S}\subseteq \mathcal{I}$ of IRIs, every graph pattern is Web-safe under c-semantics with S as seed IRIs.

As a basis to prove Theorem 21, we first focus on PP patterns, for which we show the following lemma.

Lemma 22.

Given an arbitrary reachability criterion c and any finite set $\mathit{S}\subseteq \mathcal{I}$ of IRIs, every PP pattern is Web-safe under c-semantics with S as seed IRIs.

Proof (Lemma 22).

We prove the lemma by providing Algorithm 1. It is easily verified that this algorithm has the desired properties (as listed in Definition 20). Note that the execution of this algorithm consists of two consecutive phases: a data retrieval phase (lines 1 to 12) and a standard result computation phase (line 13). During the data retrieval phase the algorithm incrementally discovers all documents that are $\mathrm{(}\mathit{S}\mathrm{,}\mathit{c}\mathrm{,}\mathit{P}\mathrm{)}$ -reachable in the queried Web, and collects their data in RDF graph ${\mathit{G}}_{\mathsf{R}}$ . The second condition in line 11 ensures that any other document is ignored during the data retrieval phase. Hence, when the execution of the algorithm reaches line 13, we have ${\mathit{G}}_{\mathsf{R}}={\bigcup }_{\mathit{d}\in {\mathit{D}}_{\mathsf{R}}}\mathit{data}\mathrm{(}\mathit{d}\mathrm{)}$ where ${\mathit{D}}_{\mathsf{R}}$ is the set of all ( $\mathit{S}\mathrm{,}\mathit{c}\mathrm{,}\mathit{P}$ )-reachable documents. Due to the finiteness of the queried Web of Linked Data, both ${\mathit{D}}_{\mathsf{R}}$ and ${\mathit{G}}_{\mathsf{R}}$ are finite. Therefore, there exists a finite upper bound on the number of different IRIs that the algorithm has to look up; in the worst case this upper bound is the number of all IRIs in the final version of ${\mathit{G}}_{\mathsf{R}}$ (in practice, the upper bound may be smaller depending on the reachability criterion c). The existence of this upper bound and the first condition in line 11 ensure that the data retrieval phase terminates.  □

Algorithm 1

Computation of the S-seeded evaluation of a PP pattern P over any Web of Linked Data under c-semantics (where $\mathit{S}\subseteq \mathcal{I}$ is a finite set of IRIs and c is a reachability criterion)

Given Lemma 22, it is trivial to prove Theorem 21.

Proof (Theorem 21).

Theorem 21 is a direct consequence of Definition 19 and Lemma 22. That is, given multisets of solution mappings computed for PP patterns, combining such multisets as per the algebra operators does not require any more URI lookups (or any other kind of access to the queried Web of Linked Data) and can be done by any algorithm that implements these algebra operators.  □

We emphasize that, while Algorithm 1 is sufficient for proving Lemma 22 and, thus, Theorem 21, it is perhaps not a very efficient algorithm to use in practice. Systems might instead implement traversal-based execution approaches to evaluate PP patterns under reachability-based semantics [19,38]; the processing of IRIs from the Open list (used in the algorithm) can be parallelized by a multi-threaded implementation; additionally, assuming a suitable invalidation policy, documents may be cached and reused for later queries [17].

6.2. Web-safeness of context-based semantics

After finding that under any reachability-based semantics all graph patterns are Web-safe, we now come back to the context-based semantics for which we know from Example 17 that Web-safeness cannot be assumed in general. We begin our analysis by providing the following example, which extends Example 17.

Example 23.

Consider the following graph pattern: $$\begin{array}{c}{\mathit{P}}_{\mathsf{\text{E23}}}=\mathrm{(}⟨\mathsf{\text{Bob}}\mathrm{,}\mathsf{\text{knows}}\mathrm{,}?\mathit{v}⟩\mathsf{\text{AND }}⟨?\mathit{v}\mathrm{,}\mathsf{\text{knows}}\mathrm{,}\mathsf{\text{Tim}}⟩\mathrm{)}.\end{array}$$ The right sub-pattern ${\mathit{P}}_{\mathsf{\text{E17}}}=⟨?\mathit{v}\mathrm{,}\mathsf{\text{knows}}\mathrm{,}\mathsf{\text{Tim}}⟩$ is not Web-safe because evaluating it completely over the WWW is not possible under context-based semantics (cf. Example 17). However, the larger pattern ${\mathit{P}}_{\mathsf{\text{E23}}}$ is Web-safe under context-based semantics: A possible algorithm may first evaluate the left sub-pattern, $⟨\mathsf{\text{Bob}}\mathrm{,}\mathsf{\text{knows}}\mathrm{,}?\mathit{v}⟩$ , which is possible because it requires the lookup of a single IRI only (the IRI $\mathsf{\text{Bob}}$ ). Thereafter, the evaluation of the right sub-pattern ${\mathit{P}}_{\mathsf{\text{E17}}}$ can be reduced to looking up a finite number of IRIs only, namely the IRIs bound to variable  $?\mathit{v}$ in solution mappings obtained in the first step for the left sub-pattern. Although any other IRI, say  ${\mathit{u}}^{\ast }$ , might also be used to discover triples for ${\mathit{P}}_{\mathsf{\text{E17}}}$ , each of these triples has IRI  ${\mathit{u}}^{\ast }$ as its subject (which is a consequence of restricting retrieved data based on the context selector introduced in Section 4.3). Therefore, possible solution mappings resulting from such triples cannot be compatible with any solution for the left sub-pattern and, thus, do not satisfy the join condition established by the semantics of AND in pattern  ${\mathit{P}}_{\mathsf{\text{E23}}}$ .

The example illustrates that some graph patterns are Web-safe under context-based semantics even if some of their sub-patterns are not. Consequently, we are interested in a decidable property that enables us to identify Web-safe patterns under context-based semantics, including those whose sub-patterns are not Web-safe.

Buil-Aranda et al. study a similar problem in the context of SPARQL federation where graph patterns of the form $\mathrm{(}\mathsf{\text{SERVICE }}?\mathit{v}\mathit{P}\mathrm{)}$ are allowed [7]. For such a pattern ${\mathit{P}}_{\mathit{S}}=\mathrm{(}\mathsf{\text{SERVICE }}?\mathit{v}\mathit{P}\mathrm{)}$ , variable  $?\mathit{v}$ ranges over a possibly large set of IRIs, each of which represents the address of a (remote) SPARQL service that needs to be called to assemble the complete result of  ${\mathit{P}}_{\mathit{S}}$ . However, many service calls may be avoided if  ${\mathit{P}}_{\mathit{S}}$ is embedded in a larger graph pattern that allows for an evaluation during which  $?\mathit{v}$ can be bound before evaluating  ${\mathit{P}}_{\mathit{S}}$ . To identify such cases, Buil-Aranda et al. introduce a notion of strong boundedness of variables in graph patterns and use it to show a notion of safeness for the evaluation of patterns like ${\mathit{P}}_{\mathit{S}}$ within larger graph patterns. The idea behind the notion of strongly bound variables has already been used in earlier work (e.g., “certain variables” [34], “output variables” [37]), and it is tempting to adopt it for our problem. To this end, we first define the notion of strongly bound variables for our PP-based graph patterns:

Definition 24.

The set of strongly bound variables in a graph pattern P, denoted by $\mathrm{sbvars}\mathrm{(}\mathit{P}\mathrm{)}$ , is defined recursively as follows (recall that $\mathrm{vars}\mathrm{(}\mathit{P}\mathrm{)}$ is the set of all variables in P):

If P is a PP pattern, then $$\begin{array}{c}\mathrm{sbvars}\mathrm{(}\mathit{P}\mathrm{)}=\mathrm{vars}\mathrm{(}\mathit{P}\mathrm{)}.\end{array}$$

If P is of the form $\mathrm{(}{\mathit{P}}_1\mathsf{\text{AND }}{\mathit{P}}_2\mathrm{)}$ , then $$\begin{array}{c}\mathrm{sbvars}\mathrm{(}\mathit{P}\mathrm{)}=\mathrm{sbvars}\mathrm{(}{\mathit{P}}_1\mathrm{)}\cup \mathrm{sbvars}\mathrm{(}{\mathit{P}}_2\mathrm{)}.\end{array}$$

If P is of the form $\mathrm{(}{\mathit{P}}_1\mathsf{\text{UNION }}{\mathit{P}}_2\mathrm{)}$ , then $$\begin{array}{c}\mathrm{sbvars}\mathrm{(}\mathit{P}\mathrm{)}=\mathrm{sbvars}\mathrm{(}{\mathit{P}}_1\mathrm{)}\cap \mathrm{sbvars}\mathrm{(}{\mathit{P}}_2\mathrm{)}.\end{array}$$

If P is of the form $\mathrm{(}{\mathit{P}}_1\mathsf{\text{OPT }}{\mathit{P}}_2\mathrm{)}$ , then $$\begin{array}{c}\mathrm{sbvars}\mathrm{(}\mathit{P}\mathrm{)}=\mathrm{sbvars}\mathrm{(}{\mathit{P}}_1\mathrm{)}.\end{array}$$

Given the definition of strongly bound variables, we observe that one cannot identify Web-safe graph patterns by using only this notion of strong boundedness.

Table 1

Cases of the recursive definition of the conditionally bound variables of a graph pattern P w.r.t. a set of variables $\mathit{X}\subseteq \mathcal{V}$

If P is:		then $\mathrm{cbvars}\mathrm{(}\mathit{P}|\mathit{X}\mathrm{)}$ is:
1)	$⟨\mathit{\alpha }\mathrm{,}\mathit{u}\mathrm{,}\mathit{\beta }⟩$   or   $⟨\mathit{\alpha }\mathrm{,}!\mathrm{(}{\mathit{u}}_1|\dots |{\mathit{u}}_{\mathit{n}}\mathrm{)}\mathrm{,}\mathit{\beta }⟩$   such that $\mathit{\alpha }\in \mathrm{(}\mathcal{I}\cup \mathcal{L}\mathrm{)}$ or $\mathit{\alpha }\in \mathit{X}$	$\mathrm{vars}\mathrm{(}\mathit{P}\mathrm{)}$
2)	$⟨\mathit{\alpha }\mathrm{,}\mathit{u}\mathrm{,}\mathit{\beta }⟩$   or   $⟨\mathit{\alpha }\mathrm{,}!\mathrm{(}{\mathit{u}}_1|\dots |{\mathit{u}}_{\mathit{n}}\mathrm{)}\mathrm{,}\mathit{\beta }⟩$   such that $\mathit{\alpha }\notin \mathrm{(}\mathcal{I}\cup \mathcal{L}\mathrm{)}$ and $\mathit{\alpha }\notin \mathit{X}$	∅
3)	$⟨\mathit{\alpha }\mathrm{,}{\mathrm{(}\mathtt{\text{path}}\mathrm{)}}^{\ast }\mathrm{,}\mathit{\beta }⟩$   such that $\mathit{\alpha }\in \mathcal{V}$ and $\mathit{\beta }\notin \mathcal{V}$	$\mathrm{cbvars}\mathrm{(}⟨\mathit{\beta }\mathrm{,}{\mathrm{(}{}^{\wedge }\mathtt{\text{path}}\mathrm{)}}^{\ast }\mathrm{,}\mathit{\alpha }⟩|\mathit{X}\mathrm{)}$
4)	$⟨\mathit{\alpha }\mathrm{,}{\mathrm{(}\mathtt{\text{path}}\mathrm{)}}^{\ast }\mathrm{,}\mathit{\beta }⟩$   such that $\mathit{\alpha }\notin \mathcal{V}$ or $\mathit{\beta }\in \mathcal{V}$ , and for any two variables $?\mathit{x}\mathrm{,}?\mathit{y}\in \mathcal{V}$ it holds that $\mathrm{cbvars}\mathrm{(}⟨?\mathit{x}\mathrm{,}\mathtt{\text{path}}\mathrm{,}?\mathit{y}⟩|\{?\mathit{x}\}\mathrm{)}=\{?\mathit{x}\mathrm{,}?\mathit{y}\}$	$\mathrm{cbvars}\mathrm{(}⟨\mathit{\alpha }\mathrm{,}\mathtt{\text{path}}\mathrm{,}\mathit{\beta }⟩|\mathit{X}\mathrm{)}$
5)	$⟨\mathit{\alpha }\mathrm{,}{\mathrm{(}\mathtt{\text{path}}\mathrm{)}}^{\ast }\mathrm{,}\mathit{\beta }⟩$   such that none of the above	∅
6)	$⟨\mathit{\alpha }\mathrm{,}{}^{\wedge }\mathtt{\text{path}}\mathrm{,}\mathit{\beta }⟩$ with ${\mathit{P}}^{\prime }=⟨\mathit{\beta }\mathrm{,}\mathtt{\text{path}}\mathrm{,}\mathit{\alpha }⟩$	$\mathrm{cbvars}\mathrm{(}{\mathit{P}}^{\prime }|\mathit{X}\mathrm{)}$
7)	$⟨\mathit{\alpha }\mathrm{,}\mathrm{(}{\mathtt{\text{path}}}_1|{\mathtt{\text{path}}}_2\mathrm{)}\mathrm{,}\mathit{\beta }⟩$ with ${\mathit{P}}^{\prime }=\mathrm{(}⟨\mathit{\alpha }\mathrm{,}{\mathtt{\text{path}}}_1\mathrm{,}\mathit{\beta }⟩\mathsf{\text{UNION }}⟨\mathit{\alpha }\mathrm{,}{\mathtt{\text{path}}}_2\mathrm{,}\mathit{\beta }⟩\mathrm{)}$	$\mathrm{cbvars}\mathrm{(}{\mathit{P}}^{\prime }|\mathit{X}\mathrm{)}$
8)	$⟨\mathit{\alpha }\mathrm{,}{\mathtt{\text{path}}}_1\mathrm{/}{\mathtt{\text{path}}}_2\mathrm{,}\mathit{\beta }⟩$ such that for any $?\mathit{v}\in \mathcal{V}\setminus \mathrm{(}\mathit{X}\cup \{\mathit{\alpha }\mathrm{,}\mathit{\beta }\}\mathrm{)}$ we have $?\mathit{v}\in \mathrm{cbvars}\mathrm{(}{\mathit{P}}^{\prime }|\mathit{X}\mathrm{)}$ where ${\mathit{P}}^{\prime }=\mathrm{(}⟨\mathit{\alpha }\mathrm{,}{\mathtt{\text{path}}}_1\mathrm{,}?\mathit{v}⟩\mathsf{\text{AND }}⟨?\mathit{v}\mathrm{,}{\mathtt{\text{path}}}_2\mathrm{,}\mathit{\beta }⟩\mathrm{)}$	$\mathrm{cbvars}\mathrm{(}{\mathit{P}}^{\prime }|\mathit{X}\mathrm{)}\setminus \{?\mathit{v}\}$
9)	$⟨\mathit{\alpha }\mathrm{,}{\mathtt{\text{path}}}_1\mathrm{/}{\mathtt{\text{path}}}_2\mathrm{,}\mathit{\beta }⟩$ such that none of the above	∅
10)	$\mathrm{(}{\mathit{P}}_1\mathsf{\text{AND }}{\mathit{P}}_2\mathrm{)}$ s.t.  $\mathrm{cbvars}\mathrm{(}{\mathit{P}}_1|\mathit{X}\mathrm{)}=\mathrm{vars}\mathrm{(}{\mathit{P}}_1\mathrm{)}$ and $\mathrm{cbvars}\mathrm{(}{\mathit{P}}_2|\mathit{X}\cup \mathrm{sbvars}\mathrm{(}{\mathit{P}}_1\mathrm{)}\mathrm{)}=\mathrm{vars}\mathrm{(}{\mathit{P}}_2\mathrm{)}$	$\mathrm{vars}\mathrm{(}\mathit{P}\mathrm{)}$
11)	$\mathrm{(}{\mathit{P}}_1\mathsf{\text{AND }}{\mathit{P}}_2\mathrm{)}$ s.t.  $\mathrm{cbvars}\mathrm{(}{\mathit{P}}_2|\mathit{X}\mathrm{)}=\mathrm{vars}\mathrm{(}{\mathit{P}}_2\mathrm{)}$ and $\mathrm{cbvars}\mathrm{(}{\mathit{P}}_1|\mathit{X}\cup \mathrm{sbvars}\mathrm{(}{\mathit{P}}_2\mathrm{)}\mathrm{)}=\mathrm{vars}\mathrm{(}{\mathit{P}}_1\mathrm{)}$	$\mathrm{vars}\mathrm{(}\mathit{P}\mathrm{)}$
12)	$\mathrm{(}{\mathit{P}}_1\mathsf{\text{AND }}{\mathit{P}}_2\mathrm{)}$ such that none of the above	∅
13)	$\mathrm{(}{\mathit{P}}_1\mathsf{\text{UNION }}{\mathit{P}}_2\mathrm{)}$	$\mathrm{cbvars}\mathrm{(}{\mathit{P}}_1|\mathit{X}\mathrm{)}\cap \mathrm{cbvars}\mathrm{(}{\mathit{P}}_2|\mathit{X}\mathrm{)}$
14)	$\mathrm{(}{\mathit{P}}_1\mathsf{\text{OPT }}{\mathit{P}}_2\mathrm{)}$ s.t.  $\mathrm{cbvars}\mathrm{(}{\mathit{P}}_1|\mathit{X}\mathrm{)}=\mathrm{vars}\mathrm{(}{\mathit{P}}_1\mathrm{)}$ and $\mathrm{cbvars}\mathrm{(}{\mathit{P}}_2|\mathit{X}\cup \mathrm{sbvars}\mathrm{(}{\mathit{P}}_1\mathrm{)}\mathrm{)}=\mathrm{vars}\mathrm{(}{\mathit{P}}_2\mathrm{)}$	$\mathrm{vars}\mathrm{(}\mathit{P}\mathrm{)}$
15)	$\mathrm{(}{\mathit{P}}_1\mathsf{\text{OPT }}{\mathit{P}}_2\mathrm{)}$ such that none of the above	∅

Example 25.

Consider graph pattern ${\mathit{P}}_{\mathsf{\text{E23}}}$ from Example 23. We know that (i)  ${\mathit{P}}_{\mathsf{\text{E23}}}$ is Web-safe and that (ii)  $\mathrm{vars}\mathrm{(}{\mathit{P}}_{\mathsf{\text{E23}}}\mathrm{)}=\{?\mathit{v}\}$ and also $\mathrm{sbvars}\mathrm{(}{\mathit{P}}_{\mathsf{\text{E23}}}\mathrm{)}=\{?\mathit{v}\}$ . Then, one might hypothesize that a graph pattern P is Web-safe if $\mathrm{sbvars}\mathrm{(}\mathit{P}\mathrm{)}=\mathrm{vars}\mathrm{(}\mathit{P}\mathrm{)}$ . However, the PP pattern ${\mathit{P}}_{\mathsf{\text{E17}}}=⟨?\mathit{v}\mathrm{,}\mathrm{knows}\mathrm{,}\mathrm{Tim}⟩$ disproves such a hypothesis because, even if $\mathrm{sbvars}\mathrm{(}{\mathit{P}}_{\mathsf{\text{E17}}}\mathrm{)}=\mathrm{vars}\mathrm{(}{\mathit{P}}_{\mathsf{\text{E17}}}\mathrm{)}$ , pattern ${\mathit{P}}_{\mathsf{\text{E17}}}$ is not Web-safe (cf. Example 17). Alternatively, one might also hypothesize that if a graph pattern P is Web-safe, then $\mathrm{sbvars}\mathrm{(}\mathit{P}\mathrm{)}=\mathrm{vars}\mathrm{(}\mathit{P}\mathrm{)}$ . However, this hypothesis can be disproved by using pattern ${\mathit{P}}_{\mathsf{\text{E25}}}=\mathrm{(}⟨\mathsf{\text{Bob}}\mathrm{,}\mathsf{\text{knows}}\mathrm{,}?\mathit{x}⟩\mathsf{\text{OPT }}⟨?\mathit{x}\mathrm{,}\mathsf{\text{knows}}\mathrm{,}?\mathit{y}⟩\mathrm{)}$ . It can easily be verified that ${\mathit{P}}_{\mathsf{\text{E25}}}$ is Web-safe (e.g., it is not difficult to adjust the algorithm for pattern ${\mathit{P}}_{\mathsf{\text{E23}}}$ in Example 23 accordingly). However, in contradiction to the hypothesis we have $\mathrm{sbvars}\mathrm{(}{\mathit{P}}_{\mathsf{\text{E25}}}\mathrm{)}\ne \mathrm{vars}\mathrm{(}{\mathit{P}}_{\mathsf{\text{E25}}}\mathrm{)}$ .

We conjecture the following reason why strong boundedness cannot be used directly for our problem. Consider the types of graph patterns that combine two sub-patterns (by using operators such as AND). For such a pattern, the sets of strongly bound variables of its sub-patterns are defined independent from each other, whereas the algorithm outlined in Example 23 leverages a specific relationship between sub-patterns. More precisely, the algorithm leverages the fact that the same variable that is the subject of the right sub-pattern is also the object of the left sub-pattern.

Based on this observation, we introduce the notion of conditionally bound variables, which is based on particular relationships between sub-patterns due to which the result of one sub-pattern may be used to evaluate another sub-pattern in a more well-behaved manner (along the lines of Example 23). This notion shall turn out to be suitable for our case.

Definition 26.

Let $\mathit{X}\subseteq \mathcal{V}$ be a set of variables. The conditionally bound variables in a graph pattern P w.r.t. X, denoted by $\mathrm{cbvars}\mathrm{(}\mathit{P}|\mathit{X}\mathrm{)}$ , is a subset of the variables in P (i.e., $\mathrm{cbvars}\mathrm{(}\mathit{P}|\mathit{X}\mathrm{)}\subseteq \mathrm{vars}\mathrm{(}\mathit{P}\mathrm{)}$ ) that is defined recursively as given in Table 1.

Example 27.

The conditionally bound variables in the PP pattern ${\mathit{P}}_{\mathsf{\text{E17}}}=⟨?\mathit{v}\mathrm{,}\mathsf{\text{knows}}\mathrm{,}\mathsf{\text{Tim}}⟩$ w.r.t. the empty set of variables can be determined based on line 2 in Table 1, and we obtain: $\mathrm{cbvars}\mathrm{(}{\mathit{P}}_{\mathsf{\text{E17}}}|\varnothing \mathrm{)}=\varnothing$ . However, if we use the set $\{?\mathit{v}\}$ instead, then, by line 1 in Table 1, we obtain: $\mathrm{cbvars}\mathrm{(}{\mathit{P}}_{\mathsf{\text{E17}}}|\{?\mathit{v}\}\mathrm{)}=\{?\mathit{v}\}$ .

Example 28.

As another example consider the graph pattern ${\mathit{P}}_{\mathsf{\text{E23}}}=\mathrm{(}⟨\mathsf{\text{Bob}}\mathrm{,}\mathsf{\text{knows}}\mathrm{,}?\mathit{v}⟩\mathsf{\text{AND }}⟨?\mathit{v}\mathrm{,}\mathsf{\text{knows}}\mathrm{,}\mathsf{\text{Tim}}⟩\mathrm{)}$ for which we obtain $\mathrm{cbvars}\mathrm{(}{\mathit{P}}_{\mathsf{\text{E23}}}|\varnothing \mathrm{)}=\{?\mathit{v}\}$ by using line 10 in Table 1 and the following facts:

$\mathrm{cbvars}\mathrm{(}⟨\mathsf{\text{Bob}}\mathrm{,}\mathsf{\text{knows}}\mathrm{,}?\mathit{v}⟩|\varnothing \mathrm{)}=\{?\mathit{v}\}$ ,

$\mathrm{sbvars}\mathrm{(}⟨\mathsf{\text{Bob}}\mathrm{,}\mathsf{\text{knows}}\mathrm{,}?\mathit{v}⟩\mathrm{)}=\{?\mathit{v}\}$ ,

$\mathrm{cbvars}\mathrm{(}⟨?\mathit{v}\mathrm{,}\mathsf{\text{knows}}\mathrm{,}\mathsf{\text{Tim}}⟩|\{?\mathit{v}\}\mathrm{)}=\{?\mathit{v}\}$ .

We note that for the pattern ${\mathit{P}}_{\mathsf{\text{E17}}}$ , which is not Web-safe under context-based semantics (as discussed in Example 17), we have $\mathrm{cbvars}\mathrm{(}{\mathit{P}}_{\mathsf{\text{E17}}}|\varnothing \mathrm{)}\ne \mathrm{vars}\mathrm{(}{\mathit{P}}_{\mathsf{\text{E17}}}\mathrm{)}$ , whereas for the pattern ${\mathit{P}}_{\mathsf{\text{E23}}}$ , which is Web-safe under context-based semantics (cf. Example 23), we have $\mathrm{cbvars}\mathrm{(}{\mathit{P}}_{\mathsf{\text{E23}}}|\varnothing \mathrm{)}=\mathrm{vars}\mathrm{(}{\mathit{P}}_{\mathsf{\text{E23 }}}\mathrm{)}$ . This example seems to suggest that, if all variables of a graph pattern are conditionally bound w.r.t. the empty set of variables, then the graph pattern is Web-safe under context-based semantics. The following result verifies this hypothesis.

Theorem 29.

A graph pattern P is Web-safe under context-based semantics if $\mathrm{cbvars}\mathrm{(}\mathit{P}|\varnothing \mathrm{)}=\mathrm{vars}\mathrm{(}\mathit{P}\mathrm{)}$ .

Before proving Theorem 29 in the remainder of this section, we emphasize the following observation.

Note 30.

Due to the recursive nature of Definition 26, the condition $\mathrm{cbvars}\mathrm{(}\mathit{P}|\varnothing \mathrm{)}=\mathrm{vars}\mathrm{(}\mathit{P}\mathrm{)}$ (as used in Theorem 29) is decidable for any graph pattern P.

To prove Theorem 29 we aim to provide an algorithm that evaluates graph patterns recursively by passing (intermediate) solution mappings to recursive calls. To capture the desired results of each recursive call formally, we introduce a special evaluation function for a graph pattern P over a Web of Linked Data W that takes a solution mapping μ as input and returns only the solutions of P over W that are compatible with μ (recall from Section 3.1 that the compatibility of two solution mappings, ${\mathit{\mu }}_1$ and ${\mathit{\mu }}_2$ , is denoted by ${\mathit{\mu }}_1\sim {\mathit{\mu }}_2$ ).

Definition 31.

Let P be a graph pattern, let W be a Web of Linked Data, and let $⟨\mathrm{\Omega }\mathrm{,}\mathit{card}⟩=⟦\mathit{P}{⟧}_{\mathit{W}}^{\mathtt{\text{ctx}}}$ . Given a solution mapping μ, the μ-restricted evaluation of P over W under context-based semantics, denoted by $⟦\mathit{P}|\mathit{\mu }{⟧}_{\mathit{W}}^{\mathtt{\text{ctx}}}$ , is the multiset of solution mappings $⟨{\mathrm{\Omega }}^{\prime }\mathrm{,}{\mathit{card}}^{\prime }⟩$ with ${\mathrm{\Omega }}^{\prime }=\{{\mathit{\mu }}^{\prime }\in \mathrm{\Omega }|{\mathit{\mu }}^{\prime }\sim \mathit{\mu }\}$ and ${\mathit{card}}^{\prime }$ is the restriction of $\mathit{card}$ to  ${\mathrm{\Omega }}^{\prime }$ , i.e., for every solution mapping ${\mathit{\mu }}^{\prime }\in {\mathrm{\Omega }}^{\prime }$ we have ${\mathit{card}}^{\prime }\mathrm{(}{\mathit{\mu }}^{\prime }\mathrm{)}=\mathit{card}\mathrm{(}{\mathit{\mu }}^{\prime }\mathrm{)}$ .

The following lemma shows the existence of the aforementioned recursive algorithm.

Lemma 32.

Let P be a graph pattern and ${\mathit{\mu }}_{\mathsf{in}}$ be a solution mapping. If $\mathrm{cbvars}\mathrm{(}\mathit{P}|\mathrm{dom}\mathrm{(}{\mathit{\mu }}_{\mathsf{in}}\mathrm{)}\mathrm{)}=\mathrm{vars}\mathrm{(}\mathit{P}\mathrm{)}$ , then there exists an algorithm that, for any finite Web of Linked Data  $\mathit{W}=⟨\mathit{D}\mathrm{,}\mathit{adoc}⟩$ , has the following three properties:

The algorithm computes $⟦\mathit{P}|{\mathit{\mu }}_{\mathsf{in}}{⟧}_{\mathit{W}}^{\mathtt{\text{ctx}}}$ .

During its execution, the algorithm looks up only a finite number of IRIs (that is, conceptually, the algorithm invokes function $\mathit{adoc}$ only a finite number of times).

Neither the set D nor the set ${\mathrm{dom}}^{\perp ̸}\mathrm{(}\mathit{adoc}\mathrm{)}$ is required as input for the algorithm (hence, the algorithm does not require any a priori information about W).

Before proving the lemma (and Theorem 29), we point out two important properties of Definition 31. First, it is easily seen that, for any graph pattern P and Web of Linked Data W, $⟦\mathit{P}|{\mathit{\mu }}_{\varnothing }{⟧}_{\mathit{W}}^{\mathtt{\text{ctx}}}=⟦\mathit{P}{⟧}_{\mathit{W}}^{\mathtt{\text{ctx}}}$ , where ${\mathit{\mu }}_{\varnothing }$ is the empty solution mapping with $\mathrm{dom}\mathrm{(}{\mathit{\mu }}_{\varnothing }\mathrm{)}=\varnothing$ . Consequently, given an algorithm, say A, that, for P and ${\mathit{\mu }}_{\varnothing }$ , has the properties of the algorithm described by Lemma 32, a trivial algorithm that can be used to prove Theorem 29 may simply call algorithm A and return the result of this call (a more detailed discussion of this approach follows in the proof of Theorem 29 below). Second, for any PP pattern $⟨\mathit{\alpha }\mathrm{,}\mathtt{\text{path}}\mathrm{,}\mathit{\beta }⟩$ and Web of Linked Data W, if α is a variable and $\mathtt{\text{path}}$ is a PP expression that corresponds to one of the first two cases in the grammar in Section 3.1 (i.e., the two base cases), then $⟦\mathit{P}|\mathit{\mu }{⟧}_{\mathit{W}}^{\mathtt{\text{ctx}}}$ is empty for every solution mapping μ that binds (variable) α to a literal or a blank node. Formally, we show the latter as follows.

Lemma 33.

Let $?\mathit{v}\in \mathcal{V}$ be a variable, P be a PP pattern of the form $⟨?\mathit{v}\mathrm{,}\mathit{u}\mathrm{,}\mathit{\beta }⟩$ or $⟨?\mathit{v}\mathrm{,}!\mathrm{(}{\mathit{u}}_1|\dots |{\mathit{u}}_{\mathit{n}}\mathrm{)}\mathrm{,}\mathit{\beta }⟩$ with $\mathit{u}\mathrm{,}{\mathit{u}}_1\mathrm{,}\dots \mathrm{,}{\mathit{u}}_{\mathit{n}}\in \mathcal{I}$ , and μ be a solution mapping. If $?\mathit{v}\in \mathrm{dom}\mathrm{(}\mathit{\mu }\mathrm{)}$ and $\mathit{\mu }\mathrm{(}?\mathit{v}\mathrm{)}\in \mathrm{(}\mathcal{B}\cup \mathcal{L}\mathrm{)}$ , then, for any Web of Linked Data W, $⟦\mathit{P}|\mathit{\mu }{⟧}_{\mathit{W}}^{\mathtt{\text{ctx}}}$ is the empty multiset (of solution mappings).

Proof (Lemma 33).

Recall that for any IRI u and any Web of Linked Data W, every triple in the context ${\mathrm{C}}^{\mathit{W}}\mathrm{(}\mathit{u}\mathrm{)}$ has IRI u as its subject. As a consequence, for any Web of Linked Data W, every solution mapping in $⟦\mathit{P}{⟧}_{\mathit{W}}^{\mathtt{\text{ctx}}}$ binds variable  $?\mathit{v}$ to some IRI (and not to a literal or a blank node); that is, formally, for every ${\mathit{\mu }}^{\prime }\in ⟦\mathit{P}{⟧}_{\mathit{W}}^{\mathtt{\text{ctx}}}$ we have ${\mathit{\mu }}^{\prime }\mathrm{(}?\mathit{v}\mathrm{)}\in \mathcal{I}$ . Therefore, if $?\mathit{v}\in \mathrm{dom}\mathrm{(}\mathit{\mu }\mathrm{)}$ and $\mathit{\mu }\mathrm{(}?\mathit{v}\mathrm{)}\in \mathrm{(}\mathcal{B}\cup \mathcal{L}\mathrm{)}$ , then none of the solution mappings in $⟦\mathit{P}{⟧}_{\mathit{W}}^{\mathtt{\text{ctx}}}$ is compatible with μ, and, thus, $⟦\mathit{P}|\mathit{\mu }{⟧}_{\mathit{W}}^{\mathtt{\text{ctx}}}$ is empty.  □

Algorithm 2

EvalCtxBased $\mathrm{(}\mathit{P}\mathrm{,}{\mathit{\mu }}_{\mathsf{in}}\mathrm{)}$ , which computes $⟦\mathit{P}|{\mathit{\mu }}_{\mathsf{in}}{⟧}_{\mathit{W}}^{\mathtt{\text{ctx}}}$ for a Web of Linked Data W

We use Lemma 33 to prove Lemma 32 as follows.

Proof idea (Lemma 32).

We prove Lemma 32 by induction on the possible structure of graph pattern P. To this end, we provide Algorithm 2 and show that this (recursive) algorithm has the desired properties for any possible graph pattern (i.e., any case of the induction, including the base case). In this paper we focus on a fragment of the algorithm and highlight essential properties thereof. This fragment covers the base case (lines 1–11) and one pivotal case of the induction step, namely, graph patterns of the form  $\mathrm{(}{\mathit{P}}_1\mathsf{\text{AND }}{\mathit{P}}_2\mathrm{)}$ . The complete version of the algorithm and the full proof can be found in our technical report [22].

For the base case (i.e., PP patterns of the form $⟨\mathit{\alpha }\mathrm{,}\mathit{u}\mathrm{,}\mathit{\beta }⟩$ or $⟨\mathit{\alpha }\mathrm{,}!\mathrm{(}{\mathit{u}}_1|\dots |{\mathit{u}}_{\mathit{n}}\mathrm{)}\mathrm{,}\mathit{\beta }⟩$ ), Algorithm 2 looks up at most one IRI (cf. lines 2-5). The crux of showing that the returned result is sound and complete is Lemma 33 and the fact that a triple $⟨\mathit{s}\mathrm{,}\mathit{p}\mathrm{,}\mathit{o}⟩$ with $\mathit{s}\in \mathcal{I}$ can be found only in the context  ${\mathrm{C}}^{\mathit{W}}\mathrm{(}\mathit{s}\mathrm{)}$ .

For PP patterns of the form $\mathrm{(}{\mathit{P}}_1\mathsf{\text{AND }}{\mathit{P}}_2\mathrm{)}$ consider lines 57–72. For sub-patterns ${\mathit{P}}_{\mathit{i}}$ and ${\mathit{P}}_{\mathit{j}}$ as used in this part of the algorithm, we may use Definition 26 to show that (i)  $\mathrm{cbvars}\mathrm{(}{\mathit{P}}_{\mathit{i}}|\mathrm{dom}\mathrm{(}{\mathit{\mu }}_{\mathsf{in}}\mathrm{)}\mathrm{)}=\mathrm{vars}\mathrm{(}{\mathit{P}}_{\mathit{i}}\mathrm{)}$ and (ii)  $\mathrm{cbvars}\mathrm{(}{\mathit{P}}_{\mathit{j}}|\mathrm{dom}\mathrm{(}{\mathit{\mu }}_{\mathsf{in}}\mathrm{)}\cup \mathrm{dom}\mathrm{(}\mathit{\mu }\mathrm{)}\mathrm{)}=\mathrm{vars}\mathrm{(}{\mathit{P}}_{\mathit{j}}\mathrm{)}$ for all $\mathit{\mu }\in {\mathrm{\Omega }}^{{\mathit{P}}_{\mathit{i}}}$ . Therefore, by induction, any recursive call of the algorithm in line 61 and line 63 looks up a finite number of IRIs and returns the expected (sound and complete) result; that is, $⟨{\mathrm{\Omega }}^{{\mathit{P}}_{\mathit{i}}}\mathrm{,}{\mathit{card}}^{{\mathit{P}}_{\mathit{i}}}⟩=⟦{\mathit{P}}_{\mathit{i}}|{\mathit{\mu }}_{\mathsf{in}}{⟧}_{\mathit{W}}^{\mathtt{\text{ctx}}}$ and $⟨{\mathrm{\Omega }}^{\mathit{\mu }}\mathrm{,}{\mathit{card}}^{\mathit{\mu }}⟩=⟦{\mathit{P}}_{\mathit{j}}|{\mathit{\mu }}_{\mathsf{in}}\cup \mathit{\mu }{⟧}_{\mathit{W}}^{\mathtt{\text{ctx}}}$ for all $\mathit{\mu }\in {\mathrm{\Omega }}^{{\mathit{P}}_{\mathit{i}}}$ . Then, since every $\mathit{\mu }\in {\mathrm{\Omega }}^{{\mathit{P}}_{\mathit{i}}}$ is compatible with every ${\mathit{\mu }}^{\prime }\in {\mathrm{\Omega }}^{\mathit{\mu }}$ and all processed solution mappings are compatible with ${\mathit{\mu }}_{\mathsf{in}}$ , it is easily verified that the computed result is $⟦\mathrm{(}{\mathit{P}}_1\mathsf{\text{AND }}{\mathit{P}}_2\mathrm{)}|{\mathit{\mu }}_{\mathsf{in}}{⟧}_{\mathit{W}}^{\mathtt{\text{ctx}}}$ .  □

We are now ready to prove Theorem 29.

Proof (Theorem 29).

Suppose P is a graph pattern such that $\mathrm{cbvars}\mathrm{(}\mathit{P}|\varnothing \mathrm{)}=\mathrm{vars}\mathrm{(}\mathit{P}\mathrm{)}$ . Then, by using the empty solution mapping ${\mathit{\mu }}_{\varnothing }$ with $\mathrm{dom}\mathrm{(}{\mathit{\mu }}_{\varnothing }\mathrm{)}=\varnothing$ , we have $\mathrm{cbvars}\mathrm{(}\mathit{P}|\mathrm{dom}\mathrm{(}{\mathit{\mu }}_{\varnothing }\mathrm{)}\mathrm{)}=\mathrm{vars}\mathrm{(}\mathit{P}\mathrm{)}$ . Therefore, by Lemma 32, there exists an algorithm, say A, that, for any finite Web of Linked Data  $\mathit{W}=⟨\mathit{D}\mathrm{,}\mathit{adoc}⟩$ , computes $⟦\mathit{P}|{\mathit{\mu }}_{\varnothing }{⟧}_{\mathit{W}}^{\mathtt{\text{ctx}}}$ by looking up a finite number of IRIs only without using the set D or the set ${\mathrm{dom}}^{\perp ̸}\mathrm{(}\mathit{adoc}\mathrm{)}$ as input. We also know that the empty solution mapping ${\mathit{\mu }}_{\varnothing }$ is compatible with any solution mapping. Consequently, by Definition 31, we have $⟦\mathit{P}|{\mathit{\mu }}_{\varnothing }{⟧}_{\mathit{W}}^{\mathtt{\text{ctx}}}=⟦\mathit{P}{⟧}_{\mathit{W}}^{\mathtt{\text{ctx}}}$ for any Web of Linked Data W. Hence, algorithm A can be used to compute $⟦\mathit{P}{⟧}_{\mathit{W}}^{\mathtt{\text{ctx}}}$ for any finite Web of Linked Data W (and during this computation the algorithm looks up a finite number of IRIs only without using D or ${\mathrm{dom}}^{\perp ̸}\mathrm{(}\mathit{adoc}\mathrm{)}$ as input).  □

While the condition given in Theorem 29 is sufficient to identify graph patterns that are Web-safe under context-based semantics, the question that remains is whether it is a necessary condition (i.e., whether it can be used to decide Web-safeness of all graph patterns under context-based semantics). Unfortunately, the answer is no as the following example shows.

Example 34.

For the graph pattern $\mathit{P}=\mathrm{(}{\mathit{P}}_1\mathsf{\text{UNION }}{\mathit{P}}_2\mathrm{)}$ with ${\mathit{P}}_1=⟨{\mathit{u}}_1\mathrm{,}{\mathit{p}}_1\mathrm{,}?\mathit{x}⟩$ and ${\mathit{P}}_2=⟨{\mathit{u}}_2\mathrm{,}{\mathit{p}}_2\mathrm{,}?\mathit{y}⟩$ we note that $\mathrm{cbvars}\mathrm{(}{\mathit{P}}_1|\varnothing \mathrm{)}=\{?\mathit{x}\}$ and $\mathrm{cbvars}\mathrm{(}{\mathit{P}}_2|\varnothing \mathrm{)}=\{?\mathit{y}\}$ , and, thus, $\mathrm{cbvars}\mathrm{(}\mathit{P}|\varnothing \mathrm{)}=\varnothing$ . Hence, the pattern does not satisfy the condition in Theorem 29. Nonetheless, it is easy to see that there exists a (sound and complete) algorithm that, for any finite Web of Linked Data W, computes $⟦\mathit{P}{⟧}_{\mathit{W}}^{\mathtt{\text{ctx}}}$ by looking up a finite number of IRIs only. For instance, such an algorithm, say A, may first use two other algorithms that compute $⟦{\mathit{P}}_1{⟧}_{\mathit{W}}^{\mathtt{\text{ctx}}}$ and $⟦{\mathit{P}}_2{⟧}_{\mathit{W}}^{\mathtt{\text{ctx}}}$ by looking up a finite number of IRIs, respectively. Such algorithms exist by Theorem 29, because $\mathrm{cbvars}\mathrm{(}{\mathit{P}}_1|\varnothing \mathrm{)}=\mathrm{vars}\mathrm{(}{\mathit{P}}_1\mathrm{)}$ and $\mathrm{cbvars}\mathrm{(}{\mathit{P}}_2|\varnothing \mathrm{)}=\mathrm{vars}\mathrm{(}{\mathit{P}}_2\mathrm{)}$ . Finally, algorithm A can generate the (sound and complete) query result $⟦\mathit{P}{⟧}_{\mathit{W}}^{\mathtt{\text{ctx}}}$ by computing the multiset union $⟦{\mathit{P}}_1{⟧}_{\mathit{W}}^{\mathtt{\text{ctx}}}\bigsqcup ⟦{\mathit{P}}_2{⟧}_{\mathit{W}}^{\mathtt{\text{ctx}}}$ , which requires no additional IRI lookups.

The example illustrates that “only if” cannot be shown in Theorem 29. It remains an open question whether there exists an alternative condition for Web-safeness that is both sufficient and necessary (and decidable) and, thus, can be used to decide Web-safeness of all graph patterns under context-based semantics.

7. Experimental comparison

In the previous section we have shown that, when querying Linked Data on the WWW, it is possible for PP-based graph patterns to be evaluated completely under any reachability-based semantics, and, similarly, under the context-based semantics (assuming, for the latter, we use only patterns that have been identified to be Web-safe). Hence, we have shown that – based on these semantics – one can build a system that answers PP-based SPARQL queries over the WWW in a well-defined manner. At this point, a natural question that arises is:

How do these query semantics compare when actually used in practice?

To achieve empirical insights related to this question we conducted an experimental comparison of the context-based semantics and a reachability-based semantics. For this comparison we selected ${\mathit{c}}_{\mathsf{PPMatch}}$ -semantics as an exemplar of the family of reachability-based semantics; as argued in Section 4.2, ${\mathit{c}}_{\mathsf{PPMatch}}$ is very close in nature to the reachability criterion ${\mathit{c}}_{\mathsf{Match}}$ [18] which is commonly used in the literature on Linked Data query execution approaches [19,38] (note that ${\mathit{c}}_{\mathsf{Match}}$ is defined for SPARQL queries constructed from triple patterns, instead of PP patterns).

Fig. 7.

Comparison between context-based semantics and (reachability-based) ${\mathit{c}}_{\mathsf{PPMatch}}$ -semantics on D1.

In the remainder of this section, we specify the experimental setup, describe the experiments, present the measurements, and discuss the experimental results.

7.1. Metrics and experimental setup

The objective of the experimental comparison is to identify the differences between the studied semantics in terms of (i) number of dereferencing operations performed to evaluate a query and (ii) number of solutions in the respective query results, including duplicates (which are possible in our bag semantics as Example 13 illustrates). Hereafter, we refer to these metrics as (i) nderef and (ii) ressize, respectively. Since this paper focuses on possible query semantics rather than on efficient techniques to implement such semantics, performance-related metrics such as query execution time are out of scope of our study.

For the experiments, which we conducted during the days of November 16–28, 2015, we used a prototypical implementation of the studied semantics to execute PP-based SPARQL queries directly on the WWW. To avoid overloading Web servers we introduced a delay of 3 seconds between dereferencing operations. While we did not use any client-side caching of retrieved documents, there may have been Web caches (proxy servers) between our prototypical query clients and the Web servers that host the data discovered and retrieved during the execution of our test queries. Measurements reported in the following are the average of five executions with rounding to the next integer.

7.2. Experiments and measurements

We conducted two different experiments considering two different topical domains of Linked Data on the WWW, namely, distributed social network data (D1) and encyclopedic data about influence relationships between people (D2). Within these domains we focus on navigational queries that we express using PP patterns. The particular queries used for the experiments can be found in Appendix. In the following, we describe the experiments and the queries in more detail, and we present the measurements.

7.2.1. Experiment on D1

In our first experiment we considered the distributed social network of FOAF profiles [14]. Such FOAF profiles typically are RDF documents that people make available online to provide Linked Data that describes themselves in terms of their interests, their works, and, most important for our experiment, references to other people they know. Such references are expressed using triples with the IRI3

³

For the compact representation of IRIs in this section we use the following two prefixes. foaf: <http://xmlns.com/foaf/> and dbo: <http://dbpedia.org/ontology/>.

foaf:knows as predicate and the persons’ IRIs as subject and object (i.e., along the lines of our example Web in Fig. 4). Hence, such triples establish data links between different people’s FOAF profiles. The resulting network of such “foaf:knows links” is thus a part of the Web of Linked Data, and it is the focus of our first experiment. We point out that this experiment is particularly significant due to the truly distributed nature of the FOAF profiles, which typically reside (and get updated) on different servers. Indeed, there is no SPARQL endpoint to query (the live version of) this kind of distributed social network.

In this experiment we use the IRI of Nuno Lopes4 ⁴

http://nunolopes.org/foaf.rdf#me.

in his FOAF profile as a starting point for six queries that retrieve Lopes’ acquaintances from distances 1 to 6, respectively. The measurements obtained by executing these queries under both the context-based semantics and the (reachability-based) ${\mathit{c}}_{\mathsf{PPMatch}}$ -semantics are reported in the charts in Fig. 7; the x-axes list the six queries and the y-axes represent our metrics, nderef and ressize, respectively (reported in log-scale).

By looking at Fig. 7(a), we notice that, under the context-based semantics, nderef is increasing steadily with the (increasing) distance selected in the queries. In contrast, under ${\mathit{c}}_{\mathsf{PPMatch}}$ -semantics, nderef is almost the same for all six queries, and it is significantly higher than under the context-based semantics, even for the distance-6 query. Considering the definition of the reachability criterion  ${\mathit{c}}_{\mathsf{PPMatch}}$ (cf. Definition 10), this observation is not unexpected: While the PP patterns of the six queries differ, they all mention the same IRI in their PP expressions, namely, foaf:knows. Consequently, in all six cases, the same set of documents is reachable by applying ${\mathit{c}}_{\mathsf{PPMatch}}$ as reachability criterion (and using the same seed IRI). Essentially, this set of documents represents the complete strongly connected component of FOAF profiles that contains the profile of the seed IRI. Recall that the data of all these documents must be retrieved to compute query results that are guaranteed to be complete under ${\mathit{c}}_{\mathsf{PPMatch}}$ -semantics; this explains the comparable high number of dereferencing operations. The slight variations of these numbers across the six queries are due to occasional timeouts of dereferencing operations and Web servers that did not always respond during each query execution.

The effect of taking into account more data can be observed by looking at our ressize measurements in Fig. 7(b). Clearly, under ${\mathit{c}}_{\mathsf{PPMatch}}$ -semantics we obtain query results that have a much greater size than the results under the context-based semantics, in particular, for the higher distance queries. This effect, again, is not unexpected. Instead, it can also be seen, on a much smaller scale, in the examples in Section 4 (compare in particular Examples 14 and 16). However, we note that the greater ressize per query under ${\mathit{c}}_{\mathsf{PPMatch}}$ -semantics is due not only to finding paths to additional persons in the data retrieved under ${\mathit{c}}_{\mathsf{PPMatch}}$ -semantics, but also to a greater number of duplicates, which result from finding a greater number of alternative paths to some persons (cf. Example 3).

The only exception, where the query result under both semantics is the same, is the distance-1 query. This query consists only of a single triple pattern with the seed IRI as subject, foaf:knows as predicate, and a variable as object. In the given case of using Nuno Lopes’ IRI as seed, all triples that match this pattern happen to be in the same document (Lopes’ FOAF profile) and, thus, all other documents retrieved under ${\mathit{c}}_{\mathsf{PPMatch}}$ -semantics turn out to not contribute to the query result (which may be different for other seeds).

Fig. 8.

Comparison between context-based semantics and (reachability-based) ${\mathit{c}}_{\mathsf{PPMatch}}$ -semantics on D2.

7.2.2. Experiment on D2

For our second experiment we considered influence relationships between people described in Linked Data that is made available by the DBpedia project [4]. In particular, we focused on the relationships expressed by triples with the IRI dbo:influencedBy as predicate, and we used the IRI of Veno Taufer5

⁵

http://dbpedia.org/resource/Veno_Taufer.

as starting point for six queries that obtain influences of Taufer at distance 1 to 6, respectively. These queries are of the same form as the queries used in the first experiment. However, the main difference w.r.t. the first experiment is that the “dbo:influencedBy links” point only to data in DBpedia. In other words, every document that is reachable according to the reachability criterion ${\mathit{c}}_{\mathsf{PPMatch}}$ (and, thus, has to be retrieved under ${\mathit{c}}_{\mathsf{PPMatch}}$ -semantics) comes from the DBpedia Linked Data server. Hence, with this second experiment we wanted to capture a more dataset-centric scenario, while the first experiment has captured a scenario in which the data to be discovered during query execution is truly distributed all over the WWW. Another important difference is that the dbo:influencedBy links are bidirectional; that is, any triple with predicate dbo:influencedBy can be found in both the document for the subject IRI of the triple and the document for the object IRI.

Due to the availability of these bidirectional data links, the query results under both semantics are the same for each of the six queries (cf. Fig. 8). In contrast, the nderef measurements differ significantly and present the same pattern as observed in the first experiment. In fact, the number of dereferencing operations necessary to guarantee complete results under ${\mathit{c}}_{\mathsf{PPMatch}}$ -semantics is even higher in the second experiment. We explain this observation by the fact that the strongly connected component established by the dbo:influencedBy links is bigger than the component of FOAF profiles in the first experiment. Apparently, this “fact” is known only after the corresponding traversal processes have been performed.

7.3. Discussion of the experimental results

Our experiments indicate that choosing one of the two tested query semantics over the other may have a significant impact in practice. Considering the size of query results first, our experiments show that there are cases in which the query result computed under the context-based semantics is smaller than under the (reachability-based) ${\mathit{c}}_{\mathsf{PPMatch}}$ -semantics. We explain this finding by two important properties that distinguish the context-based semantics from reachability-based semantics such as the ${\mathit{c}}_{\mathsf{PPMatch}}$ -semantics.

First, since it is based on the context selector (cf. Section 4.3), the context-based semantics ignores all the triples from any given document that have a subject IRI different from the IRI whose lookup resulted in retrieving the document. Ignoring such triples significantly decreases the number of paths (of triples) that can be found to match a given PP expression.

Second, the context-based semantics is designed to be very selective in the way the queried Web of Linked Data has to be traversed. More precisely, every traversal step is the result of first discovering a triple in the data of the current context document such that this triple can be used as a next step along a path that eventually may match the given PP expression. As a consequence of enforcing such a behavior, the traversal may not reach some documents that are reached under the ${\mathit{c}}_{\mathsf{PPMatch}}$ -semantics, and some of these documents may happen to contain triples that can be used to compute additional solutions under the ${\mathit{c}}_{\mathsf{PPMatch}}$ -semantics.

Our first experiment shows that this may happen in particular if the region of the Web that a query focuses on has a very heterogeneous link structure with many unidirectional links. On the other hand, if the link structure is more homogeneous, with mostly bidirectional links, then the query results under both semantics are more likely to coincide. Our second experiment presents an extreme case of such a scenario.

The downside of potentially larger query results that may be expected under ${\mathit{c}}_{\mathsf{PPMatch}}$ -semantics is a greater number of dereferencing operations, which implies longer execution times and more network traffic generated. Our experiments provide remarkable evidence that this problem is not negligible. That is, for every query in our experiments the difference w.r.t. the corresponding number of dereferencing operations under the context-based semantics is substantial (up to two orders of magnitude). The fact that we made this observation in both experiments also shows that a greater number of dereferencing operations under ${\mathit{c}}_{\mathsf{PPMatch}}$ -semantics is not a peculiarity of traversing an either more homogeneous or more heterogeneous link structure.

The significantly smaller number of dereferencing operations may be seen as a crucial advantage of the context-based semantics over the ${\mathit{c}}_{\mathsf{PPMatch}}$ -semantics. The flip side of course is that users of systems that implement the context-based semantics may see query results with less solutions. Hence, choosing among the two semantics is a question of whether a user is willing to accept the price of possibly having to retrieve many more documents (and, thus, longer execution times) for the chance of seeing a greater number of solutions.

8. Concluding remarks

This paper studies the problem of extending the scope of the Property Paths feature in SPARQL to query Linked Data that is distributed on the WWW. We have investigated reachability-based query semantics, which decouple navigation from querying. Additionally, we have proposed a different interpretation for PPs over the Web via the context-based query semantics. An interesting finding regarding this latter semantics is that there exist queries whose evaluation over the WWW is not possible in practice. We studied this aspect using a notion of Web-safeness and introduced a decidable syntactic property for identifying queries that are Web-safe under the context-based semantics. Moreover, we have presented an experimental evaluation that compares the two semantics on different datasets showing that the context-based semantics incurs in a lower number of dereferencing operations that will have an impact on the running time.

We believe that the presented work provides valuable input to a wider discussion about defining how the SPARQL language can be used for accessing Linked Data on the WWW. There are several directions for future research including an investigation of the relationships between navigational queries and SPARQL federation, as well as an exploration of techniques based on which query execution systems may implement efficiently the machinery developed in this paper.