Re: log:forSome/#rdfms-identity-anon-resources

Dan,

is what you describe below truly the difference between named and anonymous 
nodes, or the difference between variable names and constant names, or 
something else.

I think a URI, by the way it is defined, must name a constant -- i.e. it 
references exactly one item in the domain of interpretation.  [debatable]

I can imagine two (other) ways to resolve the problem you define;  I don't 
know which, if either, is most helpful.

(1) Unknown binding...

in a recent message, Pat said:
>>   child(fred) & parentOf(Y,fred)
>
>Well, the existential variable Y would become a (new) constant name, say 
>sk2356, and this would become
>child(fred) & parentOf(sk2356,fred)
>The fact that this name is 'new' means that there are no other assertions 
>about it, ie all that you know about sk2356 is that it exists (since all 
>FOL names refer to something) and that the above axiom is true of it, 
>which is exactly what you knew about Y.  Now, there could logically have 
>been several Y's that might have existed and would have satisfied the 
>orginal existential axiom (so in this sense the existential variable might 
>be said to 'bind to' more than one thing, though this sense of 'bind' is 
>not that used in programming language semantics); the existential 
>quantifer doesn't guaranteee uniqueness. The skolemised formula in effect 
>'picks out' one of them and says something about it, since every logical 
>name only denotes one thing in a given interpretation. But there isnt 
>really any difference in content, since you don't know which of them it 
>picks out (denotes), and in fact it could denote any of them (if there was 
>more than one) and still be correct.

Following this line, any pair of names can bind to the same object in the 
domain of interpretation that matches what we know about them, so from your 
examples:

[[[
<http://skolem.example#432oj34oij2o3ijo23j>
<http://purl.org/dc/elements/1.1/title> "Fractals Everywhere" .
  :
]]]

and

[[[
<http://booksRus.example/inv2001-06-25#item342323>
<http://purl.org/dc/elements/1.1/title> "Fractals Everywhere" .
  :
]]]

Can be matched by an interpretation in which 
<http://skolem.example#432oj34oij2o3ijo23j> and 
<http://booksRus.example/inv2001-06-25#item342323> indicate the same value.

The problem here seems to be one of computation rather than logic:  if 
*any* pair of constants must be tested to see if they match the same 
conditions, then the search space becomes impossibly large for a practical 
problem.  So the information you want to preserve would seem to be that 
only some of the names are to be considered as possibly equivalent to other 
names, in order that the query can be  resolved in reasonable time.


(2) Variable terms

The model theories I have seen distinguish between constant names and 
variable names:  the meaning of a constant name is defined entirely by an 
interpretation.  The meaning of a variable name is defined by the 
interpretation AND some variable substitution.

It seems to me that your "anonymous" node could be viewed as a node named 
by a variable.  The statement containing such a name would be satisfiable 
under a given interpretation iff there exists a substitution of a value in 
the domain of interpretation for the variable that makes the target 
expression true.

The query then becomes the problem of finding a variable substitution that 
satisfies an interpretation defined by the database.


#g
--


