RDF-star and SPARQL-star

1.3 Conformance

As well as sections marked as non-normative, all authoring guidelines, diagrams, examples, and notes in this specification are non-normative. Everything else in this specification is normative.

The key words MAY, MUST, and MUST NOT in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.

3.1 Turtle-star

In this section, we present Turtle-star, an extension of the Turtle format [TURTLE] allowing the representation of RDF-star graphs. For the sake of conciseness, we only describe here the differences between Turtle-star and Turtle.

@base <http://example.org/> .
@prefix : <#> .
_:a :name "Alice" .
<< _:a :name "Alice" >> :statedBy :bob .

@base <http://example.org/> .
@prefix : <#> .
_:a :name "Alice" {| :statedBy :bob |} .

3.2 TriG-star

This section describes TriG-star, a minimal extension of the TriG format [TRIG] using the same production updates described in § 3.1 Turtle-star.

A TriG-star document defines an RDF-star dataset, composed of a single default graph and zero or more named graphs, all of which are RDF-star graphs.

The TriG-star grammar contains exactly the same production updates described in § 3.1.1 Grammar.

TriG-star parsing uses the same updates described in § 3.1.2 Parsing as applied to Section 5 of the TriG specification [TRIG].

A conforming TriG-star parser MUST parse any valid TriG document and any valid Turtle-star document in addition to the Turtle-star grammar productions contained within a named graph.

@base <http://example.org/> .
@prefix : <#> .
:G {
  _:a :name "Alice" {| :statedBy :bob |} .
}

3.3 N-Triples-star

This section describes N-Triples-star, a minimal extension of the N-Triples format [N-TRIPLES] allowing a subject or an object of an RDF-star triple to be an embedded triple.

3.4 N-Quads-star

The [N-QUADS] format is extended to describe the N-Quads-star format using the same production updates described in the N-Triples-star Grammar.

An N-Quads-star document defines an RDF-star dataset, composed of a single default graph and zero or more named graphs, all of which are RDF-star graphs.

A conforming N-Quads-star parser MUST parse any valid N-Quads document and additionally parse the subject and object productions from N-Triples-star to generate RDF-star triples which are added to either the default graph or associated named graph, as appropriate.

4.1 Initial Definitions

In the following, we introduce a number of SPARQL-star-specific definitions, which rely on the following notions, defined in SPARQL 1.1 Query Language [SPARQL11-QUERY]: RDF term, query variable, triple pattern, property path pattern, property path expression, and solution mapping.

A SPARQL-star triple pattern is a 3-tuple that is defined recursively as follows:

1. Every SPARQL triple pattern is a SPARQL-star triple pattern;
2. If t and t' are SPARQL-star triple patterns, x is an RDF term or a query variable, and p is an IRI or a query variable, then (t, p, x), (x, p, t), and (t, p, t') are SPARQL-star triple patterns.

As for RDF-star triples, a SPARQL-star triple pattern MUST NOT contain itself.

A SPARQL-star basic graph pattern (BGP-star) is a set of SPARQL-star triple patterns.

A SPARQL-star property path pattern is a 3-tuple (s,p,o) where

• s is either an RDF term, a query variable, or a SPARQL-star triple pattern,
• p is a property path expression, and
• o is either an RDF term, a query variable, or a SPARQL-star triple pattern.

A SPARQL-star solution mapping μ is a partial function from the set of all query variables to the set of all RDF-star terms. The domain of μ, denoted by dom(μ), is the set of query variables for which μ is defined.

All notions related to SPARQL solution mappings carry over naturally to SPARQL-star solution mappings. In particular, the definition of compatibility extends naturally to SPARQL-star solution mappings: two SPARQL-star solution mappings μ₁ and μ₂ are compatible if, for every variable v that is both in dom(μ₁) and in dom(μ₂), μ₁(v) and μ₂(v) are the same RDF-star term. In this case, μ₁ ∪ μ₂ is also a SPARQL-star solution mapping. Moreover, for any SPARQL-star solution mapping μ we write card[Ω](μ) to denote the cardinality of μ in a multiset Ω of such mappings. Finally, given a BGP-star B and a SPARQL-star solution mapping μ, we write μ(B) to denote the result of replacing every variable v in B for which μ is defined with μ(v).

