author | Eric Prud'hommeaux <eric@w3.org> |

Mon, 18 Mar 2013 13:29:51 -0400 | |

changeset 669 | 4eae782b8493 |

parent 668 | 98062c0b31fa (current diff) |

parent 666 | b01487d0a676 (diff) |

child 670 | 381bedd01fbd |

~ merge

--- a/rdf-mt/index.html Mon Mar 18 13:28:29 2013 -0400 +++ b/rdf-mt/index.html Mon Mar 18 13:29:51 2013 -0400 @@ -129,9 +129,9 @@ <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 of x and y. RDF graph syntax is indicated using the notational conventions of - the <a - href="http://www.w3.org/TR/rdf-testcases/#ntriples">N-Triples</a> syntax described - in the RDF test cases document [[!RDF-TESTCASES]] + the N-Triples syntax described + in the <a + href="https://dvcs.w3.org/hg/rdf/raw-file/default/rdf-turtle/n-triples.html">Turtle Working Draft</a> [[!]] 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> @@ -187,16 +187,18 @@ 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 treat such equivalent graphs as identical.</p> - -<p class="issue">The following definitions of blank node scope, scoped graph and complete graph, and the modified definition of merging, are at risk, and at the time of writing (13 march) have not yet been aligned with Concepts. </p> -<p>Blank nodes may be identified in a surface (document) syntax for RDF using blank node identifiers. Each surface syntax MUST specify an unambiguous notion of the <dfn>scope</dfn> of such identifiers, such that any graph defined by this syntax will be inside a single scope. Two graphs not in the same scope do not share any blank nodes. Each combination of a blank node identifier and a surrounding scope is understood to define a unique blank node, local to the graphs described by the surface syntax. A blank node can occur in only one scope. The same blank node identifier used in different scopes identifies a different blank node in each scope in which it occurs. Scope boundaries are defined by the surface syntax used to encode RDF. For example, in RDF/XML [[!RDF-SYNTAX-GRAMMAR]] and NTriples [[!RDF-TESTCASES]], the scope is defined by the document. In TriG, [[a trig reference]] a syntax for RDF datastores, the scope is the entire datastore. </p> + 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>The set of all triples in a given scope is an RDF graph, called a <dfn>scoped graph</dfn>. (The scoped graph may be an abstraction, e.g. for a dataset it is the set of all triples which occur in any graph in the dataset, which might not be represented explicitly in the dataset itself.) Every RDF graph described by a surface syntax for RDF must be a subgraph of a scoped graph. </p> +<p>Any set of graphs can be treated as a single graph simply by taking the union of the sets of triples. If two or more of the graphs share a blank node it will retain its identity when the union graph is formed. Graphs can share blank nodes only if they are derived from graphs described by documents or surface structures which share a single scope for blank node identifiers.</p> +<p class="issue">The Concepts document does not yet define blank node identifier scopes.</p> -<p>An RDF graph is <dfn>complete</dfn> when, for every blank node in the graph, the graph contains all triples in the scoped graph which contain that blank node. That is, for every blank node in the scope, the graph either does not contain the blank node, or else it contains all triples in the scoped graph which contain that blank node. Scoped graphs and ground graphs are always complete. Non-complete graphs may fail to give enough information to reconstruct the information contained in their union.</p> -<p>Any set of graphs can be treated as a single graph simply by taking the union of the sets of triples. If two or more of the graphs are in the same scope, then the same blank node might occur in more than one of them, and will retain its identity when the union graph is formed. If the graphs in a set are from different scopes they cannot share blank nodes, so if they are represented by a notation which uses blank node identifiers then care should be taken to change the identifiers to avoid name clashes between blank node identifiers used in graphs from different scopes. Once this is done − that is, when graphs from different scopes are not represented using the same blank node identifier − then the union graph can be formed by taking the union of the triples in the various graphs in S, and treating this set as the scoped graph of a single blank node scope. 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>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> + +<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 >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 @@ -210,10 +212,6 @@ -<ul><li><p class="changenote"> The 2004 RDF 1.0 specification did not define a notion of blank node scope, so allowed the possibility of two graphs 'accidentally' sharing a blank node. It was therefore obliged to define a process of 'standardizing apart' blank nodes, and to distinguish graph unions from graph merges. Requiring each RDF graph to be in a single blank node scope simplifies the basic syntax and renders this distinction unnecessary. Standardizing apart blank node identifiers may still be needed at a concrete syntax level, but is not 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. <br/>Since 2004, in subsequent practice, the term "RDF graph" is widely used to mean what is here defined as a scoped graph. </p> -</li></ul> - -<p class="issue">The Concepts document does not yet define blank node scopes.</p> </section> @@ -299,10 +297,6 @@ <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> -<p>The semantics of blank nodes is defined as a condition on all RDF triples in a single blank node scope. All blank nodes in an RDF graph must be in a single scope, but a scope might extend beyond a single graph. Two graphs not in the same blank node scope do not share any blank nodes.</p> - -<p class="issue">The Concepts document does not yet define blank node scopes.</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> <div class="tabletitle">Semantic condition for blank nodes.</div> @@ -312,7 +306,7 @@ <tr> <td class="semantictable">If E is an RDF graph then I(E) = true if [I+A](E) = - true for some mapping A from the set of blank nodes in the scope of E to IR, otherwise + true for some mapping A from the set of blank nodes in E to IR, otherwise I(E)= false.</td> </tr> </tbody> @@ -359,23 +353,27 @@ is entailed by any of its <a href="#definst" class="termref">instances</a>.<a href="#instlemprf" class="termref"> [Proof]</a></p> -<p><a name="mergelem" id="mergelem"><strong>Merging lemma.</strong></a> The merge - of a set S of complete RDF graphs is entailed by S, and entails every member of S. <a href="#mergelemprf" class="termref">[Proof]</a></p> - -<p class="issue">the definition of complete graph, and the status of the following counterexample, are currently (13 March) under discussion.</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> +<code>:a :p _:x . </code></p> +<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>The merging lemma does not hold for incomplete graphs. For example, consider the graph</p> -<p> -<code>:a :p _:x . <br/> -:b :p _:x .</code></p> -<p>and let S be the set of its singleton subgraphs. Treated in isolation, these 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 triple considered in isolation, and the mapping <code>_:x</code>/I(<code>:b</code>) for the second triple considered in isolation, but there is no mapping which works for the combination. The incompleteness of the subgraphs means that neither 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>This means that a set of complete graphs can be treated as <a +<p><a name="mergelem" 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> + + + + <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 complete graphs and the single graph formed by merging them. </p> + 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 name="interplemma" 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>