At 02:44 AM 6/25/01 -0500, Dan Connolly wrote:
>pat hayes wrote:
>[...]
> > The RDF distinction between anonymous nodes and named nodes is
> > logically invisible, as far as I can see.
>
>I have been convinced otherwise. I'm still not certain,
>but let's see if I can reproduce the argument
>and its ability to convince...
>
> > All nodes have an identity,
> > so giving one of them a URI doesnt really change anything about it or
> > what it means. All nodes could be non-anonymous and nothing would
> > change in the meanings of any RDF. Anonymity seems to be a kind of
> > syntactic sweetener which works by removing some bitterness rather
> > than by adding sugar.
>
>I think anonymous nodes have non-trivial expressive power.
>
>In sum: skolemization is *not* a two-way street:
>while a proof of a skolemized formula is generally
>accepted as a proof of the formula with existential
>quantifiers, it doesn't work the other way around.
>You lose information when you replace an
>existentially quanitified variable/term with
>a URI.
>
>In detail: let's suppose you're buying a book.
>You transmit, to the bookseller, a description
>of the book you want to buy; roughly,
>"it's by Barnsley and it's called
>Fractals Everywhere. I want it in
>hardback, tomorrow."
>
>Formally, in n-triples:
>
>---8<---
>_:g0 <http://purl.org/dc/elements/1.1/title> "Fractals Everywhere" .
>_:g0 <http://purl.org/dc/elements/1.1/creator> "Barnsley" .
>_:g0 <http://booksellers.example/vocab#binding>
><http://booksellers.example/vocab#hardback> .
>_:g0     <http://booksellers.example/vocab#shipping>
><http://booksellers.example/vocab#nextDay> .
>---8<---
>
>In KIF, by my understanding of anonymous nodes:
>
>---8<---
>(exists (?x0 )
>  (and
>   (PropertyValue http\:\/\/purl\.org\/dc\/elements\/1\.1\/title
>      ?x0
>      "Fractals Everywhere")
>   (PropertyValue http\:\/\/purl\.org\/dc\/elements\/1\.1\/creator
>      ?x0
>      "Barnsley")
>   (PropertyValue http\:\/\/booksellers\.example\/vocab\#binding
>      ?x0
>      http\:\/\/booksellers\.example\/vocab\#hardback)
>   (PropertyValue http\:\/\/booksellers\.example\/vocab\#shipping
>      ?x0
>      http\:\/\/booksellers\.example\/vocab\#nextDay)
>) )
>---8<---
>
>Now if I use something like Sergey's algorithm[1,2]
>to compute a URI for this anonymous term, I get
>something like:
>
>---8<---
><http://skolem.example#432oj34oij2o3ijo23j>
><http://purl.org/dc/elements/1.1/title> "Fractals Everywhere" .
><http://skolem.example#432oj34oij2o3ijo23j>
><http://purl.org/dc/elements/1.1/creator> "Barnsley" .
><http://skolem.example#432oj34oij2o3ijo23j>
><http://booksellers.example/vocab#binding>
><http://booksellers.example/vocab#hardback> .
><http://skolem.example#432oj34oij2o3ijo23j>
><http://booksellers.example/vocab#shipping>
><http://booksellers.example/vocab#nextDay> .
>---8<---
>
>i.e. in KIF:
>
>---8<---
>  (and
>   (PropertyValue http\:\/\/purl\.org\/dc\/elements\/1\.1\/title
>      http\:\/\/skolem\.example\#432oj34oij2o3ijo23j
>      "Fractals Everywhere")
>   (PropertyValue http\:\/\/purl\.org\/dc\/elements\/1\.1\/creator
>      http\:\/\/skolem\.example\#432oj34oij2o3ijo23j
>      "Barnsley")
>   (PropertyValue http\:\/\/booksellers\.example\/vocab\#binding
>      http\:\/\/skolem\.example\#432oj34oij2o3ijo23j
>      http\:\/\/booksellers\.example\/vocab\#hardback)
>   (PropertyValue http\:\/\/booksellers\.example\/vocab\#shipping
>      http\:\/\/skolem\.example\#432oj34oij2o3ijo23j
>      http\:\/\/booksellers\.example\/vocab\#nextDay)
>)
>---8<---
>
>Now suppose the bookseller's inventory database shows:
>
>---8<---
><http://booksRus.example/inv2001-06-25#item342323>
><http://purl.org/dc/elements/1.1/title> "Fractals Everywhere" .
><http://booksRus.example/inv2001-06-25#item342323>
><http://purl.org/dc/elements/1.1/creator> "Barnsley" .
><http://booksRus.example/inv2001-06-25#item342323>
><http://booksellers.example/vocab#binding>
><http://booksellers.example/vocab#hardback> .
><http://booksRus.example/inv2001-06-25#item342323>
><http://booksellers.example/vocab#shipping>
><http://booksellers.example/vocab#nextDay> .
>---8<---
>
>i.e.
>
>---8<---
>(and
>   (PropertyValue http\:\/\/purl\.org\/dc\/elements\/1\.1\/title
>      http\:\/\/booksRus\.example\/inv2001\-06\-25\#item342323
>      "Fractals Everywhere")
>   (PropertyValue http\:\/\/purl\.org\/dc\/elements\/1\.1\/creator
>      http\:\/\/booksRus\.example\/inv2001\-06\-25\#item342323
>      "Barnsley")
>   (PropertyValue http\:\/\/booksellers\.example\/vocab\#binding
>      http\:\/\/booksRus\.example\/inv2001\-06\-25\#item342323
>      http\:\/\/booksellers\.example\/vocab\#hardback)
>   (PropertyValue http\:\/\/booksellers\.example\/vocab\#shipping
>      http\:\/\/booksRus\.example\/inv2001\-06\-25\#item342323
>      http\:\/\/booksellers\.example\/vocab\#nextDay)
>)
>---8<---
>
>
>This information from the inventory database clearly
>provides a match (i.e. a proof, or the interesting
>bits of one, anyway) for the
>description of the book stated as a formula involving
>an existentially quantified variable, ?x0.
>
>But it doesn't match/prove the formula where _:g0
>is replaced by the skolem constant
><http://skolem.example#432oj34oij2o3ijo23j> .
>
>So an RDF document with anonymous nodes is *not*
>interchangeable with a skolemized version of that document.
>Q.E.D.
>
>
>I think this is the important part of Pat's message
>that I disagree with is:
>
> > RDF is supposed to
> > consist of assertions, not equations, and they are pretty simple
> > assertions of the logical form (V s o) . Those s's and o's are
> > logical names = logical constants, ie they denote things, one thing
> > each in a given interpretation. Now, logical names are *just* like
> > existentially quantified variables where the quantifers are at the
> > top level (the only level there is in RDF), ie not inside any
> > universal quantifiers.
>
>The s's and o's would be just logical constants if we
>left out anonymous/existentially-quantified terms.
>But RDF does have such terms, as demonstrated above.
>And the semantics of such terms is non-trivially
>different from the semantics of constants:
>an existentially quantified formula is satisfied
>by an interpretation if there's *some* thing
>you can bind the existential term to that makes
>it work out. Skolemizing the formula reduces
>the number of interpretations that satisify the
>formula. It's one of those things that usually
>works "without loss of generality," but doesn't,
>in the case of RDF; i.e. in the case when constant
>symbols that are shared between documents.
>
>
>
>
>p.s. This message is really about an existing issue
>http://www.w3.org/2000/03/rdf-tracking/#rdfms-identity-anon-resources
>
>The fact that there are graphs involving anonymous nodes
>that are not expressible in RDF/XML is, I agree, another
>issue; one that, I'm afraid, belongs in the
>postpone-to-next-version pile.
>
>[1] Re: RDF API 1.0 Draft / algorithm for anonymous URIs
>Sergey Melnik (Wed, 08 Dec 1999)
>http://lists.w3.org/Archives/Public/www-rdf-interest/1999Dec/0046.html
>
>[2] what I actually used was random scratching at the keyboard ;-)
>
>--
>Dan Connolly, W3C http://www.w3.org/People/Connolly/

------------------------------------------------------------
Graham Klyne                    Baltimore Technologies
Strategic Research              Content Security Group
<Graham.Klyne@Baltimore.com>    <http://www.mimesweeper.com>
                                 <http://www.baltimore.com>
------------------------------------------------------------

Received on Tuesday, 26 June 2001 07:15:48 UTC