ISSUE-86: Incompatible definitions of “graph equivalence†between RDF Concepts and RDF Semantics
GraphIsomorphism
Incompatible definitions of “graph equivalence†between RDF Concepts and RDF Semantics
- State:
- CLOSED
- Product:
- RDF Concepts
- Raised by:
- Richard Cyganiak
- Opened on:
- 2012-05-01
- Description:
- 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?
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 - Related Actions Items:
- No related actions
- Related emails:
- Re: RDF-ISSUE-86 (GraphIsomorphism): Incompatible definitions of “graph equivalence†between RDF Concepts and RDF Semantics [RDF Concepts] (from phayes@ihmc.us on 2012-05-01)
- Re: RDF-ISSUE-86 (GraphIsomorphism): Incompatible definitions of “graph equivalence†between RDF Concepts and RDF Semantics [RDF Concepts] (from david@3roundstones.com on 2012-05-01)
- RDF-ISSUE-86 (GraphIsomorphism): Incompatible definitions of “graph equivalence†between RDF Concepts and RDF Semantics [RDF Concepts] (from sysbot+tracker@w3.org on 2012-05-01)
Related notes:
The WG resolved to accept the proposal above:
http://www.w3.org/2011/rdf-wg/meeting/2012-05-02#resolution_4
This is implemented in the RDF Concepts ED.
Display change log