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 rdf:type ex:Publication .
(2) ex:book2 rdf:type ex:Article .
(3) ex:Article rdfs:subClassOf ex:Publication .
(4) ex:publishes rdfs:range ex:Publication .
(5) ex:MITPress ex:publishes ex:book3 .

Figure 1: A graphical representation of the RDF graph for the example where green dashed lines indicate RDF-entailed triples and red dashed lines indicate triples that are also RDFS-entailed.

Consider, for example, the following query:

SELECT ?prop WHERE { ?prop rdf:type 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 rdf:type 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 following query asks for a list of all publications:

SELECT ?pub WHERE { ?pub rdf:type 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 rdf:type 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 at least RDFS entailment. RDFS entailment rules can be used to illustrate which new consequences can be derived from the given data. For example, the rule rdfs9 can be applied to the triples (3) and (2) to derive

(6) ex:book2 rdf:type ex:Publication .

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

(7) ex:book3 rdf:type 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 OWL 2 Web Ontology Language allows for even more inferences and the Rule Interchange Format RIF allows for customizing the inferences by specifying custom rule sets. The remainder of this document specifies correct answers for different entailment regimes using SPARQL's extension mechanism for Basic Graph Pattern Matching.

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 beyond simple entailment:

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 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. An inconsistent graph is one for which no interpretation exists that satisfies all conditions of the semantics that is used. The issue is discussed in more detail in Section 3.1, which also provides an example for an RDFS-inconsistent graph. Since inconsistent graphs entail any triple, special care has to be taken to address the situation. The effect of a query on an inconsistent graph is covered by the particular entailment regimes and, for each regime, the relevant details can be found in the corresponding section for that entailment regime. The SPARQL Query conditions for using a logical entailment relation E, such as RDFS entailment, instead of subgraph matching for the case of a consistent active graph are repeated below for clarity. An overview of how the different entailment regimes satisfy these conditions follows.

1. The scoping graph, SG, corresponding to any E-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 ∪ P₁(BGP₁) ∪ ... ∪ 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 defines certain conditions which guarantee that query answers are finite for most entailment regimes herein (with the exception of RIF, where finiteness is not always guaranteed, see details below in Section 8.3). 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. For example, 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 Direct Semantics 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 rdf:type rdf:Property, rdf:_2 rdf:type rdf:Property, ... Thus, a query with BGP { ?x rdf:type 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. These restrictions are explained in greater detail in the following sections.

1.4 Parts of an Entailment Regime

• Name: A name for the entailment regime, usually the same as the entailment relation used to define the evaluation of a basic graph pattern.
• IRI: The IRI for the regime, which can be used in the service description of a SPARQL endpoint. The IRI for a SPARQL endpoint can be related via the property sd:defaultEntailmentRegime to the IRI of an entailment regime which applies per default to graphs queried via this endpoint. Additionally, the property sd:entailmentRegime can be used to relate a particular named graph with an entailment regime that is different from the otherwise used default entailment regime.
• Legal Graphs: Describes which graphs are legal for the regime.
• Legal Queries: Describes which queries are legal for the regime.
• Illegal Handling: Describes what happens in case of an illegal graph or query.
• Entailment: Specifies which entailment relation is used in the evaluation of basic graph patterns.
• Inconsistency: Defines what happens if the queried graph is inconsistent under the used semantics.
• Query Answers: Defines how a basic graph pattern is evaluated, i.e., what the solutions are for a given graph and basic graph pattern of a query.

3.1 Blank Nodes in the Queried Graph

The third condition for extensions of basic graph pattern matching requires that if blank node names are returned as bindings for a variable, then the same blank node name occurs in different solutions only if it corresponds to the same blank node in the graph. To illustrate why this is required, consider the following graphs, which are also illustrated in Figure 2:

Figure 2: A graphical representation of the RDF graphs for the example on blank nodes in the queried graph.

The graph G simply entails G1 and G2, but not G3 where the two blank nodes are identified. Now consider a basic graph pattern BGP:

ex:a ex:b ?x . ?y ex:e ex:f . 

When taking just the possible answers, without applying condition (C1) and (C2), a solution multiset for BGP would include

Thus, we have μ₁(BGP)=G1 and μ₂(BGP)=G2, and both solutions are entailed by G. In fact, 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 infinite answers. Furthermore, condition 3 requires that G ∪ μ₁(BGP) ∪ μ₂(BGP) is also entailed by G, and this is not the case in the example since this union contains G3. The reason is that the solutions have unintended co-references of blank nodes that condition 3 does not allow. SPARQL’s basic subgraph matching semantics respects these conditions by requiring solution mappings to refer to blank nodes that actually occur in the active graph, which essentially treats blank nodes as (Skolem) constants.

The use of Skolemization in the definition of an entailment regime makes this understanding of blank nodes explicit while still allowing for inferred triples that are not necessarily present in the queried graph. For the above example, condition (C1) works as follows: let skol be a prefix that denotes a fresh IRI not occurring in G and let sk(G) be the following (Skolemized) graph:

ex:a ex:b skol:c .
skol:d ex:e ex:f .

The Skolem function maps _:c to skol:c and _:d to skol:d. In order to satisfy (C1), the only blank nodes that can be used in the range of μ are _:c and _:d, since other blank nodes will either cause sk(μ(BGP)) to be non-ground since sk is not defined for the blank nodes or they might be Skolemized to terms not occurring in G, leading to non-entailed triples sk(μ(BGP)). Furthermore, we can only use a solution mapping that maps x to _:c and y to _:d because otherwise the entailment does not hold, assuming that G is actually the scoping graph. Note, however, that the scoping graph SG could equally be a graph that is RDF-equivalent to G, but possibly with renamed blank nodes. In this case, the solution could contain a blank node other than _:c, but importantly there is just one solution under condition (C1). Clearly, the Skolemized blank nodes should not occur in query results themselves, i.e., instead of skol:c it is expected that _:c is returned in the solution sequence; the Skolemization is just a way of defining conditions on possible solutions.

Note that (C1) still permits derived solutions. If we assume RDFS entailment (RDF entailment is too weak to infer any meaningful consequences) and assume that G additionally contains the triple

ex:b rdfs:subPropertyOf ex:b' .

the BGP

ex:a ex:b' ?x . ?y ex:e ex:f . 

still yields the same one solution.

Materialization is a common implementation technique (e.g., for the RDF or RDFS regime) and it is worth pointing out that new blank nodes introduced in the saturation process are not to be returned in the solutions. Consider the following graph and RDFS entailment

ex:s ex:p "<a/>"^^rdf:XMLLiteral .

If the system were to follow the RDFS inference rules the saturation process would result in the triples

ex:s ex:p _:lit .
_:lit rdf:type rdfs:Literal .

being added to the graph, where _:lit is a blank node allocated to the literal "<a/>"^^rdf:XMLLiteral. The BGP ?x rdf:type rdfs:Literal would have an empty answer. The blank node _:lit is not returned because it is not part of the queried graph. The Skolem function is, therefore, not defined for _:lit and a solution that maps x to _:lit will not yield a ground triple as required by (C1). Note, however, that the entailment regimes do not prescribe any particular implementation technique. Thus, one can use materialization in which the saturated graph contains literals in the subject position of triples or blank nodes in the predicate position in order to implement complete RDFS reasoning [RDFSENTAILMENT], although only mappings that instantiate the BGP into well-formed such RDF triples can constitute solutions. Instead of materializing inferences, techniques based on query rewriting are equally possible to implement the regime.

3.2 Answers from Axiomatic Triples

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

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

against a (scoping) graph containing only the triples

ex:a ex:b ex:c . 
ex:d rdf:type 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 rdf:type rdf:Property RDF entails _:exb1 rdf:type 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), μ(x) occurs in 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.

1. For the possible solution μ₂, 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 μ₃, although μ₃(x)=rdf:subject does not occur in SG, it occurs in rdfV-Minus and this possible solution mapping is, therefore, also returned as an answer.
3. For the possible solution μ₄, since μ₄(x)=rdf:_1 occurs in SG, this is a solution.
4. For the possible solution μ₅, since μ₅(x)=rdf:_2 occurs neither in SG nor in rdfV-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.

3.3 Literals in the Subject Position

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). For example, given a query

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

even the empty graph would RDF entail all statements

xxx rdf:type 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 change in future versions of RDF. If literals were allowed in the subject position, condition (C2) would still guarantee finite answers.

3.4 Boolean Queries

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 rdf:type 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 pattern has four solution triples from rdfV-Minus and hence the answer is true. For Boolean queries without variables the situation is slightly different. Consider, for example, the query

ASK { rdf:type rdf:type rdf:Property }

against the empty graph. Since rdf:type rdf:type 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.5 Aggregates and Blank Nodes

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, for instance, under a such modified entailment regime for RDF(S) one could get less results than with simple entailment. For example, if no blank nodes were to be returned, then the books would have just one author under non-simple entailment.

4.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. For example, 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 derive an inconsistency as follows:

(5) ex:d ex:b "<"^^rdf:XMLLiteral .    (e.g., by applying rule rdfs7 to (3) and (4))
(6) "<"^^rdf:XMLLiteral rdf:type 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} }