Next, we aim to carry over the notion of solutions for BGPs to BGP-star. To this end, we first define an auxiliary concept that carries over the notion of an RDF instance mapping [RDF11-MT] to RDF-star.

An RDF-star instance mapping σ is a partial function from the set of all blank nodes to the set of all RDF-star terms. The domain of σ, denoted by dom(σ), is the set of blank nodes for which σ is defined.

Similar to the corresponding notation for solution mappings, for an RDF-star instance mapping σ and a BGP-star B we write σ(B) to denote the result of replacing every blank node b in B for which σ is defined with σ(b).

Now we are ready to define the notion of solution for BGP-star.

Given a BGP-star B and an RDF-star graph G, a SPARQL-star solution mapping μ is a solution for the BGP-star B over G if it has the following two properties

• dom(μ) is equivalent to the set of query variables in B, and
• there exists an RDF-star instance mapping σ such that dom(σ) is equivalent to the set of blank nodes in B and μ(σ(B)) is a subgraph of G.

4.2 Grammar

SPARQL-star is defined to follow the same grammar as SPARQL 1.1, except for the EBNF productions specified below, which replace the productions having the same number (if any) in the original grammar. The parts in which these productions differ from the corresponding productions in the original grammar are marked in bold font. Productions [174] and following have been added and have no counterpart in the original grammar.

This introduces a notation for embedded triple patterns (production [174]), which is similar to the one defined for embedded triples in § 3.1 Turtle-star, but accepting also variables. These embedded triple patterns are allowed in both the subject position ([75], [81]) and the object position ([80], [87]) of SPARQL-star triple patterns, as well as in the short-hand notation for querying collections ([102], [103]).

Additionally, production [65] for values that can be used in the VALUES clause is extended to permit RDF-star triples as possible values, and the set of available built-in functions is extended with the five functions TRIPLE, SUBJECT, PREDICATE, OBJECT, and isTRIPLE ([121]) that are defined in § 4.4 Function Definitions.

Yet another extension is that both the Object and the ObjectPath productions now accept an optional annotation pattern after each object. The purpose of this feature is to enable users to use the same kind of annotation syntax that is supported in Turtle-star. As in the case of Turtle-star, the annotation syntax in SPARQL-star is purely syntactic sugar that has to be processed in accordance to the first expansion rule in § 4.3.2 Expand Syntax Forms.

A restriction to the use of the annotation syntax in SPARQL-star exists that is not captured by the grammar as defined above: An AnnotationPatternPath may be added only to SPARQL-star property path patterns in which the property path expression is a PredicatePath (i.e., a single IRI) or the keyword a (as a short form for the IRI rdf:type). Hence, a query such as the following violates this restriction and, thus, is invalid.

SELECT * WHERE {
    ?s :p/:q ?o {| ?pp ?oo |}.
}

While annotation patterns must not be added to property path patterns other than the ones permitted by the restriction above, it is possible to use property path expressions within annotation patterns (but without violating the restriction in the case of nested annotation patterns). For instance, the following query is valid.

SELECT * WHERE {
    ?s ?p ?o {| :p/:q ?oo |}.
}

4.3 Translation to the Algebra

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 [SPARQL11-QUERY, Section 18.2]. This process must be adjusted to consider the extended grammar introduced above. In the following, any step of the conversion process that requires adjustment is discussed.

4.4 Function Definitions

SPARQL introduces operators and functions that can be used in an expression of a FILTER clause, a BIND clause, or a SELECT clause (see Section 17.3 and Section 17.4 in [SPARQL11-QUERY]). While these operators and functions are defined to operate on RDF terms and query variables, for SPARQL-star they have to be defined to operate on RDF-star terms and query variables. To this end, when using these operators and functions in the context of SPARQL-star, their definitions as given in Section 17.4 of [SPARQL11-QUERY] are extended by assuming that any mention of RDF term as a data type for operands is understood to be the type of all RDF-star terms.

In addition to carrying over the operators and functions of SPARQL, SPARQL-star introduces five new functions that are defined as follows (where the data types RDF-star term and RDF-star triple capture all RDF-star terms and all RDF-star triples, respectively).

SELECT ?t WHERE {
  ?s ?p ?o .
  BIND( TRIPLE(?s,?p,?o) AS ?t )
  FILTER( isTRIPLE(SUBJECT(?t)) )
}

SELECT ?t WHERE {
  ?s ?p ?o .
  BIND( TRIPLE(?s,?p,?o) AS ?t )
  FILTER( isTRIPLE(?s) )
}

PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>

SELECT ?t WHERE {
  ?s ?p ?o .
  BIND( TRIPLE(?s,rdf:type,rdfs:Resource) AS ?t )
}

SELECT ( COUNT(?t1) AS ?t1Count )
       ( COUNT(?t2) AS ?t2Count )
       ( COUNT(?t3) AS ?t3Count )
       ( COUNT(DISTINCT ?t1) AS ?t1DistCount )
       ( COUNT(DISTINCT ?t2) AS ?t2DistCount )
       ( COUNT(DISTINCT ?t3) AS ?t3DistCount )
WHERE {
  GRAPH ?g {
    BIND( TRIPLE(BNODE(), :p, :o) AS ?t1 )
    BIND( TRIPLE(BNODE("id"), :p, :o) AS ?t2 )
    BIND( TRIPLE(:s, :p, :o) AS ?t3 )
  }
}

PREFIX rdf:  <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX rdfg: <http://www.w3.org/2004/03/trix/rdfg-1/>

SELECT ( COUNT(?t1) AS ?t1Count )
       ( COUNT(?t2) AS ?t2Count )
WHERE {
  GRAPH ?g {
    ?g rdf:type rdfg:Graph .
    BIND( TRIPLE(?g, rdf:type, rdfs:Resource) AS ?t1 )
    BIND( TRIPLE(?x, rdf:type, rdfs:Resource) AS ?t2 )
  }
}

4.5 Evaluation Semantics

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 [SPARQL11-QUERY, Section 18.6]. Recall that the dataset D in the context of SPARQL-star is an RDF-star dataset and, thus, the active graph G is an RDF-star graph, and so is any other graph in dataset D. The definition of the eval function is recursive; the base case of this definition for SPARQL-star are given as follows:

• For every BGP-star B, eval(D(G), B) is a multiset Ω that consists of all SPARQL-star solution mappings that are a solution for the BGP-star B over G. For every such mapping μ, card[Ω](μ) is the number of distinct RDF-star instance mappings σ such that dom(σ) is equivalent to the set of blank nodes in B and μ(σ(B)) is a subgraph of G. (For any SPARQL-star solution mapping μ' that is not a solution for B over G, we have that card[Ω](μ')=0; i.e., μ' is not in Ω.)

For any other algebra expression, the SPARQL specification defines algebra operators [SPARQL11-QUERY]. These definitions can be extended naturally to operate over multisets of SPARQL-star solution mappings (instead of ordinary solution mappings). Given this extension, the recursive steps of the definition of the eval function for SPARQL-star are the same as in the SPARQL specification.

4.6 Query Result Formats

In SPARQL, queries can take four forms: SELECT, CONSTRUCT, DESCRIBE, and ASK - see SPARQL1.1 Query, Section 16 [SPARQL11-QUERY]. The first of these returns a sequence of solution mappings that contain variable bindings. The second and third both return an RDF graph, and the last returns a boolean value.

The result of the ASK query form is not changed by the introduction of RDF-star, and the result of the CONSTRUCT and DESCRIBE forms can be represented by Turtle-star. However, since the SELECT form deals with returning individual RDF terms, the specific serialization formats for representing such query results need to be extended so that the new embedded triple RDF term can be represented. In this section, we propose extensions for the two most common formats for this purpose: SPARQL 1.1 Query Results JSON Format, and SPARQL Query Results XML Format (Second Edition).

5.2 Grammar

SPARQL-star Update is an extension of the SPARQL Update language [SPARQL11-UPDATE]. As mentioned in SPARQL 1.1 Update, Appendix C [SPARQL11-UPDATE], the grammar of the latter is provided as part of the SPARQL 1.1 Query grammar. Similarly, the grammar of SPARQL-star Update is provided as part of the grammar of the SPARQL-star query language, which is defined by the SPARQL 1.1 Query grammar with the extensions specified in § 4.2 Grammar. As a result of these extensions, the production rules QuadData and QuadPattern, which are used in the definition of SPARQL Update [SPARQL11-UPDATE], are extended to capture nested triples and nested triple patterns as demonstrated in the examples above.

5.3 Semantics

The semantics of SPARQL-star Update operations can also be defined by a simple extension of the formalization of SPARQL Update [SPARQL11-UPDATE]. This extension assumes that any mention of "RDF triple" or "triple" in the formalization of SPARQL Update is understood as an RDF-star triple. Similarly, "RDF graph" and "solution mapping" are understood as RDF-star graph and SPARQL-star solution mapping, respectively. Any mention of the "evaluation function eval()" is understood as the eval function for SPARQL-star as defined in § 4.5 Evaluation Semantics.

6.1 Mapping RDF-star abstract syntax to RDF

We consider six IRIs ST, PT, OT, SS, PS and OS that will have a special meaning in our mapping.

We define a mapping L that maps any IRI or literal t to a literal with:

• xsd:string as its datatype, and
• the canonical N-Triples representation of t as its lexical form [N-TRIPLES]. If t is itself a literal with the xsd:string datatype, the representation MUST be a simple literal.

Given an RDF-star graph G, the following steps transform it into an RDF graph that we call unstar(G).

1. Pick an RDF-star triple (s, p, o) in the constituents of G such that neither s nor o is an embedded triple.
2. Mint a fresh blank node b, and replace by b all occurrences of (s, p, o) in the subject or object position of an asserted or embedded triple of G.
3. Add the following asserted triples to G:
   • (b, ST, s)
   • (b, PT, p)
   • (b, OT, o) unless o is an ill-typed literal
   • (b, SS, L(s)) unless s is blank node
   • (b, PS, L(p))
   • (b, OS, L(o)) unless o is blank node
4. Repeat the steps above until there are no embedded triples left in G.

After these steps, unstar(G) is an RDF graph, as it contains no embedded triples. Note that if G was already an RDF graph, then unstar(G) = G.

6.2 Entailment of RDF-star graphs

Following RDF 1.1 Semantics, we extend the notions of satisfiability and entailment for RDF-star graphs. Given two RDF-star graphs G and H:

• We say that G is (simply) satisfiable (resp. unsatisfiable) if and only if unstar(G) is (simply) satisfiable (resp. unsatisfiable).
• We say that H is (simply) entailed by (resp. equivalent to) G if and only if unstar(H) is (simply) entailed by (resp. equivalent to) unstar(G).
• Other notions of satisfiability and entailment, such as RDF entailment or RDFS entailment, can be extended in the same way for RDF-star graphs.

6.3 Merging RDF-star graphs

RDF 1.1 Semantics [RDF11-MT] defines the merging of two or more RDF graphs as "[taking their] union after forcing any shared blank nodes, which occur in more than one graph, to be distinct in each graph." Note that, in the case of RDF-star graphs, any blank node in the constituent terms of that graph is governed by the definition above, not only those in the subject or object position of some asserted triple.

#### graph #1
:alice :says
  << _:x :name "bob" >>,
  << _:x :likes :alice >>.

#### graph #2
:bob :says
  << :alice :hates _:x >>.

#### Merge of graphs #1 and #2 →
:alice :says
  << _:y :name "bob" >>,
  << _:y :likes :alice >>.
:bob :says
  << :alice :hates _:z >>.