- From: Jeremy Carroll <jjc@hplb.hpl.hp.com>
- Date: Tue, 9 Oct 2001 11:14:06 +0100
- To: "Pat Hayes" <phayes@ai.uwf.edu>
- Cc: <w3c-rdfcore-wg@w3.org>
Jeremy: > >+ equivalence of RDF graphs is NP complete Pat: > Presume you mean semantic equivalence, ie A equivalent B means: A > entails B and B entails A (?) Yes. Jeremy: > >So the "graphs are sets?!" thread was triggered by my observation that an > >ntriple file with two identical triples > > > >A: > > > ><uri> <pred> <uri2> . > ><uri> <pred> <uri2> . > > > >was equivalent to one with only one: > > > >B: > > > ><uri> <pred> <uri2> . Pat: > They are certainly equivalent in the sense that each entails the > other. I thought what we were discussing was whether we even want to > allow the first one as a well-formed graph. > It *is* a well-formed N-Triples file. Jeremy: > > > >I am unclear as to whether these are theoretical difficulties that can > >safely be ignored; or real practical difficulties that should be > addressed > >by fundamental changes to the model theory. Pat: > > I don't think that they are too surprising, and that we shouldnt > *worry* about them. There is no way to get past them in any case by > changing the model theory; we would have to abandon anonymous nodes > altogether in order to get rid of the subgraph-isomorphism property. > Even if we used Ntriples documents with bNodes, there is always the > possibility of permuting the bNode labels, and that gives us the > leeway to encode graph isomorphism. I will need to think about this some more - may there be some other understanding of anonymous nodes that has better worst case tractability? An example of such an understanding would be that an anonymous node stands for a one-time use gensym URI; and each time you read a file you get a different one. It makes it hard to use anonymous nodes, but they then are a purely syntactic macro and at the higher levels everything is more tractable. I *do not* advocate this - it is bonkers since a file does not even equal itself in any useful sense! Jeremy
Received on Tuesday, 9 October 2001 06:14:24 UTC