5.1 The D-Entailment Regime

It is possible to define one datatype as a refinement of another one. For example, in the XML Schema Datatypes specification [XML Schema Datatypes], the datatype long is derived from the datatype integer, which is itself derived from decimal. The datatype decimal is a primitive type, i.e., it is not a refinement of another datatype. The canonical representation of a data value does, however, not define a datatype. For example, the two literals "2"^^xsd:integer and "2"^^xsd:long both represent the data value 2. This raises the question which literals should be returned in query answers. Let D be a datatype map containing xsd:decimal, xsd:integer and xsd:long. We further assume the queried graph to contains the triple

ex:s ex:p "01"^^xsd:long .

and a query

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

The graph D-entails any triple ex:s ex:p "l"^^dt where dt is a datatype for which the value space contains 1 and where l is a valid lexical form for the value 1. Thus, even if we restrict to the canonical represenations, we still get at least the 3 solutions "1.0"^^xsd:decimal, "1"^^xsd:integer, and "1"^^xsd:long. If D contains further datatypes that contain 1 in their value space, we would get further solutions.

The D-entailment regime assumes, therefore, that for each literal there is a well-defined canonical literal. For D a datatype map, a canonical datatype mapping maps each data value v that occurs in the data space of a datatype dt from D to a unique datatype dc such that the value space of dc contains v. Given a literal "l"^^dt, the canonical literal for "l"^^dt is "lc"^^dc, where lc is the canonical representation for the data value that "l" represents and dc is the canonical datatype for the data value. For the XML Schema Datatypes one can, for example, use the primitive type as the canonical datatype.

