Introduction

SPARQL as a standard query language for the Semantic Web data has been the subject of many theoretical and practical works in over the last years. Upon version 1.0 of its standardisation, works have been published on its expressivity [2,8,10,11] and on adding features, among others value creation and subqueries [2,9].

These features have been taken on board in version 1.1 of the SPARQL specification. The first feature corresponds to an extension of SPARQL select queries, allowing SELECT clauses to assign values (i.e., blank nodes, literals or IRIs) to particular variables, by means of a new keyword AS. But more importantly, SPARQL 1.1 now permits the use of subqueries, that is, select queries can be arbitrarily nested within WHERE clauses [4,Section 12].

To showcase these operators, let us start from the following simple SPARQL 1.0 query that essentially replaces all object values in a given graph with blank nodes: While nested select queries are allowed in SPARQL 1.1, other forms of subqueries such as nested CONSTRUCT queries in FROM clauses, as proposed in [2,9], were not included to the new specification under the-unproven-conjecture that select subqueries can express nested construct queries. 5For instance, consider the following query Q that uses nested constructs:

CONSTRUCT { ?X ex:goodFriend ?Y } FROM { CONSTRUCT { ?U ex:friends ?V } WHERE { ?U foaf:knows ?V . ?U ex:worksWith ?V } } WHERE { ?X ex:friends ?Y . ?X ex:friends ?Z . ?Y ex:friends ?Z }.

The intention of this query is to construct first an RDF document where a person U is a friend of V if U knows V and U works together with V. This is done by means of the inner construct subquery of Q. In essence, we have replaced and rewritten each of the triples in the outer WHERE clause for the conditions in the inner construct query that give rise to these triples, as it is for instance commonly done in query rewriting using views [1].

But can this idea be generalised for all nested construct queries? That is, is it true that given any SPARQL query Q that uses nested CONSTRUCT one can find a query in SPARQL 1.1 (without nested CONSTRUCT) that is equivalent to Q? This question was considered in [7], with a positive answer for a restricted case of SPARQL queries where one disallows blank nodes in templates and only uses the functionalities in SPARQL 1.0. On the other hand, it was shown that there are some queries with nested CONSTRUCT that cannot be expressed as a SPARQL 1.0 query (this follows from the close connection between construct queries and data exchange [3]). However, the results in [7] consider a much weaker language, because they do not consider any of the SPARQL 1.1 operators, and in particular the binding of variables in SELECT subqueries.

In this paper we show that by allowing full SPARQL 1.1 one can indeed express nested construct queries, that is, in other words, the language of SPARQL 1.1 construct queries is composable. However, our result, just as [7], assumes set semantics, contrary to bag semantics in the specification. Also, our rewriting, even if polynomial when just one construct query is nested in another, is exponential in the depth of nesting. Moreover, it is quite cumbersome and unintuitive. Nevertheless, this is the first step in proving the conjecture that nested SELECT queries are indeed the right notion for subqueries in SPARQL. We do believe that looking at set semantics is a natural and important first step in the direction of this work.

The plan of this paper is as follows: after formalisation of SPARQL 1.1 in Section 2, we define the notion of composability in Section 3, present our rewriting in Section 4, and conclude in Section 5.

SPARQL Algebra

We next recapitulate the SPARQL algebra as well as basic notions on RDF.

RDF Graphs Let I, L, and B be countably infinite pairwise disjoint sets of IRIs, literals, and blank nodes, respectively, where literals include numbers, strings, and Boolean values true and false. The set of (RDF) terms T is I ∪ L ∪ B. An (RDF) triple is an element (s, p, o) of (I ∪ B) × I × T where s is called the subject, p the predicate, and o the object. An (RDF) graph is a finite set of RDF triples.

SPARQL Algebra Syntax

We concentrate on the core of SPARQL 1.1 and build upon the formalisation by [8]. We distinguish three types of syntactic building blocksfilter expressions, patterns, and queries, built over terms T and an infinite set V = {?x, ?y, . . .} of variables, disjoint from T as defined next.

(Filter) expressions are defined inductively as follows: -all variables in V and all terms in I ∪ L are expressions, -bNode() and IRINode(b), for b ∈ B, are expressions, -if ?x is a variable in V then bound(?x) is an expression, -if R 1 is an expression then so are isBlank(R 1 ), isIRI(R 1 ) and isLiteral(R 1 ), -if also R 2 is an expression then so are (R

1 = R 2 ), (R 1 < R 2 ), (¬R 1 ), (R 1 ∧ R 2 ), -if also R 3 is an expression, then so is if(R 1 , R 2 , R 3 ). We use expressions R 1 ∨ R 2 , R 1 → R 2 and R 1 ↔ R 2 as abbreviations for ¬(¬R 1 ∧ ¬R 2 ), ¬R 1 ∨ R 2 and (R 1 ∧ R 2 ) ∨ (¬R 1 ∧ ¬R 2 ), respectively. A triple pattern is a triple in (I ∪ L ∪ V) × (I ∪ V) × (I ∪ L ∪ V).

Then, (graph) patterns are inductively defined as follows:

-a BGP, that is a possibly empty set of triple patterns, is a pattern; -if P 1 and P 2 are patterns, then so are P 1 AND P 2 and P 1 UNION P 2 ; -if also R is an expression, then P 1 FILTER R and P 1 OPT R P 2 are patterns; -if also ?x is a variable not appearing in P 1 , then

P 1 BIND R AS ?x is a pattern; -if also X is a set of variables, then SELECT X WHERE R is a pattern.

If a pattern is of the form SELECT X WHERE R then the set of its free variables is X; otherwise, it is the union of the free variables of all its immediate subpatterns and, in case of P 1 BIND R AS ?x, of the singleton set {?x}.

Finally, there are several types of queries in SPARQL. Most commonly used and studied are select queries, which are just patterns in our formalisation. In this paper, however, we concentrate on construct queries of the form

CONSTRUCT H WHERE P,

where H is a set of triples from (T ∪ V) × (I ∪ V) × (T ∪ V), called template, and P is a pattern. For S a pattern, condition, template, etc., let IRI(S), blank(S) and var(S) denote all the IRIs, blank nodes and variables, respectively, that appear in S.

The standard includes several other constructs besides the ones defined above. Some of them, such as subqueries in expressions (i.e., Exists in filters), VALUES and MINUS are easily (and polynomially) expressible, under set semantics, adopted here (see below), via the core operators [5,6]. Others, such as the named graph operator GRAPH and property paths, are immaterial to our research and omitted for brevity. Finally, note that filter expression IRINode(b), whose intention is to create a fresh IRI for each blank node b, does not appear in SPARQL 1.1. However, this operator can be expressed in our formalisation, provided it additionally include the string concatenation operator as well as casting operators from strings to IRIs and back, which are present in the specification.

To distinguish SPARQL 1.1 as in the standard and our formalisation we denote S C the language of construct queries as in the latter.

SPARQL Algebra Semantics

The semantics of patterns in S C is defined in terms of (solution) mappings, that is, partial functions µ from variables V to terms T. The domain of µ, denoted dom(µ), is the set of variables over which µ is defined. Mappings µ 1 and µ 2 are compatible, written µ 1 ∼ µ 2 , if µ 1 (?x) = µ 2 (?x) for each ?x in dom(µ 1 ) ∩ dom(µ 2 ). If µ 1 ∼ µ 2 , then µ 1 ∪ µ 2 is the mapping obtained by extending µ 1 according to µ 2 on all the variables in dom(µ 2 ) \ dom(µ 1 ).

The evaluation [[R]] µ of an expression R in S C with respect to a mapping µ is a value in T ∪ {error}, where error is a special symbol not in T, defined as follows:

-

[[?x]] µ is µ(?x) if ?x ∈ dom(µ)-[[isBlank(R 1 )]] µ , [[isIRI(R 1 )]] µ , and [[isLiteral(R 1 )]] µ are true if [[R 1 ]] µ ∈ B, [[R 1 ]] µ ∈ I, and [[R 1 ]] µ ∈ L, respectively, and false otherwise; -[[R 1 • R 2 ]] µ , for a comparison operator •, is [[R 1 ]] µ • [[R 2 ]] µ if [[R 1 ]] µ and [[R 2 ]] µ

are both not error and of suitable types, or error otherwise; -

[[¬R 1 ]] µ is true if [[R 1 ]] µ = false, it is false if [[R 1 ]] µ = true, and it is error otherwise, while [[R 1 ∧ R 2 ]] µ is true if [[R 1 ]] µ = [[R 2 ]] µ = true, it is false if [[R 1 ]] µ or [[R 2 ]] µ is false, and it is error otherwise; -[[if(R 1 , R 2 , R 3 )]] µ = [[R 2 ]] µ if [[R 1 ]] µ = true, it is [[R 3 ]] µ if [[R 1 ]] µ = false,

and error otherwise. The semantics of patterns over a graph G is defined as follows, where µ(P ) is the pattern obtained from P by replacing its variables according to µ:

-

[[P ]] G = µ : var(P ) → T | µ(P ) ⊆ G for a BGP P ; -[[P 1 AND P 2 ]] G = µ | µ 1 ∈ [[P 1 ]] G , µ 2 ∈ [[P 2 ]] G , µ = µ 1 ∪ µ 2 ; -[[P 1 UNION P 2 ]] G = [[P 1 ]] G ∪ [[P 2 ]] G ; -[[P 1 FILTER R]] G = µ | µ ∈ [[P 1 ]] G , [[R]] µ = true ; -[[P 1 OPT R P 2 ]] G = [[P 1 AND P 2 ]] G ∪ µ | µ ∈ [[P 1 ]] G , ∀µ 2 ∈ [[P 2 ]] G . µ ∼ µ 2 or [[R]] µ∪µ2 = false ; -[[P BIND R AS ?x]] G = µ | µ ∈ [[P ]] G , µ = µ ∪ {?x → [[R]] µ }, [[R]] µ = error ∪ µ | µ ∈ [[P ]] G , [[R]] µ = error ; -[[SELECT X FROM P 1 ]] G = µ | µ = µ | X , µ ∈ [[P 1 ]] G }, where µ | X is a restriction of µ to X.

To define the semantics of construct queries in S C fix, for every template H and graph G, a family F (H, G) of renaming functions. This family contains, for every mapping µ from var(H) to T, an injective function f µ : blank(H) → B \ blank(G). These functions must have pairwise disjoint ranges (i.e., there are no b and b such that

f µ1 (b) = f µ2 (b ) for different µ 1 and µ 2 ). Then, [[CONSTRUCT H WHERE P ]] G = {µ(f µ (t)) | µ ∈ [[G]] P , t is a triple in H and µ(f µ (t)) is well-formed},

where f µ is the corresponding renaming function for µ in F (H, G). Here, a triple is well-formed if it is indeed an RDF triple, that is, does not have a blank node as predicate, literal as subject, etc. 6Note that we adopt set semantics, contrary to bag (multi-set) semantics in the specification. We leave the consideration of bag semantics for future work.

Definitions and Problem Statement

In this paper we address the question of composability of SPARQL. Definition 1. A query language L with the same input and output domains D is composable if for any queries q 1 , q 2 ∈ L there is a query q ∈ L such that q 2 (q 1 (D)) = q(D) for any D ∈ D, where q (D ) is the output of a query q on an input D .

The language of SPARQL select queries does not satisfy the requirements in this definition, because its input domain is RDF graphs and its output domain is sets of mappings. However, the language of SPARQL construct queries does satisfy the requirements, because its inputs, the set of RDF graphs, are its outputs as well; therefore, this is the subject of inquiry of this paper.

Note, however, that whether

[[Q 2 ]] [[Q1]] G = [[Q]] G holds, for construct queries Q 1 , Q 2 and

Q, depends on the particular blank-node generating functions in the definitions of the semantics of bNode() and construct templates. Since the intuitive meaning of blank nodes is to represent existentially quantified named nulls whose exact names are immaterial, we silently consider RDF graphs and sets of mappings up to isomorphism, that is, up to bijective renaming of blank nodes. In this way checking whether

[[Q 2 ]] [[Q1]] G is equivalent to [[Q]

] G under such renaming does not depend on the particular choice of the generating functions.

As it is mentioned in the introduction, the question of composability of construct queries was considered in [7], and it was shown, using techniques from data exchange [3], that these queries are not composable. However, the language considered in this previous work is different from ours, because it includes neither the BIND operator nor the bNode() and IRINode(b) functions. The main result of this paper is the following theorem, which shows that the negative result does not extend to S C . Theorem 1. The language S C of construct queries is composable.

Composability of Construct Queries

Consider the following queries in language S C described in Section 2.

Q 1 = CONSTRUCT H 1 WHERE P 1 , Q 2 = CONSTRUCT H 2 WHERE P 2 .

In the rest of the paper we explain how to rewrite these queries to just one query

Q = CONSTRUCT H 2 WHERE P, also in S C , such that [[Q 2 ]] [[Q1]] G = [[Q]]

G for any graph G. Since we apply Q 2 to the result of Q 1 , we call these queries the outer and the inner, respectively.

Note that the template of the rewriting Q is the template of the outer query Q 2 . The pattern P of Q is defined as P unif (P blank , P rew ) for patterns P unif , P blank , and P rew , with the former taking the latter two as parameters (i.e., subpatterns). Next we define these patterns and study their properties. It is important to mention that rewriting Q is always of polynomial size in the size of Q 1 and Q 2 (but the rewriting is exponential in the number of queries we nest in this fashion). Without loss of generality we assume that all local (not free) variables in different SELECT subpatterns of P 1 and P 2 have different names; and that var(P 1 )∩var(P 2 ) = ∅ (we can always achieve this by renaming). In what follows we denote the variables in var(P 1 ) and in var(P 2 ) by ?x and ?y, respectively (both possibly with subscripts). We also assume that P 2 does not use any BIND sub-patterns; it is possible to cover the general case by a construction similar to the one described below, but the notation becomes more elaborated.

We start with P blank . The idea of this pattern is to produce the same set of mappings as P 1 except that each of them is extended to new variables bound to fresh blank nodes, one variable for each blank node in H 1 . To this end, let ?b 1 , . . . , ?b l be fresh variables, for l the size of blank(H 1 ). Then

P blank = P 1 BIND bNode() AS ?b 1 . . . BIND bNode() AS ?b l .

The following property of P blank follows from the definition of the BIND operator (recall that we consider sets of mappings up to renaming of blank nodes).

Lemma 1. For each mapping µ, let λ µ map each ?b i , 1 ≤ i ≤ l, to a fresh blank node. Then, for any graph G, we have that

[[P blank ]] G = {µ 1 | µ 1 = µ ∪ λ µ , µ ∈ [[P 1 ]] G }.

For space reasons we cannot give a complete example of our construction, but we have uploaded one at http://web.ing.puc.cl/˜jreutter/construct/.

Our results confirm the fact that nested CONSTRUCT queries are, in theory, an unnecessary feature of SPARQL, at least concerning set semantics. However, our construction introduces a blowup when translating from nested CONSTRUCT to SPARQL 1.1, which can be exponential in the depth of nesting. We conjecture that this blowup is unavoidable in the worst case. But even if this blowup was not important, the rewriting appears to be a very deep and technical translation, and unfortunately it is not easy to discover the intentions of nested CONSTRUCT queries simply by looking at their translation. For this reason we believe that nested CONSTRUCT queries are actually a desired feature of SPARQL. As a future work we would like to investigate update queries in SPARQL. Since we conjecture that update queries can be expressed as nested construct queries, it would be conceivable that the former are also a replaceable (but welcome) addition of SPARQL 1.1.