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 [SPARQL 1.1 Query] 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 on 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 do not cover the case of inconsistent graphs. The effect of a query on an inconsistent graph has to be covered by the particular entailment regimes. The relevant details for each of the specified entailment regimes can be found in the corresponding section for that entailment regime. The SPARQL Query conditions for consistent active graphs are repeated below for clarity and are followed by an overview of how the different entailment regimes satisfy them.

1. The scoping graph, SG, corresponding to any consistent active graph AG is uniquely specified up to RDF graph equivalence and is E-equivalent to AG.
2. For any basic graph pattern BGP and pattern instance 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 the set of triples obtained by instantiating BGP with each solution μ is uniquely specified up to RDF graph equivalence, and SHOULD provide further conditions to prevent trivial infinite answers as appropriate to the regime.

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.
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. All entailment regimes use the same definition of a scoping graph as simple entailment. The condition is satisfied since a form of Skolemization is used to restrict the answers containing blank nodes.
4. This point is very important since infinite answers are easily possible under all the considered regimes. 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. Such answers are to be understood as trivial infinite answers. Other sources of trivial infinite answers are answers that only differ in blank node labels. In order to exclude such sources of infinity, the entailment regimes will define a (finite) 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, the following solution mappings are also possible solutions under RDF entailment (simple entailment restricts solutions to subgraphs of the queried graph):

Observe that, for instance, the inclusion of solution μ₄ invalidates condition 3 from the SPARQL Query specification. This condition requires that SG entails the union of SG with all possible instantiations of BGP. Since BGP does not contain blank nodes, the blank node renaming as required by the condition is obsolete. Furthermore, we can use the empty RDF instance mapping σ to obtain the pattern instance mappings P₃=(μ₃, σ) and P₄=(μ₄, σ), which applied to BGP yield: P₃(BGP) = ex:a2 ex:b _:c3 . and P₄(BGP) = ex:a1 ex:b _:c3 .

The union of the two triples is not entailed by SG and adding further triples does not change that. This is because the reuse of the same blank node in different solutions has introduced an unintended co-reference, whereas the queried graph does not support the fact that both ex:a1 and ex:a2 are related to the same element.

Furthermore, the set of possible solutions is clearly infinite in this case, which is problematic with respect to condition 4 from the SPARQL Query specification since the use of different blank node labels is considered a trivial source of infinie answers. 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) For each variable x in V(BGP), sk(μ(x)) occurs in sk(SG) or in rdfV-Minus.

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 _:c3 to skol:c3. 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 both sk(μ₁(?s)) = sk(ex:a1) = ex:a1 and sk(μ₁(?o)) = sk(_:c1) = skol:c1 occur in the Skolemized scoping graph, C2 is satisfied too 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) For each variable x in V(BGP), sk(μ(x)) occurs in sk(SG) or in rdfV-Minus.

The 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 (and also in rdfV-Minus), 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. Although μ₃(?x)=rdf:subject does not occur in SG, it occurs in rdf-Minus and this possible solution mapping is, therefore, also 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 occurs neither in SG nor in rdf-Minus, this solution mapping is not a solution.

Similar arguments as for rdf:_2 can be used for rdf:_n with n > 2. Thus the query answer contains ex:b, rdf:_1, and the subjects of RDF axiomatic triples of the form X rdf:type rdf:Property with X in rdfV-Minus.

2.3 Literals in the Subject Position (Informative)

Please note that solution mappings that map variables that occur in the subject position of the basic graph pattern BGP to literals will not be returned as solutions. Indeed, although 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 there is at least one solution mapping (i.e., a solution that satisfies also conditions C1 and C2) and it is no (false) otherwise. For example, if the queried graph is the empty graph, the query has no solution since even if a pattern instance mapping yields an axiomatic triple, condition C2 cannot be satisfied.

For Boolean queries without variables the situation is slightly different. Consider, for example, the query

ASK { rdf:type a rdf:Property }

against the empty graph. Since rdf:type a rdf:Property is an axiomatic triple, even the empty graph RDF entails the triple. We have two possible outcomes for such a Boolean query: 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). Since C2 only operates on the variables in the query, only C1 is relevant in this case. Since neither the BGP nor the queried (empty) graph contains a blank node, also C1 holds and the query answer is yes (true).

