SPARQL 1.1 Entailment Regimes

1.1.1 Graph Syntax

This document uses the Turtle [TURTLE] data format to show triples explicitly. This notation uses a node identifier (nodeID) convention to indicate blank nodes in the triples of a graph. While node identifiers such as _:xxx serve to identify blank nodes in the surface syntax, these expressions are not considered to be the label of the graph node they identify; they are not names, and do not occur in the actual graph. In particular, the RDF graphs described by two Turtle documents which differ only by re-naming their node identifiers will be understood to be equivalent. This re-naming convention should be understood as applying only to whole documents, since re-naming the node identifiers in part of a document may result in a document describing a different RDF graph. A generated blank node may also be made with [].

IRIs are written enclosed in < and > and may be absolute RDF IRI References or relative to the current base IRI. IRIs may also be abbreviated by using Turtle's @prefix directive that allows declaring a short prefix name for a long prefix of repeated IRIs. Once a prefix such as @prefix foo: <http://example.org/ns#> is defined, any mention of an IRI later in the document may use a qualified name that starts foo: to stand for the longer IRI. For example, the qualified name foo:bar is a shorthand for the IRI http://example.org/ns#bar.

For example, the following triples use prefixes and abbreviated IRIs and also non-abbreviated IRIs such as <book2>, which are relative to the base IRI of the document.

1.1.2 Namespaces

Examples assume the following namespace prefix bindings unless otherwise stated:

In the interests of brevity, the prefix ex: is also used in the examples. The prefix is assumed to be bound to an imaginary IRI such as http://www.example.org/.

1.1.3 Preliminary Definitions

This document uses the same definitions as the SPARQL Query Language specification and we recapture the most important terms here for clarity. In the case of any difference, the SPARQL Query Language definitions are the normative ones.

We use RDF-L for the set of all RDF Literals, RDF-B for the set of all blank nodes in RDF graphs, and RDF-T for the set of RDF Terms, which is a union of the set of all IRIs, RDF-L, and RDF-B.

We use V for the set of query variables, where V is infinite and disjoint from RDF-T. A triple pattern is member of the set:

(RDF-T union V) x (I union V) x (RDF-T union V),

A Basic Graph Pattern is a set of Triple Patterns.

2.1.1 Examples for the Restrictions on Solutions (Informative)

The following example illustrates the use of both conditions C1 and C2. Consider the query

against a graph containing only the triples

We assume that the scoping graph is the same as the active graph, i.e., the graph for the triples shown above. As part of the possible solutions we find { (x, ex:b) } since according to the RDF entailment rule rdf1

entails

Further, from the axiomatic triples, we also get the possible solutions { (x, rdf:_1) }, { (x, rdf:_2) }, ... We get even more possible answers since the simple entailment rule se2 means that

RDF entails

for some blank node _:exb1 allocated to ex:b and { (x, _:exb1) } is a possible solution. The rule se2 can be applied again to the just mentioned triple and we get that the following triple is also entailed by the queried graph

for some blank node _:exb2 allocated to _:exb1 and { (x, _:exb2) } is a possible solution too. We can in fact infer infinitely many blank nodes to be possible solutions to the query.

Clearly, the set of possible solutions is infinite in this case, but for a possible solution to actually be a solution, the two conditions C1 and C2 have to be met: (C1) each subject s of a triple ( s, p, o ) in P(BGP) occurs in the scoping graph and (C2) each blank node b in the range of μ and σ occurs in the scoping graph SG.

In this case, condition C1 limits the answers from the axiomatic triples. We consider the two examplary possible answers { (x, rdf:_1) } and { (x, rdf:_2) }.

• For the possible solution μ: x->rdf:_1, we can take an empty RDF instance mapping σ to obtain a pattern instance mapping P=(μ, σ) with P(BGP) =

and since the subject rdf:_1 occurs in the scoping graph (here the scoping graph and the active graph are equal) and condition C2 is trivially satisfied, and this solution mapping is actualy a solution.

• For the possible solution μ: x->rdf:_2, we can again take an empty RDF instance mapping σ to obtain a pattern instance mapping P=(μ, σ) with P(BGP) =

but since the subject rdf:_2 does not occur in the scoping graph, this solution mapping is not a solution. We can argue similarly for rdf:_n with n > 2.

The second condition rules out { (x, _:exb1) }, { (x, _:exb2) }, ... since the blank nodes _:exb1, _:exb2, ... do not occur in the scoping graph (again the scoping graph equals the active graph here). Thus, the only answers are { (x, ex:b) } and { (x, rdf:_1) }.

We give another example for RDFS entailment that shows the behavior if the query contains blank nodes and for the case where entailment really makes a difference other than adding some axiomatic triples.

2.1.2 Literals in the Subject Position (Informative)

Please note that solution mappings that map variables that occur in the subject in the basic graph pattern BGP to literals will not be returned as solutions even though there might be a pattern instance mapping P for the solution mapping such that P(BGP) is RDF entailed by the queried graph, but P(BGP) is not well-formed as required (see also the SPARQL triple patterns definition). E.g., given a query

