W3C

SPARQL 1.1 Entailment Regimes

W3C Working Draft 26 January 2010

This version:
http://www.w3.org/TR/2010/WD-sparql11-entailment-20100126/
Latest version:
http://www.w3.org/TR/sparql11-entailment/
Previous version:
http://www.w3.org/TR/2009/WD-sparql11-entailment-20091022/
Editors:
Birte Glimm, Oxford University Computing Laboratory <birte.glimm@comlab.ox.ac.uk>
Bijan Parsia, University of Manchester <bparsia@cs.manchester.ac.uk>

Abstract

SPARQL is a query language for data that is stored natively as RDF or viewed as RDF via middle-ware. What the correct answers to a SPARQL query are, depends on the used entailment regime and the vocabulary from which the resulting answers can be taken. SPARQL 1.1 Query [SPARQL 1.1 Query] defines basic graph pattern matching only for simple entailment, but it defines a set of conditions that have to be met when defining what correct results are for SPARQL queries under different entailment regimes. The goal of this document is to specify conditions such that SPARQL can be used with some other entailment regimes beyond simple entailment.

Status of this Document

This section describes the status of this document at the time of its publication. Other documents may supersede this document. A list of current W3C publications and the latest revision of this technical report can be found in the W3C technical reports index at http://www.w3.org/TR/.

This is a Working Draft.

Comments on this document should be sent to public-rdf-dawg-comments@w3.org, a mailing list with a public archive. Questions and comments about SPARQL that are not related to this specification, including extensions and features, can be discussed on the mailing list public-sparql-dev@w3.org, (public archive).

This document was produced by the SPARQL Working Group, which is part of the W3C Semantic Web Activity.

Change Summary

The first public working draft defined the semantics of SPARQL queries under RDF and RDFS entailment. In this public working draft the RDF and RDFS entailment regimes have been changed to use a Skolemized version of the queried RDF triples to limit the possible answers to a finite set of answers. This prevents non-local effects that caused additional results for existing triples from unrelated newly added triples that contain new blank nodes. This draft further adds an entailment regime for OWL Direct Semantics, which covers the OWL 2 DL, EL, and QL Profiles.

Future working drafts will also include entailment regimes for D-entailment, OWL with RDF-Based Semantics including the OWL 2 RL Profile, and the rule interchange format RIF.

No Endorsement

Publication as a Working Draft does not imply endorsement by the W3C Membership. This is a draft document and may be updated, replaced or obsoleted by other documents at any time. It is inappropriate to cite this document as other than work in progress.

Patents

This document was produced by a group operating under the 5 February 2004 W3C Patent Policy. W3C maintains a public list of any patent disclosures made in connection with the deliverables of the group; that page also includes instructions for disclosing a patent. An individual who has actual knowledge of a patent which the individual believes contains Essential Claim(s) must disclose the information in accordance with section 6 of the W3C Patent Policy.

Table of Contents

1 Introduction
    1.1 Document Conventions
        1.1.1 Graph Syntax
        1.1.2 Namespaces
        1.1.3 Preliminary Definitions
        1.1.4 Result Descriptions
    1.2 Effects of Different Entailment Regimes
    1.3 Extensions to Basic Graph Pattern Matching
2 RDF Entailment Regime
    2.1 Blank Nodes in the Queried Graph (Informative)
    2.2 Answers from Axiomatic Triples (Informative)
    2.3 Literals in the Subject Position (Informative)
    2.4 Boolean Queries (Informative)
3 RDFS Entailment Regime
    3.1 Inconsistencies (Informative)
        3.1.1 Effects of Unchecked Inconsistencies
4 D-Entailment Regime
5 OWL 2 RDF-Based Semantics Entailment Regime
6 OWL 2 Direct Semantics Entailment Regime
    6.1 Restrictions on Solutions (Informative)
        6.1.1 From BGPs to Ontology Structures
        6.1.2 Parsing Basic Graph Pattern for Direct Semantics
        6.1.3 Queries for Numbers in Number Restrictions
        6.1.4 Combined Semantics
        6.1.5 Restriction on Data Property Assertions
        6.1.6 Queries for Axioms with Annotations and Non-Logical Axioms
            6.1.6.1 Queries for Declarations
            6.1.6.2 Queries for Annotations
    6.2 Higher Order Queries (Informative)
    6.3 OWL 2 Profiles for Direct Semantics
        6.3.1 OWL 2 DL
        6.3.2 The OWL 2 EL Profile
        6.3.3 The OWL 2 QL Profile
7 RIF Entailment
8 Entailment Regimes and Data Sets (Informative)
9 Entailment Regimes and Updates (Informative)

Appendices

A Related Issues
B References
    B.1 Normative References
    B.2 Other References
C CVS History
    C.1


1 Introduction

The SPARQL 1.1 Query specification [SPARQL 1.1 Query] defines only simple entailment, which allows for finding answers by matching the triple pattern of the query onto the RDF graph of the queried data. Other entailment regimes, such as RDFS entailment, allow for finding answers to a query that are not directly specified in the queried graph, but can be inferred using a set of inference rules. In this document, we specify how SPARQL can be used with some other entailment regimes beyond simple entailment.

SPARQL Entailment Regimes is closely related to the following specifications:

References to RDF or RDFS entailment rules from the RDF Semantics specification are in some places used in an informative way and implementations are not expected to implement these rules as they are used here.

1.1 Document Conventions

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

1.1.1 Graph Syntax

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

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

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

@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.1.2 Namespaces

Examples assume the following namespace prefix bindings unless otherwise stated:

PrefixIRI
rdf:<http://www.w3.org/1999/02/22-rdf-syntax-ns#>
rdfs:<http://www.w3.org/2000/01/rdf-schema#>
owl:<http://www.w3.org/2002/07/owl#>
xsd:<http://www.w3.org/2001/XMLSchema#>
fn:<http://www.w3.org/2005/xpath-functions#>

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

1.1.3 Preliminary Definitions

