From: Graham Klyne <gk@ninebynine.org>

Date: Tue, 10 Jun 2003 11:11:28 +0100

Message-Id: <5.1.0.14.2.20030610103031.030f38a8@127.0.0.1>

To: pat hayes <phayes@ihmc.us>, w3c-rdfcore-wg@w3.org

Date: Tue, 10 Jun 2003 11:11:28 +0100

Message-Id: <5.1.0.14.2.20030610103031.030f38a8@127.0.0.1>

To: pat hayes <phayes@ihmc.us>, w3c-rdfcore-wg@w3.org

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 CB5EReceived on Tuesday, 10 June 2003 06:24:39 EDT

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