Re: RDF-ISSUE-86 (GraphIsomorphism): Incompatible definitions of “graph equivalence” between RDF Concepts and RDF Semantics [RDF Concepts]

On May 1, 2012, at 10:41, RDF Working Group Issue Tracker wrote:

> RDF-ISSUE-86 (GraphIsomorphism): Incompatible definitions of “graph equivalence” between RDF Concepts and RDF Semantics [RDF Concepts]
> 
> http://www.w3.org/2011/rdf-wg/track/issues/86
> 
> Raised by: Richard Cyganiak
> On product: RDF Concepts
> 
> RDF Concepts defines the term “graph equivalence”. RDF Semantics defines the term “equivalent”. I think the two definitions are not quite compatible. The RDF Concepts definition coincides with RDF Semantics *only* under simple entailment. In more advanced forms of entailment, graphs that are not equivalent according to the RDF Concepts definition are in fact equivalent according to RDF Semantics.
> 
> The notion of equivalence defined in RDF Semantics is more general and sensible to me.
> 
> I think the best way to resolve this is to *rename* the definition in RDF Concepts, while keeping its unchanged.
> 
> The most technically correct name would perhaps be something like “simple graph equivalence”, but I note that the term “graph isomorphism” is already frequently used in the community to denote exactly the concept we're after (see e.g. Jena's Model.isIsomorphicWith() method), and is in fact a nicely descriptive term for what's actually being defined.
> 
> What do people think about:
> 
> 1. renaming “graph equivalence” to “graph isomorphism” in RDF Concepts, and
> 2. adding a sentence in the RDF Semantics section on simple entailment, stating that isomorphic graphs are equivalent under simple entailment?


+1 from me unless Pat or Peter object.  Thanks, Richard.

Regards,
Dave

> 
> 
> This is the definition of “graph equivalence” from RDF Concepts:
> 
> [[
> Graph equivalence: Two RDF graphs G and G' are equivalent if there is a bijection M between the sets of nodes of the two graphs, such that:
> 
> 1. M maps blank nodes to blank nodes.
> 2. M(lit)=lit for all RDF literals lit which are nodes of G.
> 3. M(uri)=uri for all IRIs uri which are nodes of G.
> 4. The triple ( s, p, o ) is in G if and only if the triple ( M(s), p, M(o) ) is in G'
> 
> With this definition, M shows how each blank node in G can be replaced with a new blank node to give G'. A definition of graph equivalence is needed to support the RDF Test Cases [RDF-TESTCASES] specification.
> ]]
> http://dvcs.w3.org/hg/rdf/raw-file/default/rdf-concepts/index.html#dfn-graph-equivalence
> 
> This is the definition of “equivalent” from RDF Semantics:
> 
> [[
> Equivalent (prep., with to) True under exactly the same conditions; making identical claims about the world, when asserted. Entails and is entailed by.
> ]]
> http://www.w3.org/TR/2004/REC-rdf-mt-20040210/#gloss
> 
> 
>

Received on Tuesday, 1 May 2012 21:23:29 UTC