5.2 XML Schema Datatypes and Canonical Lexical Representations

Most XML Schema Datatypes [XML Schema Datatypes] can be used with the D-Entailment regime. The canonical mapping, which is defined for all XML Schema Datatypes, is used as a means to achive finite answers. Infinite answers can otherwise occur if a datatype has infinitely many different lexical forms for a data value. For example, in the decimal datatype from the XML Schema Datatypes all of the following lexical forms represent the same value:

• 100.5
• +100.5
• 0100.5
• 100.50
• 100.500
• 100.5000

For the above data values, the canonical lexical form is: 100.5. For the values

• 100
• +100
• 0100
• 100.0
• 100.00
• 100.000

the canonical lexical form is: 100 according to XSD 1.1. XSD 1.1 defines that, for data values that are integers, the canonical representation has no decimal point and no fractional part. This is different in XSD 1.0. XSD 1.0 always requires a decimal point for the canonical representation of a decimal value. Thus, although 1.0 and 1 denote the same value, the canonical form would be 1.0 for a decimal. For integer, however, XSD 1.0 requires that the canonical form has no fraction digits and no decimal point. Thus, the canonical representation must be 1, which is strange since 1 and 1.0 denote the same value and integers are decimals. For this reason, XSD 1.1 seems better suited for use with SPARQL entailment regimes.

