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

From: <jos.deroo.jd@belgium.agfa.com>
Date: Tue, 9 Oct 2001 00:56:27 +0100

```
[...]
> A:
>
> <uri> <pred> <uri2> .
> <uri> <pred> <uri2> .
>
> was equivalent to one with only one:
>
> B:
>
> <uri> <pred> <uri2> .
>
>
> This was intended as a harmless sort of comment :-(.
> It was motivated by the graph abstract syntax.
>
> Under the model theory, we would say that two graphs are equivalent if they
> mutually entail one another.
> This would mean - wait for it Aaron :) - that
>
> C:
>
> <uri> <pred> <uri2> .
> <uri> <pred> _:bnode .
>
> was another version of the same RDF model (if not the same RDF graph!).
> From a model theoretic point of view A B and C are all equivalent.
> This follows from the bnode being taken as an existentially qualified
> variable.
>
> I assume that it would, in the fullness of time, be desirable to determine a
> canonical RDF graph for any particular equivalence class of RDF graphs, for
> instance, the equivalence class containing graphs corresponding to A, B, and
> C would have canonical form B. This paragraph refers to the graph not to a
> serialization of the graph. The canonicalization of the serialization of a
> graph is known to be graph isomorphism complete.
>
>
> If we consider an extension of C being:
>
> D:
>
> <uri> <pred> <uri2> .
> <uri> <pred> _:bnode .
> _:bnode <pred> _:bnode2 .
>
> then we can no longer ignore the second triple, since it is saying something
> more substantive than the second triple in C.

(after some bug corrections) we currently find that
A simple-entails A
A simple-entails B
A simple-entails C
B simple-entails A
B simple-entails B
B simple-entails C
C simple-entails A
C simple-entails B
C simple-entails C
D simple-entails A
D simple-entails B
D simple-entails C
D simple-entails D
and we *fail* to find that
A simple-entails D
B simple-entails D
C simple-entails D

--
Jos
```
Received on Monday, 8 October 2001 18:58:59 UTC

This archive was generated by hypermail 2.3.1 : Wednesday, 7 January 2015 14:53:52 UTC