Note that even though rdf:_n is not in rdfV-Minus for any n, this means that queries such as ASK { rdf:_n a rdf:Property } will always be answered with yes (true) even if rdf:_n does not occur in the scoping graph.

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:

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

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} }

3.2 Aggregates and Blank Nodes (Informative)

SPARQL 1.1 Query allows for aggregates in queries such as COUNT, MIN, etc. Aggregates apply expressions over groups of solutions, e.g., by counting the number of solutions. Thus, aggregation is layered on top of basic graph pattern matching and all solutions computed for the basic graph pattern of the query and the entailment regime in use are passed on to the algebra functions. For the RDF (and RDFS) entailment regime this means that since blank nodes are treated as Skolem constants due to condition C1, each blank node contributes one value for the aggregates. Assume, for example, the query

SELECT ?publication (COUNT(?author) AS ?numAuthors)
WHERE { ?author ex:writes ?publication . }
GROUP BY ?publication

evaluated over the data:

_:a1 ex:writes ex:book1 . 
ex:author2 ex:writes ex:book1 .
_:a1 ex:writesBook ex:book2 .
ex:author3 ex:writesBook ex:book2 .
_:a4 ex:writesBook ex:book2 .
ex:writesBook rdfs:subPropertyOf ex:writes .

Under simple and RDF entailment, basic graph pattern matching finds two solutions:

The results are then grouped and aggregated by algebra operators. In this case, there is only one group for ex:book1 and the authors for the group are counted due to the COUNT aggregate over ?author resulting in the query answer:

RDFS further gives semantics to rdfs:subPropertyOf and the basic graph pattern matching under RDFS entailment finds five solution mappings:

These solutions are then processed by the algebra operators. Again, the authors for each book (now there are two groups) are counted due to the COUNT aggregate over ?author, which leads to the following result for the query under RDFS entailment:

Note that the algebra operator just takes the solutions returned by the basic graph pattern matching mechanism. If, for example, blank nodes should not be counted or counted only once, this would mean that in general the entailment regimes must be modified to return no blank nodes or collapse blank nodes in results. A consequence of this would be that under entailment regimes such as RDF(S) one could get less results than with simple entailment. E.g., if no blank nodes were to be returned, then the books would have just one author under non-simple entailment.

4.1 Canonical Lexical Representations (Informative)

Depending on the datatype map D, it can happen that a datatype from D allows for infinitely many lexical forms that denote the same data value. E.g., if D includes the decimal datatye from the XML Schema Datatypes [XSD], then all of the following lexical forms represent the same value:

• 100
• +100.0
• 0100.0
• 100.0
• 100.00
• 100.000

SPARQL queries are answered with respect to a graph and any triple serialization format such as RDF/XML or Turtle has to be parsed into a graph representation. During this parsing process systems may or may not transform the lexical forms of data values into a canonicalized form. E.g., for the above data value, the canonical lexical form is: 100.0.

Whether or not a parser performs canonicalization can have an effect on query answers. Consider the query

SELECT ?x WHERE { ex:s ex:p ?x }

over the graph obtained from the triples

ex:s ex:p "100.0"ˆˆxsd:decimal .
ex:s ex:p "100.00"ˆˆxsd:decimal .

If the parsing process involves canonicalization, then the obtained graph will contain just two nodes (one for ex:s and one for the data value 100.0) connected by one edge (for ex:p), whereas without canonicalization, the graph contains one extra node for 100.00 and an extra edge connecting the node for ex:s with the node for the data value 100.00. In the first case, the query has one answer, whereas in the second case, the query has two answers.

Whether or not canonicalization takes place depends on the parsing process, which is not part of this specification. Thus, the answers of systems that use the D-Entailment regimes can vary according to how parsing is implemented and canonicalization during parsing is encouraged in order to obtain more intuitive answers.

5.1 Restriction on Solutions

In this section the restrictions on solutions are explained. As the previously defined regimes, a Skolemization of the queried graph and the BGP is used to limit answers that just differ in blank node labels (C1). An explanation for this restriction is given in the RDF entailment regime section. Under OWL 2 RDF-Based Semantics the axiomatic triples are not included and owl2V-Minus could equally be replaced by owl2V. Without C2, infinite answers can, however, easily occur due to the powerful OWL 2 datatype reasoning. Since the datatype literals are not part of the vocabulary owl2V-Minus, only the values explicitly present in the queried ontology have to be considered, which again guarantees finite answers. Consider, for example, an ontology containing an axiom that states that all the data values to which Peter is related with the property ex:dp are in the singleton set containing the interger 5:

