W3C home > Mailing lists > Public > w3c-rdfcore-wg@w3.org > October 2001

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
To: jjc@hplb.hpl.hp.com
Cc: w3c-rdfcore-wg@w3.org
Message-Id: <OFCD0E2917.AC6A89A4-ON41256ADF.0052C1E7@bayer-ag.com>

[...]
> 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 EDT

This archive was generated by hypermail pre-2.1.9 : Wednesday, 3 September 2003 09:40:58 EDT