SPARQL CDTs: Representing and Querying Lists and Maps as RDF Literals

Abstract

This specification defines an approach to represent generic forms of composite values (lists and maps, in particular) as literals in RDF, and corresponding extensions of the SPARQL language. These extensions include an aggregation function to produce such composite values, functions to operate on such composite values in expressions, and a new operator to transform such composite values into their individual components.

This section is non-normative.

The basis of the approach is to capture composite values (lists and maps) as RDF literals. The components of such a composite value may be RDF terms, including literals representing scalar values (numbers, strings, etc.) as well as literals representing other composite values. The lexical form (i.e., the string representation) of such a literal that represents a composite value contains the components of the composite value serialized in a format that is based on the RDF Turtle format [TURTLE]. For instance, the literals in the object positions of the following three RDF triples represent lists. Notice that, in the lexical form of these literals, the elements of the lists are separated by commas and enclosed in square brackets.

Example 1

ex:s ex:p1 "[ 0.504, 0.344, 0.002, 0.716 ]"^^cdt:List .
ex:s ex:p2 "[ <http://example.org/alice>, <http://example.org/bob> ]"^^cdt:List .
ex:s ex:p3 "[ '1999-08-16'^^<http://www.w3.org/2001/XMLSchema#date>, 42 ]"^^cdt:List .

In addition to lists, the approach considers maps, which are sets of key-value pairs where the keys must be distinct. Within the lexical form, the key-values pairs of such a map are separated by commas and a colon is used as separator between each key and its value, as demonstrated by the literal in the object position of the following triple.

Example 2

ex:s ex:p1 "{ 'name' : 'Tuva', 1: <http://example.org/>, 2: null }"^^cdt:Map .

The previous example also illustrates that, in addition to RDF terms, the approach supports null as a special value to be used within maps, as well as in lists. Moreover, the kinds of elements within each list or map may be mixed arbitrarily (defining strongly-typed variations of the proposed composite datatypes is part of our ongoing work).

