- From: Herman ter Horst <herman.ter.horst@philips.com>
- Date: Fri, 28 Oct 2005 13:51:36 +0200
- To: www-rdf-comments@w3.org, phayes@ihmc.us
- Message-ID: <OF2CC83B4A.C832479D-ONC12570A8.003CBEED-C12570A8.004150E9@philips.com>

Following the period during which I reviewed preliminary versions of the RDF Semantics spec (on behalf of the WebOnt WG) I investigated various aspects of the RDF semantics, which led to two papers [1] [2] that contain information that can be viewed as complementing the spec [3]. In this message I include several comments relating to [3], derived from [1] [2]. In particular I discovered an error that remains in the RDFS entailment lemma and that was missed earlier. === A) In [3] decidability and complexity of RDFS entailment are not considered. The completeness proof in [3] does not prove decidability of RDFS entailment because the RDFS closure graphs used are infinite. In [2] it is proved that these infinite RDFS closure graphs can be replaced by finite, partial RDFS closure graphs that can be computed in polynomial time. This is used in [2] to prove that RDFS entailment is decidable, NP-complete, and in P if the target RDF graph has no blank nodes. More specifically, a decision procedure for RDFS entailment can be described as follows. Given: a finite set S of finite RDF graphs, a finite RDF graph G: - form a merge M(S) of S - add to M(S) all RDF, RDFS axiomatic triples, except those including a container membership property rdf:_i (this is a finite set of axiomatic triples) - for each container membership property rdf:_i that appears in either S or G, add the four (RDF, RDFS) axiomatic triples that include rdf:_i; if S and G do not include a container membership property, then add the four axiomatic triples for just one container membership property - apply rule lg to any triple containing a literal, in such a way that distinct, well-formed XML literals with the same value are associated with the same surrogate blank node - apply rules rdf2 and rdfs1 to each triple forming a well-formed XML literal or a plain literal, respectively - apply rule rdf1, rule gl and the remaining RDFS entailment rules until the graph is unchanged In [2] I call the graph H that is now obtained a partial RDFS closure: it is finite (see [2] for the proof). It can be decided whether S RDFS-entails G by checking whether H contains an instance of G as a subset or whether H contains an XML-clash (see [2] for the proof). In this decision procedure, the entailment rules are interpreted in a broader way than in [3]: blank nodes are allowed in predicate position. See the following comment. === B) There is an error in the RDFS entailment lemma [3]. For example, the three RDF triples p subPropertyOf b . b domain u . v p w . (where b is a blank node) RDFS-entail the triple v type u . This RDFS-entailment cannot be found with the axiomatic triples and entailment rules for RDFS. These entailment rules are therefore not complete. In [2] it is proved that this problem can be solved by extending RDF graphs to allow blank nodes in predicate position. The origin of the problem seems to be a 'mismatch' between the notion of RDF graph and the semantics of RDF. The semantics allows blank nodes to refer to properties, while RDF graphs do not allow blank nodes in predicate position. It seems that if blank nodes would be allowed in predicate position in RDF graphs, then the abstract syntax (i.e. RDF graphs) would fit more closely with the semantics. === C) The definition of RDFS interpretations in [3] does not make it obvious that the many uses of the functions IEXT and ICEXT in this definition are inside their domains, as required (i.e. that IEXT is used only for properties and ICEXT only for classes). In [2] it is proved that the description of RDFS interpretations in [3] is well-defined. This is done by using a slightly reformulated, equivalent version of the definition. === D) In [2] the completeness, decidability and complexity results for RDFS are extended to a version of datatyped reasoning that weakens D-entailment. === Earlier discussion on points C and D took place on rdf-comments in the period during which I reviewed preliminary versions of the RDF Semantics spec. Herman ter Horst Philips Research [1] H. ter Horst, Extending the RDFS Entailment Lemma, Proceedings 3rd International Semantic Web Conference (ISWC2004), Springer LNCS 3298, pp. 77-91. The following is a revised and extended version of [1] [2] H. ter Horst, Completeness, decidability and complexity of entailment for RDF Schema and a semantic extension involving the OWL vocabulary, Journal of Web Semantics 3 (2005) pp. 79-115. http://www.sciencedirect.com/science?_ob=IssueURL&_tockey=%23TOC%2312925%232005%23999969997%23606589%23FLA%23&_auth=y&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=814973d32693889bd7e4cf071c815f01 [3] http://www.w3.org/TR/rdf-mt/

Received on Friday, 28 October 2005 11:53:44 UTC