RE: NP completeness & rdf entailment, graph identity, MT etc.

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