As the examples illustrate, list and map elements that are numeric literals (of particular types) can be written using the Turtle-specific shorthand notation (e.g., 0.504 is a shortened version of '0.504'^^<http://www.w3.org/2001/XMLSchema#decimal>), and the same holds for boolean-typed literals. Yet, IRIs cannot be shortened in the ways as are possible in Turtle; instead, within the lexical forms of list and map literals, they must be written as absolute IRIs (which is to avoid loosing the definition of the prefix label or the base IRI when the list and map literals are taken out of context). However, as another form of shorthand notation, our approach allows users to directly nest the lexical forms of lists and maps into one another (but still interpreting such contained lists or maps as literals with the corresponding data type). For instance, the literal in the object position of the following triple represents a map in which both of the key-value pairs have a literal as their value, with one of these literals representing a list and the other one a map.

Example 3

ex:s ex:p1 """{
                'names' : ['Tuva', 'Ada', 'Eva'],
                'address': {
                    'street': 'Harbor St.',
                    'number': 43,
                }
              }"""^^cdt:Map .

The attentive reader may observe that the lexical form of the literal in the previous example looks like a JSON document, which is not a coincidence. In contrast, our approach is designed such that, by and large, JSON is a subset of what can be used in the lexical forms of the list and map literals (see Section 4.4 Relationship to JSON for further details).

For the definition of the datatypes used for such list and map literals, refer to Sections 3. The cdt:List Datatype and 4. The cdt:Map Datatype, respectively.

Given such composite datatype literals, this document defines extensions to the SPARQL language that introduce functionality related to the types of composite values that these literals capture. The first of these extensions is a collection of various functions for such literals that can be used in expressions within BIND clauses, FILTER clauses, and SELECT clauses of SPARQL queries.

For instance, the following SPARQL query (prefix declarations omitted) uses two such functions in a BIND clause; one of these functions (cdt:concat) concatenates two or more lists, returning the resulting list as a literal again, and the other function (cdt:size) returns the cardinality of the resulting list.

Example 4

SELECT * WHERE {
  ex:s ex:p1 ?l1 .
  ex:s ex:p2 ?l2 .
  ex:s ex:p3 ?l3 .
  BIND( cdt:size( cdt:concat(?l1,?l2,?l3) ) AS ?combinedLength )
}

When executing this query over the first example data above (the example with the three lists), the value produced for the ?combinedLength variable would be 8.

Further functions for lists that are defined in this document (in addition to cdt:concat and cdt:size, as already used in the previous example) are the following:

cdt:contains - can be used to check whether a particular RDF term is contained in a given list
cdt:get - returns the RDF term that is at a particular position within a given list
cdt:head - returns the RDF term that is at the first position within a given list
cdt:reverse - returns a list in which the elements of a given list are in the reverse order
cdt:subseq - returns a part of a given list
cdt:tail - returns a list with all elements of a given list except for the first element

In addition to functions for lists, the document defines functions for maps. As an example, consider the following SPARQL query (prefix declarations omitted).

Example 5

SELECT ?newAddressSubMap WHERE {
  ex:s ex:p1 ?map .
  BIND( cdt:get( ?map, "address" ) AS ?addressSubMap )
  BIND( cdt:put( ?addressSubMap, "number", 42 ) AS ?newAddressSubMap )
}

This query focuses on the earlier example with the JSON-like map (Example 3). By using the cdt:get function, the query obtains the 'address' object of that map and, then, creates and returns a version of this object in which the value of the 'number' field is replaced (using cdt:put). Hence, the result of the query, when executed over the data of Example 3, is a literal such as the following one.

Example 6

"{ 'street': 'Harbor St.', 'number': 42 }"^^cdt:Map .

In addition to cdt:get and cdt:put, further functions for maps in this document are:

cdt:containsKey - can be used to check whether a particular RDF term is a key in a given map
cdt:keys - returns a list of all keys in a given map
cdt:merge - returns a map that is the result of merging two maps
cdt:remove - returns a map resulting from a given map but without a particular key-value pair
cdt:size - returns the number of key-value pairs in a given map

While all the functions mentioned above operate on the composite datatype literals introduced in this document, the document also defines functions to construct such literals. In particular, the cdt:List function can be used to construct a literal that represents a list consisting of the elements that are passed as arguments to the function. For instance, the following query constructs and returns such a literal with the three integers 1, 2, and 3 as elements of the represented list.

Example 7

SELECT ?list WHERE {
  BIND( 1 AS ?arg )
  BIND( cdt:List(?arg, ?arg+1, ?arg+2) AS ?list )
}

Similarly, the cdt:Map function can be used to construct a literal representing a map of the key-value pairs that are passed as arguments to that function.

For both of these constructor functions, it is possible that some of the given arguments evaluate to an error. For instance, the second and the third argument in the previous query would evaluate to an error if the variable ?arg was bound to an IRI (because the + operator is not defined for IRIs). For any such argument that evaluates to an error, the corresponding element in the created list or map literal becomes the null value, unless it is an argument that specifies the key of a key-value pair for a map literal; in such a case, this key-value pair is ignored because keys cannot be null.

Another way to create list and map literals from within SPARQL queries (in addition to the aforementioned two constructor functions, cdt:List and cdt:Map) is to use the FOLD function introduced in this document. As a so-called set function, which are typically used for aggregation, FOLD produces composite values for groups of solution mappings. The following query illustrates how this function can be used to create lists of persons that have the same surname.

Example 8

SELECT ?sname (FOLD(?person) AS ?list) WHERE {
  ?person rdf:type foaf:Person .
  ?person foaf:surname ?sname .
}
GROUP BY ?sname

Notice that the solution mappings within each of the groups in the previous query are not sorted. As a consequence, the order of the elements in the lists created by the query (i.e., the person IRIs in these lists) is undefined and may even be different each time the query is executed. For use cases in which a particular order is required, the FOLD function can be used with an ORDER BY clause. As an example, consider the following query, which extends the previous one with the requirement that the persons within each list are ordered based on their first names.

Example 9

SELECT ?sname (FOLD(?person ORDER BY ?fname) AS ?list) WHERE {
  ?person rdf:type foaf:Person .
  ?person foaf:surname ?sname .
  ?person foaf:firstName ?fname .
}
GROUP BY ?sname

The ORDER BY feature of FOLD works exactly as the ORDER BY clause that can be used in SPARQL queries. Hence, it is possible to specify multiple ordering comparators, each with the optional keywords ASC and DESC (where ASC is the default).

In addition to creating list literals, the FOLD function can also be used to create map literals. To this end, two arguments must be passed to the function, where the first argument provides the keys of the key-value pairs to be added to the map, and the second argument provides the corresponding values. The following query illustrates this functionality; it creates a single map literal in which the key-value pairs are surnames paired up with the number of persons in the queried graph that have the respective surname.

Example 10

SELECT (FOLD(?sname, ?cnt) AS ?map) WHERE {
  {
    SELECT ?sname (COUNT(*) AS ?cnt) WHERE {
      ?person rdf:type foaf:Person .
      ?person foaf:surname ?sname .
    }
    GROUP BY ?sname
  }
}

When using the two-argument version of FOLD, it may be the case that multiple solution mappings within a group to which FOLD is applied result in key-value pairs with the same key. If that is the case, only one of these key-value pairs is added to the map (which one is undefined unless ORDER BY is used within FOLD, in which case it is the last one in the specified order).

While FOLD compiles values from multiple solution mappings into a composite value, to support the reverse of this process as well this document adds a new operator to SPARQL. This operator, called UNFOLD, breaks composite values into their individual components and assigns these components separately to a new query variable. The following query illustrates how this operator can be used to extract all elements from each list literal of the triples that match a given triple pattern.

Example 11

SELECT ?p ?element WHERE {
  ex:s ?p ?list .
  UNFOLD( ?list AS ?element )
}

When executing this query over the first example data above, the query result consists of eight solutions as enumerated in the following tabular representation of the result. Notice that the first four solutions in this table are produced from the four elements of the list in the first triple of the example data; the next two solutions are from the two elements of the list in the second triple; and the last two solutions from the two elements of the list in the third triple.

?p	?element
ex:p1	0.504
ex:p1	0.344
ex:p1	0.002
ex:p1	0.716
ex:p2	http://example.org/alice
ex:p2	http://example.org/bob
ex:p3	'1999-08-16'^^<http://www.w3.org/2001/XMLSchema#date>
ex:p3	42

If a list literal that is given to the UNFOLD operator contains null values, then the variable introduced in the UNFOLD operator remains unbound in the solution mappings created for these null elements. Yet, it is also possible to add a second variable in the UNFOLD operator, which then gets assigned an integer that represents the position of the list element assigned to the first variable. The following query illustrates this feature for a list that contains a null value.

Example 12

SELECT ?element ?pos WHERE {
  BIND( "[42, null, <http://example.org/>]"^^cdt:List AS ?list ).
  UNFOLD( ?list AS ?element, ?pos )
}

The result of this query is illustrated in the following table. The empty cell in the table indicates that the solution mapping represented by the corresponding table row does not contain a binding for the corresponding variable (?element).

?element	?pos
42	1
	2
http://example.org/	3

The UNFOLD operator can be used for map literals as well. In this case, the one-variable version extracts the keys of the key-value pairs, whereas the two-variables version extracts both the keys (into the first variable) and the their corresponding values (into the second variable). As an example of the latter option, consider the following query.

Example 13

SELECT ?p ?key ?value WHERE {
  ex:s ?p ?map .
  UNFOLD( ?map AS ?key, ?value )
}

When executing this query over the data of the first map-related example above, the query result consists of the three solutions listed in the following table (where the variable ?value is unbound in the last solution because the value of the corresponding key-value pair in the map is null).

?p	?key	?value
ex:p1	"name"	"Tuva"
ex:p1	1	http://example.org/
ex:p1	2

Another important contribution of this document is to extend the definition of the SPARQL comparison operators (=, !=, <, >, <=, and >=) for list and map literals. The general idea captured by this extension is that two composite values of the same type (i.e., either two lists or two maps) are compared based on a pairwise comparison of the components of the compared composite values.

In particular, two list literals are considered equal (=) if they contain the same number of elements and, for each position within the lists, the elements at that position are equal (=). For instance, "[42]"^^cdt:List and "[42,43]"^^cdt:List are not equal, and neither are "[42]"^^cdt:List and "['42']"^^cdt:List. In contrast, "[42,43]"^^cdt:List and "[ 42 , 43 ]"^^cdt:List are equal, and so are "['1'^^<http://www.w3.org/2001/XMLSchema#integer>]"^^cdt:List and "['001'^^<http://www.w3.org/2001/XMLSchema#integer>]"^^cdt:List.

Similarly, two map literals are considered equal (=) if they contain the same number of key-value pairs, they have the exact same keys, and for each such key, the values associated with that key in both maps compare equal (=). The algorithms that define these two comparison processes in detail can be found in Sections 6.1 list-equal and 6.2 map-equal, respectively.

The definition of whether a list literal is smaller (<) than another list literal is also captured in terms of an algorithm that iterates over the two lists (see Section 6.3 list-less-than). In this case, the iteration stops once it arrives at a position where the respective elements at this position in the two lists do not compare equal (=). At this point, if one of these two elements is smaller (<) than the other one, then the list with this element is considered smaller. If, however, comparing the two elements results in an error or one of them is null and the other one not, then the comparison of the two lists also raises an error. In case the iteration arrives at the end of one of the two lists without stopping, then this list (with fewer elements) is considered smaller.

Finally, to define whether a map literal is smaller than another map literal we provide another algorithm (see Section 6.4 map-less-than). This algorithm iterates over the key-value pairs of both maps, assuming these pairs are ordered based on their keys. Once the iteration arrives at two such pairs that do not have both the same key and equal values, the iteration stops. At this point, the algorithm first compares the keys of these two pairs. If the two keys are not the same, then the map with the key that would be ordered before the other one is considered smaller. If the keys are the same, the decision is made by comparing the corresponding values (in the same way as done by the algorithm for the list literals).

The last main contribution of this document is to define a relative order of list and map literals, to be used in the context of the ORDER BY clause of SPARQL (and, therefore, also for the aforementioned ORDER BY feature of FOLD). This definition is based on algorithms—one for list literals and one for map literals—that are similar to the respective comparison algorithms as mentioned in the previous section. In particular, these algorithms that define the relative order also iterate over the components of a given pair of composite values; i.e., the elements of two lists (resp. the key-value pairs of two maps) are considered in a pairwise manner. The major difference between these algorithms and the comparison algorithms is that the latter apply the smaller-than operator (<) at each iteration step whereas the former consider the relative ordering of the list elements (resp. key-value pairs) considered at each iteration step.

The effect of this difference can be observed for composite values that contain IRIs or blank nodes. For instance, while the expression

"[<http://example.org/a>]"^^cdt:List  <  "[<http://example.org/b>]"^^cdt:List

yields an error because < is not defined for IRIs, the relative order of the two list literals in this expression is defined (namely based on the relative order of the IRIs they contain).

Similarly, the expression

"[<http://example.org/a>]"^^cdt:List  <  "[42]"^^cdt:List

yields an error because < is not defined between IRIs and (numeric) literals, whereas the relative order of the two list literals in this expression is defined (namely based on the fact that literals are ordered higher than IRIs).

Yet, there are also pairs of list literals and pairs of map literals for which the relative order is undefined. For instance, this is the case for "['hello'@en]"^^cdt:List and "['hello']"^^cdt:List, because the relative order between language-tagged literals and string literals without language tag is undefined in SPARQL.

The complete algorithms that define the relative order for list literals and for map literals can be found in Section 10.1 Relative Order of cdt:List Literals and in Section 10.2 Relative Order of cdt:Map Literals, respectively.

The cdt:List datatype is the RDF datatype that consists of the value space, the lexical space, and the lexical-to-value mapping defined in this section (see Subsections 3.1 Value Space, 3.2 Lexical Space, and 3.3 Lexical-To-Value Mapping, respectively), and that is denoted by the following datatype IRI:

http://w3id.org/awslabs/neptune/SPARQL-CDTs/List

Every literal that has this IRI as its datatype IRI is called a cdt:List literal. If the lexical form of such a literal is in the lexical space of the cdt:List datatype, as defined in Section 3.2 Lexical Space, then the literal is called a well-formed cdt:List literal. In contrast, a cdt:List literal whose lexical form is not in the lexical space of the cdt:List datatype is called an ill-formed cdt:List literal.

The value space of the cdt:List datatype consists of all finite sequences of list elements, where the notion of a list element is defined as follows:

every RDF term is a list element and
null is a list element.

Any such sequence is called term list, and the empty sequence of list elements is the empty term list.

null is a special symbol that can be used as a list element (and as a map value) and that is not an RDF term.

Note

Every RDF term MAY occur multiple times in a term list, and so may null.

The lexical space of the cdt:List datatype consists of all strings that are recognized by the List production of the following grammar (the EBNF notation used here is defined in XML 1.0 [EBNF-NOTATION]).

The grammar uses productions from the grammar of the Turtle serialization format for RDF data [TURTLE]. In particular, the terminal and nonterminal symbols for which no production rule is provided below (i.e., IRIREF, BLANK_NODE_LABEL, NumericLiteral, BooleanLiteral, String, and LANGTAG) are defined in the Turtle grammar.

The RDFLiteral production in the given grammar is special as the Turtle grammar also contains a very similar production for the same symbol (see RDFLiteral in [TURTLE]). The difference is that the version of the rule in the Turtle grammar permits the datatype IRI of a literal to be written as a prefixed name, whereas the version of the rule as defined below does not permit datatype IRIs written as prefixed names (but only as absolute IRIs and as relative IRIs).

An additional restriction that is not explicitly captured in the given grammar is that any occurrence of the IRIREF production MUST—after handling of escape sequences—also match the (more restrictive) absolute-IRI production of [RFC3987]. Hence, IRI references in the lexical form of cdt:List literals and cdt:Map literals MUST be absolute; they cannot be written as prefixed names (see the previous paragraph about the RDFLiteral production) nor as relative IRI references.

[1]	`List`	::=	`'['` `(` NonEmptyListContent `)?` `']'`
[2]	`NonEmptyListContent`	::=	ListElement `(` `','` ListElement `)*`
[3]	`ListElement`	::=	IRIREF `\|` BLANK_NODE_LABEL `\|` RDFLiteral `\|` NumericLiteral `\|` BooleanLiteral `\|` NULL `\|` List `\|` Map
[4]	`Map`	::=	`'{'` `(` NonEmptyMapContent `)?` `'}'`
[5]	`NonEmptyMapContent`	::=	MapEntry `(` `','` MapEntry `)*`
[6]	`MapEntry`	::=	MapKey `':'` MapValue
[7]	`MapKey`	::=	IRIREF `\|` RDFLiteral `\|` NumericLiteral `\|` BooleanLiteral
[8]	`MapValue`	::=	IRIREF `\|` BLANK_NODE_LABEL `\|` RDFLiteral `\|` NumericLiteral `\|` BooleanLiteral `\|` NULL `\|` List `\|` Map
[9]	`NULL`	::=	`'null'`
[128s]	`RDFLiteral`	::=	String `(` LANGTAG `\|` `'^^'` IRIREF `)?`

Note

The complete grammar can be found in B.1 Composite Datatypes EBNF Grammar.

The lexical-to-value mapping of the cdt:List datatype is defined for every string that is recognized by the List production of the grammar defined in Section 3.2 Lexical Space.

For the definition of this mapping, we assume an injective function bnl2bn from the set of all strings recognized by the BLANK_NODE_LABEL production of the grammar to the set of all blank nodes. Hence, bnl2bn maps every string recognized by the BLANK_NODE_LABEL production to a distinct blank node.

Then, given a string S that is recognized by the List production of the grammar, the term list that S is mapped to is defined as follows.

If the string S does not contain a substring that is recognized by the NonEmptyListContent production of the grammar, then S is mapped to the empty term list.

Otherwise, let S' be the greatest substring of S that is recognized by the NonEmptyListContent production and let (E₁, ..., E_n) be the sequence of all substrings of S' that are recognized by the ListElement production, in the order in which they appear in S'. Then, S is mapped to the term list tm that consists of n list elements such that, for all i in {1, ..., n}, the i-th element in tm is the following list element, depending on which of the cases of the ListElement production recognizes the substring E_i:

If E_i is recognized by the IRIREF production, then the i-th element in tm is the IRI constructed from the substring E_i according to the table in Section 7.2 of [TURTLE].
Note
The procedure described in Section 7.2 of [TURTLE] involves unescaping Turtle's numeric escape sequences. If an IRI appears in the lexical form of a cdt:List literal in a SPARQL query, it will be subject to both Turtle's numeric escaping and SPARQL's Codepoint Escape Sequences [SPARQL11-QUERY]. For example, including BIND("[<http://example.org/\u005cu0041>]"^^cdt:List AS ?list) in a SPARQL query will result in a well-formed cdt:List literal whose value is a term list with the IRI http://example.org/A as element.

In contrast, if the literal "[<http://example.org/\u005cu0041>]"^^cdt:List occurs in a Turtle file, then the literal is not pre-processed for SPARQL's codepoint escape sequences but the IRI inside the lexical form of the literal is still subject to unescaping the numeric escape sequences. The result of this unescaping is the substring http://example.org/\u0041 which is not a valid IRI.
If E_i is recognized by the BLANK_NODE_LABEL production, then the i-th element in tm is the blank node bnl2bn(E_i).
If E_i is recognized by the RDFLiteral production, then the i-th element in tm is a literal that has as its lexical form the string that has matched the first rule argument, String, and the datatype IRI and language tag of the literal are as follows.
- If the LANGTAG rule matched, the datatype IRI is rdf:langString and the language tag is the string that has matched the LANGTAG rule.
- If the '^^'IRIREF rule matched, the datatype IRI is the IRI constructed from the IRIREF match according to the table in Section 7.2 of [TURTLE], and the literal has no language tag.
- If neither matched, the datatype is xsd:string and the literal has no language tag.
If E_i is recognized by either the NumericLiteral production or the BooleanLiteral production, then the i-th element in tm is the literal constructed from the substring E_i according to the table in Section 7.2 of [TURTLE].
If E_i is recognized by the NULL production, then the i-th element in tm is null.
If E_i is recognized by the List production, then the i-th element in tm is the literal that has the string E_i as its lexical form, the IRI cdt:List as its datatype IRI, and no language tag.
If E_i is recognized by the Map production, then the i-th element in tm is the literal that has the string E_i as its lexical form, the IRI cdt:Map as its datatype IRI, and no language tag.

Since producing the term list for S as defined above relies on the capability to construct RDF terms according to the table in Section 7.2 of [TURTLE], it requires a parser that maintains state of the bnodeLabels mapping used for parsing Turtle, as defined in Section 7.1 of [TURTLE].

Note

By the definition of the lexical-to-value mapping of the cdt:List datatype, there can be no term list that contains a cdt:List literal whose literal value is that same term list.

This section is non-normative.

The RDF Collection vocabulary, as introduced in Section 5.2 of [RDF11-SCHEMA], provides vocabulary terms to describe lists of resources explicitly by using RDF triples. For instance, the triples in the following snippet of Turtle (prefix declarations omitted) describe a list consisting of two resources that are denoted by the IRIs http://example.org/alice and http://example.org/bob, respectively.

Example 14

ex:book1 ex:authors _:b1 .
_:b1 rdf:first <http://example.org/alice> .
_:b1 rdf:rest _:b2 .
_:b2 rdf:first <http://example.org/bob> .
_:b2 rdf:rest rdf:nil .

Some serialization formats for RDF, including Turtle [TURTLE], provide some form of shorthand notation based on which such lists can be written in a more concise way. For instance, by using the Turtle syntax for collections, the snippet of Turtle as given in the previous example can be shortened as follows.

Example 15

ex:book1 ex:authors (<http://example.org/alice> <http://example.org/bob>) .

Note that even if the latter snippet of Turtle looks more compact, it still captures the same set of five RDF triples as the snippet of Turtle in Example 14.

Such lists can be converted into cdt:List literals and vice versa. The remainder of this section introduces generic approaches to describe such conversions using the SPARQL language. These approaches are generic in the sense that they do not make any assumptions about the given lists that are to be converted (such as assuming knowledge of the list size or of the absence of duplicate entries).

To convert an RDF collection into a cdt:List literal by using a SPARQL query, this query needs to traverse the corresponding rdf:rest triples using a property path expression, collect the object of each rdf:first triple along the path, and finally combine these objects as list elements of a term list for a cdt:List literal by using the FOLD aggregate defined in Section 11. FOLD. Additionally, to preserve the order of the list elements, grouping needs to be used for each position in the given list and the number of path traversal steps to this position need to be counted. The following query illustrates how this approach can be used in the context of the example data above.

Example 16

SELECT ( FOLD(?elmt ORDER BY ?index) AS ?cdtList ) WHERE {
  {
    SELECT ?position (COUNT(?step) AS ?index) WHERE {
      ex:book1 ex:authors ?rdfList .
      ?rdfList rdf:rest* ?step .
      ?step rdf:rest* ?position .
    }
    GROUP BY ?position
  }

  ?position rdf:first ?elmt .
}

If the given list is known to be free of duplicates, the query can be slightly simplified:

Example 17

SELECT ( FOLD(?elmt ORDER BY ?index) AS ?cdtList ) WHERE {
  {
    SELECT ?elmt (COUNT(?step) AS ?index) WHERE {
      ex:book1 ex:authors ?rdfList .
      ?rdfList rdf:rest* ?step .
      ?step rdf:rest* ?position .
      ?position rdf:first ?elmt .
    }
    GROUP BY ?elmt
  }
}

If the order of the list elements does not need to be preserved, an even simpler version of the query without grouping and counting can be used (which is also duplicate preserving in case the given list contains duplicate entries):

Example 18

SELECT ( FOLD(?elmt) AS ?cdtList ) WHERE {
  ex:book1 ex:authors ?rdfList .
  ?rdfList rdf:rest/rdf:first ?elmt .
}

To convert a cdt:List literal into an RDF collection a CONSTRUCT query needs to be used that produces the relevant RDF triples based on the RDF collection vocabulary. The WHERE clause of such a query needs to use the UNFOLD operator (see Section 12. UNFOLD) to obtain each list element together with its position within the term list represented by the given cdt:List literal. The positions can then be associated with blank nodes to be used for the various resources based on which the structure of the created RDF collection is built (the following query creates a cdt:Map literal as an intermediary structure for this purpose). Special care needs to be taken to correctly close the RDF collection with the term rdf:nil, for which the position of each element needs to be compared with the size of the list (as can be obtained with the cdt:size function defined in Section 7.2 cdt:size). Finally, to properly handle empty lists as well, the whole query pattern for the non-empty lists needs to be placed within an OPTIONAL block and a second OPTIONAL block needs to be added to cover the cases of empty lists. The following query illustrates this approach for all cdt:List literals in the object positions of triples with the IRI ex:authorList as predicate.

Example 19

CONSTRUCT {
  ?s ex:authors ?firstStep .
  ?thisStep rdf:first ?elmt .
  ?thisStep rdf:rest ?rest .
}
WHERE {
  OPTIONAL { # for the cases of non-empty lists
    {
      SELECT ?s ?list (FOLD(?pos, BNODE()) AS ?listHeads) WHERE {
        ?s ex:authorList ?list .
        FILTER( DATATYPE(?list) = cdt:List )
        UNFOLD( ?list AS ?elmt, ?pos )
      }
      GROUP BY ?s ?list
    }

    UNFOLD( ?list AS ?elmt, ?pos )
    BIND( cdt:get(?listHeads, ?pos) AS ?thisStep )
    BIND( cdt:size(?list) AS ?size )
    BIND( IF( ?pos=?size,
              rdf:nil,
              cdt:get(?listHeads, ?pos+1)
          ) AS ?rest )
    BIND( cdt:get(?listHeads, 1) AS ?firstStep )
  }
  OPTIONAL { # for the cases of empty lists
    ?s ex:authorList ?list .
    FILTER( DATATYPE(?list) = cdt:List )
    FILTER( cdt:size(?list) = 0 )
    BIND( rdf:nil AS ?firstStep )
  }
}

It needs to be emphasized that, for cdt:List literals that represent term lists with null values, the given query creates no rdf:first triples for the corresponding positions in the resulting RDF collection (but the rdf:rest triples for these positions are created by the query). The reason for this is that the UNFOLD operator leaves the variable ?elmt unbound for the positions where a term list has a null value.

Notice also that the query contains two FILTER clauses (one in each OPTIONAL block) that ensure the datatype of the literals bound to the variable ?list is indeed cdt:List. The purpose of these two FILTER clauses is to avoid accidentially creating RDF collections from potentially matching cdt:Map literals (as the UNFOLD operator and the cdt:size function can be applied to such literals as well). For cases in which it is guaranteed, however, that ?list would not be bound to any cdt:Map literal, the query can be slightly simplified by removing these two FILTER clauses.

Another possible simplification (orthogonal to aforementioned one about removing the two FILTER clauses) can be applied if the cdt:List literals that are to be converted are guaranteed to represent only nonempty term lists. In this case, the whole pattern within the first OPTIONAL block does not need to be wrapped within an OPTIONAL block and the second OPTIONAL block can be removed completely.

The cdt:Map datatype is the RDF datatype that consists of the value space, the lexical space, and the lexical-to-value mapping defined in this section (see Subsections 4.1 Value Space, 4.2 Lexical Space, and 4.3 Lexical-To-Value Mapping, respectively), and that is denoted by the following datatype IRI:

http://w3id.org/awslabs/neptune/SPARQL-CDTs/Map

Every literal that has this IRI as its datatype IRI is called a cdt:Map literal. If the lexical form of such a literal is in the lexical space of the cdt:Map datatype, as defined in Section 4.2 Lexical Space, then the literal is called a well-formed cdt:Map literal. In contrast, a cdt:Map literal whose lexical form is not in the lexical space of the cdt:Map datatype is called an ill-formed cdt:Map literal.

The value space of the cdt:Map datatype consists of all functions that map from a finite set of map keys to the set of map values, where the notion of a map key is defined as follows:

every IRI is a map key and
every literal is a map key,

and the notion of a map value is defined as follows:

every RDF term is a map value (i.e., every IRI, literal, and blank node) and
null is a map value.

Any such function is called term map, and the empty function for the set of map values (i.e., the function that maps from the empty set to the set of map values) is the empty term map. Moreover, every pair (k,v) consisting of a map key k and a map value v is called a map entry where k is called the key of the map entry and v is called the value of the map entry.

Given a term map tm and a map entry (k,v), we say that tm contains this map entry if k is in the domain of tm and tm maps k to v; i.e., tm(k)=v.

Note

The empty term map does not contain any map entries.

Note

A term map MAY contain multiple map entries that all have the same value, but they MUST have different keys. It is possible, however, that multiple map entries of a term map MAY have literals with the same literal value as their respective keys, as long as all these literals have a different lexical form. For instance, a term map MAY contain two map entries, (k,v) and (k',v'), such that k is the literal "0042"^^xsd:integer and k' is the literal "42"^^xsd:integer (using a Turtle representation of these literals for the sake of readability). Clearly, these are two different literals and, thus, two different map keys, but their literal value is the same (the integer 42).

Distinguishing map keys that are literals based on their lexical form rather than their value is a deliberate design decision. If the distinction was based on the value instead, then the distinction could be made only for literals with recognized datatype IRIs. This would not only raise the question of what to do with map keys that are literals with an unrecognized datatype IRI, but it would also make the notion of map keys (and what makes them different from one another) dependent on the set of datatype IRIs recognized by the RDF processing system. Such a dependency may then result in different and potentially incompatible behavior in terms of how cdt:Map literals are handled by different RDF processing systems that support different sets of recognized datatype IRIs. Distinguishing map keys that are literals based on their lexical form avoids such incompatibilities.

The lexical space of the cdt:Map datatype consists of all strings that are recognized by the Map production of the grammar defined in Section 3.2 Lexical Space and in which all substrings that matched the MapKey production are different from one another.

Issue 1

The constraint about the substrings is not restrictive enough because the MapKey production recognizes both the generic way of serializing literals in Turtle and the Turtle shorthand notations for some datatypes. For instance, consider the following string:

"{ 42 : 'value1',  '42'^^<http://www.w3.org/2001/XMLSchema#integer> : 'value2' }"

This string satisfies the definition given above (including the constraint about the substrings) and, thus, would be a valid lexical form for cdt:Map literals. Yet, the keys of the two map entries represented in this string are the exact same literal, which is illegal according to the definition of term maps.

The lexical-to-value mapping of the cdt:Map datatype is defined as follows for every string S that is recognized by the Map production of the grammar defined in Section 3.2 Lexical Space. The definition assumes the same bnl2bn function as assumed for the lexical-to-value mapping of the cdt:List datatype.

If the string S does not contain a substring that is recognized by the NonEmptyMapContent production of the grammar, then S is mapped to the empty term map.

Otherwise, let S' be the greatest substring of S that is recognized by the NonEmptyMapContent production, let (E₁, ..., E_n) be the sequence of all substrings of S' that are recognized by the MapEntry production, and for every i in {1, ..., n}, let K_i and V_i be the substrings of E_i that are recognized by the MapKey and the MapValue productions, respectively. Then, S is mapped to the term map tm that contains n map entries, one for each substring E_i, where i in {1, ..., n}. The particular map entry (k_i,v_i) that tm contains for E_i depends on which of the cases of the MapKey and the MapValue productions recognize K_i and V_i. In particular, depending on K_i, k_i is defined as follows.

If K_i is recognized by the IRIREF production, then k_i is the IRI constructed from the substring K_i according to the table in Section 7.2 of [TURTLE].
If K_i is recognized by the RDFLiteral production, then k_i is a literal that has as its lexical form the string that has matched the first rule argument, String, and the datatype IRI and language tag of the literal are as follows.
- If the LANGTAG rule matched, the datatype IRI is rdf:langString and the language tag is the string that has matched the LANGTAG rule.
- If the '^^'IRIREF rule matched, the datatype IRI is the IRI constructed from the IRIREF match according to the table in Section 7.2 of [TURTLE], and the literal has no language tag.
- If neither matched, the datatype is xsd:string and the literal has no language tag.
If K_i is recognized by either the NumericLiteral production or the BooleanLiteral production, then k_i is the literal constructed from the substring K_i according to the table in Section 7.2 of [TURTLE].

Moreover, depending on V_i, v_i is defined as follows.

If V_i is recognized by the IRIREF production, then v_i is the IRI constructed from the substring V_i according to the table in Section 7.2 of [TURTLE].
If V_i is recognized by the BLANK_NODE_LABEL production, then v_i is the blank node bnl2bn(V_i).
If V_i is recognized by the RDFLiteral production, then v_i is a literal that has as its lexical form the string that has matched the first rule argument, String, and the datatype IRI and language tag of the literal are as follows.
- If the LANGTAG rule matched, the datatype IRI is rdf:langString and the language tag is the string that has matched the LANGTAG rule.
- If the '^^'IRIREF rule matched, the datatype IRI is the IRI constructed from the IRIREF match according to the table in Section 7.2 of [TURTLE], and the literal has no language tag.
- If neither matched, the datatype is xsd:string and the literal has no language tag.
If V_i is recognized by either the NumericLiteral production or the BooleanLiteral production, then v_i is the literal constructed from the substring V_i according to the table in Section 7.2 of [TURTLE].
If V_i is recognized by the NULL production, then v_i is null.
If V_i is recognized by the List production, then v_i is the literal that has the string V_i as its lexical form, the IRI cdt:List as its datatype IRI, and no language tag.
If V_i is recognized by the Map production, then v_i is the literal that has the string V_i as its lexical form, the IRI cdt:Map as its datatype IRI, and no language tag.

Since producing the term map for S as defined above relies on the capability to construct RDF terms according to the table in Section 7.2 of [TURTLE], it requires a parser that maintains state of the bnodeLabels mapping used for parsing Turtle, as defined in Section 7.1 of [TURTLE].

Note

The note about unescaping of IRIs as given in Section 3.3 Lexical-To-Value Mapping applies here too.

This section is non-normative.

By the definition of the lexical space of the cdt:Map datatype (see Section 4.2 Lexical Space), strings that match the object production of the grammar of the JavaScript Object Notation (JSON) [RFC8259] can generally be used as a lexical form of a cdt:Map literal (with a few exceptions related to escaping of characters in strings, see the corresponding note in the following list). When doing so, the lexical-to-value mapping of the cdt:Map datatype (see Section 4.3 Lexical-To-Value Mapping) interprets the various elements of the JSON format as follows.

The JSON object that is used as the lexical form of the given cdt:Map literal is mapped to a term map. Every name-value pair of the JSON object becomes a map entry that is contained in the resulting term map. The map key of each such map entry is a literal created from the name of the corresponding name-value pair by using the rule for JSON string values as defined below. The map value of each such map entry depends on the type of the value of the corresponding name-value pair.
A JSON value that is another JSON object is mapped to a cdt:Map literal that has the JSON object as its lexical form.
A JSON value that is an array is mapped to a cdt:List literal that has the JSON object as its lexical form.
A JSON value that is a number is mapped to a literal with the number as the lexical form, no language tag, and a datatype IRI that is determined based on the following rules.
- If the number has an exponent part (see the exp production of the JSON grammar), then the datatype IRI is xsd:double.
- If the number has no exponent part but it has a fraction part (see the frac production of the JSON grammar), then the datatype IRI is xsd:decimal.
- If the number has no exponent part and no fraction part, then the datatype IRI is xsd:integer.
A JSON value that is a string is mapped to a literal with datatype xsd:string, no language tag, and a lexical form that is the result of using the sequence of characters between the first and the last quotation mark of the string and applying Turtle's unescaping of numeric escape sequences and string escape sequences to this sequence of characters.
Note
The support for escaping of characters in strings in JSON goes beyond the numeric escape sequences and string escape sequences in Turtle. In particular, while both Turtle's string escape sequences and JSON support the two-character sequence '\\' to represent the reverse solidus character (i.e., codepoint U+005C in Unicode), only JSON supports the two-character sequence '\/' to represent the solidus character (codepoint U+002F). JSON strings that use this two-character escape sequence cannot be used as a lexical form of a cdt:Map literal; attempting to do so will result in a parser error. Moreover, JSON supports encoding of UTF-16 surrogate pairs using 12-character sequences of the form '\uNNNN\uNNNN' which are not recognized by the numeric escape sequences of Turtle as a singular pair. Hence, when using a JSON string with such surrogate pairs as a lexical form of a cdt:Map literal, then the surrogate pairs are not unescaped correctly.
A JSON value that is the name false or the name true is mapped to a literal with datatype xsd:boolean, no language tag, and a lexical form that is the JSON value (i.e., false or true).
A JSON value that is the name null is mapped to null.

This section is non-normative.

In the normal handling of an RDF syntax, blank node identifiers are scoped to the current document, and any identifiers used in that document are merely a syntactic convenience for referencing blank nodes freshly allocated during parsing. As an example, consider the following snippet of Turtle syntax [TURTLE].

Example 20

_:b1 ex:p4 "[ <http://example.org/alice>, <http://example.org/bob>, _:eve ]"^^cdt:List .

Parsing this data as Turtle will result in a single triple whose subject is a blank node (now dissociated from the b1 identifier), and whose object is a cdt:List literal that represents a three-element term list in which the third element is a blank node. However, using a Turtle parser not aware of the cdt:List datatype will result in an object literal containing the substring "_:eve"; that is, the literal will keep the exact lexical form as given in the Turtle snippet above (Example 20). Allowing multiple such composite values, from multiple sources, to be inserted into the same RDF Dataset (e.g., via two SPARQL LOAD updates) presents a challenge: when a system interprets the literals obtained from its Turtle parser, the term lists that it creates by applying the cdt:List lexical-to-value mapping will contain the same blank nodes (because, during the mapping process for each cdt:List literal, the bnl2bn function is applied to the same blank node identifier, _:eve). This is problematic, as it introduces a form of unintentional skolemization, removing the scoping of serialized blank nodes and allowing them to be universally referenced so long as they are wrapped in an enclosing composite type.

The following sections describe requirements that conforming SPARQL systems must comply with to support proper handling of blank nodes when importing or exporting RDF data that contains cdt:List or cdt:Map literals.

Conforming implementations MUST process cdt:List literals and cdt:Map literals during loading, replacing, in their lexical form, any substring bnl matching the BLANK_NODE_LABEL production of the grammar with a string bnl' such that

bnl' also matches the BLANK_NODE_LABEL production, and
if the format of the document being processed has a mechanism for explicitly identifying blank nodes outside of cdt:List and cdt:Map literals (e.g., _:b1 syntax in N-Triples and in Turtle, rdf:nodeID in RDF/XML), and id is the blank node identifier represented by bnl (i.e., bnl is of the form _:id), then bnl' must be picked such that bnl2bn(bnl')=B where B is the blank node that the parser for this document emits for occurrences of id outside of the literals, and
if the format of the document being processed does not have a mechanism for explicitly identifying blank nodes outside of cdt:List and cdt:Map literals, then bnl' must be picked such that bnl2bn(bnl') is a fresh blank node not already used in the SPARQL system or RDF Dataset, and
within the scope of the document being processed, all occurrences of bnl used to represent a blank node identifier within the lexical forms of cdt:List and cdt:Map literals are replaced with the same bnl' value, and
within the scope of the document being processed, no other substring that matches the BLANK_NODE_LABEL production within the lexical form of a cdt:List or cdt:Map literal is replaced by the same substring bnl'.

