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

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

This archive was generated by hypermail 2.4.0 : Friday, 17 January 2020 20:24:05 UTC