ex:Peter a [
    a owl:Restriction ;
    owl:onProperty ex:dp ;
    owl:allValuesFrom [
      rdf:type rdfs:Datatype .
      owl:oneOf ("5"^^xsd:integer) 
    ]
]

A query, which asks for all data values to which ex:Peter cannot be related with the ex:dp property, has infinitely many answers since any literal different from 5 will satisfy these constraints. This can be formulated by the following query:

SELECT ?x WHERE { 
    ex:Peter a [
      a owl:Restriction ;
      owl:onProperty ex:dp ;
      owl:allValuesFrom [
        a rdfs:Datatype ;
        owl:datatypeComplementOf [
          a rdfs:Datatype ; 
          owl:oneOf (?x)
      ]
    ]
  ]
}

Note that a similar query for data ranges instead of literals has a finite answer even without C2. E.g., if the same ontology is queried with:

SELECT ?x WHERE { 
    ex:Peter a [
      a owl:Restriction ;
      owl:onProperty ex:dp ;
      owl:allValuesFrom [
        a rdfs:Datatype ;
        owl:datatypeComplementOf ?x .
    ]
  ]
}

The answer to this query consists of all datatypes of the datatype map that are disjoint from xsd:integer, e.g., xsd:string, xsd:double, etc. Note that complex data ranges, which are derived from datatypes by applying facet restrictions to them, are not valid bindings. E.g., the data range

[
  a rdfs:Datatype ;
  owl:onDatatype xsd:int ;
  owl:withRestrictions (
    [ xsd:minExclusive "0.2"^^xsd:double ]
    [ xsd:maxExclusive "0.8"^^xsd:double ]
  )
]

cannot be used as a binding for the variable ?x

With C2, only the literals and datatypes that occur in the queried graph can be used as bindings. In order to drop C2, one would have to precisely characterize which queries can cause infinite answers, e.g, by analysing which variables bind to literals and occur under negation. Such queries could then be excluded. Condition C2 is, however, easier to understand and it is easy to see that it achieves finiteness.

5.2 Computing Query Answers under the RDF-Based Semantics (Informative)

The standard reasoning problems in OWL under the OWL 2 RDF-Based Semantics are undecidable, which means that although the query answers are guaranteed to be finite, it cannot be guaranteed that the computation of the query results will finish in a finite amount of time. Guaranteed termination might be achieved by returning an incomplete solution sequence for certain queries.

5.3 The OWL 2 RL Profile

OWL 2 RL defines a syntactic subset of OWL 2, which is amenable to implementation using rule-based technologies. The OWL 2 RL specification presents a partial axiomatization of the OWL 2 RDF-Based Semantics in the form of first-order implications for this purpose. For RDF graphs that can be mapped into OWL 2 RL ontologies, a suitable rule-based implementation has desirable computational properties. For RDF graphs that cannot be mapped into an OWL 2 RL ontology, the proposed rule set can still be used to compute query answers, but the result set might not contain all query answers that are entailed under the RDF-Based Semantics.

Endpoints that implement the OWL 2 RL profile can use the URI http://www.w3.org/ns/owl-profile/RL to describe this in their service description.

If the input ontology satisfies certain restrictions, the rules can also be used to compute all and only the answers that are entailed under the OWL 2 Direct Semantics. Thus, OWL 2 RL can also be used with the Direct Semantics of OWL 2.

_:o1 a owl:ontology .
ex:C a owl:Class . 
ex:D a owl:Class .
ex:C rdfs:subClassOf ex:D .
ex:D rdfs:subClassOf ex:C .

SELECT ?rel WHERE { ex:C ?rel ex:D . }

6.1 Introduction

For the OWL 2 Direct Semantics entailment regime, semantic conditions are defined with respect to ontology structures (i.e., instances of the Ontology class as defined in the OWL 2 structural specification [OWL 2 Structural Specification]). Given an RDF graph G, the ontology structure for G, denoted O(G), is obtained by mapping the queried RDF graph into an OWL 2 ontology [OWL 2 Mapping to RDF Graphs]. This mapping is only defined for OWL 2 DL ontologies, i.e., ontologies that satisfy certain syntactic conditions.