Here, "loading" is every individual, discrete process by which composite values enter a SPARQL system or RDF Dataset. This includes (but is not limited to):

The parsing of a SPARQL Query string [SPARQL11-QUERY] or of a SPARQL Update string [SPARQL11-UPDATE], which may contain literals.
The loading of RDF data via a SPARQL LOAD operation [SPARQL11-UPDATE]
The loading of RDF data via a single SPARQL graph store protocol request [SPARQL11-HTTP-RDF-UPDATE]
The loading of RDF data via any single SPARQL FROM or FROM NAMED clause [SPARQL11-QUERY] in systems that support the dereferencing and loading of RDF data specified for the dataset to be queried
Importing of any RDF data to the internally-managed RDF dataset via means other than SPARQL Update statements [SPARQL11-UPDATE] or the SPARQL Graph Store HTTP Protocol [SPARQL11-HTTP-RDF-UPDATE]
The loading of a SPARQL result obtained from a SPARQL service when evaluating a SERVICE pattern [SPARQL11-FEDERATED-QUERY]

As an example, consider the Turtle document in Example 21. Loading this document MUST result in a system-internal representation of a single triple whose object is a cdt:List literal containing a blank node that, in the lexical form of the literal, is captured by a blank node identifier that may have been replaced during import (e.g., Example 22).