Non-primitive datatypes in the XSD are always based on some primitive datatype, e.g., integer, byte, and short are all based on decimal and are obtained by restricting the value space to values without decimal point for integer and by further specifying minimal and maximal values for byte and short. Thus, if "2"^^xsd:integer, "+02"^^xsd:short, and "+2"^^xsd:byte occur in SG and we assume that the canonical datatype is the primitive type according to XSD 1.1, then all three literals contribute "2"^^xsd:decimal to Lit(SG).

Condition (C2) uses the set Lit(SG) to make sure that only the canonical literals can occur in solutions, which guarantees finiteness of the answers. For example, if the queried graph contains

ex:s ex:p "0100.50"^^xsd:decimal .
ex:s ex:p "100.00"^^xsd:decimal .
ex:s ex:p "+100"^^xsd:short .

and the BGP is

ex:s ex:p ?x

then Lit(SG) contains "100.5"^^xsd:decimal (from the first triple) and "100"^^xsd:decimal (from the second and third triple since the primitive type underlying short is decimal and 100.00 is the same value as 100). The BGP evaluation yields two answers with ?x binding once to "100.5"^^xsd:decimal and once to "100"^^xsd:decimal. Without such a restriction, one could get infinitely many answers since solutions that bind ?x "0100"^^xsd:decimal, "00100"^^xsd:decimal, etc. or to "100"^^xsd:integer or"00100"^^xsd:short equally result in entailed triples.

Implementations will typically achieve the desired behavior by transforming the lexical forms of data values into a canonicalized form when loading an RDF graph.

6.1 Entailments under the OWL 2 RDF-Based Semantics (Informative)

Before the restrictions on solutions are explained, a general note about the RDF-Based Semantics is given. The OWL 2 RDF-Based Semantics treats classes as individuals that refer to elements of the domain. Each such element is then associated with a subset of the domain, called the class extension. This means that semantic conditions on class extensions are only applicable to those classes that are actually represented by an element of the domain which can lead to less consequences than expected. An example is given by the following graph G

ex:a rdf:type ex:C

and basic graph pattern BGP

?x a [ rdf:type owl:Class ; owl:unionOf ( ex:C ex:D ) ]

The graph G states that ex:a has type ex:C, while the BGP asks for instances of the complex class denoting the union of ex:C and ex:D. One might expect that a solution mapping μ that maps x to ex:a is a solution, but this is not the case under the OWL 2 RDF-Based Semantics (see also [OWL 2 RDF-Based Semantics], Sec. 7.1). It is guaranteed that the union of the class extensions for ex:C and ex:D exists as a subset of the domain; no statement in G implies, however, that this union is the class extension of any domain element. Thus, μ(BGP) is not entailed by G. The entailment holds, however, when the statement

ex:E owl:unionOf ( ex:C ex:D ) 

is added to G. In the OWL 2 Direct Semantics, in contrast, classes denote sets and not domain elements, so G entails μ(BGP) under the Direct Semantics where, formally, G must first be extended with an ontology header to become well-formed.

6.2 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 General Notes section. Under OWL 2 RDF-Based Semantics the axiomatic triples are not included and owl2V-Minus could equally be replaced by owl2V. The lexical representation for data values are restricted as explained for the case of D-entailment. Infiniteness can, however, not only arise due to different lexical representations of one and the same data value as in the case of the D-entailment regime. Consider, for example, an ontology containing the following axiom:

ex:x owl:sameAs "5"^^xsd:decimal .

A query, which asks for all things that are different to ex:x then has infinitely many possible answers since any literal different from 5 will satisfy the constraints. This can be formulated by the following query:

SELECT ?l WHERE { ex:x owl:differentFrom ?l .}

