SPARQL 1.1 Entailment Regimes

1.1 Document Conventions

Throughout the document, certain conventions are used, which are outlined below.

@prefix dc:   <http://purl.org/dc/elements/1.1/> .
@prefix :     <http://example.org/book/> .
:book1  dc:title "SPARQL Tutorial" . 
<book2> dc:title "Turtle Tutorial" .

1.2 Effects of Different Entailment Regimes

The SPARQL Query specification already envisages that SPARQL can be used with entailment regimes other than simple entailment. To illustrate the differences between simple, RDF, and RDFS entailment, consider the following data:

(1) ex:book1 a ex:Publication .
(2) ex:book2 a ex:Article .
(3) ex:Article rdfs:subClassOf ex:Publication .
(4) ex:publishes rdfs:range ex:Publication .
(5) ex:MITPress ex:publishes ex:book3 .

The following query asks for a list of all publications:

SELECT ?pub WHERE { ?pub a ex:Publication }

Clearly, ex:book1 is an answer due to triple (1). Intuitively, we can expect that ex:book2 is also a publication because it is an article (2) and all articles are publications (3). Even ex:book3 is a publication because it is published by MIT Press (5) and everything that is published is a publication (4). Under simple and RDF entailment, ex:book1 is the only answer because a system that uses simple entailment will not perform any of the reasoning steps that were required to find that ex:book2 and ex:book3 are publications. Under simple entailment, the basic graph pattern ?pub a ex:Publication is mapped to the queried graph and variables act as a kind of wild-card, e.g., by mapping ?pub to ex:book1 the BGP matches. RDF already supports a few inferences, but not those that are required to derive that ex:book2 and ex:book3 are publications. In order to retrieve ex:book2 and ex:book3, one would need a system that supports RDFS entailment. RDFS entailment rules can be used to illustrate which new consequences can be derived from the given data. E.g., the rule rdfs9 can be applied to the triples (3) and (2) to derive

(6) ex:book2 a ex:Publication .

The rule rdfs3 can be applied to (4) and (5) to derive

(7) ex:book3 a ex:Publication .

The triples (6) and (7) can then be used to find that ex:book2 and ex:book3 are also answers to the query under an RDFS entailment regime. The difference between RDF and simple entailment is less significant since RDF supports only few inferences. Consider, for example, the following query:

SELECT ?prop WHERE { ?prop a rdf:Property }

Under simple entailment the query has an empty answer when querying the above graph. Under RDF entailment, the RDF rule rdf1 can be used on (5) to derive the triple ex:publishes a rdf:Property which means that ex:publishes is a valid binding for ?prop and will be returned as an answer for the query from a system that uses RDF entailment. The OWL 2 Web Ontology Language allows for even more inferences. The remainder of this document specifies what correct answers are for the different entailment regimes.

1.3 Extensions to Basic Graph Pattern Matching

The SPARQL Query specification gives a set of conditions that have to be met when extending the basic graph pattern matching to other entailment regimes:

An entailment regime specifies

1. A subset of RDF graphs called well-formed for the regime
2. An entailment relation between subsets of well-formed graphs and well-formed graphs.

Since the OWL 2 Direct Semantics is, for example, only defined for certain well-formed of RDF graphs, the first condition can be used to define an OWL 2 Direct Semantics entailment regime only over those RDF graphs that represent an OWL 2 DL ontology. For the entailment relations mentioned in the second condition, this specification uses entailment relations that are already specified and used in the Semantic Web such as RDF(S) entailment or OWL Direct Semantics entailment.

SPARQL Query further defines a set of conditions for extensions of the basic graph pattern matching. These conditions are repeated here for clarity and are followed by an overview of how the different entailment regimes satisfy them. Further details for each of the specified entailment regimes can be found in the corresponding section for that entailment regime.