Example 21: Loading of a cdt:List literal with a blank node

ex:s ex:p1 "[ _:b0 ]"^^cdt:List .

Example 22: Loading of a cdt:List literal with a blank node: Result

<http://example.org/s> <http://example.org/p1> "[ _:b001 ]"^^<http://w3id.org/awslabs/neptune/SPARQL-CDTs/List> .

Consider the INSERT DATA operation in Example 23, which adds a triple with a blank-node-containing cdt:List literal. Evaluating two separate SPARQL Update requests that both contain this INSERT DATA operation (i.e., using the same blank node identifier within the lexical form of the given cdt:List literal in both requests) MUST result in a system-internal representation of two triples whose objects are cdt:List literals containing different blank nodes that, in the lexical form of these literals, are captured by different blank node identifiers (e.g., Example 24).

Example 23: Repeated loading of cdt:List literals with a blank node

INSERT DATA { <s> <p2> "[ _:b0 ]"^^cdt:List } ;

Example 24: Repeated loading of cdt:List literals with a blank node: Result

<http://example.org/s> <http://example.org/p2> "[ _:b002 ]"^^<http://w3id.org/awslabs/neptune/SPARQL-CDTs/List> .
<http://example.org/s> <http://example.org/p2> "[ _:b003 ]"^^<http://w3id.org/awslabs/neptune/SPARQL-CDTs/List> .

Note

While a SPARQL Update request may contain multiple INSERT DATA operations, it is illegal to use the same blank node identifiers across these operations. This constraint extends to blank node identifiers in (the lexical form of) cdt:List and cdt:Map literals within such INSERT DATA operations. For instance, the following SPARQL Update request with two INSERT DATA operations is illegal.

Example 25: Two INSERT DATA operations within a single SPARQL Update request, both with the same blank node identifier in a cdt:List literal, which makes the request syntactically incorrect

INSERT DATA { <s> <p2> "[ _:b0 ]"^^cdt:List } ;
INSERT DATA { <s> <p2> "[ _:b0 ]"^^cdt:List } ;

Loading the Turtle in Example 26 with a triple with _:b0 appearing in both the subject position and inside a cdt:List literal object MUST result in a system-internal representation with a single triple whose subject is the same blank node as contained in the single-element cdt:List literal object (e.g., Example 27).

Example 26: Producing consistent blank node identifiers shared between a cdt:List literal and the RDF data that contains this literal

_:b0 ex:p3 "[ _:b0 ]"^^cdt:List .

Example 27: Producing consistent blank node identifiers shared between a cdt:List literal and the RDF data that contains this literal: Result

_:b004 <http://example.org/p3> "[ _:b004 ]"^^<http://w3id.org/awslabs/neptune/SPARQL-CDTs/List> .

Loading the Turtle in Example 28 with a triple with a cdt:Map literal containing two map entries, both having the same blank node as their value, MUST result in a system-internal representation with a single triple whose cdt:Map literal object contains two map entries having the same blank node value, and whose identifier MUST NOT be "b0" (e.g., Example 29).

Example 28: Consistent rewriting of blank node identifiers that are used multiple times in a cdt:Map literal

ex:s ex:p3 "{ 'this': _:b0, 'again': _:b0 }"^^cdt:Map .

Example 29: Consistent rewriting of blank node identifiers that are used multiple times in a cdt:Map literal: Result

<http://example.org/s> <http://example.org/p3> "{'this': _:b005,'again': _:b005}"^^<http://w3id.org/awslabs/neptune/SPARQL-CDTs/Map> .

TODO

This section defines extensions of some of the existing operators of SPARQL. In particular, the = operator and the != operator are extended both for cdt:List literals and for cdt:Map literals. Implementations of SPARQL that recognize the datatypes defined above MUST implement these operators with the extensions defined in this section.

To define the extensions formally, the operator mapping table for binary operators in Section 17.3 of [SPARQL11-QUERY] is extended with the following twelve rows.

Operator	Type(A)	Type(B)	Function	Result type
A = B	cdt:List	cdt:List	list-equal(A, B)	xsd:boolean
A = B	cdt:Map	cdt:Map	map-equal(A, B)	xsd:boolean
A != B	cdt:List	cdt:List	fn:not(list-equal(A, B))	xsd:boolean
A != B	cdt:Map	cdt:Map	fn:not(map-equal(A, B))	xsd:boolean
A < B	cdt:List	cdt:List	list-less-than(A, B)	xsd:boolean
A < B	cdt:Map	cdt:Map	map-less-than(A, B)	xsd:boolean
A > B	cdt:List	cdt:List	list-less-than(B, A)	xsd:boolean
A > B	cdt:Map	cdt:Map	map-less-than(B, A)	xsd:boolean
A <= B	cdt:List	cdt:List	logical-or(list-less-than(A, B), list-equal(A, B))	xsd:boolean
A <= B	cdt:Map	cdt:Map	logical-or(map-less-than(A, B), map-equal(A, B))	xsd:boolean
A >= B	cdt:List	cdt:List	logical-or(list-less-than(B, A), list-equal(A, B))	xsd:boolean
A >= B	cdt:Map	cdt:Map	logical-or(map-less-than(B, A), map-equal(A, B))	xsd:boolean

The four new functions used in these table rows are defined in Subsections 6.1 list-equal, 6.2 map-equal, 6.3 list-less-than, and 6.4 map-less-than below.

Note

It should be noted that extending the operator mapping table with these twelve rows changes the behavior of the corresponding operators (=, !=, <, >, <=, and >=) only for cases in which these operators would otherwise (i.e., without the extension) yield a type error. Therefore, this extension is conformant with the SPARQL specification, as explicitly stated in Section 17.3.1 of [SPARQL11-QUERY].

xsd:boolean list-equal ( cdt:List term₁, cdt:List term₂ )

This function cannot be used directly in expressions. Instead, the purpose of this function is to define the semantics of the = operator when applied to two cdt:List literals.

If both term₁ and term₂ are well-formed cdt:List literals, then the result of this function is determined by the following algorithm.

Let list₁ be the term list obtained by applying the lexical-to-value mapping of the cdt:List datatype to the lexical form of term₁ (i.e., list₁ is the value of term₁).
Let list₂ be the term list obtained by applying the lexical-to-value mapping of the cdt:List datatype to the lexical form of term₂ (i.e., list₂ is the value of term₂).
If both list₁ and list₂ are the empty term list, then return true.
If the length of list₁ is different from the length of list₂, then return false.
For every integer i from 1 to n, where n is the length of list₁:
1. Let elmt₁ be the i-th element in list₁.
2. Let elmt₂ be the i-th element in list₂.
3. If elmt₁ is null and elmt₂ is not null, return false.
4. If elmt₂ is null and elmt₁ is not null, return false.
5. If neither elmt₁ nor elmt₂ is null, then:
  1. If elmt₁ is a blank node and elmt₂ is a blank node, terminate with an error.
  2. If evaluating the SPARQL expression elmt₁ = elmt₂ results in an error, terminate with an error.
  3. If evaluating the SPARQL expression elmt₁ = elmt₂ results in false, return false.
Return true.

If term₁ or term₂ is an ill-formed cdt:List literal, then this function produces an error.

Note

Whenever the given algorithm, during its pairwise comparison of the elements of the two given lists, comes across a pair in which both elements are null, the algorithm advances to the next pair of elements. In this sense, the algorithm considers null values to be indistinguishable from one another. This behavior is necessary to guarantee that an expression such as the following evaluates to true (rather than to false or to an error).

"[null]"^^cdt:List = "[null]"^^cdt:List

Guaranteeing that this expression evaluates to true is necessary for the following reason. Notice that the two arguments in this expression are identical (i.e., they are the same literal, with the same lexical form and the same datatype IRI). Therefore, by the definition of the = operator in [SPARQL11-QUERY], the evaluation of the expression is true if cdt:List is not in the set of recognized datatype IRIs (i.e., if the RDF processing system does not support cdt:List). Then, the version of the = operator for systems that support cdt:List (i.e., the version of the operator as defined by the list-equal function in this section) must also return true, because "no additional operator may yield a result that replaces any result other than a type error" (see Section 17.3.1 of [SPARQL11-QUERY]).

xsd:boolean map-equal ( cdt:Map term₁, cdt:Map term₂ )

This function cannot be used directly in expressions. Instead, the purpose of this function is to define the semantics of the = operator when applied to two cdt:Map literals.

If both term₁ and term₂ are well-formed cdt:Map literals, then the result of this function is determined by the following algorithm.

Let map₁ be the term map obtained by applying the lexical-to-value mapping of the cdt:Map datatype to the lexical form of term₁ (i.e., map₁ is the value of term₁).
Let map₂ be the term map obtained by applying the lexical-to-value mapping of the cdt:Map datatype to the lexical form of term₂ (i.e., map₂ is the value of term₂).
If both map₁ and map₂ are the empty term map, then return true.
If the number of map entries that map₁ contains is different from the number of map entries that map₂ contains, then return false.
Let error be a boolean-typed flag that is initialized with the value false.
For every map entry (k, v₁) contained in map₁:
1. If k is not in the domain of map₂, return false.
2. Let v₂ be the map value map₂(k).
3. If v₁ is null and v₂ is not null, return false.
4. If v₂ is null and v₁ is not null, return false.
5. If neither v₁ nor v₂ is null, then:
  1. If v₁ is a blank node and v₂ is a blank node, set error to true and move on to the next map entry in map₁ (i.e., skip over the remaining instructions within this for loop).
  2. If evaluating the SPARQL expression v₂ = v₁ results in an error, set error to true and move on to the next map entry in map₁ (i.e., skip over the remaining instructions within this for loop).
  3. If evaluating the SPARQL expression v₂ = v₁ results in false, return false.