Note that triples which are seemingly unrelated to the query can still influence the query results. For example, if we add to the queried ontology the triple:

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

Then the query no longer has an empty answer but returns one answer with binding "6"^^xsd:int for l.

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

The standard reasoning problems in OWL under the OWL 2 RDF-Based Semantics are semidecidable, 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.

6.4 OWL 2 Profiles and Entailment Checkers

The OWL 2 Profiles specification [OWL 2 Profiles] describes several syntactic restrictions for OWL ontologies. For ontologies that fall into these fragments, specialized implementation techniques can be used, which often result in a better performance.

The OWL 2 RDF-Based Semantics can, in general, be used with arbitrary RDF graphs (OWL 2 Full ontologies) and, therefore, with all above described profiles. Taking this into account, the OWL 2 Conformance [OWL 2 Conformance] document specifies five different kinds of entailment checkers, which can all be used with the RDF-Based Semantics:

1. OWL 2 Full entailment checkers, which take OWL 2 Full ontology documents as input;
2. OWL 2 DL entailment checkers, which takes OWL 2 DL ontology documents as input;
3. OWL 2 EL entailment checkers, which takes OWL 2 EL ontology documents as input;
4. OWL 2 QL entailment checkers, which takes OWL 2 QL ontology documents as input;
5. OWL 2 RL entailment checkers, which takes OWL 2 Full ontology documents as input.

The OWL 2 RL entailment checker is slightly different in that OWL 2 RL entailment checkers work, as OWL 2 Full entailment checkers, on OWL 2 Full Ontologies, whereas the others make restrictions on the allowed input. The first four entailment checkers should not return Unknown when checking entailment on the respective allowed inputs. OWL 2 RL entailment checkers should not return Unknown under the RDF-Based Semantics if it is possible to derive True using the OWL 2 RL/RDF rules.

SPARQL 1.1 Service Descriptions can be used to describe what kind of entailment checker is used in the backgroud to answer SPARQL queries. In addition to specifying the used semantics by relating the IRI of the endpoint via the property sd:defaultEntailmentRegime or sd:entailmentRegime to the IRI of the entailment regime, one can relate the endpoint IRI via the property sd:defaultSupportedEntailmentProfile or sd:supportedEntailmentProfile to one of the following profile IRIs:

1. http://www.w3.org/ns/owl-profile/Full for OWL 2 Full entailment checkers;
2. http://www.w3.org/ns/owl-profile/DL for OWL 2 DL entailment checkers;
3. http://www.w3.org/ns/owl-profile/EL for OWL 2 EL entailment checkers;
4. http://www.w3.org/ns/owl-profile/QL for OWL 2 QL entailment checkers;
5. http://www.w3.org/ns/owl-profile/RL for OWL 2 RL entailment checkers.

The property sd:supportedEntailmentProfile is used to indicate that a different profile applies to a certain named graph. Together with the semantics, this indictaes which type of OWL entailment checker is used to answer the queries.

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

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

7.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. For example, the triples

ex:Peter rdf:type _:x . 
_:x rdf:type 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)

7.2 The OWL 2 Direct Semantics Entailment Regime

7.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. The use of owl2V-Minus is purely for consistency with the other regimes, but could be omitted completely since under the Direct Semantics there are no axiomatic triples and variables can only bind to built-in terms that are also built-in entities. Built-in entities such as owl:Thing are assumed to be present in any ontology (see Table 5 [OWL 2 Structural Specification]), i.e., O(SG) automatically includes declarations for these built-in entities. 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. An explanation for the restriction to canonical forms of literals is given in the D-entailment regime.

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 .

7.4 Higher-Order Queries (Informative)

OWL's Direct Semantics is rooted in standard First-Order Logic, but it might seem as if the OWL Direct Semantics entailment regime goes beyond First-Order queries. For example, one can use the BGP ?x rdfs:subClassOf ?y to query for pairs of sub and superclasses. This is, 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 rdf:type [ 
        rdf:type 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.