1. The scoping graph, SG, corresponding to any consistent active graph AG is uniquely specified and is E-equivalent to AG.
2. For any basic graph pattern BGP and pattern solution mapping P, P(BGP) is well-formed for E.
3. For any scoping graph SG and answer set {P₁ ... P_n} for a basic graph pattern BGP, and where {BGP₁ .... BGP_n} is a set of basic graph patterns all equivalent to BGP, none of which share any blank nodes with any other or with SG

   SG E-entails (SG union P₁(BGP₁) union ... union P_n(BGP_n))

   These conditions do not fully determine the set of possible answers, since RDF allows unlimited amounts of redundancy. In addition, therefore, the following must hold.
4. Each SPARQL extension must provide conditions on answer sets which guarantee that every BGP and AG has a finite set of answers which is unique up to RDF graph equivalence.

This specification does not change any of the existing entailment relations, but rather defines the vocabulary from which possible answers can be taken and which answers are legal answers in order to guarantee that query answers are always finite. The set of legal graphs, i.e., graphs that can be queried, is also unrestricted apart from the restriction to graphs that are legal under the entailment regime in question. E.g., under the RDFS entailment regime, one can query all legal RDF graphs, while under OWL 2 Direct Semantics, one can query all graphs that correspond to legal OWL 2 DL ontologies. Further it is defined which queries are legal and how illegal queries, illegal graphs, and inconsistencies are handled. All defined entailment regimes satisfy the above conditions as follows:

1. All entailment regimes specified here use the same definition of a scoping graph as given for simple entailment. Thus, the required equivalence is immediate.

   Editorial note	11/01/2010
   It should be noted that the scoping graph is only uniquely specified up to blank node equivalence. Thus, there are several choices for the scoping graph; all choices are, however, equivalent.

2. Only mappings that, when applied to the BGP, yield a set of RDF triples that are well-formed for E are legal solution mappings and included in the answer. For example, under RDFS entailment, any SPARQL query is legal, but queries that require literals as a binding for a variable in a subject position have no answer because all mappings that result in a set of RDFS entailed triples are not well-formed RDF since RDF forbids literals in the subject position. Similarly, for OWL 2 DL entailment, a query might have no answer because all possible bindings might result in RDF triples that are not well-formed for OWL 2 DL.
3. This condition prevents the reuse of blank nodes between query answers unless those blank nodes are really the same in the queried graph. Under this restriction no accidental co-references among blank nodes are introduced. Since we use the same definition of a scoping graph, and we use a form of Skolemization to restrict the answers under RDF(S) entailment, the condition is also satisfied.

   Editorial note	14/10/2009
   The proof needs to be redone though since it uses the interpolation lemma, which does not hold e.g., for RDFS-entailment.

4. For entailment regimes other than simple entailment this point is very important since a finite set of answers is no longer guaranteed. For example, already under RDF and RDFS entailment, even the empty graph entails an infinite number of axiomatic triples such as rdf:_1 a rdf:Property, rdf:_2 a rdf:Property, ... Thus, a query with BGP { ?x a rdf:Property . } would, without further restrictions, have infinitely many answers. In order to guarantee finite answers, different entailment regimes will impose different restrictions on the vocabulary from which bindings can be taken. We explain these restrictions in greater detail in the following sections.

2.1 Blank Nodes in the Queried Graph (Informative)

The following example illustrates the use of condition C1. Consider the query

SELECT ?s ?o WHERE { ?s ex:b ?o } 

against a (scoping) graph containing only the triples

ex:a1 ex:b _:c1 . 
ex:a1 ex:b _:c2 .
ex:a2 ex:b _:c3 .

Simple entailment would give the solutions

Since blank nodes only denote the existence of something and the actual blank node names do not matter, also the following solution mappings are possible solutions under RDF entailment (simple entailment restricts solutions to subgraphs of the queried graph):

Observe that, for instance, solution μ₄ violates condition 3 from the SPARQL Query specification and the set of possible solutions is clearly infinite in this case, which is problematic with respect to condition 4 from the SPARQL Query specification. For a possible solution to actually be a solution, however, the two additional conditions C1 and C2 have to be met:

(C1) The RDF triples sk(P(BGP)) are ground and RDF entailed by sk(SG).

(C2) Each variable x that occurs in the subject position of a triple in BGP is such that sk(μ(x)) occurs in sk(SG).

In this case, condition C1 limits the answers by checking entailments against a Skolemization of SG. Thus, let skol be a prefix that denotes a fresh IRI not occurring in the triples for SG and sk(SG) the following (Skolemized) graph:

ex:a1 ex:b skol:c1 . 
ex:a1 ex:b skol:c2 .
ex:a2 ex:b skol:c3 .

The skolem function maps _:c1 to skol:c1, _:c2 to skol:c2, and _:a2 to skol:a2. Consider the pattern instance mapping P₁=(μ₁, σ₁) with μ₁ as given above and σ₁ an empty RDF instance mapping. In this case, P₁(BGP) = ex:a1 ex:b _:c1. Since sk(P(BGP)) = ex:a1 ex:b skol:c1 is a ground triple that is RDF entailed by the Skolemized scoping graph, C1 is satisfied. Since sk(μ₁(?s)) = sk(ex:a1) = ex:a1 occurs in the scoping graph, also C2 is satisfied and μ₁ is a solution. Similarly, it can be shown that μ₂ and μ₃ are solutions. The other possible solutions are, however, not returned as solutions. For example, consider the pattern instance mapping P₄=(μ₄, σ₄) for an empty RDF instance mapping σ₄. In this case P₄(BGP) = ex:a1 ex:b _:c3 and although sk(P(BGP)) = ex:a1 ex:b skol:c3 is ground, it is not RDF entailed by the Skolemized scoping graph. The pattern instance mapping P₅=(μ₅, σ₅) for an empty RDF instance mapping σ₅ leads to P₅(BGP) = ex:a1 ex:b _:whatever. Since sk is not defined for _:whatever, sk(P(BGP)) = ex:a1 ex:b _:whatever is not a ground triple, which violates C1.

In fact, we could have directly used a Skolemized version of the scoping graph to define the answers under RDF entailment. Since the Skolemized scoping graph sk(SG) is, however, not RDF-equivalent to SG, this violates the first condition that the SPARQL Query specification places on extensions of the basic graph pattern matching.

2.2 Answers from Axiomatic Triples (Informative)

The following example mainly illustrates the use of condition C2. Consider the query

SELECT ?x WHERE { ?x a rdf:Property } 

against a (scoping) graph containing only the triples

ex:a ex:b ex:c . 
ex:d a rdf:Bag .
ex:d rdf:_1 ex:a .

One of the possible solutions is

since ex:a ex:b ex:c RDF entails ex:b a rdf:Property (see also the RDF entailment rule rdf1). Further, the axiomatic triples give possible solutions such as

There are even more possible answers since ex:b a rdf:Property RDF entails _:exb1 a rdf:Property for some blank node _:exb1 allocated to ex:b, i.e., _:exb1 is a possible solution. As shown above, condition C1 prevents such possible solutions from newly introduced blank nodes to be returned as solutions. To limit the answers from the axiomatic triples condition C2 is used:

(C2) Each variable x that occurs in the subject position of a triple in BGP is such that sk(μ(x)) occurs in sk(SG).

The exemplary possible answers μ₂ to μ₅ are considered here in greater detail. Since all these solution mappings lead to (ground) axiomatic triples when instantiating the BGP, C1 is trivially satisfied. Since the queried graph contains no blank nodes, sk(SG) = SG and sk(μ_i(?x)) = μ_i(?x) for any solution mapping μ_i, which is used to simplify the checking of C2 below.