If error is true, terminate with an error.
Return true.

If term₁ or term₂ is an ill-formed cdt:Map literal, then this function produces an error.

xsd:boolean list-less-than ( cdt:List term₁, cdt:List term₂ )

This function cannot be used directly in expressions. Instead, the purpose of this function is to define the semantics of the < operator when applied to two cdt:List literals.

If both term₁ and term₂ are well-formed cdt:List literals, then the result of this function is determined by the following algorithm.

Let list₁ be the term list obtained by applying the lexical-to-value mapping of the cdt:List datatype to the lexical form of term₁ (i.e., list₁ is the value of term₁).
Let list₂ be the term list obtained by applying the lexical-to-value mapping of the cdt:List datatype to the lexical form of term₂ (i.e., list₂ is the value of term₂).
If both list₁ and list₂ are the empty term list, then return false.
For every integer i from 1 to n, where n is the minimum of the length of list₁ and the length of list₂:
1. Let elmt₁ be the i-th element in list₁.
2. Let elmt₂ be the i-th element in list₂.
3. If elmt₁ is null and elmt₂ is null, return false.
4. If elmt₁ is null or elmt₂ is null, terminate with an error.
5. If elmt₁ is a blank node and elmt₂ is a blank node, terminate with an error.
6. If evaluating the SPARQL expression elmt₁ < elmt₂ results in true or in false (i.e., not in an error), return this result.
7. If evaluating the SPARQL expression elmt₁ = elmt₂ results in an error, terminate with an error.
8. If evaluating the SPARQL expression elmt₁ = elmt₂ results in false, return false.
If the length of list₁ is smaller than the length of list₂, return true.
Return false.

If term₁ or term₂ is an ill-formed cdt:List literal, then this function produces an error.

xsd:boolean map-less-than ( cdt:Map term₁, cdt:Map term₂ )

This function cannot be used directly in expressions. Instead, the purpose of this function is to define the semantics of the < operator when applied to two cdt:Map literals.

If both term₁ and term₂ are well-formed cdt:Map literals, then the result of this function is determined by the following algorithm.

Let map₁ be the term map obtained by applying the lexical-to-value mapping of the cdt:Map datatype to the lexical form of term₁ (i.e., map₁ is the value of term₁).
Let map₂ be the term map obtained by applying the lexical-to-value mapping of the cdt:Map datatype to the lexical form of term₂ (i.e., map₂ is the value of term₂).
If both map₁ and map₂ are the empty term map, then return false.
Let entryset₁ be the set of all map entries that are contained in map₁.
Let entryset₂ be the set of all map entries that are contained in map₂.
Let entrylist₁ be a list of all map entries in entryset₁, ordered based on their respective map keys by using the following order:
- Map entries with map keys that are IRIs are listed first, ordered based on comparing the string representation of these IRIs using the < operator (i.e., the IRIs are used as the lexical form of literals with the datatype xsd:string and the order is then determined by comparing these literals using the < operator)
- The remaining map entries have map keys that are literals. They are primarily ordered based on the string representation of their datatype IRIs (i.e., using these datatype IRIs as the lexical form of literals with the datatype xsd:string and, then, determining the order by comparing these string literals using the < operator). Literals of the same datatype are ordered based on their lexical form (i.e., replacing their datatype IRI by xsd:string and, then, using the < operator for the resulting string literals). Finally, literals with datatype rdf:langString that have the same lexical form are sorted based on the string representation of their language tags.
Let entrylist₂ be a list of all map entries in entryset₂, ordered in the same way as entrylist₁.
For every integer i from 1 to n, where n is the minimum of the respective length of entrylist₁ and of entrylist₂:
1. Let (k₁, v₁) be the i-th map entry in entrylist₁.
2. Let (k₂, v₂) be the i-th map entry in entrylist₂.
3. If evaluating the SPARQL expression SAMETERM(k₁, k₂) results in false, then:
  1. Return true if k₁ is ordered before k₂ according to the ordering of map keys as defined above for creating entrylist₁.
  2. Return false.
4. If v₁ is null and v₂ is null, return false.
5. If v₁ is null or v₂ is null, terminate with an error.
6. If evaluating the SPARQL expression v₁ < v₂ results in true or in false (i.e., not an error), return this result.
7. If evaluating the SPARQL expression v₁ = v₂ results in an error, terminate with an error.
8. If evaluating the SPARQL expression v₁ = v₂ results in false, return false.
Return true if the length of entrylist₁ is smaller than the length of entrylist₂.
Return false.

If term₁ or term₂ is an ill-formed cdt:Map literal, then this function produces an error.

This section defines SPARQL extension functions which operate over both cdt:List literals and cdt:Map literals. These functions can be used in SPARQL expressions for testing values in FILTER clauses and for assigning values in, e.g., BIND clauses and SELECT expressions.

These extension functions are evaluated as defined in Section 17.2.1 of [SPARQL11-QUERY].

RDF term cdt:get ( cdt:List term, xsd:integer idx )

If term is a well-formed cdt:List literal, the value of idx is greater than 0 (zero) and smaller or equal than the number of elements of the term list represented by term, and the element at the idx-th position of the term list represented by term is an RDF term (i.e., not null), then the result of this function is that RDF term at the idx-th position of the term list represented by term. In all other cases an error is raised.

RDF term cdt:get ( cdt:Map term, RDF term key )

If term is a well-formed cdt:Map literal, and there exists a map entry (k,v) in the term map represented by term where k is the same term as key and v is an RDF term (i.e., not null), then the result of this function is v. In all other cases an error is raised.

Example 30

Evaluating the SPARQL expression

cdt:get( "[<http://example.org/a>, <http://example.org/b>]"^^cdt:List, 2 )

results in the IRI http://example.org/b.

Example 31

Evaluating the SPARQL expression

cdt:get( "{2: <http://example.org/a>, 1: <http://example.org/b>}"^^cdt:Map, 2 )

results in the IRI http://example.org/a.

Note

By its definition as given above, cdt:get for cdt:List literals raises an error not only if the given cdt:List literal is not well-formed but also in the following cases:

if term is a well-formed cdt:List literal that represents the empty term list,
if the value of idx is out of the bounds of the term list represented by term, and
if the element at the idx-th position of the term list represented by term is null.

Similarly, cdt:get for cdt:Map literals raises an error not only if the given cdt:Map literal is not well-formed but also in the following cases:

if term is a well-formed cdt:Map literal that represents the empty term map,
if key is not a map key in the term map represented by term, and
if the value associated with key in the term map represented by term is null.

Note

The list version of the function uses a 1-based numbering scheme to address the elements in term list (i.e., the first element of a term list is addressed by an idx value of 1), in contrast to a 0-based numbering scheme which is common for addressing elements of arrays in many programming languages. The reason for using 1-based numbering for this function is to remain consistent with existing build-in functions of SPARQL, which are also 1-based (e.g., substr for string literals). Moreover, the 1-based numbering scheme is also used by functions of other W3C languages such as XPath (see, e.g., the XPath array:get function which is similar to cdt:get).

xsd:integer cdt:size ( cdt:List term )

If term is a well-formed cdt:List literal, then the result of this function is the number of elements that the term list represented by term contains.

An error is raised if term is not a well-formed cdt:List literal.

xsd:integer cdt:size ( cdt:Map term )

If term is a well-formed cdt:Map literal, then the result of this function is the number of map entries in the term map represented by term.

An error is raised if term is not a well-formed cdt:Map literal.

Example 32

Evaluating the SPARQL expression

cdt:size( "[1,'a','a',4]"^^cdt:List )

results in a literal with the datatype IRI xsd:integer and the value 4.

Example 33

Evaluating the SPARQL expression

cdt:size( "{1:'a','a':4}"^^cdt:Map )

results in a literal with the datatype IRI xsd:integer and the value 2.

This section defines SPARQL extension functions specifically for cdt:List literals. These functions can be used in SPARQL expressions for testing values in FILTER clauses and for assigning values in, e.g., BIND clauses and SELECT expressions.

Except for cdt:List, these extension functions are evaluated as defined in Section 17.2.1 of [SPARQL11-QUERY]. In contrast, cdt:List is a so-called functional form which has specific evaluation rules (as defined in Section 8.1 cdt:List).

cdt:List cdt:List ( SPARQL expression expr₁, ..., SPARQL expression expr_n )

The result of this function is a cdt:List literal that represents a term list tm that contains n elements where, for every i in {1, ..., n}, the element at the i-th position of tm is constructed as follows. Evaluate the i-th expression, expr_i, as defined in [SPARQL11-QUERY]. If evaluating expr_i raises an error, then the element at the i-th position of tm is null. Otherwise, the element at the i-th position of tm is the RDF term resulting from the evaluation of expr_i.

If the function is called without arguments, then the result is a cdt:List literal that represents the empty term list.

Example 34

Evaluating the SPARQL expression