Due to the restriction that variables can only bind to terms from a finite vocabulary, any query can be reduced to a finite set of Boolean queries that can be answered under OWL's First-Order semantics. For example, the subclass query above can be answered, by asking for all pairs of class names from the queried ontology, whether the instantiated (hence, variable-free) pattern is entailed by the queried ontology under the OWL Direct Semantics. Thus, the SPARQL queries in the entailment regime still have a First-Order semantics.

7.5 OWL 2 Entailment Checkers and Profiles

The OWL 2 Direct Semantics is not defined for arbitrary RDF graphs, but only for graphs that satisfy the OWL 2 DL constraints. The OWL 2 profiles further restrict the allowed inputs. As for the RDF-Based Semantics, SPARQL 1.1 Service Descriptions can be used to describe what kind of entailment checkers is used in the backgroud to answer SPARQL queries. In addition to specifying the used semantics by relating the IRI of the endpoint via the property sd:defaultEntailmentRegime or sd:entailmentRegime to the IRI of the entailment regime, one can relate the endpoint IRI via the property sd:defaultSupportedEntailmentProfile or sd:supportedEntailmentProfile to one of the following profile IRIs:

1. http://www.w3.org/ns/owl-profile/DL for OWL 2 DL entailment checkers;
2. http://www.w3.org/ns/owl-profile/EL for OWL 2 EL entailment checkers;
3. http://www.w3.org/ns/owl-profile/QL for OWL 2 QL entailment checkers;
4. http://www.w3.org/ns/owl-profile/RL for OWL 2 RL entailment checkers.

The profile IRI together with the semantics then indicates what kind of entailment checker is used in the backgroud and what syntactic restrictions this tool makes.

8.1 (Simple) RIF Core Entailment Regime

For example, consider the Class_Membership test case from the RIF test cases repository comprised of the following RDF graph and imported RIF Core document (in the presentation syntax):

(1) ex:Adrian ex:isChildOf ex:Uwe .
(2) ex:Adrian rdf:type ex:Male .
(3) ex:Uwe rdf:type ex:Male  .
(4) <Class_Membership_rule.rifps> rif:usedWithProfile <http://www.w3.org/ns/entailment/Simple> . 
            

Group ( 
        Forall ?X ?Y ( 
               ?Y [ ex:isFatherOf -> ?X ] :- And( ?X [ ex:isChildOf -> ?Y  ] 
                                                  ?Y [ rdf:type -> ex:Male ] 
        )  
    )
)               

The SPARQL query below can be dispatched against the graph using the (Simple) RIF Core Entailment Regime:

SELECT ?father ?child WHERE { ?father ex:isFatherOf ?child . }

producing the single solution:

This follows from the fact that the result of applying a pattern instance mapping comprised of the solution μ₁ above and an empty mapping for blank nodes against the BGP in the query, i.e., sk(P(?father ex:isFatherOf ?child)), is RIF-Simple entailed by the RIF-RDF combination formed from the RIF Core document and a graph comprised of just statements (1)-(3).

8.2 Custom Rulesets for Common Vocabulary Interpretations (Informative)

RDF vocabulary such as RDFS and OWL 2 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 OWL 2 RL.

8.3 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 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 every query) it is necessary to test whether a given query is safe [SAFETY].

Certain safety conditions on logic programs permit the use of cyclic references between built-in function symbols 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 condition C4 regarding SPARQL extensions and their solution 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) <.. path to above document ..> rif:usedWithProfile <http://www.w3.org/ns/entailment/Simple>.
(2) ex:Operation1 rdf:type 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   rdf:type 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      rdf:type 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:

8.4 Referencing a RIF Document

RIF RDF and OWL Compatibility [RIF RDF] defines the entailments of combinations (R, G) where R (a RIF rule set) includes an import of G (an RDF graph).

For the inverse of such a reference, i.e., the import of a RIF document into an RDF graph the designated RDF predicate rif:usedWithProfile enables an import to be specified from the graph G instead of from R.