1. For the possible solution μ₂, take an empty RDF instance mapping σ₂ to obtain a pattern instance mapping P₂=(μ₂, σ₂) with P₂(BGP) = rdf:type a rdf:Property. Since μ₂(?x)=rdf:type occurs in SG, condition C2 is also satisfied and this solution mapping is a solution.
2. For the possible solution μ₃: take again an empty RDF instance mapping σ₃ to obtain a pattern instance mapping P₃=(μ₃, σ₃) with P₃(BGP) = rdf:subject a rdf:Property. Since μ₃(?x)=rdf:subject does not occur in SG, this possible solution mapping is not returned as an answer.
3. For the possible solution μ₄: take again an empty RDF instance mapping σ₄ to obtain a pattern instance mapping P₄=(μ₄, σ₄) with P₄(BGP) = rdf:_1 a rdf:Property. Since μ₄(?x)=rdf:_1 occurs in SG, this is a solution.
4. For the possible solution μ₅: take again an empty RDF instance mapping σ₅ to obtain a pattern instance mapping P₅=(μ₅, σ₅) with P₅(BGP) = rdf:_2 a rdf:Property. Since μ₅(?x)=rdf:_2 does not occur in SG, this solution mapping is not a solution.

Similar arguments as for rdf:_2 can be used for rdf:_n with n > 2 and for other bindings from axiomatic triples such as rdf:first from the axiomatic triple rdf:first a rdf:Property. Thus, the only answers are:

2.3 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

SELECT ?x WHERE { ?x a rdf:XMLLiteral }

even the empty graph would RDF entail all statements

xxx a rdf:XMLLiteral

for xxx a well-formed RDF XML literal, but any solution that maps x to an xml literal such as "<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 C2 would still guarantee finite answers.

2.4 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.,

ASK { ?x a rdf:Property }

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 empty domain is a possible solution, but condition C1 rules this solution mapping out as an answer and the query answer is no (false).

3.1 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 malformed XML string, e.g.,

ex:a ex:b "<"^^rdf:XMLLiteral .

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

ex:b rdfs:range rdf:XMLLiteral .

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):

(1) ex:a rdfs:subClassOf rdfs:Literal .
(2) ex:b rdfs:range ex:a .
(3) ex:c rdfs:subPropertyOf ex:b.
(4) ex:d ex:c "<"^^rdf:XMLLiteral .

Here we can to derive the inconsistency as follows:

(6) ex:d ex:b "<"^^rdf:XMLLiteral .    (e.g., by applying rule rdfs7 to (3) and (4))
(7) "<"^^rdf:XMLLiteral a ex:a.   (e.g., by applying rule rdfs3 to (2) and (6))
(8) "<"^^rdf:XMLLiteral rdf:type rdfs:Literal .   (e.g., by applying rule rdfs9 to (1) and (7))

At this point, the inconsistency can be detected since "<" is not a valid lexical form for an RDF XML literal and has to be interpreted as some element that 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.

ex:b ex:s ex:y1 .
ex:b ex:s ex:y2 .
...
ex:b ex:s ex:y10000 .
ex:a ex:d "<"^^rdf:XMLLiteral .
ex:d rdfs:range rdf:XMLLiteral . 

SELECT * WHERE { ex:b ex:r ?x . ?x ex:s ?y }

SELECT * WHERE { {BGP1} UNION {BGP2} }

6.1 Restrictions on Solutions (Informative)

In this section the restrictions on solutions are explained. All restrictions use a Skolemization of the queried graph and the BGP as in the RDF and RDFS entailment regimes. This restricts the solutions containing blank nodes in the same way as for RDF(S), and we refer to the examples given for RDF.

SELECT ?o, ?d WHERE { ?o owl:topObjectProperty ?d }

SELECT ?s ?p ?o WHERE { ?s ?p ?o }

SELECT ?x WHERE { ?x ex:r ex:b }

ObjectPropertyAssertion(ex:r ?x ex:b)

AnnotationAssertion(ex:r ?x ex:b)

ClassAssertion(ObjectMaxCardinality(1 ex:hasSon) ex:Peter)

ex:Peter a [
    a owl:Restriction ;
    owl:onProperty ex:hasSon ;
    owl:maxCardinality "1"^^xsd:nonNegativeInteger .
] . 

