--- a/rdf-mt/index.html Thu May 09 16:50:16 2013 -0400
+++ b/rdf-mt/index.html Fri May 10 00:11:56 2013 -0500
@@ -91,8 +91,7 @@
<section id='abstract'>
<p> This document describes a precise semantics for the Resource Description
Framework 1.1 [[RDF-PRIMER]] and RDF Schema [[RDF-SCHEMA]]. It defines a number of distinct entailment regimes and corresponding systems of inference rules. It is part of a suite of documents which comprise the full specification of RDF 1.1.</p>
-<p>This is a revision of the 2004 RDF Semantics specification for RDF
- [[RDF-MT]] and supersedes that document. </p> </section>
+ </section>
<section id='sotd'>
<p>This is a revision of the 2004 Semantics specification for RDF
@@ -105,8 +104,8 @@
<section>
<h2 id="introduction">Introduction</h2>
<p>
- This document defines a model-theoretic semantics for RDF graphs and the RDF and RDFS vocabularies, providing an exact formal specification of when truth is preserved by transformations of RDF, or operations which derive RDF content from other RDF. Readers who are unfamiliar with model theory can find a brief introduction to the basic ideas and terminology in <a>Appendix A</a>, and may find the informative section 13 useful. </p>
-<p>This specification is normative for RDF <a>formal</a> semantics. However, there are many aspects of RDF meaning which are not covered by this semantics, including social issues of how IRIs are assigned meanings in use, and how the referents of IRIs are related to Web content expressed in other media such as natural language texts. Accounts of such extended notions of meaning will go beyond this specification, but MUST NOT violate the conditions described here. </p>
+ This document defines a model-theoretic semantics for RDF graphs and the RDF and RDFS vocabularies, providing an exact formal specification of when truth is preserved by transformations of RDF, or operations which derive RDF content from other RDF. Readers who are unfamiliar with model theory can find a brief introduction to the basic ideas and terminology in <a>Appendix A</a>. </p>
+<p>This specification is normative for RDF semantics and the validity of inference processes. However, there are many aspects of RDF meaning which are not covered by this semantics, including social issues of how IRIs are assigned meanings in use, and how the referents of IRIs are related to Web content expressed in other media such as natural language texts. Accounts of such extended notions of meaning will go beyond this specification, but MUST NOT violate the conditions described here. </p>
</section>
<section>
@@ -116,7 +115,7 @@
<p>A particular such set of semantic assumptions is called a <dfn>semantic extension</dfn>. Each semantic extension defines an <dfn>entailment regime</dfn> of entailments which are valid under that extension. RDFS, described later in this document, is one such semantic extension. We will refer to an entailment regime by names such as <em>rdfs-entailment</em>, <em>D-entailment</em>, etc.. </p>
<p>Semantic extensions MAY impose special syntactic conditions or restrictions upon RDF graphs, such as requiring certain triples to be present, or prohibiting particular combinations of IRIs in triples, and MAY consider RDF graphs which do not conform to these conditions to be errors. For example, RDF statements of the form <br/>
-<code>:a rdfs:subClassOf owl:Thing .</code><br/>
+<code>ex:a rdfs:subClassOf owl:Thing .</code><br/>
are prohibited in the OWL-DL [[OWL2-SYNTAX]] semantic extension. In such cases, basic RDF operations such as taking a subset of triples, or merging RDF graphs, may cause syntax errors in parsers which recognize the extension conditions. None of the semantic extensions normatively defined in this document impose syntactic restrictions on RDF graphs.</p>
<p>All entailment regimes MUST be <a>monotonic</a> extensions of the simple entailment regime described in the next section, in the sense that if A simply entails B then A also entails B under any extended notion of entailment, provided of course that any syntactic conditions of the extension are also satisfied. Put another way, a semantic extension cannot "cancel" an entailment made by a weaker entailment regime, although it can treat the result as a syntax error.</p>
@@ -125,57 +124,45 @@
<section>
<h2 id="notation">Notation and terminology</h2>
-<p class="issue">This section needs some cleaning up. Some of the 2004 definitions may no longer be needed. <br/><br/> Maybe some of the material should be in Concepts. </p>
-
- <p>This document uses the terminology //list terms// defined in //Concepts// for describing RDF graph syntax.</p>
-<p>Throughout this document, precise semantic conditions will be set out in tables
- which state semantic conditions, tables containing true assertions and <a>valid</a> inference rules, and tables listing syntax. These tables, which
- are distinguished by background color, amount
- to a formal summary of the entire semantics.
-</p>
-<p>Throughout this document, the equality sign = indicates
- identity. The statement "A = B" means that there is one entity which both expressions "A" and "B" refer to. Angle brackets < x, y > are used to indicate an ordered pair
+ <p>This document uses the following terminology for describing RDF graph syntax, all as defined in the companion Concepts specification [[RDF11-CONCEPTS]]: <em><a class="externalDFN">RDF triple</a>, <a class="externalDFN">RDF graph</a>, <a class="externalDFN">subject</a>, <a class="externalDFN">predicate</a>, <a class="externalDFN">object</a>, <a class="externalDFN">RDF source</a>, <a class="externalDFN">node</a>, <a class="externalDFN">RDF term</a>, <a class="externalDFN">blank node</a>, <a class="externalDFN">literal</a>, <a class="externalDFN">isomorphic</a>.</em></p>
+
+<p>Throughout this document, the equality sign = indicates
+ identity. The statement "A = B" means that there is one entity to which both expressions "A" and "B" refer. Angle brackets < x, y > are used to indicate an ordered pair
of x and y. RDF graph syntax is indicated using the notational conventions of
the N-Triples syntax described
in the Turtle Working Draft [[TURTLE-TR]]
literal strings are enclosed within double quote marks and attached to a type IRI using a double-caret <code>^^</code>, language tags indicated
by the use of the <code>@</code> sign, and triples terminate with a 'code dot'
<code>.</code> . </p>
-<p>In stating general rules or conditions we will use the following conventions:<br/>
-sss or ttt indicates a Unicode character string; <br/>
-aaa or bbb indicates an IRI<br/>
-lll or mmm indicates a literal<br/>
-_:xxx or _:yyy indicates a blank node. <br/></p>
+<p>In stating general rules or conditions we use the following conventions:</p>
+<p>sss, ttt, etc. indicate a Unicode character string; <br/>
+aaa, bbb, etc. indicate an IRI<br/>
+lll, mmm, etc. indicate a literal<br/>
+_:xxx, _:yyy, etc. indicate a blank node <br/>
+xxx, yyy, etc. indicate any component of a triple.</p>
-<p>A <dfn>name</dfn> is any IRI or literal. A <dfn>vocabulary</dfn> is a set of names.
+<p class="issue">Should the following definitions be in Concepts rather than here?</p>
+
+<p>A <dfn>name</dfn> is any IRI or literal. Note that a typed literal contains
+ two <a>name</a>s: itself and its internal type
+ IRI. A <dfn>vocabulary</dfn> is a set of names.
</p>
-
-<p>An <a class="externalDFN">RDF
- graph</a>, or simply a <dfn>graph</dfn>, is a set of RDF triples.</p>
+<p>The <dfn>empty graph</dfn> is the empty set of triples. </p>
<p>A <dfn>subgraph</dfn> of an RDF graph is a subset
of the triples in the graph. A triple is identified with the singleton set
containing it, so that each triple in a graph is considered to be a subgraph.
A <dfn>proper subgraph</dfn> is a proper subset of the triples in the graph. </p>
-<p>A <dfn>ground</dfn> RDF graph is one with no blank
+<p>A <dfn>ground</dfn> RDF graph is one which contains no blank
nodes.</p>
-
-<p>A <dfn>name</dfn> is an IRI or a literal.
- Note that a typed literal comprises
- two <a>name</a>s: itself and its internal type
- IRI. </p>
-<p>A <dfn>vocabulary</dfn> is a set of <a>name</a>s. The vocabulary of a graph is
- the set of names which occur as the subject, predicate or object of any triple
- in the graph. IRIs which occur only inside typed literals
- are not required to be in the vocabulary of the graph.</p>
<p>Suppose that M is a functional mapping from a set of blank
nodes to some set of literals, blank nodes and IRIs. Any graph obtained
from a graph G by replacing some or all of the blank nodes N in G by M(N) is
- an <dfn id="definst">instance</dfn> of G. Any graph is an instance of itself,
+ an <dfn>instance</dfn> of G. Any graph is an instance of itself,
an instance of an instance of G is an instance of G,
and if H is an instance of G then every triple in H is an instance of at least one triple
in G.</p>
@@ -187,14 +174,8 @@
<p>A <dfn>proper instance</dfn> of a graph
is an <a>instance</a> in which a blank node has been replaced by a name, or two blank
nodes in the graph have been mapped into the same node in the instance. </p>
-<p >Any <a>instance</a> of a graph in which a blank node is mapped to a new blank node
- not in the original graph is an instance of the original and also has it as
- an instance, and this process can be iterated so that any 1:1 mapping between
- blank nodes defines an instance of a graph which has the original graph as an
- instance. Two such graphs, each an instance of the other but neither a proper
- instance, which differ only in the identity of their blank nodes, are considered
- to be <dfn>equivalent</dfn>. Equivalent graphs are mutual instances with an invertible instance
- mapping. As blank nodes have no particular identity beyond their location in a graph, we will often treat such equivalent graphs as identical.</p>
+<p><a class="external">Isomorphic</a> graphs are mutual instances with an invertible instance
+ mapping. As blank nodes have no particular identity beyond their location in a graph, we will treat such isomorphic graphs as identical.</p>
<p>
Graphs share blank nodes only if they are derived from graphs
@@ -203,28 +184,48 @@
of blank nodes between different RDF graphs. Simply downloading a
web document does not mean that the blank nodes in a resulting RDF
graph are the same as the blank nodes coming from other downloads of
-the same document.
+the same document or from the same source.
</p>
-<p>We will refer to this process of forming the union of graphs as <dfn>merging</dfn>, and to the union graph as the <dfn>merge</dfn> of the original graphs. A merge may be represented by a new document or datastructure, or may be treated as a conceptual entity when processing RDF.</p>
+<p>Forming the union of a set of graphs preserves the identity of blank nodes shared between the graphs. A related process, called <dfn>merging</dfn>, first changes any blank nodes shared between two or more graphs so that none of the graphs share any blank nodes, then forms the union. The result is called the <dfn>merge</dfn> of the graphs in the set. </p>
-<ul><li><p class="changenote"> The 2004 RDF 1.0 specification defined a process of 'standardizing apart' blank nodes to distinguish graph unions from graph merges. Standardizing apart blank node identifiers may still be needed at a concrete syntax level, but is no longer part of the underlying conceptual model of RDF. The earlier terminology is retained to avoid confusion, but now 'merging' simply means 'taking the union' at the graph syntax level. </p>
-</li></ul>
+<p>For example, given the three graphs</p>
+<p><code><ex:a> <ex:p> _:x .</code></p>
+<p>and</p>
+<p><code>_:x <ex:q> <ex:b> . </code></p>
+<p>and</p>
+<p><code><ex:c> <ex:p> _:x .<br/>
+_:x <ex:q> <ex:d> .</code></p>
+<p> their union is</p>
+<p><code><ex:a> <ex:p> _:x .<br/>
+_:x <ex:q> <ex:b> . <br/>
+<ex:c> <ex:p> _:x .<br/>
+_:x <ex:q> <ex:d> .</code></p>
+
+<p>but the merge is</p>
+
+<p><code><ex:a> <ex:p> _:x1 .<br/>
+_:x2 <ex:q> <ex:b> . <br/>
+<ex:c> <ex:p> _:x3 .<br/>
+_:x3 <ex:q> <ex:d> .</code></p>
+
+<p>where the occurrences of the blank node _:x have been "standardized apart" by replacing each with a new blank node which is distinct from the blank nodes in the other graphs in the set. The particular blank node identifiers used in a text describing the graph, as here, have no significance outside the text. </p>
+
+<p>The merge of a set of graphs is unique (up to isomorphism.) A union or merge may be represented by a new RDF source, or may be thought of as a conceptual entity when describing RDF processing. This document will often treat a set of graphs as being identical to a single graph comprising their union, without further comment. </p>
<p >An RDF graph is <dfn>lean</dfn> if it has no instance which is
- a proper subgraph of the graph. Non-lean graphs have internal redundancy
+ a proper subgraph of itself. Non-lean graphs have internal redundancy
and express the same content as their lean subgraphs. For example, the graph</p>
<p ><code><ex:a> <ex:p> _:x .<br/>
_:y <ex:p> _:x .</code></p>
<p >is not lean, but</p>
<p ><code><ex:a> <ex:p> _:x .<br/>
_:x <ex:p> _:x .</code></p>
-<p >is lean. </p>
+<p >is lean. Ground graphs are lean. </p>
-
-
+<p>We use the words <dfn>denotes</dfn> and <dfn>refers to</dfn> interchangeably as synonyms for the relationship between an expression (usually an IRI) and what it refers to in a given interpretation, itself called the <em>referent</em> or <em>denotation</em>. IRI meanings may also be determined by other constraints external to the RDF semantics; when we wish to refer to such an externally defined naming relationship, we will use the word <dfn>identify</dfn> and its cognates. For example, the fact that the IRI <code>http://www.w3.org/2001/XMLSchema#decimal</code> is treated as the name of a datatype described in the XML Schema document [XMLSCHEMA11-2] might be described by saying that the IRI <em>identifies</em> that datatype. If an IRI identifies something it may or may not refer to it in a given interpretation, depending on how the semantics is specified. For example, an IRI used as a graph name identifying a named graph in an <a class="external">RDF dataset</a> may refer to something different from the graph it identifies. </p>
</section>
@@ -258,10 +259,10 @@
set of pairs which identify the arguments for which the property is true,
that is, a binary relational extension.
</p>
-<p>The distinction between IR and IL will become significant below when the semantics of datatypes are defined. IL is allowed to be partial because some literals may fail to have a referent. However, IL is total onlanguage-tagged strings (but not on literals of type <code>xsd:string</code>). </p>
+<p>The distinction between IR and IL will become significant below when the semantics of datatypes are defined. IL is allowed to be partial because some literals may fail to have a referent. </p>
<ul><li><p class="technote">
-It is conventional to map a relation name to a relational extension directly. This however presumes that the vocabulary is segregated into relation names and individual names, and RDF makes no such assumption. Moreover, RDF allows an IRI to be used as a relation name applied to itself as an argument. Such self-application structures are used in RDFS, for example. The use of the IEXT mapping to distinguish the relation as an object from its relational extension accommodates both of these requirements. It also provides for a more intuitive notion of RDFS 'class' which can be distinguished from its set-theoretic extension.
+It is conventional to map a relation name to a relational extension directly. This however presumes that the vocabulary is segregated into relation names and individual names, and RDF makes no such assumption. Moreover, RDF allows an IRI to be used as a relation name applied to itself as an argument. Such self-application structures are used in RDFS, for example. The use of the IEXT mapping to distinguish the relation as an object from its relational extension accommodates both of these requirements. It also provides for a notion of RDFS 'class' which can be distinguished from its set-theoretic extension.
</p>
</li></ul>
@@ -299,18 +300,19 @@
</table>
-<p> If IL(E) is undefined for some literal E, then E has no semantic value, so any triple containing it will be false, so any graph containing that triple will also be false.</p>
-<p> The final condition implies that the empty graph (empty set of triples) is always true.</p>
+<p> If IL(E) is undefined for some literal E then E has no semantic value, so any triple containing it will be false, so any graph containing that triple will also be false.</p>
+<p> The final condition implies that the empty graph (the empty set of triples) is always true.</p>
<p>The sets IP and IR may overlap, indeed IP can be a subset of IR. Because of the domain conditions on IEXT, the denotation of the subject and object of any true triple will be in IR; so any IRI which occurs in a graph both as a predicate and as a subject or object will denote something in the intersection of IP and IR.</p>
+<p>Semantic extensions may impose further constraints upon interpretation mappings by requiring some IRIs to refer in particular ways. For example, D-interpretations, described below, require some IRIs, understood as identifying and referring to datatypes. to have a fixed interpretation. </p>
<h3 id="blank_nodes">Blank Nodes</h3>
-<p>Blank nodes are treated as simply indicating the existence of a thing, without using an IRI to identify any particular thing. They play a similar role to existentially quantified variables in a conventional logical notation. This is not the same as assuming that the blank node indicates an 'unknown' IRI.
+<p>Blank nodes are treated as simply indicating the existence of a thing, without using an IRI to identify any particular thing. This is not the same as assuming that the blank node indicates an 'unknown' IRI. Blank node identifiers play a similar role to existentially quantified variables in a conventional logical notation; they are local to the document in which they occur.
</p>
-<p> Suppose I is an interpretation and A is a mapping from a set of blank nodes to the universe IR of I. Define the mapping [I+A] to be I on names, and A on blank nodes on the set: [I+A](x)=I(x) when x is a name and [I+A](x)=A(x) when x is a blank node; and extend this mapping to triples and RDF graphs using the rules given above for ground graphs. </p>
+<p> Suppose I is an interpretation and A is a mapping from a set of blank nodes to the universe IR of I. Define the mapping [I+A] to be I on names, and A on blank nodes on the set: [I+A](x)=I(x) when x is a name and [I+A](x)=A(x) when x is a blank node; and extend this mapping to triples and RDF graphs using the rules given above for ground graphs. Then the semantic conditions for an RDF graph are:</p>
<div class="tabletitle">Semantic condition for blank nodes.</div>
<table border="1">
@@ -328,55 +330,80 @@
<p>Mappings from blank nodes to referents are not part of the definition of an interpretation, since the truth condition refers only to <em>some</em> such mapping.
Blank nodes themselves differ from other nodes in not being assigned
a denotation by an interpretation, reflecting the intuition that
-they have no 'global' meaning.
+they have no 'global' meaning. </p>
+<p>While a blank node may occur in more than one graph, the truth conditions refer only to its occurrences inside the graph whose truth is being determined. This affects the way that graphs can be validly combined, as described in later sections.
</p>
<h3 id="intuitions">Intuitive summary</h3>
<p>An RDF graph is true exactly when:</p>
-<p>1. the IRIs and literals in subject or object position in the graph all refer to things,</p><p>2. there is some way to interpret all the blank nodes in the graph as referring to things,</p><p>3. the IRIs in property position identify binary relationships,</p><p>4. and, under these interpretations, each triple S P O in the graph asserts that the thing referred to as S, and the thing referred to as O, do in fact stand in the relationship identified by P. </p>
+<p>1. the IRIs and literals in subject or object position in the graph all refer to things,</p><p>2. there is some way to interpret all the blank nodes in the graph as referring to things,</p><p>3. the IRIs in property position identify binary relationships,</p><p>4. and under these interpretations, each triple S P O in the graph asserts that the thing referred to as S, and the thing referred to as O, do in fact stand in the relationship referred to by P. </p>
-<p>All semantic extensions of any vocabulary or higher-level notation encoded in RDF MUST conform to these minimal truth conditions. Other semantic extensions may extend and add to these, but they MUST NOT over-ride or negate them. </p>
-
+<p>All semantic extensions of any vocabulary or higher-level notation encoded in RDF MUST conform to these minimal truth conditions. Other semantic extensions may extend and add to these, but they MUST NOT modify or negate them. For example, because interpretations are mappings which apply to IRIs, a semantic extension MUST NOT interpret different occurrences of a single IRI differently.</p>
</section>
<section id="simpleentailment"><h2>Simple Entailment</h2>
-<p class="issue">Should the 'explanatory' material in here be moved to the tutorial appendix? </p>
-<p>Following standard terminology, we say that I <dfn>satisfies</dfn> E when I(E)=true, and a set
+
+<p>Following standard terminology, we say that I <dfn>satisfies</dfn> E when I(E)=true, that E is <dfn>satisfiable</dfn> when an interpretation exists which satisfies it, (otherwise <dfn>inconsistent</dfn>), and that a set
S of RDF graphs <dfn>simply entails</dfn> a graph E when every interpretation
which satisfies every member of S also satisfies E. This means that it is always correct to infer E from S, even when one does not know what the names in the vocabulary actually mean. In later sections these notions will be adapted to other classes of interpretations, but throughout this section 'entailment' should be interpreted as meaning simple entailment.
</p>
<p><a id="defvalid">Any process which constructs a graph E from
- some other graph(s) S is said to be (simply) <dfn>valid</dfn> if S
+ some other graph(s) S is (simply) <dfn>valid</dfn> if S
simply entails E in every case, otherwise <dfn>invalid.</dfn></a></p>
-<p>The fact that an inference is valid should not be understood as meaning that the inference must be made, or that any process is obliged or required to make the inference; and similarly, the logical invalidity of some RDF transformation or process does not mean that the process is incorrect or prohibited. Nothing in this specification requires or prohibits any particular operations to be applied to RDF graphs. Entailment and validity are concerned solely with establishing the conditions on operations which guarantee the preservation of truth. While logically invalid processes, which do not follow valid entailments, are not prohibited, users should be aware that they may be at risk of introducing falsehoods and errors into otherwise correct RDF data. Nevertheless, particular uses of logically invalid processes may be justified and appropriate for data processing under circumstances where truth can be ensured by other means. </p>
-
-<p>Entailment refers only to the truth of RDF graphs, not to their suitability for any other purpose. It is possible for an RDF graph to be fitted for a given purpose and yet validly entail another graph which is not appropriate for the same purpose. An example is the RDF test cases manifest [[!RDF-TESTCASES]] which is provided as an RDF document for user convenience. This document lists examples of correct entailments by describing their antecedents and conclusions. Considered as an RDF graph, the manifest validly entails a subgraph which omits the antecedents, and would therefore be incorrect if used as a test case manifest. This is not a violation of the RDF semantic rules, but it shows that the property of <em> "being a correct RDF test case manifest"</em> is not preserved under RDF entailment, and therefore cannot be described as an RDF semantic extension. Such entailment-risky uses of RDF should be restricted to cases, as here, where it is obvious to all parties what the intended special restrictions on entailment are, in contrast with the more normal case of using RDF for the open publication of data on the Web.</p>
+<p>The fact that an inference is valid should not be understood as meaning that any RDF application is obliged or required to make the inference; and similarly, the logical invalidity of some RDF transformation or process does not mean that the process is incorrect or prohibited. Nothing in this specification requires or prohibits any particular operations on RDF graphs or sources. Entailment and validity are concerned solely with establishing the conditions on such operations which guarantee the preservation of truth. While logically invalid processes, which do not follow valid entailments, are not prohibited, users should be aware that they may be at risk of introducing falsehoods and errors into otherwise correct RDF data. Nevertheless, particular uses of logically invalid processes may be justified and appropriate for data processing under circumstances where truth can be ensured by other means. </p>
-<h3 id="basic_properties">Some basic properties of simple entailment. </h3>
-<p>The properties described here apply only to simple entailment, not to extended notions
- of entailment introduced in later sections. Proofs
- are given in <a>Appendix B</a>.</p>
+<p>Entailment refers only to the truth of RDF graphs, not to their suitability for any other purpose. It is possible for an RDF graph to be fitted for a given purpose and yet validly entail another graph which is not appropriate for the same purpose. An example is the RDF test cases manifest [[!RDF-TESTCASES]] which is provided as an RDF document for user convenience. This document lists examples of correct entailments by describing their antecedents and conclusions. Considered as an RDF graph, the manifest simply entails a subgraph which omits the antecedents, and would therefore be incorrect if used as a test case manifest. This is not a violation of the RDF semantic rules, but it shows that the property of <em> "being a correct RDF test case manifest"</em> is not preserved under RDF entailment, and therefore cannot be described as an RDF semantic extension. Such entailment-risky uses of RDF should be restricted to cases, as here, where it is obvious to all parties what the intended special restrictions on entailment are, in contrast with the more normal case of using RDF for the open publication of data on the Web.</p>
-<p>Simple entailment can be recognized by relatively simple syntactic comparisons. The two basic forms of simply valid inference in RDF are, in logical terms, the inference from <code>(P and Q)</code> to <code>P</code>, and the inference from <code>foo(baz)</code> to <code>(exists (x) foo(x) ) </code>. The first corresponds to taking a subgraph of a graph, the second to replacing an IRI or literal with a blank node.</p>
+</section>
-<p><strong>Empty Graph Lemma.</strong> The empty set of triples is entailed by
+<section>
+
+<h3>Properties of simple entailment. </h3>
+<p>The properties described here apply only to simple entailment, not to extended notions of entailment introduced in later sections. </p>
+
+
+<p>Simple entailment can be recognized by relatively simple syntactic comparisons. The two basic forms of simply valid inference in RDF are, in logical terms, the inference from <code>(P and Q)</code> to <code>P</code>, and the inference from <code>foo(baz)</code> to <code>(exists (x) foo(x) ) </code>. The first corresponds to taking a subgraph of a graph, the second to replacing an IRI or literal with a blank node. More precisely, the following <dfn>interpolation</dfn> <strong>lemma</strong> </p>
+ <p>==
+ S simply entails a graph E if and only if a subgraph of S is an instance of E. </a>
+<!-- <a href="#interplemmaprf" class="termref">[Proof]</a> -->
+</p>
+<p> completely characterizes simple entailment in syntactic
+ terms. To tell whether a set of RDF graphs simply entails another, check that
+ there is some instance of the entailed graph which is a subset of the union
+ of the original set of graphs. </p>
+<p>This is clearly decidable, but it is also complex in general, since one can encode the NP-hard subgraph problem (detecting whether one mathematical graph is a subgraph of another) as detecting simple entailment between RDF graphs. ([[Refer to Jeremy Carroll.]]) This uses graphs containing many blank nodes, which are unlikely to occur in practice. The complexity of checking simple entailment is reduced by having fewer blank nodes in the conclusion E. When E is a <a>ground</a> graph, it is simply a matter of checking the subset relationship on sets of triples.</p>
+<p><a>Interpolation</a> has a number of direct consequences, for example:</p>
+
+<p>== The <a>empty graph</a> is entailed by
any graph, and does not entail any graph except itself.
<!-- <a href="#emptygraphlemmaprf" class="termref">[Proof]</a> -->
</p>
-<p><a id="subglem"><strong>Subgraph Lemma.</strong></a> A graph
- entails all its subgraphs.
-<!-- <a href="#defsubg" class="termref"> subgraphs</a>. -->
+<p> == A graph entails all its subgraphs.
<!-- <a href="#subglemprf" class="termref">[Proof]</a> -->
</p>
-<p><a id="instlem"><strong>Instance Lemma.</strong></a> A graph
- is entailed by any of its <a
- href="#definst" class="termref">instances</a>.
+<p>== A graph
+ is entailed by any of its <a>instance</a>s.
<!-- <a href="#instlemprf" class="termref"> [Proof]</a> -->
</p>
+<p>== If
+ E is a <a>lean</a> graph and E' is a <a>proper instance</a> of E, then E does
+ not simply entail E'.
+</p>
+
+<p>== If S is a subgraph of S' and S entails E, then S' entails E.
+<!-- <a href="#monotonicitylemmaprf" class="termref"> [Proof]</a> -->
+</p>
+<p>==
+ If S entails a finite graph E, then some finite subset S' of S entails E.
+<!-- <a href="#compactlemmaprf" class="termref"> [Proof]</a> -->
+</p>
+<p>
+This property is often called <em>compactness</em>. RDF is compact. As RDF graphs can be infinite, this is sometimes important.</p>
+<p>== If E contains an IRI which does not occur anywhere in S, then S does not entail E.</p>
<p>Obviously, the union of a set of graphs entails every member of the set, since they are all subgraphs of the union. However, if two or more graphs in the set share a blank node. then the set may fail to entail the union. For example, consider the graphs</p>
<p>
@@ -384,74 +411,36 @@
<p>and</p>
<p>
<code>:b :p _:x .</code></p>
-<p>Both graphs can be satisfied by an interpretation which does not satisfy their union, e.g. one with <br/>IEXT(I(<code>:p</code>)) = {< I(<code>:a</code>),I(<code>:a</code>) >, < I(<code>:b</code>),I(<code>:b</code>) > }. This is because the mapping <code>_:x</code>/I(<code>:a</code>) works for the first graph, and the mapping <code>_:x</code>/I(<code>:b</code>) for the second graph, but there is no mapping which works for the combination. Neither graph is obliged to consider the full set of constraints on the blank node that are represented by their union. </p>
-
-<p>Say that a set S of graphs is <dfn>segregated</dfn> when no two graphs in the set share a blank node.</p>
+<p>Both graphs can be satisfied by an interpretation which does not satisfy their union, e.g. one with <br/>IEXT(I(<code>:p</code>)) = {< I(<code>:a</code>),I(<code>:a</code>) >, < I(<code>:b</code>),I(<code>:b</code>) > }. This is because the mapping <code>_:x</code>/I(<code>:a</code>) works for the first graph, and the mapping <code>_:x</code>/I(<code>:b</code>) for the second graph, but there is no mapping which makes the combination true. Neither graph, taken alone as a single graph, is obliged to consider the full set of constraints on the blank node that are represented by their union. </p>
+<p>Say that a set of graphs is <dfn>segregated</dfn> when no two graphs in the set share a blank node. Then:</p>
-<p><a id="mergelem"><strong>Merging lemma.</strong></a> The union
- of a segregated set S of RDF graphs is entailed by S, and entails every member of S.
-<!-- <a href="#mergelemprf" class="termref">[Proof]</a> -->
+<p>== the union
+ of a <a>segregated</a> set of RDF graphs is entailed by the set, and entails every member of the set.
+
+</p>
+ <p>This means that a <a>segregated</a> set of graphs can be treated as equivalent to its
+ union, a single graph. </p>
+
+<p>Creating a <a>merge</a> can be described as first modifying the set to ensure that it is <a>segregated</a>, then creating the union. Since a blank node replacement operation does not change the truth conditions of any single graph, </p>
+<p>== the merge of any set of graphs entails and is entailed by the set. </p>
+<p>However, when the graphs share blank nodes, the merge loses information compared to the union. In general, when two graphs share blank nodes they should usually be treated as parts of a single RDF graph.</p>
+
+</section>
+
+<section><h2 id="skolemization">Skolemization</h2>
+<p>Skolemization is a transformation on RDF graphs which eliminates blank nodes by replacing them with "new" IRIs, which means IRIs which are coined for this purpose and are therefore guaranteed to not occur in any other RDF graph (at the time of creation). See [[RDF11-CONCEPTS]] for a fuller discussion. </p>
+<p> Suppose G is a graph containing blank nodes and sk is a skolemization mapping on the blank nodes in G, so that sk(G) is a skolemization of G. Then the semantic relationship between them can be summarized as follows. </p>
+
+<p>== sk(G) simply entails G (since sk(G) is an instance of G.)</p>
+<p>== G does not entail sk(G) (since sk(G) contains IRIs not in G.) </p>
+<p>== For any graph H, if sk(G) entails H then there is a graph H' such that G entails H' and H=sk(H') . </p>
+<p>== For any graph H which does not contain any of the "new" IRIs introduced into sk(G), sk(G) simply entails H if and only if G simply entails H.
</p>
-
-
- <p>This means that a segregated set of graphs can be treated as <a
- href="#glossEquivalent" class="termref">equivalent</a> to its
- merge, a single graph, as far as the <a
- href="#glossModeltheory" class="termref">model theory</a> is
- concerned. In general, we will not usually bother to distinguish between a set of graphs and the single graph formed by taking their union. </p>
- <p>The main result for simple entailment is:</p>
-<p><a id="interplemma"><strong>Interpolation Lemma.</strong>
- S entails a graph E if and only if a subgraph of S is an instance of E. </a>
-<!-- <a href="#interplemmaprf" class="termref">[Proof]</a> -->
-</p>
-<p>The interpolation lemma completely characterizes simple entailment in syntactic
- terms. To tell whether a set of RDF graphs simply entails another, check that
- there is some instance of the entailed graph which is a subset of the merge
- of the original set of graphs. </p>
-<p>This is clearly decidable, but it is also theoretically very hard in general, since one can encode the NP-hard subgraph problem (detecting whether one mathematical graph is a subgraph of another) as detecting simple entailment between RDF graphs. (///Refer to Jeremy Carroll.///) </p>
+<p>The second property means that a graph is not logically <a>equivalent</a> to its skolemization. Nevertheless, they are in a strong sense almost interchangeable, as shown the next two properties. The third property means that even when conclusions are drawn from the skolemized graph which do contain the new vocabulary, these will exactly mirror what could have been derived from the original graph with the original blank nodes in place. The replacement of blank nodes by IRIs does not effectively alter what can be validly derived from the graph, other than by giving new names to what were formerly anonymous entities. The fourth property, which is a consequence of the third, clearly shows that in some sense a skolemization of G can "stand in for" G as far as entailments are concerned. Using sk(G) instead of G will not affect any entailments which do not involve the new skolem vocabulary. </p>
-<p><a id="Anonlem1"><strong>Anonymity lemma.</strong></a> Suppose
- E is a <a>lean</a> graph and E' is a proper instance of E. Then E does
- not entail E'.
-<!--
-<a href="#Anonlem1prf" class="termref">[Proof]</a>
--->
-</p>
-
-<p><strong><a id="monotonicitylemma"></a>Monotonicity
- Lemma</strong>. Suppose S is a subgraph of S' and S entails E. Then S' entails E.
-<!-- <a href="#monotonicitylemmaprf" class="termref"> [Proof]</a> -->
-</p>
-<p><strong><a id="compactlemma"></a>Compactness Lemma</strong>.
- If S entails E and E is a finite graph, then some finite subset S' of S entails E.
-<!-- <a href="#compactlemmaprf" class="termref"> [Proof]</a> -->
-</p>
-</section>
-
-
-<section><h2 id="skolemization">Skolemization</h2>
-<p>Skolemization is a transformation on RDF graphs which eliminates blank nodes by replacing them with "new" IRIs, which means IRIs which are coined for this purpose and are therefore guaranteed to not occur in any other RDF graph (at the time of creation). See ///Concepts#/// for a fuller discussion. </p>
-<p> Suppose G is a graph containing blank nodes and sk is a skolemization mapping on the blank nodes in G, so that sk(G) is a skolemization of G. Then the semantic relationship between them can be summarized as follows. </p>
-
-<p>1. sk(G) simply entails G (by the <a href="#instlem" class="termref">instance lemma</a>, since sk(G) is an instance of G)</p>
-<p>2. G does not entail sk(G).
-<!-- <a href="#skolemizeNentaillemmaprf" class="termref"> [Proof]</a> -->
-</p>
-<p>3. For any graph H, if sk(G) entails H then there is a graph H' such that G entails H' and H=sk(H') .
-<!-- <a href="#skolemizeMainlemmaprf" class="termref"> [Proof]</a> -->
-</p>
-<p>4. For any graph H which does not contain any of the "new" IRIs introduced into sk(G), sk(G) simply entails H if and only if G simply entails H.
-<!-- <a href="#skolemizlemmaprf" class="termref"> [Proof]</a> -->
-</p>
-
-<p>The second property means that a graph is not equivalent to its skolemization, so we cannot simply identify them. Nevertheless, they are in a strong sense almost interchangeable, as the next two properties attest. The third property means that even when conclusions are drawn from the skolemized graph which do contain the new vocabulary, these will exactly mirror what could have been derived from the original graph with the original blank nodes in place. The replacement of blank nodes by IRIs does not effectively alter what can be validly derived from the graph, other than by giving new names to what were formerly anonymous entities. The fourth property, which is a consequence of the third, clearly shows that in some sense a skolemization of G can "stand in for" G as far as entailments are concerned. Using sk(G) instead of G will not affect any entailments which do not involve the new skolem vocabulary. </p>
-
-<p>Skolemization means that it is possible to use RDF without using blank nodes without losing any real expressivity. Opinions differ on the merits of this strategy.</p>
-
-<ul><li><p class=technote>The more general notion of skolemization involving Skolem functions is not used in RDF as there are no universal quantifiers.</p>
-</li></ul>
+<p>Skolemization means that it is possible to use RDF without blank nodes without losing any real expressivity. Opinions differ on the merits of this strategy.</p>
</section>
@@ -460,16 +449,16 @@
</li></ul>
<p>RDF literals and datatypes are fully described in [[!RDF11-CONCEPTS]]. In summary: RDF literals are either language-tagged strings, or datatyped literals which
-combine a string and an IRI identifying a datatype. A datatype is understood to define a partial mapping, called the <dfn>lexical-to-value mapping</dfn>, from character strings to values, and the literal refers to the value obtained by applying this mapping to the character string. If the mapping gives no value for the literal string, then the literal has no referent. The <dfn>value space</dfn> of a datatype is the range of the <a>lexical-to-value mapping</a>. Every literal with that type either refers to a value in the value space, or fails to refer at all. An <dfn>ill-typed</dfn> literal is one whose datatype IRI is recognized, but whose character string is not in the domain of the datatype lexical-to-value mapping. Datatypes are indicated by IRIs.
-</p>
-
-<p> Interpretations will vary according to which IRIs they recognize as denoting datatypes. We describe this using a parameter D on interpretations. where D is a set of IRIs that constitute the recognized datatype IRIs. IRIs listed in <a href="http://www.w3.org/TR/2013/WD-rdf11-concepts-20130115/#xsd-datatypes">///Concepts Section 5///</a> MUST be interpreted as described there, and the IRI <code>rdf:plainLiteral</code> MUST be interpreted to refer to the datatype defined in [[!RDF-PLAINLITERAL]]. When other datatypes are used, the mapping between a recognized IRI and the datatype it refers to MUST be specified unambiguously, and be fixed during all RDF transformations or manipulations.</p>
+combine a string and an IRI identifying a datatype. A datatype is understood to define a partial mapping, called the <dfn>lexical-to-value mapping</dfn>, from character strings to values, and the literal refers to (denotes) the value obtained by applying this mapping to the character string. If the mapping gives no value for the literal string, then the literal has no referent. The <dfn>value space</dfn> of a datatype is the range of the <a>lexical-to-value mapping</a>. Every literal with that type either refers to a value in the value space of the type, or fails to refer at all. An <dfn>ill-typed</dfn> literal is one whose datatype IRI is recognized, but whose character string is not in the domain of the datatype lexical-to-value mapping. </p>
-<p>Language-tagged strings are an exceptional case which are given a special treatment. The IRI <code>rdf:langString</code> is classified as a datatype IRI, and interpreted to refer to a datatype, even though no L2V mapping is defined for it. The value space of <code>rdf:langString</code> is the set of all pairs of a string with a language tag. The semantics of literals with this as their type are given below. (If datatype L2V mappings were defined on pairs of lexical values rather than strings, then the L2V mapping for <code>rdf:langString</code> would be the identity function on pairs of the form < unicode string, language tag >. But as they are not, we simply list this as a special case.)</p>
+<p> Datatypes are identified by IRIs. Interpretations will vary according to which IRIs they recognize as denoting datatypes. We describe this using a parameter D on interpretations. where D is the set of recognized datatype IRIs. </p>
-<p class="issue">This will require alignment with Concepts. rdf:langString may have an L2V mapping which is ignored by the semantics. Concepts currently states that it is not a datatype even though the IRI is a datatype IRI. </p>
+<p> RDF processors are not required to recognize any datatype IRIs other than <code>rdf:langString</code> and <code>xsd:string</code>, but when IRIs listed in Section 5 of [[!RDF11-CONCEPTS]] are recognized, they MUST be interpreted as described there, and when the IRI <code>rdf:plainLiteral</code> is recognized, it MUST be interpreted to refer to the datatype defined in [[!RDF-PLAINLITERAL]]. RDF processors MAY recognize other datatype IRIs, but when other datatype IRIs are recognized, the mapping between a recognized IRI and the datatype it refers to MUST be specified unambiguously, and MUST be fixed during all RDF transformations or manipulations.</p>
-<p>RDF literal syntax allows any IRI to be used in a typed literal, even when it does not identify a datatype. Literals with an "unknown" datatype IRI which is not in the set of recognized datatypes, are treated like IRI names and assumed to denote some thing in the universe IR. </p>
+<p>Language-tagged strings are an exceptional case which are given a special treatment. The IRI <code>rdf:langString</code> is classified as a datatype IRI, and interpreted to refer to a datatype, even though no L2V mapping is defined for it. The value space of <code>rdf:langString</code> is the set of all pairs of a string with a language tag. The semantics of literals with this as their type are given below. </p>
+
+<p>RDF literal syntax allows any IRI to be used in a typed literal, even when it is not recognized as referring to a datatype. Literals with such an "unknown" datatype IRI, which is not in the set of recognized datatypes, MUST NOT be classified as errors, although RDF applications MAY issue a warning. They SHOULD be treated like IRI names and assumed to denote some thing in the universe IR. RDF processors which fail to recognize a datatype IRI will not be able to detect some entailments which are visible to one which does. For example, the fact that </p><p><code>ex:a ex:p "20.0000"^^xsd:decimal .</code></p><p>entails </p><p><code>ex:a ex:p "20.0"^^xsd:decimal .</code></p><p>will not be visible to a processor which does not recognize the datatype URI <code>xsd:decimal</code>.</p>
+
</section>
@@ -484,11 +473,16 @@
</tbody></table>
+
<p>If the literal is ill-typed then the L2V mapping has no value, and so the literal cannot denote anything. In this case, any triple containing the literal must be false. Thus, any triple, and hence any graph, containing an ill-typed literal will be D-inconsistent, i.e. false in every D-interpretation. This applies only to datatype IRIs in D; literals with "unknown" datatypes are not ill-typed and do not produce a D-inconsistency. </p>
+<p>The built-in RDF datatypes <code>rdf:langString</code> and <code>xsd:string</code> have no ill-typed literals. Any literal with these types which is syntactically legal in RDF will denote a value in every RDF interpretation. </p>
+<p>It follows from the definitions that an inconsistent graph entails every graph. This is called the principle of '<a href="http://en.wikipedia.org/wiki/Principle_of_explosion">ex falso quodlibet</a>'.</p>
+
+
<ul><li><p class="changenote"> In the 2004 RDF 1.0 specification, ill-typed literals were required to denote a value in IR, and D-inconsistency could only be recognized by using the RDFS semantics. </p>
-<p></p>
+
</li></ul>
<h3 id="D_entailment">Datatype entailment</h3>
@@ -497,20 +491,29 @@
<p> Unlike the case with simple interpretations, it is possible for a graph to have no satisfying D-interpretations, i.e. to be <dfn>D-unsatisfiable</dfn>. A D-unsatisfiable graph D-entails any graph. </p>
-<p>In all of this language, 'D' is being used as a parameter to represent some set of datatype IRIs, and different D sets will yield different notions of satisfiability and entailment. The more datatypes are recognized, the stronger is the entailment, so that if D ⊂ E and S E-entails G then S must D-entail G. Simple entailment is { }-entailment, i.e. D-entailment when D is the empty set. If S D-entails G then S simply entails G, but not the reverse. </p>
+<p>In all of this language, 'D' is being used as a parameter to represent some set of datatype IRIs, and different D sets will yield different notions of satisfiability and entailment. The more datatypes are recognized, the stronger is the entailment, so that if D ⊂ E and S E-entails G then S must D-entail G. Simple entailment is { }-entailment, i.e. D-entailment when D is the empty set, so if S D-entails G then S simply entails G. </p>
-<p>Several of the basic properties of simple entailment are also true for D-entailment, but the <a>interpolation lemma</a> is not true for <a>D-entailment</a>, since D-entailments
-can hold because of particular properties of the lexical-to-value mappings of the recognized datatypes. For example, if D contains <code>xsd:integer</code> then </p>
-<p><code>aaa ppp "00025"^^xsd:integer .</code></p>
+
+<section> <h4>Patterns of Datatype entailment</h4>
+<p>Unlike simple entailment, it is not possible to give a single syntactic criterion to recognize all D-entailments, which
+can hold because of particular properties of the lexical-to-value mappings of the recognized datatypes. For example, if D contains <code>xsd:real</code> then </p>
+
+<p><code>ex:a ex:p "25.0"^^xsd:decimal .</code></p>
<p>D-entails</p>
-<p><code>aaa ppp "25"^^xsd:integer .</code>
+<p><code>ex:a ex:p"25"^^xsd:decimal .</code>
</p>
-<p>
-<p>Ill-typed literals are the only form of simple D-contradiction, but datatypes can give rise to a variety of other contradictions when combined with the <a>RDFS vocabulary</a>, defined later.</p>
+<p>In general, any triple containing a literal with a recognized datatype IRI D-entails a similar literal when the lexical strings of the literals map to the same value under the lexical-to-value map of the datatype. If two different datatypes in D map lexical strings to a common value, then a triple containing a literal typed with one datatype may D-entail a similar triple containing a literal typed with a different datatype. For example, <code>"25"^^xsd:integer</code> and <code>"25.0"^^xsd:decimal</code> have the same value, so the above also D-entails</p>
+
+<p><code>ex:a ex:p "25"^^xsd:integer .</code></p>
+
+<p>when D also contains <code>xsd:integer</code>.
+
+<p>Ill-typed literals are the only form of simple D-contradiction, but datatypes can give rise to a variety of other contradictions when combined with the RDFS vocabulary, defined later.</p>
+</section>
</section>
<section><h2 id="rdf_d_interpretations">RDF-D Interpretations and RDF entailment</h2>
@@ -555,40 +558,103 @@
<p>No other semantic constraints are imposed upon <a>rdf-D-interpretation</a>s, so RDF imposes no particular normative meanings on the rest of the RDF vocabulary. Some consequences of this are discussed in <a>Appendix C</a></p>
-<p id="rdfinterpdef">An <em>rdf-interpretation</em>, or <em>RDF interpretation</em>, is an rdf-{<code>rdf:langString</code>, <code>xsd:string</code> }-interpretation, i.e. an rdf-D-Interpretation with a minimal set D. The datatypes <code>rdf:langString</code> and <code>xsd:string</code> MUST be recognized by all RDF interpretations. </p><p>The RDF built-in datatypes <code>rdf:XMLLiteral</code> and <code>rdf:HTML</code> are defined in [[!RDF11-CONCEPTS]]. RDF interpretations are not required to recognize these datatypes. </p>
+<p id="rdfinterpdef">An <em>rdf-interpretation</em>, or <em>RDF interpretation</em>, is an rdf-{<code>rdf:langString</code>, <code>xsd:string</code> }-interpretation, i.e. an rdf-D-Interpretation with a minimal set D. The datatype IRIs <code>rdf:langString</code> and <code>xsd:string</code> MUST be recognized by all RDF-D interpretations. </p>
+
+<p>Two datatypes in the rdf: namespace <code>rdf:XMLLiteral</code> and <code>rdf:HTML</code> are defined in [[!RDF11-CONCEPTS]]. RDF-D interpretations MAY fail to recognize these datatypes. </p>
+</section>
+<section>
<h3><a id="rdf_entail"></a>RDF entailment</h3>
<p>S <i>rdf-D-entails</i> E when every rdf-D-interpretation which satisfies every
member of S also satisfies E. </p>
-<p>The lemmas for <a href="#simpleentailment">simple entailment</a> do not all apply to rdf-D-entailment:
- for example, all the rdf axioms are true in every <a href="#rdfinterpdef" class="termref">rdf-interpretation</a>, so are rdf-D-entailed by the empty graph,
- contradicting the <a href="#interplemma" class="termref">interpolation lemma</a> for rdf-D-entailment. Section //// gives rules that can be used to detect RDF entailment between RDF graphs. </p>
+<p>The properties of <a>simple entailment</a> described earlier do not all apply to rdf-D-entailment. For example, all the rdf axioms are true in every <a">rdf-interpretation</a>, so are rdf-D-entailed by the empty graph,
+ contradicting <a>interpolation</a> for rdf-D-entailment. </p>
-<p> The last semantic condition in the above table gives entailments of this form for recognized datatypes: </p>
-<p><code>aaa ppp "123"^^xsd:integer .</code></p>
+<section><h4>Patterns of RDF-D entailment</h4>
+<p> The last semantic condition in the above table gives the following entailment pattern for recognized datatype IRIs: </p>
+
+<div class="tabletitle">RDF-D entailment pattern.</div>
+<table border="1" >
+ <tbody>
+ <tr>
+ <th > </th>
+ <th ><strong>if S contains</strong></th>
+ <th ><strong>then S RDF-D-entails</strong></th>
+ </tr>
+ <tr >
+ <td>rdfD1</td>
+ <td> xxx aaa <code>"</code>sss<code>"^^</code>ddd <code>.</code> <br/>
+ for ddd in D</td>
+ <td>xxx aaa _:nnn <code>.</code><br/>
+_:nnn <code>rdf:type</code> ddd <code>.</code></td>
+ </tr>
+
+ </tbody>
+</table>
+<p>Note, this is valid even when the literal is ill-typed, since a contradiction entails any triple.</p>
+
+<p>For example,</p>
+<p> <code>ex:a ex:p "123"^^xsd:integer .</code></p>
<p>rdf-{<code>xsd:integer</code>}-entails</p>
-<code>aaa ppp _:x . <br/> _:x rdf:type xsd:integer .</code>
+<code>ex:a ex:p _:x . <br/>
+ _:x rdf:type xsd:integer . </code></p>
+
+<p>In addition, the first RDF semantic condition justifies the following entailment pattern:</p>
+
+<table border="1" >
+ <tbody>
+ <tr>
+ <th > </th>
+ <th ><strong>if S contains</strong></th>
+ <th ><strong>then S RDF-D-entails</strong></th>
+ </tr>
+
+ <tr>
+ <td>rdfD2</td>
+ <td>xxx aaa yyy <code>.</code></td>
+ <td>aaa <code>rdf:type rdf:Property .</code> </td>
+ </tr>
+
+
+ </tbody>
+</table>
+
+
+<p>So that the above example also rdf-{<code>xsd:integer</code>}-entails</p><p><code>ex:p rdf:type rdf:Property .</code></p>
+
+
+<p>Some datatypes support idiosyncratic RDF-D-entailment patterns which do not hold for other datatypes. For example, </p>
+
+<p><code> ex:a ex:p "true"^^xsd:boolean . <br/>
+ex:a ex:p "false"^^xsd:boolean .<br/>
+ex:v rdf:type xsd:boolean .</code></p>
+
+together rdf-{<code>xsd:boolean</code>}-entail</p>
+
+<p><code>ex:a ex:p ex:v .</code></p>
</section>
-<section><h2 id="rdfs_interpretaitons">RDFS Interpretations and RDFS entailment</h2>
+</section>
+
+<section><h2>RDFS Interpretations and RDFS entailment</h2>
<p>RDF Schema [[RDF-SCHEMA]]
- extends RDF to a larger <a id="defRDFSV"></a>vocabulary
+ extends RDF to a larger vocabulary
with more complex semantic constraints:</p>
- <div class="c1">
+ <div >
<table border="1">
<tbody>
<tr>
- <td class="othertable"><strong>RDFS vocabulary</strong></td>
+ <td ><strong>RDFS vocabulary</strong></td>
</tr>
<tr>
- <td class="othertable"><code>rdfs:domain rdfs:range rdfs:Resource rdfs:Literal
+ <td ><code>rdfs:domain rdfs:range rdfs:Resource rdfs:Literal
rdfs:Datatype rdfs:Class rdfs:subClassOf rdfs:subPropertyOf
rdfs:member rdfs:Container rdfs:ContainerMembershipProperty
rdfs:comment rdfs:seeAlso rdfs:isDefinedBy
@@ -618,7 +684,6 @@
<p><a id="rdfsinterpdef"></a> An <i>rdfs-D-interpretation</i> is an <a href="#rdfinterpdef" class="termref">rdf-D-interpretation</a> I
which satisfies the semantic conditions in the following table, and satisfies all the triples in the subsequent table of <em>RDFS axiomatic triples</em>. As before, an <em>rdfs-interpretation</em>, or <em>RDFS interpretation</em>, is an rdfs-D-interpretation with D= {<code>xsd:string</code>, <code>rdf:langString</code> }.</p>
-<p class="issue">This table has redundancies. I am inclined to leave them alone, as it takes quite a lot of thought to figure out some of the consequences when we only give non-redundant conditions. </p>
<div class="tabletitle">RDFS semantic conditions.</div>
<table border="1">
<tr>
@@ -702,8 +767,7 @@
rdfs:domain rdfs:domain rdf:Property .<br/>
rdfs:range rdfs:domain rdf:Property .<br/>
rdfs:subPropertyOf rdfs:domain rdf:Property .<br/>
- <a id="axtripleforproof1"></a>rdfs:subClassOf rdfs:domain
- rdfs:Class .<br/>
+ rdfs:subClassOf rdfs:domain rdfs:Class .<br/>
rdf:subject rdfs:domain rdf:Statement .<br/>
rdf:predicate rdfs:domain rdf:Statement .<br/>
rdf:object rdfs:domain rdf:Statement .<br/>
@@ -720,8 +784,7 @@
rdfs:domain rdfs:range rdfs:Class .<br/>
rdfs:range rdfs:range rdfs:Class .<br/>
rdfs:subPropertyOf rdfs:range rdf:Property .<br/>
- <a id="axtripleforproof2"></a>rdfs:subClassOf rdfs:range
- rdfs:Class .<br/>
+ rdfs:subClassOf rdfs:range rdfs:Class .<br/>
rdf:subject rdfs:range rdfs:Resource .<br/>
rdf:predicate rdfs:range rdfs:Resource .<br/>
rdf:object rdfs:range rdfs:Resource .<br/>
@@ -758,14 +821,15 @@
<ul><li><p class="changenote">In the 2004 RDF 1.0 semantics, LV was defined as part of a simple interpretation structure, and the definition given here was a constraint. </p>
</li></ul>
-<p>Since I is an <a href="#rdfinterpdef" class="termref">rdf-interpretation</a>, the first condition implies that IP
+<p>Since I is an rdf-interpretation, the first condition implies that IP
= ICEXT(I(<code>rdf:Property</code>)).</p>
- <p>The semantic conditions on rdf-D-interpretations, together with the RDFS conditions on ICEXT, mean that every recognized datatype can be treated as an RDFS class whose extension is the value space of the datatype, and every literal with that datatype either fails to refer (if the literal is ill-typed) or else refers to a value in that class.</p>
-<p>These axioms and conditions have some redundancy. For example, all but one
+ <p>The semantic conditions on rdf-D-interpretations, together with the RDFS conditions on ICEXT, mean that every recognized datatype can be treated as a class whose extension is the value space of the datatype, and every literal with that datatype either fails to refer, or refers to a value in that class.</p>
+<p>When using RDFS semantics, the class <code>rdfs:Datatype</code> can be considered to contain exactly the referents of recognized datatype IRIs. </p>
+<p>The axioms and conditions listed above have some redundancy. For example, all but one
of the RDF axiomatic triples can be derived from the RDFS axiomatic triples
and the semantic conditions on ICEXT,<code> rdfs:domain</code> and <code>rdfs:range</code>.
- Other triples which must be true in all <a href="#rdfsinterpdef" class="termref">rdfs-interpretation</a>s
- include the following:</p>
+ Other triples which must be true in all rdfs-interpretations
+ include the following. This is not a complete set.</p>
<div class="tabletitle">Some rdfs-valid triples.</div>
<table border="1">
<tr>
@@ -798,104 +862,230 @@
</table>
<p>RDFS does not partition the universe into disjoint categories of classes, properties and individuals. Anything in the universe can be used as a class or as a property, or both, while retaining its status as an individual which may be in classes and have properties. Thus, RDFS permits classes which contain other classes, classes of properties, properties of classes, etc. . As the axiomatic triples above illustrate, it also permits classes which contain themselves and properties which apply to themselves. A property of a class is not necessarily a property of its members, nor vice versa. </p>
-
-<h3 id="rdfs_literal">A note on rdfs:Literal</h3>
-<p>The class <code>rdfs:Literal</code> is not the class of literals, but rather that of literal <em>values</em>. For example, LV does not contain the literal <code>"24"^^xsd:integer</code> (although it might contain the string '<code>"24"^^http://www.w3.org/2001/XMLSchema#integer</code>' ) but it does contain the number twenty-four.</p>
+<section>
+<h4>A note on rdfs:Literal</h3>
+<p>The class <code>rdfs:Literal</code> is not the class of literals, but rather that of literal values, which may also be referred to by IRIs. For example, LV does not contain the literal <code>"24"^^xsd:integer</code> (although it does contain the Unicode string '<em> "24"^^http://www.w3.org/2001/XMLSchema#integer </em>' ) but it does contain the number twenty-four.</p>
<p>A triple of the form</p>
- <p><code><ex:a> rdf:type rdfs:Literal .</code></p>
+ <p><code>ex:a rdf:type rdfs:Literal .</code></p>
<p>is consistent even though its subject is an IRI rather
than a literal. It says that the IRI '<code>ex:a</code>'
refers to a literal value, which is quite possible since literal values are things in the universe. Similarly, blank nodes may range over literal values. </p>
+</section>
+</section>
+<section>
<h3 id="rdfs_entailment">RDFS Entailment</h3>
-<p>S <i>rdfs-D-entails</i> E when every <a href="#rdfsinterpdef" class="termref">rdfs-D-interpretation</a>
+<p>S <i>rdfs-D-entails</i> E when every rdfs-D-interpretation
which satisfies every member of S also satisfies E. RDFS entailment is rdfs-{<code>rdf:langString</code>, <code>xsd:string</code> }-entailment, i.e. rdfs-D-entailment with a minimal D. </p>
-<p> Since every <a href="#rdfsinterpdef" class="termref">rdfs-D-interpretation</a> is an <a href="#rdfinterpdef" class="termref">rdf-D-interpretation</a>, if S rdfs-D-entails
+<p> Since every rdfs-D-interpretation is an rdf-D-interpretation, if S rdfs-D-entails
E then S also rdf-D-entails E; but rdfs-entailment is stronger than rdf-entailment.
Even the empty graph has a large number of rdfs-entailments which are not rdf-entailments,
for example all triples of the form </p>
-<p> <code>aaa rdf:type rdfs:Resource .</code></p>
-<p>where aaa is an IRI, are true in all <a href="#rdfsinterpdef" class="termref">rdfs-interpretation</a>s.</p>
+<p> aaa <code>rdf:type rdfs:Resource .</code></p>
+<p>where aaa is an IRI, are true in all rdfs-interpretations.</p>
+
+<section> <h4>Patterns of RDFS entailment.</h4>
+
+<P>RDFS entailment holds for all the following patterns, which correspond closely to the RDFS semantic conditions:</p>
+
+<div class="title">RDFS entailment patterns.</div>
+<table border="1" summary="RDFS-D entailment patterns">
+ <tbody>
+ <tr >
+ <th ></th>
+ <th >If S contains:</th>
+ <th >then S RDFS-D-entails:</th>
+ </tr>
+ <tr >
+ <td><dfn>rdfs1</dfn></td>
+ <td>any IRI aaa in D</td>
+ <td>aaa <code>rdf:type rdfs:Datatype . </code></td>
+ </tr>
+ <tr >
+ <td><dfn>rdfs2</dfn></td>
+ <td> aaa <code>rdfs:domain</code> xxx <code>.</code><br />
+ yyy aaa zzz <code>.</code></td>
+ <td>yyy <code>rdf:type</code> xxx <code>.</code></td>
+ </tr>
+ <tr >
+ <td></a><dfn>rdfs3</dfn></td>
+ <td>aaa <code>rdfs:range</code> xxx <code>.</code><br />
+ yyy aaa zzz <code>.</code></td>
+ <td>zzz <code>rdf:type</code> xxx <code>.</code></td>
+ </tr>
+ <tr >
+ <td><dfn>rdfs4a</dfn></td>
+ <td>xxx aaa yyy <code>.</code></td>
+ <td>xxx <code>rdf:type rdfs:Resource .</code></td>
+ </tr>
+ <tr >
+ <td><dfn>rdfs4b</dfn></td>
+ <td>xxx aaa yyy<code>.</code></td>
+ <td>yyy <code>rdf:type rdfs:Resource .</code></td>
+ </tr>
+ <tr >
+ <td><dfn>rdfs5</dfn></td>
+ <td> xxx <code>rdfs:subPropertyOf</code> yyy <code>.</code><br />
+ yyy <code>rdfs:subPropertyOf</code> zzz <code>.</code></td>
+ <td>xxx <code>rdfs:subPropertyOf</code> zzz <code>.</code></td>
+ </tr>
+ <tr >
+ <td><dfn>rdfs6</dfn></td>
+ <td>xxx <code>rdf:type rdf:Property .</code></td>
+ <td>xxx <code>rdfs:subPropertyOf</code> xxx <code>.</code></td>
+ </tr>
+ <tr >
+ <td><dfn>rdfs7</dfn></td>
+ <td> aaa <code>rdfs:subPropertyOf</code> bbb <code>.</code><br />
+ xxx aaa yyy <code>.</code></td>
+ <td>xxx bbb yyy <code>.</code></td>
+ </tr>
+ <tr >
+ <td><dfn>rdfs8</dfn></td>
+ <td>xxx <code>rdf:type rdfs:Class .</code></td>
+ <td>xxx <code>rdfs:subClassOf rdfs:Resource .</code></td>
+ </tr>
+ <tr >
+ <td><dfn>rdfs9</dfn></td>
+ <td>xxx <code>rdfs:subClassOf</code> yyy <code>.</code><br />
+ zzz <code>rdf:type</code> xxx <code>.</code></td>
+ <td>zzz <code>rdf:type</code> yyy <code>.</code></td>
+ </tr>
+ <tr >
+ <td><dfn>rdfs10</dfn></td>
+ <td>xxx <code>rdf:type rdfs:Class .</code></td>
+ <td>xxx <code>rdfs:subClassOf</code> xxx <code>.</code></td>
+ </tr>
+ <tr >
+ <td><dfn>rdfs11</dfn></td>
+ <td> xxx <code>rdfs:subClassOf</code> yyy <code>.</code><br />
+ yyy <code>rdfs:subClassOf</code> zzz <code>.</code></td>
+ <td>xxx <code>rdfs:subClassOf</code> zzz <code>.</code></td>
+ </tr>
+ <tr >
+ <td><dfn>rdfs12</dfn></td>
+ <td>xxx <code>rdf:type rdfs:ContainerMembershipProperty .</code></td>
+ <td>xxx <code>rdfs:subPropertyOf rdfs:member .</code></td>
+ </tr>
+ <tr >
+ <td><dfn>rdfs13</dfn></td>
+ <td>xxx <code>rdf:type rdfs:Datatype .</code></td>
+ <td>xxx <code>rdfs:subClassOf rdfs:Literal .</code></td>
+ </tr>
+ </tbody>
+</table>
</section>
-<section><h2 id="monotonicity">Monotonicity of semantic extensions </h2>
-<p>Given a set of RDF graphs, there are various ways in which one can 'add' information
- to it. Any of the graphs may have some triples added to it; the set of graphs
- may be extended by extra graphs; or the vocabulary of the graph may be interpreted
- relative to a stronger notion of
-entailment,
-<!-- <a href="#vocabulary_entail" class="termref">vocabulary entailment</a>, -->
- i.e. with a larger set
- of semantic conditions understood to be imposed on the interpretations. All
- of these can be thought of as an addition of information, and may make more
- entailments hold than held before the change. All of these additions are <a href="#glossMonotonic" class="termref"><em>monotonic</em></a>,
- in the sense that entailments which hold before the addition of information,
- also hold after it. We can sum up this in a single lemma:</p>
-<p ><strong><a id="GeneralMonotonicityLemma"></a>General monotonicity lemma</strong>. Suppose
- that S, S' are sets of RDF graphs with every member of S a subset
- of some member of S'. Suppose that Y indicates a semantic extension
- of X, S X-entails E, and S and
- E satisfy any syntactic restrictions of Y. Then S' Y-entails E.</p>
-
-<p >In particular, if D' is a set of IRIs identifying datatypes, D a subset of D' and if S <a href="#D_entailment" class="termref"> D-entail</a>s
- E then S also D'-entails E. </p>
-
</section>
-<section class="informative"><h2 id="extensional_rdfs">Extensional RDFS Semantic Conditions (Informative)</h2>
-<p class="issue">Is this section useful, or is it more likely to be confusing? Editor is inclined to delete it. </p>
-<p>The semantics given above is deliberately chosen to be the weakest 'reasonable'
- interpretation of the RDFS vocabulary. Semantic extensions MAY
- strengthen the range, domain, subclass and subproperty semantic conditions to
- the following '<a class="termref" href="#glossExtensional">extensional</a>'
- versions:</p>
- <div class="tabletitle">Extensional alternatives for some RDFS semantic conditions.</div>
-<table border="1">
- <tr>
- <td class="semantictable"> <p>< x,y > is in IEXT(I(<code>rdfs:subClassOf</code>))
- if and only if x and y are in IC and ICEXT(x) is a subset of ICEXT(y)</p></td>
- </tr>
- <tr>
- <td class="semantictable"> <p>< x,y > is in IEXT(I(<code>rdfs:subPropertyOf</code>))
- if and only if x and y are in IP and IEXT(x) is a subset of IEXT(y)</p></td>
- </tr>
- <tr>
- <td class="semantictable"> <p><x,y> is in IEXT(I(<code>rdfs:range</code>))
- if and only if (if < u,v > is in IEXT(x) then v is in ICEXT(y))</p></td>
- </tr>
- <tr>
- <td class="semantictable"> <p>< x,y > is in IEXT(I(<code>rdfs:domain</code>))
- if and only if (if <u,v> is in IEXT(x) then u is in ICEXT(y))</p></td>
- </tr>
+
+<section><h3>Complete sets of entailment rules (Informative)</h3>
+
+<p>(This section is based on work described more fully in [[terHorst1]], [[terHorst2]], which should be consulted for technical details and proofs.) </p>
+<p> The RDF and RDFS entailment patterns listed in the above tables can be viewed as left-to-right rules which add the entailed conclusion to a graph. These rule sets can be used to check RDF- (or RDFS-) entailment between graphs S and E, by the following sequence of operations:</p>
+<p>1. Add to S all the RDF (and RDFS) axiomatic triples except those containing the container membership property IRIs <code>rdf:_1, rdf:_2, ...</code>.<br/>
+2. For every container membership property IRI which occurs in E, add the RDF (and RDFS) axiomatic triples which contain that IRI.<br/>
+3. Apply the RDF (and RDFS) inference patterns as rules, adding each conclusion to the graph, to exhaustion; that is, until they generate no new triples. <br/>
+4. Determine if E has an instance which is a subset of the set, i.e. whether the enlarged set simply entails E.</p>
+
+This process is clearly correct, in that if it gives a positive result then indeed S does RDF-(RDFS-) entail E. It is not, however, complete: there are cases of S entailing E which are not detectable by this process. Examples include:</p>
+
+<table border="1" >
+ <tbody>
+ <tr>
+
+ <th > </th>
+ <th >RDF-entails</th>
+ </tr>
+
+ <tr>
+
+ <td><code>ex:a ex:p "string"^^xsd:string .<br/>
+ex:b ex:q "string"^^xsd:string .</code></td>
+ <td><code>ex:a ex:p _:b .<br/>
+ex:b ex:q _:b .<br/>
+_:b rdf:type xsd:string .</code> </td>
+ </tr>
+
+ <tr>
+
+ <th > </th>
+ <th >RDFS-entails</th>
+ </tr>
+<tr>
+
+ <td><code>ex:a rdfs:subPropertyOf _:b .<br/>
+_:b rdfs:domain ex:c .<br/>
+ex:d ex:a ex:e .</code></td>
+ <td><code>ex:d rdf:type ex:c .</code> </td>
+ </tr>
+
+ </tbody>
</table>
-<p>which would guarantee that the subproperty and subclass properties were transitive
- and reflexive, and would also have further consequences. </p>
-<ul><li><p class="technote">These stronger conditions would be trivially satisfied when properties are
- identified with property extensions, classes with class extensions, and <code>rdfs:SubClassOf</code>
- understood to mean subset, and hence would be satisfied by an <a href="#glossExtensional" class="termref">extensional</a> semantics
- for RDFS. In some ways the extensional versions provide a simpler semantics,
- but they require more complex inference rules. The <a href="#glossIntensional" class="termref">intensional</a> semantics described
- in the main text provides for most common uses of subclass and subproperty assertions,
- and allows for simpler implementations of a <a href="#glossComplete" class="termref">
- complete</a> set of RDFS entailment rules.
-<!-- , described in <a href="#RDFSRules" class="termref"> ////</a>. -->
-</p>
-</li></ul>
+<p> Both of these can be handled by allowing the rules to apply to a generalization of the RDF syntax, in which literals may occur in subject position and blank nodes may occur in predicate position. </p>
+<p>Define a <dfn>generalized RDF triple</dfn> to be a triple <x, y, z> where x and z can be an IRI, a blank node or a literal, and y can be an IRI or a blank node; and extend this to the rest of RDF, so that a generalized RDF graph is a set of generalized RDF triples, etc.. (This extends the generalization used in [[terHorst1]] and follows exactly the terms used in [[OWL2]].) The semantics described in this document applies to the generalized syntax without change, so that the notions of interpretation, satisfiability and entailment can be used freely. Then we can replace the first RDF entailment pattern with the simpler and more direct</p>
-</section>
+<div class="tabletitle">G-RDF-D entailment pattern.</div>
+<table border="1" >
+ <tbody>
+ <tr>
+ <th > </th>
+ <th ><strong>if S contains</strong></th>
+ <th ><strong>then S RDF-D-entails</strong></th>
+ </tr>
+ <tr >
+ <td>GrdfD1</td>
+ <td> xxx aaa <code>"</code>sss<code>"^^</code>ddd <code>.</code> <br/>
+ for ddd in D</td>
+ <td><code>"</code>sss<code>"^^</code>ddd <code>rdf:type</code> ddd <code>.</code></td>
+ </tr>
+
+ </tbody>
+</table>
-<section class="informative"><h2 id="entailment_rules">Entailment Rules (Informative)</h2>
-<p class="issue"> The inference rules need to be rewritten using the convention that they apply to a syntactic generalization of RDF that allows literals in subject position. This will take some editorial work to complete but should be easier to understand once it is done. The hard work has already been done by terHorst. <br/> <br/> I do not plan to reproduce the completeness proofs which were in the RDF 2004 document. They were unreadable, intimidating, buggy and unnecessary. </p>
+<p> which gives the entailments;</p>
+<P><code>ex:a ex:p "string"^^xsd:string .<br/>
+ex:b ex:q "string"^^xsd:string .<br/>
+"string"^^xsd:string rdf:type xsd:string .</code> by GrdfD1</p>
+
+which is an instance (in generalized RDF) of the desired conclusion, above.</p>
+<p> The second example can be derived using the RDFS rules:</p>
+<p><code>ex:a rdfs:subPropertyOf _:b .<br/>
+_:b rdfs:domain ex:c .<br/>
+ex:d ex:a ex:e .<br/>
+ex:d _:b ex:c .</code> by rdfs7<br/>
+<code>ex:d rdf:type ex:c .</code> by rdfs2</p>
+
+<p>Where the entailment patterns have been applied to generalized RDF syntax but yield a final conclusion which is legal RDF. </p>
+
+<p>With the generalized syntax, these rules are complete for both RDF and RDFS entailment. Stated exactly:</p>
+<p>Let S and E be RDF graphs. Define the <dfn>generalized RDF (RDFS) closure</dfn> of S to be the set obtained by the following procedure.</p>
+<p>1. Add to S all the RDF (and RDFS) axiomatic triples which do not contain any container membership property IRI.<br/>
+2. For each container membership property IRI which occurs in E, add the RDF (and RDFS) axiomatic triples which contain that IRI.<br/>
+3. If no triples were added in step 2., add the RDF (and RDFS) axiomatic triples which contain <code>rdf:_1</code>. <br/>
+4. Apply the rules GrdfD1 and rdfD2 (and the rules rdfs1 through rdfs13), with D={<code>rdf:langString</code>, <code>xsd:string</code>), to the set in all possible ways, to exhaustion. </p>
+
+<p>Then we have a the completeness result:<em>S RDF-entails (RDFS-entails) E just when the generalized RDF (RDFS) closure of S simply entails E.</em> </p>
+
+<p>Since the closures are finite, the generation process is decideable, and of polynomial complexity. Detecting simple entailment is NP-complete in general, but of low polynomial order when E contains no blank nodes. </p>
+
+<p>Every RDF(S) closure, even starting with the empty graph, will contain all RDF(S) tautologies. In practice there is little utility in re-deriving these, and a subset of the rules can be used to establish most entailments of practical interest. </p>
+
+<p>If it is important to stay within legal RDF syntax, rule rdfD1 may be used instead of GrdfD1, and the introduced blank node can be used as a substitute for the literal in subsequent derivations. The resulting set of rules will not however be complete.</p>
+
+<p>As noted earlier, detecting D-entailment for larger sets of datatype IRIs has to pay attention to idiosyncratic properties of the particular datatypes.</p>
+
+
</section>
-
+
<section class="appendix" id="MTintro"><h2 id="model_theory">Introduction to model theory (Informative)</h2>
///
</section>
@@ -937,7 +1127,7 @@
<p>Consider an example graph containing a single triple:</p>
- <p><code><ex:a> <ex:b> <ex:c> .</code></p>
+ <p><code>ex:a ex:b ex:c .</code></p>
<p>and suppose that this graph is identified by the IRI <code>ex:graph1</code>. Exactly how this identification is achieved is external to the RDF model, but it might be by the IRI resolving to a concrete syntax document describing the graph, or by the IRI being the associated name of a named graph in a dataset. Assuming that the IRI can be used to refer to the triple, then the reification vocabulary allows us to describe the first graph in another graph:</p>
@@ -1265,7 +1455,7 @@
(Also used between a set of expressions and an expression.)</p>
<p><strong><a id="glossEquivalent"></a>Equivalent</strong> (prep., with
- <em>to</em>) True under exactly the same conditions; making
+ <em>to</em>; also <em>logically</em> equivalent) True under exactly the same conditions; making
identical claims about the world, when asserted. <a
href="#glossEntail" class="termref">Entails</a> and is entailed
by.</p>