This document uses the same definitions as the SPARQL Query Language specification. Important terms are recaptured below for clarity. In the case of any differences, the SPARQL Query Language definitions are the normative ones.

The term I denotes the set of all IRIs, RDF-L the set of all RDF Literals, and RDF-B the set of all blank nodes in RDF graphs.

The set of RDF Terms, RDF-T, is I union RDF-L union RDF-B.

The set of query variables is denoted as V and V is assumed to be countable, infinite, and disjoint from RDF-T. A triple pattern is member of the set:

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

A Basic Graph Pattern is a set of Triple Patterns.

1.1.4 Result Descriptions

Result sets are illustrated in tabular form.

xyz
"Alice"<http://example/a>     

A 'binding' is a pair (variable, RDF term). In this result set, there are three variables: x, y, and z (shown as column headers). Each solution is shown as one row in the body of the table. Here, there is a single solution, in which variable x is bound to "Alice", variable y is bound to <http://example/a>, and variable z is not bound to an RDF term. Variables are not required to be bound in a solution.

Sometimes solutions are annotated with the name of a solution mapping so that the explanatory text can refer to the solution mapping and explain or justify certain solutions. For example, in the results table below, the only solution is given by the solution mapping μ1:

xyz
μ1"Alice"<http://example/a>     

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 {P1 ... Pn} for a basic graph pattern BGP, and where {BGP1 .... BGPn} 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 P1(BGP1) union ... union Pn(BGPn))
    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 note11/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 note14/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.
Editorial note05/01/2010
The working group is looking to describe available entailment regimes in terms of service descriptions. The URIs given for each of the described entailment regimes are meant to be used to describe the semantics used by a SPARQL endpoint if it does not use simple entailment. Since endpoints that use OWL Direct Semantics might restrict the set of RDF graphs that can be queried, the section on OWL profiles further gives URIs that a SPARQL endpoint can use in its service description to advertise which restrictions it places on queried RDF graphs.

2 RDF Entailment Regime

RDF entailment is closest to simple entailment in that it provides only few additional answers and RDF is not expressive enough to express inconsistencies. RDF does, however, entail an infinite set of axiomatic triples and we have to specify how we can guarantee the forth condition on extensions of basic graph pattern matching, which requires that answer sets are always finite.

NameRDF
URIhttp://www.w3.org/ns/entailment/RDF
Legal GraphsAny legal RDF graph.
Legal QueriesAny legal SPARQL query.
Illegal handlingIn case the query or the queried graph is illegal (syntax errors), the system MUST raise an error.
EntailmentRDF Entailment
InconsistencyRDF graphs are always RDF consistent and no inconsistency handling is required.
Query Answers

Let G be the queried RDF graph, BGP be a basic graph pattern, V(BGP) the set of variables in BGP, B(BGP) the set of blank nodes in BGP, SG the scoping graph for G and BGP, sk(SG) a Skolemization of SG with respect to a vocabulary disjoint from the vocabulary of SG and BGP, and P=(μ, σ) a pattern instance mapping. We write P(BGP) to denote the result of replacing each variable v from V(BGP) for which μ is defined with μ(v) and each blank node b from B(BGP) for which σ is defined with σ(b). Applying sk to a term t, written sk(t), yields sk(t) if sk is defined for t and t otherwise. With sk(P(BGP)) we denote the result of replacing each blank node b in P(BGP) for which sk is defined with sk(b).

A solution mapping μ is a possible solution for BGP from G under RDF entailment if dom(μ) = V(BGP) and there is an RDF instance mapping σ from B(BGP) to RDF-T such that dom(σ)=B(BGP) and the pattern instance mapping P=(μ, σ) is such that P(BGP) are well-formed RDF triples that are RDF entailed by SG.

A possible solution μ is a solution for BGP from SG under RDF entailment if:

(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).

Please note that we use a a two-stage process to define what legal answers are under RDF entailment. Intuitively, the possible answers are all answers that one would expect under RDF entailment, i.e., all mappings such that instantiating the basic graph patterns with them results in RDF triples that are RDF entailed by the queried graph. The set of possible answers is, however, not necessarily finite. To obtain always a finite set of answers, the next step defines which of the possible answers are actually to be returned as answers to the query. In this step, we restrict answers to those that correspond to ground triples that are entailed by the Skolemized scoping graph (C1). This limits infinite answers from blank nodes, while still preserving most users' expectations of the cardinality of the answers. Condition C2 further makes sure that the query answer contains only finitely many of the axiomatic triples. The two restrictions are further explained below.

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

so
μ1ex:a1_:c1
μ2ex:a1_:c2
μ3ex:a2_:c3

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

so
μ4ex:a1_:c3
μ5ex:a1_:whatever
ex:a1...