even the empty graph would RDF entail all statements xxx rdf:type rdf:XMLLiteral for xxx a well-formed RDF XML literal, but applying a solution mapping such as μ : x -> "<a>abc</a>"^^rdf:XMLLiteral would result in a triple that is not a valid RDF triple.

Please note that triples with literals in the subject positions are currently not considered well-formed RDF, but this might be changed in the future. If literals were allowed in the subject position, condition C1 would still guarantee finite answers.

2.1.3 Boolean Queries (Informative)

The two conditions C1 and C2 also have an effect on the answers to Boolean queries. For Boolean queries that contain variables, e.g.,

this is straighforward. The query answer is yes (true) if x has at least one solution and it is no (false) otherwise. For Boolean queries without variables it is less clear how the answer is determined. We have two possible outcomes for a Boolean query without variables: there is a solution sequence containing a mapping ( μ ) where μ has an empty domain (it does not map any variable to anything) or there is only an empty solution sequence ( ). In the first case, the query answer is yes (true), whereas in the second case the query answer is no (false). Thus we can still apply the two conditions on possible solutions and check whether the solution mapping is indeed a solution. For example, if we ask the above query against the empty graph, we find that the solution mapping μ with empy domain is a possible solution, but condition C1 rules this solution mapping out as an answer and the query answer is no (false).

2.2.1 Examples for the Restrictions on Solutions (Informative)

For RDFS entailment, we consider an example that uses RDFS entailment to derive implicit consequences and we also consider a query with blank nodes in it. The active graph in this example is for the triples

We again assume that the scoping graph is the same as the active graph and the query we consider is

We deliberately chose to use a blank node in the query that occurs in the active graph. Since we consider RDFS entailment, the active graph entails a number of interesting triples such as

just to name some. The active graph does, however, not entail

since it is not the case that every RDFS interpretation must map _:a to an element that is the ex:r successor of something. The graph does also not entail

since ex:t is not a subproperty of ex:s.

From the entailed triples, we get a number of possible solutions, e.g.,

etc., but we do not get P=(μ, σ) with μ : x->_:x and σ : _:a->_:a since P(BGP) is not entailed by the scoping graph as argued above. To be solutions, the possible solution have to satisfy C1 and C2:

(C1) each subject s of a triple ( s, p, o ) in P(BGP) occurs in the scoping graph and

(C2) each blank node b in the range of μ and σ occurs in the scoping graph SG.

Here we have

and P₁ and P₃ do satisfy condition C1, but condition C2 rules out P₃ and we have a single answer { (x, _:a) } from P₁. Interestingly, it is not the case that the result of instatiating the BGP ?x ex:r _:a with the solution mapping (_:a ex:r _:a) results in a triple that is RDFS entailed by the active graph because we would have to use an appropriate RDF instance mapping too. Although _:a occurs in the BGP and in the queried graph, it is not required that the name in the query must match the name in the graph because blank nodes are just stating the existency of something. We can equally use the query

We only need names for the blank nodes in the query to enforce co-references. E.g., in the query

we ask for elements that start an ex:r ex:s chain. If the queried graph contains also a blank node _:b, then the name _:b in the query is, however, not necessarily mapped to the same element as the _:b in the queried graph.

We can consider the above example again, but this time with a scoping graph that does use different names for the blank nodes in the active graph and the query. E.g., assume that the scoping graph SG contains the triples

The query is again

The scoping graph entails a number of intersting triples such as

just to name some. The scoping graph does, however, not entail

since it is not the case that every RDFS interpretation must map _:sga to an element that is the ex:r successor of something. The graph does also not entail

since ex:t is not a subproperty of ex:s.

From the entailed triples, we get a number of possible solutions, e.g.,

etc., but we do not get P=(μ, μ) with μ : x->_:x and σ : _:a->_:sga since P(BGP) is not entailed by the scoping graph as argued above. To be solutions, the possible solution have to satisfy C1 and C2:

(C1) each subject s of a triple ( s, p, o ) in P(BGP) occurs in the scoping graph and

(C2) each blank node b in the range of μ and σ occurs in the scoping graph SG.

Here we have

and P₁ and P₃ do satisfy condition C1 and condition C2 rules out P₃ and we again have a single answer { (x, _:sga) } from P₁.

2.2.2 Inconsistencies (Informative)

An RDFS-inconsistent graph RDFS-entails any graph, but there are limited possibilities to express an inconsistency in RDFS. Every inconsistency is due to a literal of type rdf:XMLLiteral, where the lexical form is a mal-formed XML string, e.g.,

in combination with a range restriction on the property, e.g.,

The first triple alone does not cause an inconsistency. It only requires that the literal "<"^^rdf:XMLLiteral is interpreted as something that is not in the extension of rdfs:Literal. Since rdfs:Literal contains rdf:XMLLiteral, the second triple together with the first one results in an inconsistency. The following example illustrates that an inconsistency is not always as directly visible as in the example above and one might need to apply some inference rules to detect it. E.g., consider the following triples (numbers are only given to explain the inferences later):

Here we can to derive the inconsistency as follows:

At this point, we can detect the inconsistency since "<" is not a valid lexical form for an RDF XML literal and we have to interpret it as some element tha is NOT in rdfs:Literal, but at the same time it should be of type rdfs:Literal. The triple derived last is characteristic for an RDFS inconsistency.