W3C home > Mailing lists > Public > w3c-rdfcore-wg@w3.org > June 2003

Re: MT Bug?

From: pat hayes <phayes@ihmc.us>
Date: Mon, 9 Jun 2003 14:58:33 -0400 (EDT)
Message-Id: <p05210613bb0a7e9d0897@[10.0.100.24]>
To: Brian McBride <bwm@hplb.hpl.hp.com>
Cc: w3c-rdfcore-wg@w3.org




>Fiddling about with the MT, I noticed:
>
>The closure rule se1 is defined such that given a bnode as the object of
>a triple, it will generate a similar triple with a different bnode.
>When applied recursively, this will generate an infinite number of
>triples.  Similarly for se2.

Right. I need to add some prose to the definition of 'closure' to 
indicate that there is no need to apply these rules redundantly. Once 
you have got to (for example)

_:x aaa _:y .

then there isnt any point in adding

_:x1 aaa _:y1 .

as well.  I mean, it is *valid* to add that, but the closure 
completeness results don't require one to go on doing that for ever, 
since the only purpose of the closure is to reduce vocabulary 
entailment to simple entailment. I am working on the exact form of 
words right now, it will talk about 'redundant' triples and not 
require the closure to have them.

>
>The current official Ed's draft of the MT
>
>   http://www.w3.org/2001/sw/RDFCore/TR/WD-rdf-mt-20030117/#ClosRules
>
>states:
>
>[[
>2. Apply the rules se1 and se2 and the following RDF closure rules
>recursively to generate all legal RDF triples (i.e. until none of the
>rules apply or the graph is unchanged.) Here xxx and yyy stand for any
>URIref, blank node or literal, aaa for any URIref.
>]]
>
>Given the definitions of se1 and se2, the terminating condition can
>never be met, unless the definition of 'aaa' is intended to overrides
>that given in the definition of se1 and se2.  I'm confused.
>
>I suggest that the MT adopt a uniform terminology throughout, e.g. 'aaa'
>always means just a URIref throughtout, or whatever convention the
>editor finds most appropriate.

Yes, I hadnt noticed the mismatch in conventions, and will fix it 
pronto. (Done now in

http://www.ihmc.us/users/phayes/RDF_Semantics_Edit_nT.html

which will now be the place to look for the latest editor's version, 
BTW. Don't archive this, though, as I havnt done the rule-section 
re-organize yet.)

>What is the current position on the size of the closures generated by
>these rules?

I havnt even thought about it. These rules are not meant for serious 
implementation; they are an existence proof (and are meant to 
establish decideability of RDF(S) entailment.)

>Is it the intent to make them as small as we reasonably
>can?

No. That would be a lot more work. Though in a sense they are as 
small as possible in that if you just delete one of them, there will 
be something missing from the closure, they are full of redundancies 
(alternative ways of deriving the same triple) which could be greatly 
reduced by a cleverer set of rules, eg by imposing an order on them 
and designing them so that earlier ones covered cases used by later 
ones.

>Does it matter?

It would if you were to try to generate them, as I believe Euler does 
and Graham is apparently trying to do. I think you will only get a 
linear or log-linear improvement by optimizing, though (maybe a 
factor of four or five improvement in time to generate the full 
closure). The most efficient way to check for entailment probably 
isnt to generate closures at all, but to backtrack from the 
conclusion and apply the rules 'backwards' as needed until  you find 
a tautology.  Most of the closure of A is likely irrelevant to 
whether A entails B or not. After all, even the empty graph has a 
pretty large closure.

>  Was it the editors intention that the rules
>generate this infinite set of triples?

No, the editor's intention was always that the closure of a finite 
graph would be finite. The editor's brain was on automatic idle when 
he (the editor) inserted the rules se1 and se2 and failed to notice 
that the old, simple, definition of closure was no longer adequate. 
The editor is embarrassed to find this egg on his face from making an 
error that should have been obvious to an undergraduate, and is 
inclined to attribute this to a combination of age, loose living and 
lack of sleep.

Pat

-- 
---------------------------------------------------------------------
IHMC	(850)434 8903 or (650)494 3973   home
40 South Alcaniz St.	(850)202 4416   office
Pensacola			(850)202 4440   fax
FL 32501			(850)291 0667    cell
phayes@ihmc.us       http://www.ihmc.us/users/phayes
Received on Monday, 9 June 2003 15:50:15 EDT

This archive was generated by hypermail pre-2.1.9 : Wednesday, 3 September 2003 09:57:54 EDT