cdt:List( 'hello', ?x, ?x+1, ?y, <http://example.org/a> )

for the solution mapping μ = {?x → "2"^^xsd:integer} results in the following cdt:List literal.

"['hello', 2, 3, null, <http://example.org/a>]"^^cdt:List

cdt:List cdt:concat ( cdt:List term₁, ..., cdt:List term_n )

If all arguments (i.e., term₁, ..., term_n) are well-formed cdt:List literals, then the result of this function is a cdt:List literal that represents the term list that is the concatenation of the term lists represented by term₁ to term_n (in the order in which these arguments are given). If the function is called without arguments, then the result is a cdt:List literal that represents the empty term list. If the function is called with a single argument and that argument is a well-formed cdt:List literal, then this literal is the result of this function.

An error is raised if any of the arguments is not a well-formed cdt:List literal.

Issue 2

We should define the notion of "represents" as used in this definition!

Example 35

Evaluating the SPARQL expression

cdt:concat( "[1,2,3]"^^cdt:List, "['a',null,'a',2,3]"^^cdt:List )

results in the following cdt:List literal.

"[1,2,3,'a',null,'a',2,3]"^^cdt:List

xsd:boolean cdt:contains ( cdt:List term₁, RDF term term₂ )

If term₁ is a well-formed cdt:List literal, then the result of this function is determined by the following algorithm.

If term₂ is a blank node, return false.
If the term list represented by term₁ contains an RDF term term' such that evaluating the SPARQL expression term' = term₂ results in true, return true.
Return false.

An error is raised if term₁ is not a well-formed cdt:List literal.

Example 36

Evaluating the SPARQL expression

cdt:contains( "[1,2,3]"^^cdt:List, "02"^^xsd:integer )

results in true, whereas the expression

cdt:contains( "[1,2,3]"^^cdt:List, "2" )

results in false.

RDF term cdt:head ( cdt:List term )

If term is a well-formed cdt:List literal, the term list represented by term contains at least one element, and the element at the first position of this term list is an RDF term (i.e., not null), then the result of this function is that RDF term. In all other cases an error is raised.

Example 37

Evaluating the SPARQL expression

cdt:head( "[<http://example.org/a>, <http://example.org/b>]"^^cdt:List )

results in the IRI http://example.org/a.

Note

By its definition as given above, cdt:head raises an error not only if the given cdt:List literal is not well-formed but also in the following cases:

if term is a well-formed cdt:List literal that represents the empty term list, and
if the element at the first position of the term list represented by term is null.

cdt:List cdt:reverse ( cdt:List term )

If term is a well-formed cdt:List literal, then the result of this function is a cdt:List literal that represents the term list that contains all elements of the term list represented by term, in the reverse order (e.g., the first element of the term list of term becomes the last element of the term list represented by the resulting cdt:List literal). This definition implies that

if the term list of term consists of a single element, then the resulting cdt:List literal represents the same term list (with the same element), and
if term represents the empty term list, then the resulting cdt:List literal also represents the empty term list.

An error is raised if term is not a well-formed cdt:List literal.

Example 38

Evaluating the SPARQL expression

cdt:reverse( "['a',2,null,4]"^^cdt:List )

results in the following cdt:List literal.

"[4,null,2,'a']"^^cdt:List

cdt:List cdt:subseq ( cdt:List term, xsd:integer idx )

cdt:List cdt:subseq ( cdt:List term, xsd:integer idx, xsd:integer length )

If term is a well-formed cdt:List literal, then the result of this function is determined as follows. Let tm be the term list represented by term and let n be the number of elements contained in tm.

If the value of idx is greater than 0 (zero) and smaller than n+1, and length is not given, then the result of this function is a cdt:List literal that represents the term list that is the sub-sequence of tm, starting with the element at the idx-th position of tm and ending with the last element of tm.
If the value of idx is greater than 0 (zero) and smaller than n+1, and the value of length is greater than 0 (zero) and smaller than n−idx+1, then the result of this function is a cdt:List literal that represents the term list that is the sub-sequence of tm, starting with the element at the idx-th position of tm and ending with the element at position idx+length−1 of tm.
If the value of idx is greater than 0 (zero) and smaller than n+1, and the value of length is 0 (zero), then the result of this function is a cdt:List literal that represents the empty term list.
If the value of idx is equal to n+1, and either length is not given or the value of length is 0 (zero), then the result of this function is a cdt:List literal that represents the empty term list.

In all other cases an error is raised, including the case that term is not a well-formed cdt:List literal.

Example 39

Evaluating the SPARQL expression

cdt:subseq( "['a',2,null,4]"^^cdt:List, 2 )

results in the following cdt:List literal.

"[2,null,4]"^^cdt:List

Example 40

Evaluating the SPARQL expression

cdt:subseq( "['a',2,null,4]"^^cdt:List, 2, 2 )

results in the following cdt:List literal.

"[2,null]"^^cdt:List

Example 41

Evaluating the SPARQL expression

cdt:subseq( "['a',2,null,4]"^^cdt:List, 2, 0 )

results in the following cdt:List literal.

"[]"^^cdt:List

Note

As the cdt:get function, this function uses a 1-based numbering scheme to address the elements in term maps (i.e., the first element of a term map is addressed by an idx value of 1) in order to be consistent with existing build-in functions of SPARQL (e.g., substr) and with functions in other W3C languages such as XPath (e.g., array:subarray).

Note

This function corresponds to the XPath array:subarray function and, for the sake of consistency, is defined using the same rules and error conditions. As a consequence, the following special case of arguments is permitted for this function. For term maps with a size n>0, it is permitted to call the function with an idx value equal to n+1 as long as the value of length is 0 or length is omitted. When doing so, the result is a cdt:List literal that represents the empty term list.

cdt:List cdt:tail ( cdt:List term )

If term is a well-formed cdt:List literal and the term list represented by term contains at least one element, then the result of this function is a cdt:List literal that represents the term list that contains all but the first element of the term list represented by term, where the remaining elements are kept in the same order. This definition implies that, if the term list of term consists of a single element, the resulting cdt:List literal must represent the empty term list.

An error is raised if term is not a well-formed cdt:List literal or if it is a well-formed cdt:List literal that represents the empty term list.

Example 42

Evaluating the SPARQL expression

cdt:tail( "['a',2,null,4]"^^cdt:List )

results in the following cdt:List literal.

"[2,null,4]"^^cdt:List

This section defines SPARQL extension functions specifically for cdt:Map literals. These functions can be used in SPARQL expressions for testing values in FILTER clauses and for assigning values in, e.g., BIND clauses and SELECT expressions.

Except for cdt:Map and cdt:put, these extension functions are evaluated as defined in Section 17.2.1 of [SPARQL11-QUERY]. In contrast, cdt:Map and cdt:put are so-called functional forms which have specific evaluation rules (as defined in Section 9.1 cdt:Map and Section 9.5 cdt:put, respectively).

cdt:Map cdt:Map ( SPARQL expression expr₁, ..., SPARQL expression expr_n )

If n is an even number, then the result of this function is a cdt:Map literal that represents a term map tm that contains up to n/2 map entries, produced by the following algorithm.

Initialize tm as the empty term map.
For every integer i from 1 to n/2:
1. Evaluate the (2i-1)-th expression, expr_2i-1, as defined in [SPARQL11-QUERY].
2. If evaluating expr_2i-1 did not raise an error and the RDF term resulting from this evaluation is a map key, then:
  1. Let k be the RDF term resulting from the evaluation of expr_2i-1.
  2. Evaluate the 2i-th expression, expr_2i, as defined in [SPARQL11-QUERY].
  3. Let v be the RDF term resulting from the evaluation of expr_2i if this evaluation did not raise and error; otherwise, let v be null.
  4. If tm contains a map entry (k',v') such that k=k', then replace this map entry (k',v') by the map entry (k,v). Otherwise, add the map entry (k,v) to tm.

If n is an odd number, an error is raised.

Note

By the given definition, every argument to this function that is meant to produce the map key of a map entry for the constructed term map but that evaluates to an error or to an RDF term that is not a map key is ignored, and so is the directly following argument (i.e., the expression that is meant to produce the corresponding map value).

Example 43

Evaluating the SPARQL expression

cdt:Map( 'hello', ?x, ?x+1, ?y )

for the solution mapping μ = {?x → "2"^^xsd:integer} results in the following cdt:List literal.

"{'hello': 2, 3: null}"^^cdt:Map

Note

If the cdt:Map function is called without arguments (i.e., n=0), then the result is a cdt:Map literal that represents the empty term map.

xsd:boolean cdt:containsKey ( cdt:Map term₁, RDF term term₂ )

If term₁ is a well-formed cdt:Map literal, then the result of this function is determined by the following algorithm.

If the term map represented by term₁ contains a map entry (k,v) such that k is the same term as term₂, return true.
Return false.

An error is raised if term₁ is not a well-formed cdt:Map literal.

Example 44

Evaluating the SPARQL expression

cdt:containsKey( "{'02'^^<http://www.w3.org/2001/XMLSchema#integer>: 'two'}"^^cdt:Map, "02"^^xsd:integer )

results in true, whereas the expression

cdt:containsKey( "{'02'^^<http://www.w3.org/2001/XMLSchema#integer>: 'two'}"^^cdt:Map, 2 )

results in false.

cdt:List cdt:keys ( cdt:Map term )

If term is a well-formed cdt:Map literal, then the result of this function is a cdt:List literal that represents a term list that consists of all map keys of the map entries contained in the term map represented by term. The order of the elements in this term list is undefined.

If term is an ill-formed cdt:Map literal, then this function produces an error.

Example 45

Evaluating the SPARQL expression

cdt:keys( "{'02'^^<http://www.w3.org/2001/XMLSchema#integer>: 'two', 2: 'also two'}"^^cdt:Map )

results in one of the following two cdt:List literals (either ordering of keys is acceptable).

"['02'^^<http://www.w3.org/2001/XMLSchema#integer>, '2'^^<http://www.w3.org/2001/XMLSchema#integer>]"^^cdt:List
"['2'^^<http://www.w3.org/2001/XMLSchema#integer>, '02'^^<http://www.w3.org/2001/XMLSchema#integer>]"^^cdt:List

Note that, beyond the ordering variations, the lexical forms of the literals within the resulting lists may also vary as long as the resulting cdt:list literal is equal to any of the two aforementioned cdt:List literals. For instance, the following cdt:List literal is also a valid result.

"['02'^^<http://www.w3.org/2001/XMLSchema#integer>, 2]"^^cdt:List

Note

If the term map represented by term is the empty term map, then the resulting cdt:List literal represents the empty term list.

cdt:Map cdt:merge ( cdt:Map term₁, cdt:Map term₂ )

If term₁ is a well-formed cdt:Map literal and term₂ is a well-formed cdt:Map literal, then the result of this function is a cdt:Map literal that represents a term map containing all map entries contained in the term map represented by term₁, together with every map entry (k,v) that is contained in the term map represented by term₂ and that has a map key k that is not in the domain of the term map of term₁.

If term₁ is an ill-formed cdt:Map literal or term₂ is an ill-formed cdt:Map literal, then this function produces an error.

Example 46

Evaluating the SPARQL expression

cdt:merge( "{1: 'one', 2: 'two'}"^^cdt:Map, "{1: 'another one', 3: 'three'}"^^cdt:Map )

results in the following cdt:Map literal (or any other cdt:Map literal that is equal to the given one).

"{1: 'one', 2: 'two', 3: 'three'}"^^cdt:Map

Note

By the definition of the cdt:merge function, and as illustrated in the example above, if the term maps of the two given cdt:Map literals contain map entries with the same key, then the respective map entry from the first of the two literals is used for the resulting merged term map. The rationale for defining cdt:merge in this way is to be consistent with the default way in which the XPath map:merge function handles duplicate keys.

Note

If the term map represented by any of the two given cdt:Map literals is the empty term map, then the cdt:Map literal returned by this function represents exactly the same term map as the other of the two given cdt:Map literals (which may, of course, be the empty term map as well).

cdt:Map cdt:put ( SPARQL expression expr₁, SPARQL expression expr₂ )

cdt:Map cdt:put ( SPARQL expression expr₁, SPARQL expression expr₂, SPARQL expression expr₃ )

If evaluating the expression expr₁ results in a well-formed cdt:Map literal, hereafter denoted by lit, and evaluating the expression expr₂ results in a map key, hereafter denoted by key, then the result of this function is a cdt:Map literal that represents a term map tm produced by the following algorithm.

Initialize tm as the empty term map.
Let tm' be the term map obtained by applying the lexical-to-value mapping of the cdt:Map datatype to the lexical form of lit (i.e., tm' is the value of lit).
For every map entry (k,v) that is contained in tm':
1. If k is not the same term as key, add the map entry (k,v) to tm.
If the expression expr₃ is given and evaluating this expression does not result in an error, then add the map entry (key, term) to tm, where term is the RDF terms resulting from the evaluation of expr₃.
If the expression expr₃ is not given or evaluating this expression results in an error, then add the map entry (key, null) to tm.

In all other cases an error is raised.

Example 47

Evaluating the SPARQL expression

cdt:put( "{1: 'one'}"^^cdt:Map, 2 )

results in the following cdt:Map literal (or any other cdt:Map literal that is equal to the given one).

"{1: 'one', 2: null}"^^cdt:Map

Example 48

Evaluating the SPARQL expression

cdt:put( "{1: 'one', 2: null}"^^cdt:Map, 2, "two" )

results in the following cdt:Map literal (or any other cdt:Map literal that is equal to the given one).

"{1: 'one', 2: 'two'}"^^cdt:Map

Note

If the term map tm' represented by lit contains a map entry (k,v) such that k is the same term as key and v is the same term as the result of evaluating expr₃ (resp. v is null and either expr₃ is not given or evaluating expr₃ results in an error), then the cdt:Map literal returned by this function represents exactly the same term map as lit; i.e., tm'.

cdt:Map cdt:remove ( cdt:Map term₁, RDF term term₂ )

If term₁ is a well-formed cdt:Map literal and term₂ is a map key, then the result of this function is a cdt:Map literal that represents a term map containing all map entries contained in the term map represented by term₁, except for any map entry whose map key is the same term as term₂.

If term₁ is a well-formed cdt:Map literal and term₂ is not a map key, then the result of this function is term₁.

If term₁ is an ill-formed cdt:Map literal, then this function produces an error.

Example 49

Evaluating the SPARQL expression

cdt:remove( "{1: 'one', 2: null}"^^cdt:Map, 2 )

results in the following cdt:Map literal (or any other cdt:Map literal that is equal to the given one).

"{1: 'one'}"^^cdt:Map

Example 50

Evaluating the SPARQL expression

cdt:remove( "{1: 'one'}"^^cdt:Map, 1 )

results in a cdt:Map literal that represents the empty term map.

Example 51

Evaluating the SPARQL expression

