W3C home > Mailing lists > Public > www-rdf-comments@w3.org > July to September 2003

Re: problems with simple entailment rules

From: Peter F. Patel-Schneider <pfps@research.bell-labs.com>
Date: Thu, 07 Aug 2003 08:35:34 -0400 (EDT)
Message-Id: <20030807.083534.63231864.pfps@research.bell-labs.com>
To: phayes@ihmc.us
Cc: www-rdf-comments@w3.org

From: pat hayes <phayes@ihmc.us>
Subject: Re: problems with simple entailment rules
Date: Tue, 5 Aug 2003 10:55:50 -0500

> >I believe that there is a problem with the definition of ``allocated to''
> >in the simple entailment rules.  The definition currently (as of the 31
> >July version) states
> >
> >	The terminology 'allocated to' means that the blank node much have
> >	been created by an earlier appliation of the specified rules on the
> >	same URI reference or literal, or if there is no such blank node
> >	then it must be a 'new' node which does not occur in the graph.
> >
> >My reading of this is that the following RDF graph
> >
> >	<ex:a> <ex:p> <ex:b> .
> >
> >cannot be expanded to
> >
> >	<ex:a> <ex:p> <ex:b> .
> >	<ex:a> <ex:p> _:a .
> >	<ex:a> <ex:p> _:b .
> >
> >using the simple entailment rules because once there is a blank node
> >created from <ex:b> then all subsequent rule applications must use that
> >blank node for <ex:b>.
> 
> That is correct. This construction was adopted in order to make 
> closures be finite under these rules, and because this restricted 
> version is sufficient to produce the required completeness result for 
> the vocabulary entailments.  As the text notes, a modification of the 
> rule which allows bnodes to be allocated to other bnodes would allow 
> this inference and would be complete. The text states this explicitly 
> (last para section 7.1):
> "These rules will not generate all graphs which have the original 
> graph as an instance, which could include arbitrarily many blank-node 
> triples all of which instantiate back to the original triples. 
> Modifying the rules so that new blank nodes could be allocated to 
> existing blank nodes would generate all such graphs. "
> 
> >
> >Also
> >
> >	<ex:a> <ex:p> _:a .
> >
> >cannot be expanded to
> >
> >	<ex:a> <ex:p> _:a .
> >	<ex:a> <ex:p> _:b .
> >
> >because se1 requires that the object of the triple be a URI reference or
> >literal.
> 
> Indeed; see comment above.
> 
> >This means that the simple entailment rules are not a replacement for the
> >instance relationship, which counters the claim in Section 7.1.
> 
> What claim?

The very first sentence in Section 7.1 says

	The instance lemma in Section 2 can be stated as inference rules on
	triples. 

Section 7.1 then goes on to give the simple entailment rules.

If the simple entailment rules are not supposed to back up this claim, then
I strongly suggest that the claim be removed.

> >  Nor are
> >the simple entailment rules complete for simple entailment, which, by the
> >way, is not stated in the document.
> 
> I am not sure what you mean. The document does not state that the 
> simple entailment rules are complete for simple entailment, because 
> that would be false: they are not complete (a complete set of rules 
> would require an explicit conjunction-elimination rule, for example). 
> In fact the text makes clear the way in which they are incomplete, 
> and does not state a completeness result.
> 
> >Nor are the simple entailment rules equivalent to the alternative rule
> >formulation in the second-last paragraph of Section 7.1, as this
> >alternative formulation admits the first expansion above.
> 
> They are equivalent, and it does not admit that expansion.

This alternative formulation says

	These rules could be stated as a rule which takes as input any
	subgraph of triples all containing a given URI reference or literal
	in the subject or object position, and adding a copy of this whole
	subgraph with the URI reference or literal replaced by a single
	'new' blank node.

Under this rule formulation

	<ex:a> <ex:p> <ex:b> .

goes to (by picking the entire graph and replacing <ex:b> by _:a)

	<ex:a> <ex:p> <ex:b> .
	<ex:a> <ex:p> _:a .

which then goes to (by picking the first triple and replacing <ex:a> by _:b) 

	<ex:a> <ex:p> <ex:b> .
	<ex:a> <ex:p> _:a .
	<ex:a> <ex:p> _:b .

How is this not a valid derivation under this alternative formulation?

> >Nor is this
> >alternative rule formulation a replacement for the instance relationship,
> >as it does not admit the second expansion above.
> 
> It is not stated to be so.

> As far as I can determine, your message does not indicate any actual 
> problems with the entailment rules: you re-iterate several points 
> already made in the text and observe that some other points, not made 
> in the text, would be false if they were made there. As there is 
> nothing here I can find that indicates that there is anything wrong 
> with the text, I propose to ignore this message.

I disagree.  There is a claim (the first sentence of Section 7.1) that is
not backed up in the document.  There is a claim (that the two rule
formulations are equivalent) that is incorrect.  Both of these need
attention.


> Pat

Peter F. Patel-Schneider
Bell Labs Research
Lucent Technologies
Received on Thursday, 7 August 2003 08:35:44 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Friday, 21 September 2012 14:16:32 GMT