W3C home > Mailing lists > Public > w3c-rdfcore-wg@w3.org > October 2002

Re: rdf:first/rest/nil/List: syntax-only at the RDF level

From: pat hayes <phayes@ai.uwf.edu>
Date: Wed, 30 Oct 2002 17:53:07 -0600
Message-Id: <p05111b31b9e617ae32d7@[]>
To: "Jeremy Carroll" <jjc@hpl.hp.com>
Cc: w3c-rdfcore-wg@w3.org

>a disgruntled Pat wrote:
>>I would like to see a more detailed explanation of why the code could
>>not be modified to accommodate to this,
>I highlighted three features that I believe are in the list semantics that
>you would like to include:
>- infinity
>- equality
>- contradiction
>Of these the most difficult is infinity.
>Our typical API allows you to list the triples in a graph one by one, or the
>triples that match some expression, one by one. We are extending this API to
>support RDFS closure (compare with Ora Lassila's paper "Taking the RDF Model
>Theory Out for a Spin" Sardinia ISWC 2002).

Good luck. (See below.)

>This method will produce highly surprising and unacceptable results if the
>RDFS closure of a graph with a single triple in, has an infinite number of

But guys, be reasonable. This *obviously* is not an acceptable 
implementation strategy in general. Theorem-provers havnt been 
implemented this way since about 1965. Strictly speaking it doesn't 
even work for RDFS, since the existing container properties give you 
an infinite closure. Of course there are going to be infinite 
universes in almost any reasonable semantic theory for any slightly 
expressive language. Look at Basic or Fortran, never mind LISP. The 
value spaces of XSD datatypes are infinite, so for example all these 
triples are going to be true in RDF:

_:x  xsd:integer  xsd:integer"<insert numeral string here>" .

Even when the closure is finite, its probably going to be 
horrendously large and the rules are chock full of redundancy (even 
more if we use the IFF semantics for range, BTW). What you ought to 
do is run the closure rules backwards: use some kind of 
matching+backtracking from the target triple to at least keep the 
search space to a manageable size. The size of the forward closure is 
irrelevant: what ought to matter is the span length of the inference 
tree BACK from your target to the set of triples in the graph being 
'closed'. Hey, use Prolog.

I actually said in the MT document that those rules weren't intended 
to define a process or to be directly implemented. I wish Id never 
mentioned closure rules: it was only intended to be a way of relating 
the semantics together.

>The result would be that we would need to redesign our API

You need to do that anyway. I feel like Im being asked to help design 
an airplane made of lead here.

>so that the API
>concepts much less clearly matched the RDF Semantic concepts - which would,
>in my opinion, be too great a price to pay for supporting webont in their
>list semantic problems. Doing list comprehension is not conceivably an RDF
>Core problem. DAML+OIL didn't do it, it's new for OWL.
>Equality is also difficult.

I agree with you there, and would be happy - well, not happy, but not 
bloody miserable -  to leave that one. Seems to me that anyone who 
writes RDF describing a forked -tail list is liable to get what they 
deserve. And we can't really express identity in RDF. We can in OWL 
but it doesnt really matter there in any case.

>You say that Dan's entailment below does not hold.
>>Consider this conjecture:
>>    eg:myBrothers rdf:first eg:paul.
>>    eg:paul eg:hairColor "brown".
>>    eg:myBrothers rdf:first eg:jon.
>>    eg:jon eg:height "tallish".
>>    _:somebody eg:hairColor "brown".
>>    _:somebody eg:height "tallish".
>>I don't want that entailment to be justified by the RDF
>>nor RDFS MTs;
>Please explain why it doesn't.

Because the MT just requires that the domain of lists is closed under 
cons-ing, basically. It doesnt say anything about identity between 
lists, so it doesnt have any entailments about things being the same. 
In particular, myBrothers can have two rdf:firsts for all the MT 
cares. It wouldnt be an Sexpression, but it could still *exist*. 
What the MT does insist on is that a list exists which has eg:paul 
first and nil, say, as next. It tells the user that its always OK to 
refer to a  list using bnodes, ie to say that a list exists, just 
like they know its always OK to write a numerical string in a 
literal: the RDF engine isnt going to suddenly refuse to believe in 
seventeen, say.

>If you have a neat trick for having only one first without Dan's entailment
>then maybe that will be alright.

There can be two firsts. I think that would be OK for OWL as well, by 
the way: the abstract syntax-to-RDF mapping is never going to create 
a forked-head list, so the issue never gets to be critical. I don't 
mind leaving to OWL the task of saying that rdf:first is functional. 
(Or is it inversefunctional? Whatever.)

>The problems about the contradictoriness of
>rdf:nil rdf:rest _:a . I can probably live with, although I would need to

Yes, that does seem odd. In fact I think we could even maybe live 
with this, in fact (?). Things past nil in a list would be like 
transfinite ordinals: they are there, but you can never get to them 
('you' here being a recursive kind of guy, that is.) There could be 
some snags in OWL over identity, however. Need to think about this 
more, but no time to think right now.

IHMC					(850)434 8903   home
40 South Alcaniz St.			(850)202 4416   office
Pensacola              			(850)202 4440   fax
FL 32501           				(850)291 0667    cell
phayes@ai.uwf.edu	          http://www.coginst.uwf.edu/~phayes
s.pam@ai.uwf.edu   for spam
Received on Wednesday, 30 October 2002 18:53:51 EST

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