cdt:remove( "{'01'^^<http://www.w3.org/2001/XMLSchema#integer>: 'one'}"^^cdt:Map, '1'^^<http://www.w3.org/2001/XMLSchema#integer> )

results in the cdt:Map literal given as the first argument (or any other cdt:Map literal that is equal to the given one). The fact that the term map represented by the given cdt:Map literal is not changed in this case is because the map key of the map entry in this term map is not the same term as the second argument given to the function (while both are literals that even represent the same value, they having different lexical forms).

Example 52

Evaluating the SPARQL expression

cdt:remove( "{'01'^^<http://www.w3.org/2001/XMLSchema#integer>: 'one'}"^^cdt:Map, BNODE() )

results in the cdt:Map literal given as the first argument, because the second argument is a blank node, which is not a map key.

This section extends the definition of the ORDER BY clause of SPARQL to explicitly define the relative order of two RDF terms that both are cdt:List literals or cdt:Map literals.

According to the definition of ORDER BY ordering in Section 15.1 of [SPARQL11-QUERY], cdt:List literals and cdt:Map literals are ordered higher than any blank node and any IRI (because they are RDF literals).

Given two cdt:List literals lit₁ and lit₂, if they both are well-formed, the relative order of these two literals is determined by the algorithm listed below. In brief, the algorithm operates as follows: It iterates over the term lists of both literals and compares their elements pairwise. For every pair for which both elements are null, the algorithm advances to the next pair. Once the algorithm comes across a pair with only one null value, the corresponding cdt:List literal that contains this null value is ordered lower than the other cdt:List literal. If none of the two elements in the current pair is null, and one of the two elements is ordered higher than the other element, then the cdt:List literal from which this higher-ordered element originates is defined as ordered higher than the other cdt:List literal. It may also be possible that the relative order of the two elements in such a pair is undefined. In such a case the relative order of the two cdt:List literals is undefined as well, unless the two elements are equal, in which case the algorithm also advances to the next pair. If the algorithm reaches the end of at least one of the two term lists and the other term list contains further elements, then the cdt:List literal with the larger term list is ordered higher. If no decision can be made based on any of the aforementioned conditions, then the relative order of the two literals is determined based on their lexical forms.

Let list₁ be the term list obtained by applying the lexical-to-value mapping of the cdt:List datatype to the lexical form of lit₁ (i.e., list₁ is the value of lit₁).
Let list₂ be the term list obtained by applying the lexical-to-value mapping of the cdt:List datatype to the lexical form of lit₂ (i.e., list₂ is the value of lit₂).
For every integer i from 1 to n, where n is the minimum of the length of list₁ and the length of list₂:
1. Let elmt₁ be the i-th element in list₁.
2. Let elmt₂ be the i-th element in list₂.
3. If elmt₁ is null and elmt₂ is not null, then lit₂ is ordered higher than lit₁.
4. If elmt₂ is null and elmt₁ is not null, then lit₁ is ordered higher than lit₂.
5. If neither elmt₁ nor elmt₂ is null (i.e., both are RDF terms), then:
  1. If the relative order of elmt₁ and elmt₂ is defined such that elmt₁ is ordered higher than elmt₂ (according to the definition in Section 15.1 of [SPARQL11-QUERY], and also considering the extension of this definition as provided in this section), then lit₁ is ordered higher than lit₂.
  2. If the relative order of elmt₁ and elmt₂ is defined such that elmt₂ is ordered higher than elmt₁, then lit₂ is ordered higher than lit₁.
  3. If evaluating the SPARQL expression elmt₁ = elmt₂ results in false or in an error, then the relative order of lit₁ and lit₂ is undefined.
If the length of list₁ is greater than the length of list₂, then lit₁ is ordered higher than lit₂.
If the length of list₂ is greater than the length of list₁, then lit₂ is ordered higher than lit₁.
Let str₁ be the literal that has the same lexical form as lit₁ and the datatype IRI xsd:string.
Let str₂ be the literal that has the same lexical form as lit₂ and the datatype IRI xsd:string.
If str₁ is ordered higher than str₂, then lit₁ is ordered higher than lit₂.
If str₂ is ordered higher than str₁, then lit₂ is ordered higher than lit₁.
The relative order of lit₁ and lit₂ is undefined.

If at least one of the two literals, lit₁ or lit₂, is ill-formed, then their relative order is undefined.

Given two cdt:Map literals lit₁ and lit₂, if they both are well-formed, the relative order of these two literals is determined by the following algorithm.

Let map₁ be the term map obtained by applying the lexical-to-value mapping of the cdt:Map datatype to the lexical form of lit₁ (i.e., map₁ is the value of lit₁).
Let map₂ be the term map obtained by applying the lexical-to-value mapping of the cdt:Map datatype to the lexical form of lit₂ (i.e., map₂ is the value of lit₂).
Let entrylist₁ be a list of all map entries that are contained in map₁, ordered based on their respective map keys by using the same order as defined in Step 6 of the algorithm in Section 6.4 map-less-than.
Let entrylist₂ be a list of all map entries that are contained in map₂, ordered in the same way as entrylist₁.
For every integer i from 1 to n, where n is the minimum of the respective length of entrylist₁ and of entrylist₂:
1. Let (k₁, v₁) be the i-th map entry in entrylist₁.
2. Let (k₂, v₂) be the i-th map entry in entrylist₂.
3. If evaluating the SPARQL expression SAMETERM(k₁, k₂) results in false, then:
  1. If k₁ is ordered before k₂ according to the ordering of map keys as used above for creating entrylist₁ (and as defined in Step 6 of the algorithm in Section 6.4 map-less-than), then lit₁ is ordered before lit₂.
  2. lit₂ is ordered before lit₁.
4. If v₁ is null and v₂ is not null, then lit₂ is ordered higher than lit₁.
5. If v₂ is null and v₁ is not null, then lit₁ is ordered higher than lit₂.
6. If neither v₁ nor v₂ is null (i.e., both are RDF terms), then:
  1. If the order of v₁ and v₂ is defined such that v₁ is ordered higher than v₂, then lit₁ is ordered higher than lit₂.
  2. If the order of v₁ and v₂ is defined such that v₂ is ordered higher than v₁, then lit₂ is ordered higher than lit₁.
  3. If evaluating the SPARQL expression v₁ = v₂ results in false or in an error, then the relative order of lit₁ and lit₂ is undefined.
If the length of entrylist₁ is greater than the length of entrylist₂, then lit₁ is ordered higher than lit₂.
If the length of entrylist₂ is greater than the length of entrylist₁, then lit₂ is ordered higher than lit₁.
Let str₁ be the literal that has the same lexical form as lit₁ and the datatype IRI xsd:string.
Let str₂ be the literal that has the same lexical form as lit₂ and the datatype IRI xsd:string.
If str₁ is ordered higher than str₂, then lit₁ is ordered higher than lit₂.
If str₂ is ordered higher than str₁, then lit₂ is ordered higher than lit₁.
The relative order of lit₁ and lit₂ is undefined.

If at least one of the two literals, lit₁ or lit₂, is ill-formed, then their relative order is undefined.

This section defines a new SPARQL Set Function, FOLD, used to construct composite values. As illustrated in Section 2.3 FOLD Aggregate, this function can be used to collect individual values into cdt:List literals and cdt:Map literals.

Adding the FOLD aggregate to SPARQL requires the following extension of the Aggregate production of the SPARQL grammar. The part in which the extended production differs from the corresponding production in the original grammar is marked in bold font. The given production rule uses several symbols for which no production rule is provided below (e.g., Expression, OrderCondition); the production rules for these symbols are defined as given in the original SPARQL grammar.

[127+] Aggregate ::= 'COUNT' '(' 'DISTINCT'? ( '*' | Expression ) ')' | 'SUM' '(' 'DISTINCT'? Expression ')' | 'MIN' '(' 'DISTINCT'? Expression ')' | 'MAX' '(' 'DISTINCT'? Expression ')' | 'AVG' '(' 'DISTINCT'? Expression ')' | 'SAMPLE' '(' 'DISTINCT'? Expression ')' | 'GROUP_CONCAT' '(' 'DISTINCT'? Expression ( ';' 'SEPARATOR' '=' String )? ')' | 'FOLD' '(' 'DISTINCT'? Expression ( ',' Expression )? ( 'ORDER' 'BY' OrderCondition+ )? ')'

Based on the SPARQL grammar, the SPARQL specification defines the process of converting graph patterns and solution modifiers in a SPARQL query string into a SPARQL algebra expression (see Section 18.2 of [SPARQL11-QUERY]). This process must be adapted to consider FOLD clauses as added by the extended grammar introduced above. In particular, the step of translating grouping and aggregation during this process needs to be extended. The original algorithm that defines this translation is given in Section 18.2.4.1 of [SPARQL11-QUERY]. The extended version of the algorithm is given as follows, where the parts that are modified or added to cover the FOLD operator are marked in bold font.

Let A := the empty sequence
Let Q := the query level being evaluated
Let P := the algebra translation of the GroupGraphPattern of the query level
Let E := [], a list of pairs of the form (variable, expression)

If Q contains GROUP BY exprlist
   Let G := Group(exprlist, P)
Else If Q contains an aggregate in SELECT, HAVING, ORDER BY
   Let G := Group((1), P)
Else
   skip the rest of the aggregate step
   End

Global i := 1   # Initially 1 for each query processed

For each (X AS Var) in SELECT, each HAVING(X), and each ORDER BY X in Q
  For each unaggregated variable V in X
      Replace V with Sample(V)
      End
  For each aggregate R(args ORDER BY orderconditions; scalarvals) now in X
      # note ORDER BY clause may be omitted
      # note scalarvals may be omitted, then it's equivalent to the empty set
      If aggregate contains ORDER BY orderconditions
          G := OrderGroups(G, orderconditions)
          End
      If R = Fold
          If |args| = 1
              setfunc = Fold1
          Else
              setfunc = Fold2
              End
      Else
          setfunc = R
          End
      A_i := Aggregation(args, setfunc, scalarvals, G)
      Replace R(...) with agg_i in Q
      i := i + 1
      End
  End

For each variable V appearing outside of an aggregate
   A_i := Aggregation(V, Sample, {}, G)
   E := E append (V, agg_i)
   i := i + 1
   End

A := A_i, ..., A_i-1
P := AggregateJoin(A)

Notice that the extended algorithm uses the new algebra symbol OrderGroups. Hence, to use this algorithm, the list of symbols in the SPARQL algebra (as given in the second table of Section 18.2 [SPARQL11-QUERY]) needs to be extended by adding this symbol. The evaluation semantics of algebra expressions that contain this symbol is defined in the following.

This section defines an operator for evaluating the new algebra symbol (as Section 18.5 of [SPARQL11-QUERY] does for the standard SPARQL algebra symbols). This operator has the same name as the algebra symbol and shall be used in the following section to extend the evaluation semantics of algebra expressions that may contain the new algebra symbol.

Definition: OrderGroups

Let { key₁→Ψ₁, ..., key_m→Ψ_m } be a partial function from keys to solution sequences. OrderGroups({ key₁→Ψ₁, ..., key_m→Ψ_m }, condition) is also a partial function from keys to solution sequences that is defined as follows:

OrderGroups({ key₁→Ψ₁, ..., key_m→Ψ_m }, condition) = { key₁→OrderBy(Ψ₁, condition), ..., key_m→OrderBy(Ψ_m, condition) }

Two new set functions are introduced to support the FOLD aggregate:

Fold1 is a SPARQL set function which combines the elements in the aggregate group into a cdt:List literal.

Definition: Fold1

cdt:List Fold1(sequence S)

L = Flatten(S)

n = |L|

Fold1(S) is a cdt:List literal that represents a term list tm that contains n elements where, for every i in {1, ..., n}, the element at the i-th position of tm is determined as follows: If the element at the i-th position of L is an error, then the element at the i-th position of tm is null. Otherwise, the element at the i-th position of tm is the element at the i-th position of L.

Note

If S is the empty sequence, then n=0 and, thus, the result of Fold1(S) is a cdt:List literal that represents the empty term list.

Note

By its definition, Fold1 behaves in the same way as the cdt:List function if that function is invoked by passing each element of L as a separate argument.

Fold2 is a SPARQL set function which combines the elements in the aggregate group into a cdt:Map literal.

Definition: Fold2

cdt:Map Fold2(sequence S)

L = Flatten(S)

n = |L|
Note that n is an even number, which is due to i) the grammar of the FOLD aggregate, ii) the corresponding translation to the algebra, and iii) the definition of the Aggregation operator.

Fold2(S) is a cdt:Map literal that represents a term map tm that is constructed by the following algorithm.

Initialize tm as the empty term map.
For every integer i from 1 to n/2:
1. Let k be the element at the (2i-1)-th position of L.
2. Let v be the element at the 2i-th position of L.
3. If k is neither an error nor a blank node, then:
  1. If tm contains a map entry (k',v') such that k=k', then replace this map entry (k',v') by the map entry (k,v). Otherwise, add the map entry (k,v) to tm.

Note

If S is the empty sequence, then n=0 and, thus, the result of Fold2(S) is a cdt:Map literal that represents the empty term map.

Note

By its definition, Fold2 behaves in the same way as the cdt:Map function if that function is invoked by passing each element of L as a separate argument.

The SPARQL specification defines a function eval(D(G), algebra expression) as the evaluation of an algebra expression with respect to a dataset D having active graph G (see Section 18.6 of [SPARQL11-QUERY]). The definition of this function is recursive. To cover algebra expressions that may contain the new algebra symbol (OrderGroups) the definition of this function needs to be extended with the following additional case.

Definition: Evaluation of OrderGroups

eval(D(G), OrderGroups(L, orderconditions)) = OrderGroups(eval(D(G), L), orderconditions)

This section defines an extension of the SPARQL language that adds a new operator called UNFOLD. As illustrated in Section 2.4 UNFOLD Operator, this operator can be used to transform composite values (given in the form of cdt:List literals or cdt:Map literals) into their individual components and assigns these components separately to new query variables.

In particular, recall from Section 2.4 UNFOLD Operator that there are two variations of this operator: one that assigns a single new query variable (i.e., UNFOLD(expr AS ?v1)) and another one that assigns two new query variables (i.e., UNFOLD(expr AS ?v1, ?v2)). When applied to cdt:List literals, the one-variable version binds the new variable to each of the RDF terms in the corresponding term list (or leaves it unbound for null values) and the two-variables version binds the first new variable to each RDF term in the term list (or leaves it unbound for null values) and the second variable to the corresponding position of the term/null in the list. When applied to cdt:Map literals, the one-variable version binds the variable to each of the keys in the term map and the two-variables version binds the first variable to each key in the term map and the second variable to the corresponding value (or leaves it unbound for null values).

Note

Note that there is an asymmetry between the two-variables version of UNFOLD for cdt:List literals and the two-variables version for cdt:Map literals. In the case of maps, the values are assigned to the second variable whereas, for lists, the values (the list elements) are assigned to the first variable.

While it would be possible to eliminate this asymmetry by changing the two-variables version of UNFOLD for cdt:List literals such that the list elements are assigned to the second variable (and the positions to the first variable), doing so would introduce another asymmetry: This asymmetry would then be between the so-changed two-variables version and the one-variable version of UNFOLD for cdt:List literals, because the latter binds the first (and, in this case, only) variable to the values. A follow-up change to eliminate this asymmetry as well may be to define the one-variable version such that it assigns the (single) variable to the positions and not to the list elements. However, this definition would have a very limited practical value and, thus, the initially mentioned asymmetry is considered as the best possible compromise.