Observe that, for instance, solution μ4 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 P1=(μ1, σ1) with μ1 as given above and σ1 an empty RDF instance mapping. In this case, P1(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(μ1(?s)) = sk(ex:a1) = ex:a1 occurs in the scoping graph, also C2 is satisfied and μ1 is a solution. Similarly, it can be shown that μ2 and μ3 are solutions. The other possible solutions are, however, not returned as solutions. For example, consider the pattern instance mapping P4=(μ4, σ4) for an empty RDF instance mapping σ4. In this case P4(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 P5=(μ5, σ5) for an empty RDF instance mapping σ5 leads to P5(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

x
μ1ex:b

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

x
μ2rdf:type
μ3rdf:subject
μ4rdf:_1
μ5rdf:_2
...

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 μ2 to μ5 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 μ2, take an empty RDF instance mapping σ2 to obtain a pattern instance mapping P2=(μ2, σ2) with P2(BGP) = rdf:type a rdf:Property. Since μ2(?x)=rdf:type occurs in SG, condition C2 is also satisfied and this solution mapping is a solution.
  2. For the possible solution μ3: take again an empty RDF instance mapping σ3 to obtain a pattern instance mapping P3=(μ3, σ3) with P3(BGP) = rdf:subject a rdf:Property. Since μ3(?x)=rdf:subject does not occur in SG, this possible solution mapping is not returned as an answer.
  3. For the possible solution μ4: take again an empty RDF instance mapping σ4 to obtain a pattern instance mapping P4=(μ4, σ4) with P4(BGP) = rdf:_1 a rdf:Property. Since μ4(?x)=rdf:_1 occurs in SG, this is a solution.
  4. For the possible solution μ5: take again an empty RDF instance mapping σ5 to obtain a pattern instance mapping P5=(μ5, σ5) with P5(BGP) = rdf:_2 a rdf:Property. Since μ5(?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:

x
ex:b
rdf:type
rdf:_1

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

Editorial note14/10/2009

Other possible design choices for finite answers under RDF and the following RDFS entailment regime are:

  1. Condition C2 could be even more restrictive and require that each variable (no matter whether in subject position of a triple or not) that occurs in BGP is such that sk(μ(x)) occurs in sk(SG). This would exclude more answers that involve terms from the RDF(S) vocabulary. For example, an RDF graph containing the triple
    ex:s ex:p ex:o 
    RDF entailes
    ex:p a rdf:Property
    but the query
    SELECT ?t WHERE { ex:p a ?t } 
    against that graph would have an empty answer under this more restrictive condition. This is because a solution mapping μ that maps ?x to rdf:Property violates the condition because rdf:Property does not occur in the scoping graph and Skolemization has no effect in this example.
  2. Instead of using the vocabulary of the graph to limit the number of axiomatic triples, axiomatic triples could simply be excluded from the query answers.
  3. We do return axiomatic triples, but SELECT or CONSTRUCT queries that contain one of the following the triple patterns
    ?x a rdf:Property ;
    ?x a rdfs:ContainerMembershipProperty . 
    ?x rdfs:domain rdfs:Resource . 
    ?x rdfs:range rdfs:Resource . 
    
    must satisfy additional safety restrictions. E.g., if a query contains one of the above triple patterns, then it must specify a limit clause. This would have the advantage that we do have a kind of monotonic behavior, i.e., both ask queries described above would have the answer yes and the subject would be contained in the answers for the according select query, but the additional limit clause would restrict answers to a finite subset of all answers. The disadvantage is that we do have no control as to what would be in the returned answer and what would be left out, which is not very intuitive either.
  4. Since, as long as literals are not allowed in subject positions, only subjects of the form rdf:_1, rdf:_2, ... can cause infinite answers, we could also look at what the largest n is in elements of the form rdf:_n and return axiomatic triples such as rdf:_m a rdf:Property only if m<=n. This falls apart, however, if literals are allowed in the subject position, since in that case
    xxx a rdf:XMLLiteral 
    is an answer to the query
    SELECT ?x WHERE {  ?x a rdf:XMLLiteral }
    for xxx a well-formed RDF XML literal.

3 RDFS Entailment Regime

Under RDFS there are not only more entailments, which result in possibly more query answers, but RDF graphs can also be inconsistent under RDFS interpretations, which can result in infinite answer sets since an inconsistent graph RDFS entails any consequence. The restrictions on query answers are the same as for RDF. They are repeated here so that the description of the entailment regime is self-contained.

NameRDFS
URIhttp://www.w3.org/ns/entailment/RDFS
Legal GraphsAny legal RDF graph.
Legal QueriesAny legal SPARQL query.
Illegal handlingIn case the query or the queried graph is illegal (syntax errors), the system MUST raise an error.
EntailmentRDFS Entailment
InconsistencyIf the queried graph is RDFS-inconsistent, an implementation MAY generate an error or warning and SHOULD generate such an error or warning if, in the course of processing, it determines that the data or query is not compatible with the request.
Query Answers

Let G be the queried RDF graph, BGP be a basic graph pattern, V(BGP) the set of variables in BGP, B(BGP) the set of blank nodes in BGP, SG the scoping graph for G and BGP, sk(SG) a Skolemization of SG with respect to a vocabulary disjoint from the vocabulary of SG and BGP, and P=(μ, σ) a pattern instance mapping. We write P(BGP) to denote the result of replacing each variable v from V(BGP) for which μ is defined with μ(v) and each blank node b from B(BGP) for which σ is defined with σ(b). Applying sk to a term t, written sk(t), yields sk(t) if sk is defined for t and t otherwise. With sk(P(BGP)) we denote the result of replacing each blank node b in P(BGP) for which sk is defined with sk(b).

A solution mapping μ is a possible solution for BGP from G under RDFS entailment if dom(μ) = V(BGP) and there is an RDF instance mapping σ from B(BGP) to RDF-T such that dom(σ)=B(BGP) and the pattern instance mapping P=(μ, σ) is such that P(BGP) are well-formed RDF triples that are RDFS entailed by SG.

A possible solution μ is a solution for BGP from SG under RDFS entailment if:

(C1) The RDF triples sk(P(BGP)) are ground and RDFS 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).

As under RDF entailment, answers under RDFS entailment are defined in a two-stage process. Possible answers are all answers that one would expect under RDFS entailment, i.e., all mappings such that instantiating the basic graph patterns with them results in RDF triples that are RDFS entailed by the queried graph. To obtain always a finite set of answers, the same conditions C1 and C2 as for the RDF entailment regime are used.

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.

3.1.1 Effects of Unchecked Inconsistencies

Please note that the above definition of the RDFS entailment regimes does not require that systems MUST generate an error or a warning in the case of an inconsistency, but systems MAY generate an error or warning. A system SHOULD generate such an error or warning if, in the course of processing, it determines that the data or query is not compatible with the request. Thus, it can happen that we query an inconsistent graph and get a (finite) answer sequence as a result although such a graph would in fact (trivially) entail any RDF triple. This is to allow for more efficient implementations. Consider, for example, a default graph containing the following triples

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 . 

and a query

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

which requires a join operation in the query processor. This graph is RDFS-inconsistent due to the last two triples, but the query processor might know (after parsing) that there is no ex:r property at all in the graph. Thus, the processor knows that it does not have to evaluate the query, but a required check for consistency can be very costly (there could be more than 10,000 ex:b ex:s ex:yn tuples) and after a possibly long time the user would get an error.

Another motivation comes from queries that require a union. For example, the query

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

can be executed by dispatching BGP1 and BGP2 in parallel to some processing element, streaming results back to the caller from either side of the UNION as they become available. Since the use of HTTP for streaming back results places some constraints on what can be done, e.g., the error or success code must be transmitted before results start, at the point where a query processor might discover the inconsistency it might be too late for a conformant way of communicating this to the client.

Editorial note14/10/2009

The current understanding of the working group is that the first condition on extensions of basic graph pattern matching:

The scoping graph, SG, corresponding to any consistent active graph AG is uniquely specified and is E-equivalent to AG.

does not apply to inconsistent active graphs. This condition does, thus, not restrict on how we define the scoping graph in case of an E-inconsistent active graph and at current we just define the scoping graph the same way as for consistent graphs.

One alternative way would be to define the scoping graph only if the active graph is consistent. If the active graph is inconsistent, one then has to specify conditions independent of the scoping graph that prevent infinite answers (an inconsistent graph trivially RDFS entails any RDF triple). Another possibility would be to specify an entailment regime for a subset of RDFS that cannot express inconsistencies, e.g., by defining well-formed graphs for the regime as those that contain only syntactically valid rdf XML literals. Several other alternatives, including different, implementation-dependent behaviors for systems that do/do not check consistency are currently being under discussion in the working group.

4 D-Entailment Regime

Editorial note14/10/2009
D-Entailment is just a hook at the moment...

NameD-Entailment
URIhttp://www.w3.org/ns/entailment/D
Legal GraphsAny legal RDF graph.
Legal QueriesAny legal SPARQL query.
Illegal handlingIn case the query or the queried graph is illegal (syntax errors), the system MUST raise an error.
EntailmentD-Entailment
InconsistencyTBD
Query AnswersTBD

5 OWL 2 RDF-Based Semantics Entailment Regime

Editorial note14/10/2009
OWL 2 RDF-Based Semantics is just a hook at the moment (covers OWL 2 Full and OWL 2 RL)...

NameOWL 2 RDF-Based Semantics
URIhttp://www.w3.org/ns/entailment/OWL-RDF-Based
Legal GraphsAny legal RDF graph.
Legal QueriesAny legal SPARQL query.
Illegal handlingIn case the query or the queried graph is illegal (syntax errors), the system MUST raise an error.
EntailmentOWL 2 RDF-Based Semantics
InconsistencyTBD
Query AnswersTBD

6 OWL 2 Direct Semantics Entailment Regime

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 Syntax specification [OWL 2 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 Specification]. A FSS axiom can correspond to several RDF triples and the RDF triples might contain auxiliary blank nodes that are no longer visible in the obtained ontology structure. E.g., the axiom

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

corresponds to the RDF triples

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

where _:x is an arbitrary blank node. OWL axioms may still contain blank nodes, but these correspond to OWL individuals that have no explicit names and are called anonymous individuals. For example, the axiom

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

corresponds to the triple

ex:Peter ex:hasBrother _: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 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)

SPARQL 1.1 Query [SPARQL 1.1 Query] is only defined for basic graph patterns using a triple-based syntax. For OWL 2 Direct Semantics, an alternative syntax for BGPs based on the functional-style syntax or other popular OWL syntaxes seems natural, but is not part of this specification.

Some RDF triples that are well-formed for OWL 2 DL, are mapped to OWL 2 DL axioms that carry no semantics. If strictly applying the direct semantics, it is not possible to query for any such axioms (triples). 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. Since in particular annotations are important for users and users do want to query for annotations, the OWL 2 Direct Semantics entailment regime uses a combined semantics that also gives semantics to annotations, entity declarations, and ontology header axioms (containing the ontology IRI or other annotations).

NameOWL 2 Direct Semantics
URIhttp://www.w3.org/ns/entailment/OWL-Direct
Legal GraphsAny RDF graph which can be mapped into an OWL 2 DL ontology document.
Legal QueriesAny legal SPARQL query.
Illegal handlingIn case the query or the queried graph cannot be parsed (syntax error), the system MUST raise an error. If the queried ontology is not an OWL 2 DL ontology, the system MAY reject the ontology and raise an error or the system MAY use only a subset of the triples in the ontology.
EntailmentOWL 2 Direct Semantics
InconsistencyIf the queried ontology is inconsistent under OWL 2 Direct Semantics, the system MUST raise an error.
Query Answers

Let G be a legal RDF graph for the entailment regime, BGP be a basic graph pattern, V(BGP) the set of variables in BGP, B(BGP) the set of blank nodes in BGP, SG the scoping graph for G and BGP, O(SG) the ontology for SG, sk a total mapping from anonymous individuals in O(SG) to IRIs from a vocabulary disjoint from the vocabulary of O(SG) and BGP, sk(O(SG)) the resulting Skolemization of O(SG), and P=(μ, σ) a pattern instance mapping.

If P(BGP) can be mapped into a set of OWL 2 axioms Ax, then AI(Ax) denotes the set of anonymous individuals in Ax and sk(Ax) denotes the result of replacing each anonymous individual i in AI(Ax) for which sk is defined with sk(i).

A solution mapping μ is a solution for BGP from G under OWL 2 Direct Semantics if dom(μ) = V(BGP) and there is an RDF instance mapping σ with dom(σ)=B(BGP) and P=(μ, σ) such that

(C1) P(BGP) can be parsed into a set of OWL 2 DL axioms Ax using the typing information from O(SG),

(C2) there is no v in V(BGP) such that μ(v) is from the reserved vocabulary of OWL 2,

(C3) no variable occurs in the object position of a triple with the predicate owl:minCardinality, owl:maxCardinality, owl:cardinality, owl:minQualifiedCardinality, owl:maxQualifiedCardinality, or owl:qualifiedCardinality.

(C4) each logical axiom ax in sk(Ax) is such that ax is ground and entailed by sk(O(SG)) under the Direct Semantics,

(C5) each assertion DataPropertyAssertion(X Y Z) in sk(Ax) is such that sk(O(SG)) contains an assertion DataPropertyAssertion(X' Y Z) and sk(O(SG)) entails SubDataPropertyOf(X' X) under Direct Semantics, and

(C6) each axiom ax in sk(Ax) that is non-logical or contains an annotation is ground and structurally equivalent to an axiom ax' in sk(O(SG)).

Editorial note11/01/2010
Note that the Direct Semantics entailment regime requires a consistency check, whereas the RDF and RDFS entailment regimes do not require such a check. This is because a required check is consistent with the conditions outlined in the SPARQL/Query specification and because OWL Direct Semantics reasoners typically implement model building procedures that will anyways notice if a model cannot be build.

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.

6.1.1 From BGPs to Ontology Structures

Restriction C1 requires that the instantiated BGP can be mapped into OWL 2 DL axioms. Since instantiated BGPs are not necessarily complete ontologies, the typing information from O(SG) can be used to disambiguate the types, e.g., to determine whether an IRI in BGP is an object or a data property. Otherwise the BGP would possibly have to contain several declarations.

It is further assumes that the resulting axioms do satisfy the restrictions for OWL 2 DL ontologies, i.e., if they where added to an ontology that only contains the type declarations from O(SG), then the ontology satisfies the restrictions of OWL 2 DL. The OWL 2 DL restrictions already prevent some sources of infinite answers. E.g., for owl:topDataProperty, the following requirement has to be met in OWL 2 DL:

The owl:topDataProperty property occurs in Ax only in the superDataPropertyExpression part of SubDataPropertyOf axioms.

Without the restriction a query such as

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

would result in infinite solutions and restrictions would have to be placed on possible solutions to restrict the set of actual solutions to a finite set as for RDF and RDFS entailment. Here, however, any solution mapping applied to the BGP ?o owl:topObjectProperty ?d results in an RDF triple that cannot be parsed into an OWL 2 DL axiom as required by C1, which means that the query has an empty answer.

OWL 2 DL also places restrictions on the use of blank nodes (anonymous individuals). These restrictions require that blank nodes are only connected in a tree-like way and is required. For queries this means that known algorithms can be used to compute the query answers. Without such a restriction it is not clear whether this task is decidable. Thus, apart from making it possible to parse BGPs into ontology structures, this restriction helps to ensure finite answers and computability of solutions.

6.1.2 Parsing Basic Graph Pattern for Direct Semantics

Restriction C2 disallows the use of bindings from the reserved vocabulary for OWL 2. Without such a restriction parsing a BGP into ontology structures would we very difficult and since the semantics is defined in terms of ontology structures, a BGP first has to be interpreted as an OWL ontology structure before the answers can be determined. Consider the following query

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

Without any restrictions this query could be a query for

  1. declarations, i.e., the BGP maps to a declaration such as Declaration(Class(?s)) where ?p binds to rdf:type, ?o to owl:Class, and bindings for ?s have to be computed or Declaration(ObjectProperty(?s)) where ?p binds to rdf:type and ?o to owl:ObjectProperty, or any other type of declaration,
  2. inverse object properties, i.e., the BGP maps to ObjectInverseOf(?o) where ?s maps to a blank node and ?p to owl:inverseOf,
  3. subclasses, i.e., the BGP maps to SubClassOf( ?s ?o ) where ?p binds to rdfs:subClassOf,
  4. equivalent classes, i.e., the BGP maps to EquivalentClasses(?s ?o) where ?p binds to owl:equivalentClass,
  5. disjoint classes, i.e., the BGP maps to DisjointClasses(?s ?o) where ?p binds to owl:disjointWith,
  6. ...

In order to answer the query without any restrictions, all possible ways of mapping the BGP into ontology structures have to be considered. To make this mapping from BGPs to ontology structures and, thus, query answering more feasible, variables must not be bound to terms from the reserved vocabulary of OWL. The result of this restriction is, intuitively, that variables can only occur in the position of function parameters of the functional-style syntax and not in the position of functions. Under this restriction, the BGP from the above query can only be mapped to ObjectPropertyAssertion(?p ?s ?o), DataPropertyAssertion(?p ?s ?o), or AnnotationAssertion(?p ?s ?o). The first mapping contributes query answers that consist of a pair of individuals plus an object property with which the individuals are related. The second possible mapping contributes pairs of an individual and a literal plus the data property with which the pair is related (certain restrictions are applied on these answers as discussed below). The third mapping contributes answers from annotations, which are computed due to the combined semantics applied for this entailment regime (cf. C6).

The typing information in the queried ontology can be used to disambiguate the types in the query. E.g., the BGP of the query

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

is parsed into

ObjectPropertyAssertion(ex:r ?x ex:b)

if ex:r is declared as an object property in the queried ontology and into

AnnotationAssertion(ex:r ?x ex:b)

if ex:r is declared as an annotation property.

Editorial note05/01/2010
Restriction C2 is even more restrictive then required for forbidding variables in function positions of the FSS since, for example, also rdfs:label is a reserved keyword and if O(SG) contains AnnotationAssertion(rdfs:label ex:Person "The class of persons.") (in Turtle: ex:Person rdfs:label "The class of persons."), then the BGP ex:Person ?ap ?av . cannot be legally be instantiated with a solution mapping that maps ?ap to rdfs:label.

6.1.3 Queries for Numbers in Number Restrictions

Restriction C3 is used to prevent infinite solutions from queries that query for numbers in number restrictions. Consider an ontology containing the axioms

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

in Turtle

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

stating that Peter has at most one son and a the query

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

where the BGP corresponds to the FSS translation

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

The query asks for all n such that Peter has not more than or equal to n sons. This is the case for any n greater than two. Thus, for any instantiation of n with an integer greater than two this axiom is entailed and without any further restrictions the set of answers would be infinite. Restriction C3 prevents that by disallowing variables in the position of numbers in number restrictions.

6.1.4 Combined Semantics

Restrictions C4 to C6 restrict answers to those that satisfy the applied semantics. Restriction C4 is straightforward and used to apply OWL 2 Direct Semantics to logical axioms. Data property assertions, non-logical axioms and axioms with annotations are handled differently by C5 and C6 respectively. The following two sections explain the different treatment of those kinds of axioms.

6.1.5 Restriction on Data Property Assertions

Under OWL 2 Direct Semantics individuals can be related to a data value although this is not explicitly stated and the actual value might not occur in any axiom of the ontology. For example, consider an ontology with a data property ex:dp containing the axiom

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

The axiom states that Peter has exactly 2 ex:dp successors and these successors have to be integers greater than 5 and less than 8, which means that one successor has must have the value 6 and the other one the value 7. This axiom can be expressed in Turtle as

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

Under OWL 2 Direct Semantics, an ontology containing the above axiom entails DataPropertyAssertion(ex:dp ex:Peter "6"^^xsd:int) and DataPropertyAssertion(ex:dp ex:Peter "7"^^xsd:int), which is ex:Peter ex:dp "6"^^xsd:int and ex:Peter ex:dp "7"^^xsd:int in Turtle, respectively. Since there are infinitely many integers, a SPARQL endpoint cannot compute the answers to a query with BGP ex:Peter ex:dp ?x by replacing all possible integer values for ?x and then testing entailment. It is also not possible to restrict candidate bindings to the set of data values that occur explicitly in the queried ontology. E.g., neither 6 nor 7 necessarily occurs explicitly in the ontology. The above an axiom does not even lead to a unique solution in the system of linear in-equations that an OWL 2 DL data type checker has to solve and, although algorithms to compute the answers to such a query might exist, they are not known in the general case at the moment. Answers are, therefore, restricted by C5 to values that are either explicitly asserted or asserted for a sub property of the data property in the query. Also allowing for sub-properties at-least supports some inferences, but some inferences will not be returned even if they can be computed.

6.1.6 Queries for Axioms with Annotations and Non-Logical Axioms

Querying for non-logical axioms such as annotations and declarations is possible due to the extra semantics applied to them by restriction C6.

6.1.6.1 Queries for Declarations

Declarations in FSS have forms such as Declaration(Class(ex:myClass)) or Declaration(AnnotationProperty(ex:myAnnotationProperty)). In Turtle that is ex:myClass a owl:Class and ex:myAnnotationProperty a owl:AnnotationProperty, respectively. A query such as

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

would not return any answers under strict Direct Semantics since declarations are not entailed. With the combined semantics the query answer would consist of all IRIs for declared classes. In this case the use of simple entailment instead of structural equivalence would yield the same results, but for annotations the use of structural equivalence is more flexible.

6.1.6.2 Queries for Annotations

In OWL 2 DL several forms of annotations can be used. For example, the ontology header of an ontology with IRI ex:myOntology can contain annotation such as Annotation(rdfs:comment "This is just a toy ontology") (in Turtle: ex:myOntology rdfs:comment "This is just a toy ontology"). In order to retrieve such a comment one can, for example, use the query

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

The ontology can further contain annotation assertions such as AnnotationAssertion(rdfs:label "All persons" ex:Person) (in Turtle: ex:Person rdfs:label "All persons"), which adds a label to the class ex:Person. Finally, axioms can be annotated. For example, the following subclass axiom has a label attached to it via an annotation:

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

The RDF triple version of annotated axioms is quite verbose and several fresh blank nodes are introduced in the triple representation one of which (_:c) is used to relate the annotation to the axiom:

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." .
The following query retrieves the label of the above axiom and its BGP corresponds to the above axiom with a variable in place of the label:
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 .
}

The BGP maps to the following FSS axiom:

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

Depending on the order of parsing, the conjuncts of the intersection might be swapped. Even if the BGP of the query is mapped to ObjectIntersectionOf(ex:Human ex:Person) instead of ObjectIntersectionOf(ex:Person ex:Human), however, the use of structural equivalence, as opposed to simple entailment, makes sure that the label is still retrieved. It is, however, not possible to just add a variable or blank node in place of the (complex) superclass. Replacing the intersection with a blank node leads to axioms that cannot be parsed into an OWL 2 DL axiom. Putting a variable in place of the intersection class, leads to an empty answer because variables only bind to class IRIs and not to complex class expressions.

Apart from the annotations and annotation axioms themselves, one can also declare sub- and super-property relationships between annotation properties, e.g., by stating SubAnnotationPropertyOf(ex:ap1 ex:ap2) for two annotation properties ex:ap1 and ex:ap2 (in Turtle: ex:ap1 rdfs:subPropertyOf ex:ap2), but again such axioms are non-logical and they have no influence on the consequences of an ontology. Finally, one can declare domain and range restrictions for annotation properties, which are also non-logical axioms. Since it is only required that the ontology contains a structurally equivalent axioms to an instantiated non-logical axiom from the query, there are no inferences for sub- and super-annotation properties. E.g., if the ontology contains only the axioms SubAnnotationPropertyOf(ex:ap1 ex:ap2) and AnnotationAssertion(ex:ap1 ex:Person "Some annotation") (in Turtle: ex:ap1 rdfs:subPropertyOf ex:ap2 and ex:Person ex:ap1 "Some annotation"), a query for annotation assertions for ex:ap2 has an empty answer.

Editorial note11/01/2010
There are several alternatives to the restrictions posed on queries under the Direct Semantics entailment regime.
  1. Instead of having condition C1, one could directly restrict the legal queries for the entailment regime. The difference is that under the current all queries are legal and queries that have a BGP that cannot be parsed into OWL 2 DL structures have an empty answer. If some queries are, instead, declared as illegal for the regime, systems should throw an error in case of illegal queries.
  2. Instead of requiring that no variable is assigned to a value form the OWL 2 reserved vocabulary (C2), one could require that after mapping the BGP to OWL objects, variables occur only in the parameter position of OWL objects and never in the position of a functor, i.e., a query with BGP ?CA(:ex:Person ex:Peter) (in Turtle: ex:Peter ?CA ex:Person) would be illegal since ?CA is mapped to the functor ClassAssertion (rdf:type in Turtle). This would have the advantage that, for example, queries for annotations where a variable binds to rdfs:label or rdfs:comment will have answers, whereas under the current restriction such answers are excluded. For an example, consider a query with BGP ex:Person ?ap ?av (in FSS AnnotationAssertion(ex:Person ?ap ?av)) that asks for annotation assertions for the class ex:Person where ?ap binds to an annotation property and ?av to an annotation value. Under the current restriction, answers that bind ?ap to rdfs:label or rdfs:comment are excluded.
  3. Instead of considering only those data values that are explicitly asserted (modulo sub-property inferences) (C5), one could also use a restriction similar to the one for RDF and RDFS and require that all bindings for data values must occur in the queried graph. Under the Direct Semantics this can cause unexpected results due to some non-local effects. Consider, for example, an ontology with a data property ex:dp containing only the axiom
    ClassAssertion(DataExactCardinality(1 ex:dp DatatypeRestriction(xsd:int xsd:minExclusive "5"^^xsd:int xsd:maxExclusive "7"^^xsd:int)) ex:Peter)
    in Turtle:
    ex:Peter a [
        a owl:Restriction ;
        owl:onProperty ex:dp ;
        owl:qualifiedCardinality "1"^^xsd:nonNegativeInteger ;
        owl:onDataRange [
            a rdfs:Datatype ;
            owl:onDatatype xsd:int ;
            owl:withRestrictions (
                [ xsd:minExclusive "5"^^xsd:int ]
                [ xsd:maxExclusive "7"^^xsd:int ]
            )
        ]
    ]
    This ontology entails that ex:Peter is related with the data property ex:dp to the integer value 6. The data value 6 does, however, not occur in the ontology. Consider the following query against the above ontology:
    SELECT ?s ?d WHERE { ?s ex:dp ?d }
    where the BGP is mapped to the following FSS element:
    DataPropertyAssertion(ex:dp ?s ?d)
    Under the current condition C5 as well as under the modified condition the query has an empty answer. Assume now, that the ontology is extended with the assertion:
    DataPropertyAssertion(ex:dp ex:Mary "6"^^xsd:int)
    in Turtle:
    ex:Mary ex:dp "6"^^xsd:int .
    Under the current restriction, the query has one answer:
    sd
    ex:Mary"6"^^xsd:int
    Under the modified condition, the query has two answers:
    sd
    ex:Peter"6"^^xsd:int
    ex:Mary"6"^^xsd:int
    Thus, adding an assertion that is not related to the assertion regarding ex:Peter, ex:Peter now also appears among the answers due to the sophisticated the datatype inferences that are supported by OWL 2. Apart from being much easier to compute, the current condition also avoids such non-local effects.

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.

6.3.1 OWL 2 DL

OWL 2 DL describes the largest subset of RDF graphs for which the OWL 2 Direct Semantics is defined. Systems that support OWL 2 DL can also handle ontologies that satisfy the restrictions of the OWL 2 EL and QL profiles because these profiles are even more restrictive. Endpoints that use the OWL 2 Direct Semantics entailment regime and that can handle all of OWL 2 DL but not RDF graphs outside of the OWL 2 DL fragment can use the URI http://www.w3.org/ns/owl-profile/DL to describe this in their service description.

6.3.2 The OWL 2 EL Profile

OWL 2 EL is particularly useful in applications employing ontologies that contain very large numbers of properties and/or classes. The profile captures the expressive power used by many ontologies and is a subset of OWL 2 DL for which the basic reasoning problems can be performed in time that is polynomial with respect to the size of the ontology. Endpoints that use the OWL 2 Direct Semantics entailment regime and that support only the OWL 2 EL profile can use the URI http://www.w3.org/ns/owl-profile/EL to describe this in their service description.

6.3.3 The OWL 2 QL Profile

OWL 2 QL is aimed at applications that use very large volumes of instance data, and where query answering is the most important reasoning task. In OWL 2 QL, conjunctive query answering can be implemented using conventional relational database systems. Using a suitable reasoning technique, sound and complete conjunctive query answering can be performed in LOGSPACE with respect to the size of the data (assertions). As in OWL 2 EL, polynomial time algorithms can be used to implement the ontology consistency and class expression subsumption reasoning problems. Endpoints that use the OWL 2 Direct Semantics entailment regime and that support only the OWL 2 QL profile can use the URI http://www.w3.org/ns/owl-profile/QL to describe this in their service description.

7 RIF Entailment

Editorial note14/10/2009
RIF Entailment is just a hook at the moment...

NameRIF
URIhttp://www.w3.org/ns/entailment/RIF
Legal GraphsTBD
Legal QueriesAny legal SPARQL query.
Illegal handlingIn case the query or the queried graph is illegal (syntax errors), the system MUST raise an error.
EntailmentTBD
InconsistencyTBD
Query AnswersTBD

8 Entailment Regimes and Data Sets (Informative)

Many RDF data stores hold multiple RDF graphs and applications can make queries that involve information from more than one graph. This section clarifies how entailment regimes behave in the presence of named graphs.

As defined in the SPARQL Query specification, a SPARQL query is executed against an RDF Dataset which represents a collection of graphs. An RDF Dataset comprises one graph, the default graph, which does not have a name, and zero or more named graphs, where each named graph is identified by an IRI. The graph that is used for matching a basic graph pattern is the active graph. Under an entailment regime E other than simple entailment, we do not only consider the triples that are in the graph, but also triples that are E-entailed by the graph. The entailed triples must, however, be E-entailed by the active graph and not by a merge of the triples in all graphs. This follows from conditions 1 and 3 of the conditions on extensions for basic graph matching.

For an example, we consider a data set with consists of an empty default graph, a named graph graphA with IRI http://example.org/a.rdf, and a named graph graphB with IRI http://example.org/b.rdf. The named graphs contain the following data:

http://example.org/a.rdf:

ex:p rdfs:domain ex:A .

http://example.org/b.rdf:

ex:x ex:p ex:y .

If we ask the following query under RDFS entailment

SELECT ?g WHERE { GRAPH ?g { ex:x a ?type } }

the answer sequence is empty because neither the default graph, nor the named graphs on their own entail a triple that would provide the required binding for ?type.

In order to evaluate a query over the merge of the triples in the named graphs, one can use several FROM clauses, which result in the creation of a fresh default graph for the query that contains a merge of the triples, e.g.,

SELECT ?t FROM <http://example.org/a.rdf> FROM <http://example.org/b.rdf> WHERE { ex:x a ?t } 

has the answer { (t, ex:A) }. One can not merge triples from several sources into a named graph (they will always be merged into a fresh default graph) and such an extension would require changes to the conditions for extensions of basic graph pattern matching in the existing SPARQL query language specification.

9 Entailment Regimes and Updates (Informative)

SPARQL 1.1 also describes an update language (see SPARQL 1.1/Update and SPARQL 1.1/HTTP RDF Update), which can be used to add, modify, or delete data in an RDF graph. Support for SPARQL 1.1/Update and SPARQL 1.1/HTTP RDF Update is optional. SPARQL endpoints that use an entailment regime other than simple entailment may support update queries, but the exact behavior of the system for such queries is not covered by this specification. SPARQL endpoints that use an entailment regime other than simple entailment and that do support update queries should describe the system behavior in the system's documentation.

A Related Issues

B References

B.1 Normative References

OWL 2 Specification
OWL 2 Web Ontology Language Structural Specification and Functional-Style Syntax, ed. Boris Motik, Peter F. Patel-Schneider, Bijan Parsia. W3C Recommendation 27 October 2009. (See http://www.w3.org/TR/owl2-syntax/.)
OWL 2 Mapping to RDF Graphs
OWL 2 Web Ontology Language Mapping to RDF Graphs, ed. Peter F. Patel-Schneider, Boris Motik. W3C Recommendation 27 October 2009. (See http://www.w3.org/TR/owl2-mapping-to-rdf/.)

B.2 Other References

SPARQL 1.1 Query
SPARQL 1.1 Query, ed. Steve Harris, Andy Seaborne. W3C Working Draft 2009. (See http://www.w3.org/TR/sparql11-query/.)
RDFSENTAILMENT
Herman J. ter Horst Completeness, decidability and complexity of entailment for RDF Schema and a semantic extension involving the OWL vocabulary. Journal of Web Semantics, 3(2-3):79-115, 2005. (See http://www.websemanticsjournal.org/papers/20050719/document5.pdf.)
TURTLE
Dave Beckett. Turtle - Terse RDF Triple Language. W3C Team Submission 14 January 2008. (See http://www.w3.org/TeamSubmission/turtle/.)

C CVS History

$Log: Overview.html,v $
Revision 1.1  2010/01/27 16:24:12  bertails
sparql

Revision 1.25  2010/01/26 18:02:01  bglimm
removed link for http://www.websemanticsjournal.org because the service is not available and that causes broken links during the link validation

Revision 1.24  2010/01/26 17:14:21  bglimm
back to SPARQL 1.0 links to not get broken fragment errors

Revision 1.23  2010/01/26 16:07:48  bglimm
fixed broken inks and fragments

Revision 1.22  2010/01/24 15:07:03  apollere2
Changed order of change summary

Revision 1.15  2010/01/23 02:03:14  bglimm
tried to improve HTML markup to pass the validator check

Revision 1.14  2010/01/23 02:01:27  bglimm
tried to improve HTML markup to pass the validator check

Revision 1.13  2010/01/23 01:55:13  bglimm
tried to improve HTML markup to pass the validator check

Revision 1.12  2010/01/23 01:48:00  bglimm
tried to improve HTML markup to pass the validator check

Revision 1.11  2010/01/22 14:59:52  apollere2
Regenerated from xmlspec. Date was wrong.

Revision 1.38  2010/01/22 14:50:03  apollere2
Generated first version of next WD from xsltproc.

Revision 1.37  2010/01/13 14:17:30  bglimm
fixed HTML mark-up and informative subsections of informative sections are no longer explicitly marked as informative

Revision 1.36  2010/01/13 12:19:13  bglimm
Changed the editorial note on inconsistencies to reflect that the conditions on extensions to BGP matching do not apply to inconsistent graphs.

Revision 1.35  2010/01/12 01:06:38  bglimm
rephrased a sentence in the higher order queries paragraph

Revision 1.34  2010/01/11 17:01:28  bglimm
implemented Axel's comments part 2 (mainly adding some editorial notes to explain alternative design choices for Direct Semantics)

Revision 1.33  2010/01/08 15:00:04  bglimm
made it clearer that update support is optional even under simple entailment

Revision 1.32  2010/01/07 17:53:28  bglimm
improved grammar in the updates section

Revision 1.31  2010/01/07 17:50:55  bglimm
added a section about behaviour with update queries

Revision 1.30  2010/01/07 16:44:12  bglimm
improved Turtle syntax for examples and consistent use of FSS and Turtle in the Direct Semantics section

Revision 1.29  2010/01/05 19:42:10  bglimm
added a heading for the change summary

Revision 1.28  2010/01/05 18:37:08  bglimm
Small changes suggested by Axel in his review.

Revision 1.27  2010/01/05 17:07:12  bglimm
restructured the Direct Semantics sections according to Ivan's suggestions and corrected minor typos and rephrasings as suggested in Ivan's review

Revision 1.26  2009/12/22 12:05:23  bglimm
changed RDF to RDFS in the definition of answers for RDFS entailment

Revision 1.25  2009/12/22 11:18:24  bglimm
spell-checked the document

Revision 1.24  2009/12/19 12:57:46  bglimm
Added profile sections for Direct Semantics that mention service descriptions

Revision 1.23  2009/12/18 12:42:37  bglimm
added CVS log command