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: Fri, 08 Aug 2003 05:21:05 -0400 (EDT)
Message-Id: <20030808.052105.106432498.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: Thu, 7 Aug 2003 23:44:03 -0500

> >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.
> 
> Which is correct.
> 
> >Section 7.1 then goes on to give the simple entailment rules.
> 
> And, in addition, it says explicitly that the rule as stated is not 
> exactly equivalent to the instance lemma, but that a modification of 
> it- which it describes - is.  I see no problem with this.

I do.  The modification is not described in sufficient detail to determine
exactly what the rule set is.  In particular, simply allowing new blank
nodes to be allocated to existing blank nodes does not change the rule set
at all, as this would not change the restrictions on which kinds of triples
the rules can be applied to.

> >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?
> 
> Because you used the rule twice on the same triple.  But see the end 
> of the message.

Huh?  What is wrong with this?  I don't see any hint that the rule cannot
be applied twice to the same triple.  Where is (was) this restriction stated?

> >  > >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.
> 
> It is backed up in the document; see above.

Not so; see above.

> >There is a claim (that the two rule
> >formulations are equivalent) that is incorrect.  Both of these need
> >attention.
> >
> 
> I will concede that the paragraph mentioning the alternative 
> formulation is easy to mis-read. As the paragraph was intended only 
> to be a helpful remark and is not used elsewhere, it does not seem 
> worth the effort of stating it precisely. I will therefore simple 
> delete it.

The alternative formulation was different from the simple entailment
rules.  It is good that it is no longer in the document.

> Pat

Peter F. Patel-Schneider
Bell Labs Research
Lucent Technologies
Received on Friday, 8 August 2003 05:21:16 GMT

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