In the simple usage the graph G is a plain RDF graph and rif:usedWithProfile is used to combine that graph with one or more externally defined RIF rule sets. In this usage each subject of a rif:usedWithProfile assertion should be the URI for a RIF rule set (which may be encoded in RIF-XML or RIF-in-RDF) and the object should be an import profile as defined in RIF RDF and OWL Compatibility [RIF RDF].

The semantics of rif:usedWithProfile is explained in the following subsection.

   Document (
     Imports(R1') 
     ...
     Imports(Rn')
     Imports(G' P1)
     ...
     Imports(G' Pn)
   )

  Ri rif:usedWithProfile Pi .

  Document(
   Prefix(foaf <http://xmlns.com/foaf/0.1/>)
   Prefix(rel <http://purl.org/vocab/relationship/>)

   Group
   (
     Forall ?S ?O (
         ?S [ foaf:knows ?O ] :- ?S [ rel:worksWith ?O ]
     )
   )
  )

  @prefix : <http://www.w3.org/2007/rif#> .
  @prefix foaf: <http://xmlns.com/foaf/0.1/> .
  @prefix rel: <http://purl.org/vocab/relationship/> .

  <http://example.org/r1> a :Document;
   :directives () ;
   :payload [  rdf:type :Group ;
      :sentences  ( 
         [ rdf:type :Forall; 
           :formula  [ a :Implies ;
            :if  [ rdf:type :Frame ; 
                   :object [ rdf:type :Var; :varname "S" ] ; 
                   :slots  ( [ rdf:type :Slot; :slotkey   [ 
                                   rdf:type :Const ; 
                                   :constIRI "http://purl.org/vocab/relationship/worksWith" ];
                               :slotvalue [ rdf:type :Var; :varname "O" ] ] )
                 ];
            :then [ rdf:type :Frame ; 
                   :object [ rdf:type :Var; :varname "S" ] ; 
                   :slots  ( [ rdf:type :Slot; :slotkey   [  
                                   rdf:type :Const ; 
                                   :constIRI "http://xmlns.com/foaf/0.1/knows" ];
                               :slotvalue [ rdf:type :Var; :varname "O" ] ] )
                 ] ] ;
            :vars  ( [rdf:type :Var;  :varname "S" ] [ rdf:type :Var; :varname "O" ] ) ] ) 
  ] .

  @prefix : <http://www.example.org/> . 
  @prefix rel: <http://purl.org/vocab/relationship/> . 
  @prefix rif: <http://www.w3.org/2007/rif#> .

  :bob rel:worksWith :alice .
  <http://example.org/r1> rif:usedWithProfile <http://www.w3.org/ns/entailment/Simple> .

  SELECT * 
  WHERE { ?S ?P ?O }

  PREFIX rif:  <http://www.example.org/>
  SELECT DISTINCT ?N 
  WHERE { GRAPH <r1> {  [ rif:varname ?N ] } }

10.1 Limitations of Property Paths in Combination with Entailment Regimes

Since property paths are evaluated without entailment, the evaluation under an entailment regime can yield counter-intuitive results. Assuming the use of the RDFS entailment regime and the query

SELECT * WHERE { ?s (ex:p3+) ?o }

over the above given example data, the result is empty. Although the data contains ex:b ex:p2 ex:c and ex:p2 rdfs:subPropertyOf ex:p3, which under RDFS entailment implies ex:b ex:p3 ex:c, this fact is not used since the arbitrary length path expression ex:p+ is evaluated with simple entailment, i.e., via subgraph matching on the input data.

Since property path evaluation works directly on the active graph, the OWL Direct Semantics entailment regime is unlikely to support queries where the query pattern contains path expressions since systems that apply the Direct Semantics of OWL do not work with the graph directly, but translate the triples into OWL structural objects. Combining the other entailment regimes with property path expressions is, however, relatively straightforward.

Future versions of SPARQL may define further extensions to the handling of property paths together with entailment regimes that handle property paths in a specific way, which is why the present section is kept informative.