An OWL 2 DL ontology contains a set of axioms. In this section, OWL axioms are stated both in Turtle and in the functional-style syntax (FSS) that is used in the OWL 2 structural specification [OWL 2 Structural Specification]. A FSS axiom can correspond to several RDF triples, and the RDF triples might contain auxiliary blank nodes that are not part of the corresponding OWL objects and are not visible in the corresponding FSS axiom. E.g., the triples

ex:Peter a _:x . 
_:x a owl:Restriction ;
    owl:onProperty ex:hasFather ;
    owl:someValuesFrom ex:Person . 

corresponds to FSS syntax axiom

ClassAssertion(ObjectSomeValuesFrom(ex:hasFather ex:Person) ex:Peter)

The FSS may still contain blank nodes, but these correspond to OWL individuals that have no explicit names and are called anonymous individuals. For example, the triple

ex:Peter ex:hasBrother _:y . 

corresponds to the FSS axiom

ObjectPropertyAssertion(ex:hasBrother ex:Peter _:y)

While parsing an input document (containing RDF triples) into an OWL ontology, it can be necessary to rename blank nodes/anonymous individuals and there is no guarantee that the blank node identifier _:y from the above triple is used as an identifier for Peter's brother in the ontology structure. Thus, the above RDF triple could also be represented by the OWL axiom

ObjectPropertyAssertion(ex:hasBrother ex:Peter _:somethingelse)

Some RDF triples that are well-formed for OWL 2 DL, are mapped to OWL 2 DL axioms that carry no semantics. Axioms (triples) that carry no semantics are

1. Annotations,
2. Entity Declarations,
3. Ontology Properties (imports, ontology IRIs).

Such axioms are called non-logical axioms, whereas axioms that do carry semantics under OWL 2 Direct Semantics are called logical axioms.

ont owl:imports imported .

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

SELECT ?x WHERE { ?x ex:p ?y }

ObjectPropertyAssertion(ex:p ?x ?y)

DataPropertyAssertion(ex:p ?x ?y)

6.2 The OWL 2 Direct Semantics Entailment Regime

6.3 Restrictions on Solutions (Informative)

In this section the restrictions on solutions are explained. As the previously defined regimes, a Skolemization of the queried graph and the BGP is used to limit answers that just differ in blank node labels (C1). An explanation for this restriction is given in the RDF entailment regime section.

Condition C2 is also applied as in the previously defined regimes and guarantees finite answers. Due to the absence of the RDF(S) axiomatic triples, owl2V-Minus could equally be replaced by owl2V. As under the OWL 2 RDF-Based Semantics, C2 prevents infinite answers that could otherwise come from the very powerful datatype reasoning. An example that illustrates this is given in the OWL 2 RDF-Based Semantics entailment regime section.

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 ?s ?d WHERE { ?s ex:dp ?d }

DataPropertyAssertion(ex:dp ?s ?d)

DataPropertyAssertion(ex:dp ex:Mary "6"^^xsd:int)

ex:Mary ex:dp "6"^^xsd:int .

6.4 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 (representing sets of individuals) and not just to individuals or data values. Queries in which variables are used in positions of a First-Order Logic quantifier, will, however, be illegal since such queries cannot be mapped to OWL objects as required. For example, the following (illegal) 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 not just in the position of OWL entities such as class names or individual names.

6.5 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.

7.1 Referencing a RIF Core document

The RIF RDF Compatibility document provides a way to import an RDF graph (into a RIF document) and specify a profile that determines which model theoretic notion of satisfiability and entailment should be used to interpret the combination. However, for our scenario, the inverse of such a reference is needed and a specific IRI is designated: http://www.w3.org/ns/rif#imports. In the subsequent text, we will refer to this IRI as rif:imports. In the RDF triple with this predicate, the object (a URI reference) MUST be considered the location of the safe RIF Core document to use to form the RIF-RDF combination that entails the answers. Combinations used in this SPARQL entailment regime MUST be interpreted using the semantics specified in the Simple profile (http://www.w3.org/ns/entailment/Simple)

7.2 (Simple) RIF Core Entailment Regime

RIF-Core conformance is defined with respect to safe rules and so this entailment regime is defined with respect to combinations formed from safe RIF documents.

7.3 Custom Rulesets for Common Vocabulary Interpretations (Informative)

