Copyright © 2009 by DERI Galway at the National University of Ireland, Galway, Ireland.
This work is supported by Science Foundation Ireland under grants number SFI/02/CE1/I131 and SFI/08/CE/I1380 and under the European Commission European FP6 project inContext (IST034718).
This document is available under the W3C Document License. See the W3C Intellectual Rights Notice and Legal Disclaimers for additional information.
XSPARQL is a query language combining XQuery and SPARQL for transformations between RDF and XML. This document defines the semantics of XSPARQL.
This section describes the status of this document at the time of its publication. Other documents may supersede this document. A list of current W3C publications can be found in the W3C technical reports index at http://www.w3.org/TR/.
This document is a part of the XSPARQL Submission which comprises five documents:
By publishing this document, W3C acknowledges that the Submitting Members have made a formal Submission request to W3C for discussion. Publication of this document by W3C indicates no endorsement of its content by W3C, nor that W3C has, is, or will be allocating any resources to the issues addressed by it. This document is not the product of a chartered W3C group, but is published as potential input to the W3C Process. A W3C Team Comment has been published in conjunction with this Member Submission. Publication of acknowledged Member Submissions at the W3C site is one of the benefits of W3C Membership. Please consult the requirements associated with Member Submissions of section 3.3 of the W3C Patent Policy. Please consult the complete list of acknowledged W3C Member Submissions.
This document defines the semantics of XSPARQL based on the XQuery semantics [XQUERYSEMANTICS]. Each pragmafree XQuery is an XSPARQL query and has the same result under both XQuery and XSPARQL semantics.
The semantics of XSPARQL follows the formal treatment of the XQuery semantics [XQUERYSEMANTICS]. We adopt the notation provided there and define XSPARQL semantics by means of respective normalization mapping rules and inference rules.
We define dynamic evaluation inference rules for a new builtin function fs:sparql which evaluates SPARQL queries according to the SPARQL semantics, cf. [SPARQL]. Other modifications include normalization of the XSPARQL constructs to XQuery expressions. This means that we do do not need new grammar productions but only those defined in the XQuery Core syntax.
The XSPARQL syntax [XSPARQLLANGUAGE] defines, together with the XQuery FLWOR expression, a new forloop for iterating over SPARQL results: SparqlForClause. This object stands at the same level as XQuery's for and let expressions, i.e., such type of clauses are allowed to start new FLWOR' expressions, or may occur inside nested XSPARQL queries.
To this end, our new normalization mapping rules [·]_{Expr'} inherit from the definitions of XQuery's [·]_{Expr} mapping rules and overload some expressions to accommodate XSPARQL's new syntactic objects. The semantics of XSPARQL expressions hence stands on top of XQuery's semantics.
A single SparqlForClause is normalized as follows:


==  

Here, [·]_{SparqlQuery} and [·]_{SparqlResult} are auxiliary mapping rules for expanding the given expressions:
[$VarName]_{SparqlResult} 
== 
let $_VarName_Node := $_aux_result/_sparql_result:binding[@name = "VarName"] let $VarName := data($_VarName_Node/*) let $_VarName_NodeType := name($_VarName_Node/*) let $_VarName_NodeDatatype := string($_VarName_Node/*/@datatype) let $_VarName_NodeLang := string($_VarName_Node/*/@lang) let $_VarName_RDFTerm := _rdf_term($_VarName_Node) 
here, for each SPARQL variable:
and
 
==  

The function _rdf_term($_VarName_Node) is defined as follows:
statEnv  $_VarName_Node bound  
[_rdf_term($_VarName_Node)]_{Expr} =  

We now define the meaning of fs:sparql. It is, following the style of [XQUERYSEMANTICS], an abstract function which returns a SPARQL query result XML document [SPARQLPROTOCOL] expected as the result of a SPARQL select query. I.e., the result of fs:sparql conforms to the XML Schema definition http://www.w3.org/2007/SPARQL/result.xsd. We further assume that the _sparql_result: namespace is declared implicitly in each XSPARQL query and tied to the namespace URI http://www.w3.org/2007/SPARQL/result#.
fs:sparql($query as xs:string) as documentnode(schemaelement(_sparql_result:sparql))
Firstly, fs:sparql implicitly expands PrefixedNames within the SPARQL query string it is given, according to the namespace declarations in the prolog of XSPARQL queries.
Static typing rules apply here according to the rules given in the XQuery semantics.
The fs:serialize function behaves like
the fn:concat
function on arguments of xs:anyAtomicType
,
cf. [XPATHFUNCT], and serializes arguments bound to
XML nodes to xs:string
by converting them to a corresponding
string in the lexical space of rdf:XMLLiteral as defined in
[RDFCONCEPTS]. This ensures that the structure of
the XML literals is preserved in the output, while the conversion
to xs:string
of fn:concat
only retains the text data
of the XML Literal.
Since this function must be evaluated according to the SPARQL semantics, we need to get the value of fs:sparql in the dynamic evaluation semantics of XSPARQL.
The builtin function fs:sparql applied to Value_{1} yields Value 
dynEnv  function fs:sparql with types (xs:string) on values (Value_{1}) yields Value 
In case of error (for instance, the query string is not syntactically correct, or the DatasetClause cannot be accessed), fs:sparql issues an error:
Value_{1} cannot be evaluated according to SPARQL semantics 
dynEnv  function fs:sparql with types (xs:string) on values (Value_{1}) yields fn:error() 
The only remaining part is defining the semantics of a GroupGraphPattern using our extended [·]_{Expr'}. This mapping rule takes care that variables in scope of XSPARQL expressions are properly substituted using the evaluation mechanism of XQuery. To this end, we assume that [·]_{Expr'} takes expressions in SPARQL's GroupGraphPattern syntax and constructs a sequence of strings and variables, by applying the auxiliary mapping rule [·]_{VarSubst} to each of the graph pattern's variables. This rule looks up bound variables from the static environment and possibly replaces them to variables or to a string expression, where the value of the string is the name of the variable. This has the effect that unbound variables in GroupGraphPattern will be evaluated by SPARQL instead of XQuery. The statical semantics for [·]_{VarSubst} is defined below using the next inference rules. They use the new judgement $VarName bound, which holds if the variable $VarName is bound in the current static environment.
statEnv  $_VarName_RDFTerm bound 
statEnv  [$VarName]_{VarSubst} = [$_VarName_RDFTerm]_{Expr} 
statEnv  $VarName bound statEnv  not($_VarName_RDFTerm bound) 
statEnv  [$VarName]_{VarSubst} = [$VarName]_{Expr} 
statEnv  not($VarName bound) statEnv  not($_VarName_RDFTerm bound) 
statEnv  [$VarName]_{VarSubst} = ["$VarName"]_{Expr} 
Next, we define the normalization of for expressions. In order to handle blank nodes appropriately in construct expressions, we need to decorate the variables of standard XQuery forexpressions with position variables. First, we must normalize forexpressions to core forloops:


==  

Now we can apply our decoration of the core forloops (without position variables) recursively:
[ for $VarName_{i} OptTypeDeclaration_{i} in Expr_{i} ReturnClause ]_{Expr'} 
== 
[for $VarName_{i} OptTypeDeclaration_{i} at $_VarName_{i}_Pos in [Expr_{i}]_{Expr'} [ReturnClause]_{Expr'} ]_{Expr} 
Similarly, let expressions must be normalized as follows:


==  

Now we can recursively apply [·]_{Expr'} on the core letexpressions:
[ let $VarName_{i} OptTypeDeclaration_{i} := Expr_{i} ReturnClause ]_{Expr'} 
== 
[ let $VarName_{i} OptTypeDeclaration_{i} := [Expr_{i}]_{Expr'} [ReturnClause]_{Expr'} ]_{Expr} 
We do not specify where and order by clauses here, as they can be handled similarly as above let and for expressions.
We define now the semantics for the ReturnClause. Expressions of form return Expr are evaluated as defined in the XQuery semantics. Standalone constructclauses are normalized as follows:
[ construct ConstructTemplate ]_{Expr'} 
== 
[ return fs:serialize([ConstructTemplate]_{SubjPredObjList}) ]_{Expr} 
The auxiliary mapping rule [·]_{SubjPredObjlist} rewrites variables and blank nodes inside of ConstructTemplates using the normalization mapping rules [·]_{Subject}, [·]_{PredObjList}, and [·]_{ObjList}. They use the judgements expr is valid subject, valid predicate, and valid object, which holds if the expression expr is, according to the RDF specification [RDFCONCEPTS], a valid subject, predicate, and object, resp: i.e., subjects must be bound and not literals, predicates, must be bound, not literals and not blank nodes, and objects must be bound. If, for any reason, one criterion fails, the triple containing the illformed expression will be removed from the output. Free variables in the construct are unbound, hence triples containing such variables must be removed too. The boundness condition can be checked at runtime by wrapping each variable and FLWOR' into a fn:empty() assertion, which removes the corresponding triple from the ConstructTemplate output. Next, we sketch only some of the normalization rules; the missing rules should be clear from the context:
statEnv  VarOrTerm is valid subject  

[ [ PropertyListNotEmpty ] ]_{SubjPredObjList} 
== 
statEnv  [ fs:serialize("[ ", [PropertyListNotEmpty]_{PredObjectList}, " ]") ]_{Expr} 
statEnv  Verb is valid predicate statEnv  Object_{1} is valid object ⋮ statEnv  Object_{n} is valid object 


Otherwise, if one of the premises is not true, we suppress the generation of this triple. One of the negated rules is the following:
statEnv  not(VarOrTerm is valid subject) 
statEnv  [VarOrTerm PropertyListNotEmpty]_{SubjPredObjList} = [""]_{Expr} 
The normalization for subjects, verbs, and objects according to [·]_{Expr'} is similar to GroupGraphPattern: all variables in it will be replaced using [·]_{VarSubst}.
Blank nodes inside of construction templates must be treated carefully by adding position variables from surrounding for expressions. To this end, we use [·]_{BNodeSubst}. Since we normalize every forloop by attaching position variables, we just need to retrieve the available position variables from the static environment. We assume a new static environment component statEnv.posVars which holds  similar to the statEnv.varType component  all incontext positional variables in the given static environment, that is, the variables defined in the at clause of any enclosing for loop.
statEnv  statEnv.posVars = VarName_{1}_Pos, ..., VarName_{n}_Pos 
statEnv  [_:BNodeName]_{BNodeSubst} = [fs:serialize("_:",BNodeName,"_", VarName_{1}_Pos , ..., VarName_{n}_Pos ) ]_{Expr} 
SPARQL filter expressions in WHERE GroupGraphPattern are evaluated using fs:sparql. But we additionally allow the following functions inherited from SPARQL in XSPARQL:
BOUND($A as xs:string) as xs:boolean isIRI($A as xs:string) as xs:boolean isBLANK($A as xs:string) as xs:boolean isLITERAL($A as xs:string) as xs:boolean LANG($A as xs:string) as xs:string DATATYPE($A as xs:string) as xs:anyURI
The semantics of above functions is defined as follows:
statEnv  $_Varname_Node bound 
statEnv  [BOUND($VarName)]_{Expr'} = [if (fn:empty($_Varname_Node)) then fn:false() else fn:true()]_{Expr} 
statEnv  $_Varname_NodeType bound  

statEnv  $_Varname_NodeType bound  

statEnv  $_Varname_NodeType bound  

statEnv  $_Varname_Node bound 
statEnv  [LANG($VarName)]_{Expr'} = [fn:string($_Varname_Node/@xml:lang)]_{Expr} 
statEnv  $_Varname_Node bound 
statEnv  [DATATYPE($VarName)]_{Expr'} = [$_Varname_Node/@datatype]_{Expr} 
XSPARQL syntactically subsumes XQuery and  taking into account the shortcut notations defined in Section 4 of [XSPARQLLANGUAGE]  SPARQL construct queries. Concerning semantics, XSPARQL equally builds on top of its constituent languages. As shown above, we have extended the formal semantics of XQuery from [XQUERYSEMANTICS] by additional reduction rules which reduce each XSPARQL query to XQuery expressions which operate on results of SPARQL queries in the SPARQL's XML result format [SPARQLPROTOCOL].
Since we add only new reduction rules for SPARQLlike heads and bodies, it is easy to see that each native XQuery is treated in a semantically equivalent way in XSPARQL. The only thing affecting native XSPARQL queries are the "decoration" rules, which however, do not affect the final query result
Proposition 1. Each pragmafree XQuery is an XSPARQL query and has the same result under both XQuery and XSPARQL semantics
Proof (Sketch). As easily seen, given an XSPARQL query falling in the XQuery fragment, the result of our normalization is again an XQuery. Note that, however, even this fragment, our additional rewriting rules do change the original query in some cases. More concretely, what happens is that by our "decoration" rule each positionvariable free for loop (i.e., that does not have an at clause) is decorated with a new position variable. As these new position variables start with an underscore they cannot occur in the original query, so this rewriting does not interfere with the semantics of the original query. The only rewriting rules which use the newly created position variables are those for rewriting blank nodes in construct parts, i.e., the [·]_{BNodeSubst} rule. However, this rule only applies to XSPARQL queries which fall outside the native XQuery fragment.
A similar correspondence holds for native SPARQL queries. Let us now sketch the proof showing the equivalence of XSPARQL's semantics and the evaluation of rewritten SPARQL queries into native XQuery. Intuitively, we "inherit" the SPARQL semantics from the fs:sparql "oracle".
Let Ω denote a solution sequence of a an abstract SPARQL query q =(E, DS, R) where E is a SPARQL algebra expression, DS is an RDF Dataset and R is a set of variables called the query form (cf. [SPARQL]). Then, by SPARQLResult(Ω) we denote the SPARQL result XML format representation of Ω.
We are now ready to state some properties about our transformations. The following proposition states that any SPARQL select query can be equivalently viewed as an XSPARQL F'DWMR query.
Proposition 2. Let q = (E_{WM},DS,$x_{1},...,$x_{n}) be a SPARQL query of the form select $x_{1},...,$x_{n} DWM, where we denote by DS the RDF dataset (cf. [SPARQL]) corresponding to the DatasetClause (D), by G the respective default graph of DS, and by E_{WM} the SPARQL algebra expression corresponding to WM and P be the pattern defined in the where part (W). If eval(DS(G), q) = Ω_{1}, and
Then, Ω_{1} ≡ Ω_{2} modulo representation. Here, by equivalence (≡) modulo representation we mean that both Ω_{1} and Ω_{2} represent the same sequences of (partial) variable bindings.
Proof (Sketch). By the rule
[ for $x_{1} ... $x_{n} from D(G) where P return ($x_{1}, ..., $x_{n}) ]_{Expr'} 
== 
[ let $aux_queryresult := [·]_{SparqlQuery} ... for ... [·]_{SparqlResult} ... return ($x_{1}, ..., $x_{n}) ]_{Expr'} 
[·]_{SparqlQuery} builds q as string without replacing any variable, since all variables in P are free. Then, the resulting string is applied to fs:sparql, which  since q was unchanged  by definition returns exactly SPARQLResult(Ω_{1}), and thus the return part return ($x_{1}, ..., $x_{n}) which extracts Ω_{2} is obviously just a representational variant of Ω_{1}.
By similar arguments, we can see that SPARQL's construct queries are treated semantically equivalent in XSPARQL and in SPARQL, taking into account the shortcut notations defined in Section 4 of [XSPARQLLANGUAGE]. The idea here is that the rewriting rules constructs from Section 2.2 extract exactly the triples from the solution sequence from the body defined as defined in the SPARQL semantics [SPARQL].