Re: blank nodes out the wazoo

At 16:42 09/06/03 -0500, pat hayes wrote:
>While fixing a silly mistake in the MT document, I noticed the following. 
>We require that RDF graphs contain no redundancies in the sense that the 
>same triple cannot occur more than once in the graph. However, they can 
>contain redundancies in the sense that a triple with a bnode in it can be 
>duplicated with a different bnode, even though the resulting triples would 
>look the same in a graph diagram. The resulting graph has no extra 
>information in it, but this quirk allows an RDF graph to have infinitely 
>many consequences. For example, a single triple
>
>a p b .
>
>has infinitely many consequences;
>
>_:x p b .
>a p _:y .
>_:z1 p _:z2 .
>_:z3 p _:z4 .
>-:z5 p _:z6 .
>....
>
>where all these bnodes are distinct; see attached jpeg.
>
>My question is, does the WG feel that it might be worth ruling this out as 
>a syntactic possibility? If this kind of bnode-duplication were ruled out, 
>then the set of graphs simply entailed by any RDF graph would be 
>finite.  That would generalize the no-duplicate-triples condition implicit 
>in our definition of a graph as a set, to treat triples which 'look' the 
>same when you erase the bnode labels as though they literally were the same.

 From an implementation perspective, I'd be concerned about ruling out 
redundant bnode triples as syntactically disallowed.  I think this would 
make the implementation of merging two syntactically-valid graphs very much 
more difficult (but not impossible).

Is there not an approach you can follow more similar to your use of "tidy" 
RDF graphs, in which you demonstrate that for any RDF graph there is a 
minimum reduced form of that graph that is semantically equivalent, and 
then base your developments and proofs on that form?

Hmmm... maybe it's not that easy.  Consider:

    ex:s ex:p1 _:a
    ex:s ex:p2 _:a
    ex:s ex:p2 _:b
    ex:s ex:p3 _:b

how does one tell that the
    ex:s ex:p2 _:a
    ex:s ex:p2 _:b
are not redundant?   I think it is, at least, necessary to reason over the 
graph as a whole rather than isolated triples.

E.g. defining auxiliary functions:

    usePart a G
    notPart a G

whose values are the subgraphs of G each of whose triples contain / do not 
contain the node 'a' in some role, and

    [a/b]G

whose value is G with every occurrence of 'a' replaced by 'b', one can 
define some conditions on reducibility of a graph:

if   [_:a/_:b]usePart _:a G  `subset`  usePart _:b G

then (notPart _:a G) is semantically equivalent to G.   (Proof 
sketch:  suppose there is an interpretation that makes G true, then 
(usePart _:b G) is true for some denotation of _:b (by conjunction and defn 
of interpretation), then the same value used as a value for _:a and _:b 
makes (usePart _:a G) true.  Hence the truth of (usePart _:a G) under any 
interpretation does not change the truth of G under the same interpretation.)

And so on.

I think that as soon as one does not reason in terms of the graph as a 
whole, such conclusions cannot be drawn, because it's always possible that 
there's some other triple in the graph that makes a selected subset 
non-redundant for some interpretation.

#g


-------------------
Graham Klyne
<GK@NineByNine.org>
PGP: 0FAA 69FF C083 000B A2E9  A131 01B9 1C7A DBCA CB5E

Received on Tuesday, 10 June 2003 06:24:39 UTC