Adding this new UNFOLD operator to the language requires an extension to the grammar of SPARQL, an extension of the SPARQL algebra, and corresponding extensions both of the process of converting SPARQL graph patterns into SPARQL algebra expressions and of the evaluation semantics. The following sections define these extensions.

Adding the UNFOLD operator to SPARQL requires the following extension of the GraphPatternNotTriples production of the SPARQL grammar. The part in which the extended production differs from the corresponding production in the original grammar is marked in bold font. The second production defined below (i.e., Unfold) needs to be added and has no counterpart in the original grammar. The given production rules use several symbols for which no production rule is provided below (e.g., GroupOrUnionGraphPattern, Expression); the production rules for these symbols are defined as given in the original SPARQL grammar.

[56+]	`GraphPatternNotTriples`	::=	GroupOrUnionGraphPattern `\|` OptionalGraphPattern `\|` MinusGraphPattern `\|` GraphGraphPattern `\|` ServiceGraphPattern `\|` Filter `\|` GroupOrUnionGraphPattern `\|` Bind `\|` InlineData `\|` Unfold
[174]	`Unfold`	::=	`'UNFOLD'` `'('` Expression `'AS'` Var `(` `','` Var `)?` `')'`

Two additional constraints MUST be satisfied when using the UNFOLD operator:

For every expression of the form UNFOLD(expr AS v, v'), v and v' MUST be two different variables.
Second, the variable(s) assigned in an UNFOLD operator must not be already in use; more formally:

For every expression of the form UNFOLD(expr AS v), the variable v MUST NOT be in-scope from the preceding elements in the group graph pattern in which the expression is used.
For every expression of the form UNFOLD(expr AS v, v'), the variable v MUST NOT be in-scope from the preceding elements in the group graph pattern in which the expression is used, and the same holds for the variable v'.

The notion of in-scope variables as used in the second constraint is defined in Section 18.2.1 of [SPARQL11-QUERY]. When using the extended syntax with the UNFOLD operator, this notion must be extended as well. To capture this extension formally, the table in Section 18.2.1 of [SPARQL11-QUERY] is augmented with the following two additional rows.

Syntax Form	In-scope variables
`UNFOLD(expr AS v)`	`v` is in-scope
`UNFOLD(expr AS v, v')`	`v` and `v'` are in-scope

Based on the SPARQL grammar, the SPARQL specification defines the process of converting graph patterns and solution modifiers in a SPARQL query string into a SPARQL algebra expression (see Section 18.2 of [SPARQL11-QUERY]). This process must be adapted to consider UNFOLD clauses as added by the extended grammar introduced above. In particular, the step of translating group graph patterns (GroupGraphPattern) during this process needs to be extended. The original algorithm that defines this translation is given in Section 18.2.2.6 of [SPARQL11-QUERY]. The extended version of the algorithm is given as follows, where the parts that are added to cover the UNFOLD operator are marked in bold font.

Let G := the empty pattern, a basic graph pattern which is the empty set.

For each element E in the GroupGraphPattern

    If E is of the form OPTIONAL{P}
        Let A := Translate(P)
        If A is of the form Filter(F, A2)
            G := LeftJoin(G, A2, F)
        Else
            G := LeftJoin(G, A, true)
            End
        End

    If E is of the form MINUS{P}
        G := Minus(G, Translate(P))
        End

    If E is of the form BIND(expr AS var)
        G := Extend(G, var, expr)
        End

If E is of the form UNFOLD(expr AS var)
    G := Unfold1(G, var, expr)
    End

If E is of the form UNFOLD(expr AS var1, var2)
    G := Unfold2(G, var1, var2, expr)
    End

    If E is any other form
        Let A := Translate(E)
        G := Join(G, A)
        End

   End

The result is G.

Notice that the extended algorithm uses two new algebra symbols: Unfold1 and Unfold2. Hence, to use this algorithm, the list of symbols in the SPARQL algebra (as given in the second table of Section 18.2 [SPARQL11-QUERY]) needs to be extended by adding these two symbols. The evaluation semantics of algebra expressions that contain any of these two symbols is defined in the following.

This section defines operators for evaluating the two new algebra symbols (as Section 18.5 of [SPARQL11-QUERY] does for the standard SPARQL algebra symbols). These operators have the same name as the algebra symbols and shall be used in the following section to extend the evaluation semantics of algebra expressions that may contain the two new algebra symbols.

The operator for evaluating Unfold1 is defined as follows.

Definition: Unfold1

Let μ be a solution mapping, var be a variable, and expr be an expression.
Then, Unfold1(μ, var, expr) is a multiset of solution mappings that is defined as follows:

If var ∉ dom(μ) and expr(μ) is a well-formed cdt:List literal, then
- Unfold1(μ, var, expr) = { μ | L contains null } ∪ Ω', where
  L is the term list represented by the cdt:List literal expr(μ) and
  Ω' = { μ ∪ (var, term) | term is an RDF term in L },
- card[Unfold1(μ, var, expr)](μ') = 0 for every μ' ≠ μ and μ' ∉ Ω',
- card[Unfold1(μ, var, expr)](μ') is the number of null values in L if μ' = μ, and
- card[Unfold1(μ, var, expr)](μ') is the number of times the RDF term μ'(var) is contained in L if μ' ∈ Ω'.
If var ∉ dom(μ) and expr(μ) is a well-formed cdt:Map literal, then
- Unfold1(μ, var, expr) = { μ ∪ (var, key) | key is the key of a map entry in M }, where
  M is the term map represented by the cdt:Map literal expr(μ),
- card[Unfold1(μ, var, expr)](μ') = 1 for every μ' ∈ Unfold1(μ, var, expr), and
- card[Unfold1(μ, var, expr)](μ') = 0 for every μ' ∉ Unfold1(μ, var, expr).
If var ∉ dom(μ) and expr(μ) is an error or an RDF term that is neither a well-formed cdt:List literal nor a well-formed cdt:Map literal, then
- Unfold1(μ, var, expr) = {μ},
- card[Unfold1(μ, var, expr)](μ') = 1 if μ' = μ, and
- card[Unfold1(μ, var, expr)](μ') = 0 for every μ' ≠ μ.
If var ∈ dom(μ), then Unfold1(μ, var, expr) is undefined.

Let Ω a multiset of solution mappings. We define:
Unfold1(Ω, var, expr) = ⋃_{μ ∈ Ω} Unfold1(μ, var, expr)

Note

By the given definition , for cases in which var ∉ dom(μ) and expr(μ) is a well-formed cdt:List literal that represents the empty term list, Unfold1(μ, var, expr) is the empty multiset of solution mappings. Similarly, if var ∉ dom(μ) and expr(μ) is a well-formed cdt:Map literal that represents the empty term map, then Unfold1(μ, var, expr) is also the empty multiset.

The operator for evaluating Unfold2 is defined as follows.

Definition: Unfold2

Let μ be a solution mapping, var₁ and var₂ be two different variables, and expr be an expression.
Then, Unfold2(μ, var₁, var₂, expr) is a multiset of solution mappings that is defined as follows:

If var₁ ∉ dom(μ), var₂ ∉ dom(μ), and expr(μ) is a well-formed cdt:List literal such that the term list L represented by this literals is a nonempty, then
- Unfold2(μ, var₁, var₂, expr) = { μ ∪ μ_i ∪ (var₂, i) | 1 ≤ i ≤ n }, where
  μ_i is the empty solution mapping if the element at the i-th position of L is null,
  otherwise, μ_i = (var₁, term) where term is element at the i-th position of L, and
  n is the number of elements in L,
- card[Unfold1(μ, var, expr)](μ') = 1 for every μ' ∈ Unfold2(μ, var₁, var₂, expr), and
- card[Unfold1(μ, var, expr)](μ') = 0 for every μ' ∉ Unfold2(μ, var₁, var₂, expr).
If var₁ ∉ dom(μ), var₂ ∉ dom(μ), and expr(μ) is a well-formed cdt:List literal that represents the empty term list, then Unfold2(μ, var₁, var₂, expr) is the empty multiset.
If var₁ ∉ dom(μ), var₂ ∉ dom(μ), and expr(μ) is a well-formed cdt:Map literal, then
- Unfold2(μ, var₁, var₂, expr) = { μ ∪ (var₁, k) ∪ μ_v | (k,v) is a map entry in M }, where
  μ_v is the empty solution mapping if v is null, otherwise, μ_v = (var₂, v), and
  M is the term map represented by the cdt:Map literal expr(μ),
- card[Unfold2(μ, var₁, var₂, expr)](μ') = 1 for every μ' ∈ Unfold2(μ, var₁, var₂, expr),
- card[Unfold2(μ, var₁, var₂, expr)](μ') = 0 for every μ' ∉ Unfold2(μ, var₁, var₂, expr).
If var₁ ∉ dom(μ), var₂ ∉ dom(μ), and expr(μ) is an error or an RDF term that is neither a well-formed cdt:List literal nor a well-formed cdt:Map literal, then
- Unfold2(μ, var₁, var₂, expr) = {μ},
- card[Unfold2(μ, var₁, var₂, expr)](μ') = 1 if μ' = μ, and
- card[Unfold2(μ, var₁, var₂, expr)](μ') = 0 for every μ' ≠ μ.
If var₁ ∈ dom(μ) or var₂ ∈ dom(μ), then Unfold2(μ, var₁, var₂, expr) is undefined.

Let Ω a multiset of solution mappings. We define:
Unfold2(Ω, var₁, var₂, expr) = ⋃_{μ ∈ Ω} Unfold2(μ, var₁, var₂, expr)

Note

While the given definition captures the case of cdt:List literals with the empty term list explicitly (see the second main bullet point in the definition), the case of cdt:Map literals with the empty term map are captured implicitly as part of the third main bullet point. In this case, the result of Unfold2(μ, var₁, var₂, expr) is also the empty multiset of solution mappings.

The SPARQL specification defines a function eval(D(G), algebra expression) as the evaluation of an algebra expression with respect to a dataset D having active graph G (see Section 18.6 of [SPARQL11-QUERY]). The definition of this function is recursive. To cover algebra expressions that may contain the two new algebra symbols (Unfold1 and Unfold2) the definition of this function needs to be extended with the following two additional cases.

Definition: Evaluation of Unfold1

eval(D(G), Unfold1(P, var, expr)) = Unfold1(eval(D(G), P), var, expr)

Definition: Evaluation of Unfold2

eval(D(G), Unfold2(P, var1, var2, expr)) = Unfold2(eval(D(G), P), var1, var2, expr)

`:`	`<http://www.example.org/>`
`ex:`	`<http://example.org/>`
`rdf:`	`<http://www.w3.org/1999/02/22-rdf-syntax-ns#>`
`foaf:`	`<http://xmlns.com/foaf/0.1/>`
`cdt:`	`<http://w3id.org/awslabs/neptune/SPARQL-CDTs/>`

SPARQL CDTs: Representing and Querying Lists and Maps as RDF Literals

Abstract

Status of This Document

1. Introduction

1.1 Background and Motivation

1.2 Structure of this Document (TODO)

1.3 Document Conventions (TODO)

1.4 Conformance

2. Informal Description of the Approach

2.1 Representation of Composite Values as RDF Literals

2.2 SPARQL Functions on Composite Datatype Literals

2.3 FOLD Aggregate

2.4 UNFOLD Operator

2.5 Comparing Composite Datatype Literals

2.6 Ordering Composite Datatype Literals

3. The cdt:List Datatype

3.1 Value Space

3.2 Lexical Space

3.3 Lexical-To-Value Mapping

3.4 Relationship to RDF Collections

4. The cdt:Map Datatype

4.1 Value Space

4.2 Lexical Space

4.3 Lexical-To-Value Mapping

4.4 Relationship to JSON

5. Importing and Exporting of Composite Values

5.1 Motivation

5.2 Importing Requirements

5.3 Exporting Requirements

6. Extensions of Existing SPARQL Operators

6.1 list-equal

6.2 map-equal

6.3 list-less-than

6.4 map-less-than

7. Functions on Lists and Maps

7.1 cdt:get

7.2 cdt:size

8. Functions on Lists

8.1 cdt:List

8.2 cdt:concat

8.3 cdt:contains

8.4 cdt:head

8.5 cdt:reverse

8.6 cdt:subseq

8.7 cdt:tail

9. Functions on Maps

9.1 cdt:Map

9.2 cdt:containsKey

9.3 cdt:keys

9.4 cdt:merge

9.5 cdt:put

9.6 cdt:remove

10. Extension of ORDER BY

10.1 Relative Order of cdt:List Literals

10.2 Relative Order of cdt:Map Literals

11. FOLD

11.1 Grammar

11.2 Translation to the Algebra

11.3 Algebra

11.3.1 Aggregate Algebra

11.3.1.1 Fold1

11.3.1.2 Fold2

11.4 Evaluation Semantics

12. UNFOLD

12.1 Grammar

12.2 Translation to the Algebra

12.3 Algebra

12.4 Evaluation Semantics

A. IANA Considerations

B. Complete EBNF Grammars

B.1 Composite Datatypes EBNF Grammar

B.2 SPARQL-CDT EBNF Grammar

C. References

C.1 Normative references

C.2 Informative references