RDF语义 推荐标准-2
TransWiki - an Open Translation Project(OTP)
摘要_文档状态_目录 第0节 第1节 第2节 第3节 第4节 第5节 第6节 第7节 附录_参考文献
2. Simple Entailment between RDF graphs
Following conventional terminology, I satisfies E if I(E)=true, and a set S of RDF graphs (simply) entails a graph E if every interpretation which satisfies every member of S also satisfies E. 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.
Entailment is the key idea which connects model-theoretic semantics to real-world applications. As noted earlier, making an assertion amounts to claiming that the world is an interpretation which assigns the value true to the assertion. If A entails B, then any interpretation that makes A true also makes B true, so that an assertion of A already contains the same "meaning" as an assertion of B; one could say that the meaning of B is somehow contained in, or subsumed by, that of A. If A and B entail each other, then they both "mean" the same thing, in the sense that asserting either of them makes the same claim about the world. The interest of this observation arises most vividly when A and B are different expressions, since then the relation of entailment is exactly the appropriate semantic license to justify an application inferring or generating one of them from the other. Through the notions of satisfaction, entailment and validity, formal semantics gives a rigorous definition to a notion of "meaning" that can be related directly to computable methods of determining whether or not meaning is preserved by some transformation on a representation of knowledge.
Any process which constructs a graph E from some other graph(s) S is said to be (simply) valid if S entails E in every case, otherwise invalid. Note that being an invalid process does not mean that the conclusion is false, and being valid (http://www.w3.org/TR/2004/REC-rdf-mt-20040210/#glossValid) does not guarantee truth. However, validity represents the best guarantee that any assertional language can offer: if given true inputs, it will never draw a false conclusion from them.
This section gives a few basic results about simple entailment and valid (http://www.w3.org/TR/2004/REC-rdf-mt-20040210/#glossValid) inference (http://www.w3.org/TR/2004/REC-rdf-mt-20040210/#glossInference). 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 (P and Q) to P, and the inference from foo(baz) to (exists (?x) foo(?x)).
These results apply only to simple entailment, not to the extended notions of entailment introduced in later sections. Proofs, all of which are straightforward, are given in appendix A (http://www.w3.org/TR/2004/REC-rdf-mt-20040210/#prf), which also describes some other properties of entailment which may be of interest.
Empty Graph Lemma. The empty set of triples is entailed by any graph, and does not entail any graph except itself. [Proof (http://www.w3.org/TR/2004/REC-rdf-mt-20040210/#emptygraphlemmaprf)]
Subgraph Lemma. A graph entails all its subgraphs (http://www.w3.org/TR/2004/REC-rdf-mt-20040210/#defsubg). [Proof (http://www.w3.org/TR/2004/REC-rdf-mt-20040210/#subglemprf)]
Instance Lemma. A graph is entailed by any of its instances (http://www.w3.org/TR/2004/REC-rdf-mt-20040210/#definst).[Proof (http://www.w3.org/TR/2004/REC-rdf-mt-20040210/#instlemprf)]
The relationship between merging and entailment is simple, and obvious from the definitions:
Merging lemma. The merge of a set S of RDF graphs is entailed by S, and entails every member of S. [Proof (http://www.w3.org/TR/2004/REC-rdf-mt-20040210/#mergelemprf)]
This means that a set of graphs can be treated as equivalent (http://www.w3.org/TR/2004/REC-rdf-mt-20040210/#glossEquivalent) to its merge, i.e. a single graph, as far as the model theory (http://www.w3.org/TR/2004/REC-rdf-mt-20040210/#glossModeltheory) is concerned. This can be used to simplify the terminology somewhat: for example, the definition of S entails E, above, can be paraphrased by saying that S entails E when every interpretation which satisfies S also satisfies E.
The example (http://www.w3.org/TR/2004/REC-rdf-mt-20040210/#bnodeExample) given in section 1.5 shows that it is not the case, in general, that the simple union of a set of graphs is entailed by the set.
The main result for simple RDF inference is:
Interpolation Lemma. S entails a graph E if and only if a subgraph of S is an instance of E.[Proof (http://www.w3.org/TR/2004/REC-rdf-mt-20040210/#interplemmaprf)]
The interpolation lemma completely characterizes simple RDF entailment in syntactic terms. To tell whether a set of RDF graphs 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. Of course, there is no need to actually construct the merge. If working backwards from the consequent E (http://www.w3.org/TR/2004/REC-rdf-mt-20040210/#glossConsequent), an efficient technique would be to treat blank nodes as variables in a process of subgraph-matching, allowing them to bind to 'matching' name (http://www.w3.org/TR/2004/REC-rdf-mt-20040210/#defname)s in the antecedent (http://www.w3.org/TR/2004/REC-rdf-mt-20040210/#glossAntecedent) graph(s) in S, i.e. those which may entail the consequent (http://www.w3.org/TR/2004/REC-rdf-mt-20040210/#glossConsequent) graph. The interpolation lemma shows that this process is valid (http://www.w3.org/TR/2004/REC-rdf-mt-20040210/#glossValid), and is also complete (http://www.w3.org/TR/2004/REC-rdf-mt-20040210/#glossComplete) if the subgraph-matching algorithm is. The existence of complete (http://www.w3.org/TR/2004/REC-rdf-mt-20040210/#glossComplete) subgraph-checking algorithms also shows that RDF entailment is decidable, i.e. there is a terminating algorithm which will determine for any finite set S and any graph E, whether or not S entails E.
Such a variable-binding process would only be appropriate when applied to the conclusion of a proposed entailment. This corresponds to using the document as a goal or a query, in contrast to asserting it, i.e. claiming it to be true. If an RDF document is asserted, then it would be invalid to bind new values to any of its blank nodes, since the resulting graph might not be entailed by the assertion.
The interpolation lemma has an immediate consequence a criterion for non-entailment:
Anonymity lemma. Suppose E is a lean (http://www.w3.org/TR/2004/REC-rdf-mt-20040210/#deflean) graph and E' is a proper instance of E. Then E does not entail E'.[Proof (http://www.w3.org/TR/2004/REC-rdf-mt-20040210/#Anonlem1prf)]
Note again that this applies only to simple entailment, not to the vocabulary entailment relationships defined in rest of the document.
Several basic properties of entailment follow directly from the above definitions and results but are stated here for completeness sake:
Monotonicity Lemma. Suppose S is a subgraph of S' and S entails E. Then S' entails E.[Proof (http://www.w3.org/TR/2004/REC-rdf-mt-20040210/#monotonicitylemmaprf)]
The property of finite expressions always being derivable from a finite set of antecedents is called compactness. Semantic theories which support non-compact notions of entailment do not have corresponding computable inference systems.
Compactness Lemma. If S entails E and E is a finite graph, then some finite subset S' of S entails E.
2.1 Vocabulary interpretations and vocabulary entailment
Simple interpretations and simple entailment capture the semantics of RDF graphs when no attention is paid to the particular meaning of any of the names in the graph. To obtain the full meaning of an RDF graph written using a particular vocabulary, it is usually necessary to add further semantic conditions which attach stronger meanings to particular URI references and typed literals in the graph. Interpretations which are required to satisfy extra semantic conditions on a particular vocabulary will be generically referred to as vocabulary interpretations. Vocabulary entailment means entailment with respect to such vocabulary interpretations. These stronger notions of interpretation and entailment are indicated by the use of a namespace prefix, so that we will refer to rdf-entailment, rdfs-entailment and so on in what follows. In each case, the vocabulary whose meaning is being restricted, and the exact conditions associated with that vocabulary, are spelled out in detail.
