RDF Semantics / error in RDFS entailment lemma

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/