SELECT ?n WHERE {
    ex:Peter a [ 
        a owl:Class ;
        owl:complementOf [
            a owl:Restriction ;
            owl:onProperty ex:hasSon ;
            owl:minCardinality ?n . 
        ]
    ]
}

ClassAssertion(ObjectComplementOf(ObjectMinCardinality(?n ex:hasSon)) ex:Peter)

ClassAssertion(DataExactCardinality(2 ex:dp DatatypeRestriction(xsd:int xsd:minExclusive "5"^^xsd:int xsd:maxExclusive "8"^^xsd:int)) ex:Peter)

ex:Peter a [
    a owl:Restriction ;
    owl:onProperty ex:dp ;
    owl:qualifiedCardinality "2"^^xsd:nonNegativeInteger ;
    owl:onDataRange [
        a rdfs:Datatype ;
        owl:onDatatype xsd:int ;
        owl:withRestrictions (
            [ xsd:minExclusive "5"^^xsd:int ]
            [ xsd:maxExclusive "8"^^xsd:int ]
        )
    ]
]

SELECT ?class WHERE { ?class a owl:Class }

SELECT ?av WHERE { [] rdfs:comment ?av }

SubClassOf(Annotation(rdfs:label "Employees are persons and humans.") ex:Employee ObjectIntersectionOf(ex:Person ex:Human))

ex:Employee rdfs:subClassOf _:c .
_:c a owl:Class ;
    owl:intersectionOf [
        rdf:first ex:Person ;
        rdf:rest [
            rdf:first ex:Human ;
            rdf:rest rdf:nil .
        ] 
    ]
[] a owl:Axiom ;
   owl:AnnotationSource ex:Employee ;
   owl:AnnotationProperty rdfs:subClassOf ;
   owl:AnnotationTarget _:c ;
   rdfs:label "Employees are persons and humans." .

SELECT ?label WHERE {
ex:Employee rdfs:subClassOf _:qc .
_:qc a owl:Class ;
    owl:intersectionOf [
        rdf:first ex:Human ;
        rdf:rest [
            rdf:first ex:Person ;
            rdf:rest rdf:nil .
        ] 
    ]
[] a owl:Axiom ;
   owl:AnnotationSource ex:Employee ;
   owl:AnnotationProperty rdfs:subClassOf ;
   owl:AnnotationTarget _:qc ;
   rdfs:label ?label .
}

SubClassOf(Annotation(rdfs:label ?label) ex:Employee ObjectIntersectionOf(ex:Human ex:Person))

6.2 Higher Order Queries (Informative)

The Direct Semantics entailment regime allows for certain (but not all) forms of higher order queries. For example, one can use the BGP ?x rdfs:subClassOf ?y to query for pairs of sub- and super-class. I.e., variables can bind to classes and not just to individuals or data values. Queries in which variables are used in positions that would require bindings from the OWL 2 reserved vocabulary, e.g., in the position of a First-Order Logic quantifier, will, however, have an empty answer since such bindings violate condition C2. For example, the following query asks whether some or all brothers of Peter are persons:

SELECT ?x WHERE {
    ex:Peter a [ 
        a owl:Restriction ;
        owl:onProperty ex:hasBrother ;
        ?x ex:Person . 
   ]
} 

In functional-style syntax the BGP of the query corresponds to the axiom

ClassAssertion( ?x(ex:hasBrother ex:Person) ex:Peter )

Here the variable occurs in the position of a quantifier and any solution mapping for the above query must map ?x to owl:SomeValuesFrom or owl:AllValuesFrom in order to result in a set of triples that can be parsed into an OWL 2 DL ontology. Condition C2 excludes, however, bindings from the reserved vocabulary of OWL and the query has an empty answer.

6.3 OWL 2 Profiles for Direct Semantics

OWL 2 Direct Semantics is not defined for arbitrary RDF graphs and the OWL 2 QL and EL profiles further restrict the allowed inputs. Thus, SPARQL endpoints that use Direct Semantics can further describe what input they can process. SPARQL endpoints that use Direct Semantics can, thus, describe which inputs they can handle.