RDF vocabulary such as RDFS and OWL2-RL can be interpreted within this entailment regime through the use of custom rulesets. For example, RDFS entailment can be implemented by using the R^RDFS ruleset specified in [RIF-RDF]. Similarly, the RIF Core rules in [OWL2-RL-RIF] can be used to capture an axiomatization of OWL2-RL.

7.4 Finite Answer Set Conditions (Informative)

Traditionally, one of the ways to ensure that the underlying decision problems associated with a Horn clause knowledge representation are decidable is to prevent the use of function symbols. RIF-Core's syntax permits built-in functions and (with possibly infinite) predicates in the body of a rule. A Horn Clause query is said to be safe it it has a finite set of answers. In order to ensure that a Horn Clause logic programming language is complete (i.e., it guarantees all answers to a query) it is necessary to test whether a given query is safe [SAFETY].

Without strong safety conditions, cyclic references can rule out the existence of a unique, minimal Herbrand model of the combination. With strong safety conditions, even in the face of a cycle, the output of a built-in predicate cannot grow infinitely, since the size of its input is fixed prior to entering the cycle [ANSWERSET-SW] and the evaluation of a built-in predicate with a possibly infinite extension (such as pred:numeric-less-than or pred:dateTime-greater-than) is determined only by the terms from a collection of finite predicates. Restrictions such as these are traditionally enforced through the use of a dependency graph [STABLEMODEL] to determine if a ruleset is stratified. Stratification is typically applied to logic programs with negated literals and RIF-Core does not allow negated literals. However, logic programs restricted in this way permit the use of built-in function symbols such that the truth of a predicate is well-defined by an external procedure. RIF-Core's notion of strong safety facilitates the ability to construct a finite grounding which addresses both components of the forth requirement of SPARQL extensions on their answer sets: uniqueness and finiteness.

Consider the following strongly safe RIF Core document, scoping graph, and query, for which an answer set can be determined from the unique, minimal, and finite RIF-RDF model of the combination (despite the use of a built-in predicate). In this query, the user asks for all hospital episodes (or visits) and the various health care events they subsume (as indicated by the ex:hasHospitalization predicate). The ex:hasHospitalization predicate is defined (in the strongly safe RIF core document) as a relation between a health care event with the larger hospital encounter event it is a part of based on the ordering of the dates associated with the events. The ordering constraint is enforced through the use of the pred:dateTime-greater-than and pred:dateTime-less-than external built-in predicates.

Forall ?x ?y ?z ?u
  ( ?EVT[ ex:hasHospitalization -> ?HOSP] 
     :- And( ?HOSP # ex:HospitalEncounter
             ?HOSP [ ex:startsNoEarlierThan -> ?ENCOUNTER_START
                     ex:stopsNoLaterThan    -> ?ENCOUNTER_STOP  ]
             ?EVT # ex:HealthCareEvent
             ?EVT [ ex:startsNoEarlierThan -> ?EVT_START_MIN ]
             pred:dateTime-greater-than(xsd:dateTime(?EVT_START_MIN) xsd:dateTime(?ENCOUNTER_START))
             pred:dateTime-less-than(xsd:dateTime(?EVT_START_MIN) xsd:dateTime(?ENCOUNTER_STOP)))
  )
        

(1) <> rif:imports <.. path to above document ..> .
(2) ex:Operation1 a ex:HealthCareEvent;
(3)               ex:startsNoEarlierThan "2000-12-01T05:00:00"^^xsd:dateTime ;
(4)               ex:startsNoEarlierThan "2000-12-11T16:31:00"^^xsd:dateTime .
(5) ex:Episode1   a ex:HospitalEncounter;
(6)               ex:startsNoEarlierThan "2000-11-31T12:00:00"^^xsd:dateTime ;
(7)               ex:stopsNoEarlierThan  "2000-12-26T05:36:00"^^xsd:dateTime .
(8) ex:XRay1      a ex:HealthCareEvent;
(9)               ex:startsNoEarlierThan "1960-01-10T03:00:00"^^xsd:dateTime ;
(10)              ex:stopsNoEarlierThan  "1960-01-11T07:00:00"^^xsd:dateTime .

SELECT ?EVT ?HOSP WHERE { ?EVT ex:hasHospitalization ?HOSP }

This should result in the following bindings as a result of the rules and the triples (2)-(7) from a SPARQL service that implements the RIF Core entailment regime: