- From: David Wood <david@3roundstones.com>
- Date: Tue, 1 May 2012 17:23:00 -0400
- To: RDF Working Group <public-rdf-wg@w3.org>, RDF Working Group Issue Tracker <sysbot+tracker@w3.org>

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