- From: Sergey Melnik <melnik@db.stanford.edu>
- Date: Fri, 05 Oct 2001 17:37:50 -0700
- To: Pat Hayes <phayes@ai.uwf.edu>
- CC: jos.deroo.jd@belgium.agfa.com, jjc@hplb.hpl.hp.com, w3c-rdfcore-wg@w3.org
Pat Hayes wrote: > > > > >> One note: the current "equality" tests are computational less expensive than > >> an rdf entailment test. Technically it is the difference between Graph > >> Isomorphism and SubGraph Isomorphism. GI is thought to be strictly between P > >> and NP where SubGraph Iso is known to be NP. The requirement to check for graph isomorphism in order to determine equality sounds just horrible! A simple implementation (which, due to lazyness may be favored by many developers) might require O(N!) operations in the number of bNodes. This is prohibitive even for N=15 bNodes in the two graphs. Wrt above, two questions: 1. Do we really need bNodes? (I am still missing a convincing argument given the added complexity in MT and implementations. Any pointers?) 2. As far as I remember, RDF/XML serialization does not allow cycles made entirely of bNodes. In this case, only tree isomorphism is required, which is logspace (easier than polynomial). Would this be an option? Sergey > >> For these reason it may be desirable to either: > >> + add rdfEquivalent and rdfsEqualivalent predicates > >> or make sure we use cycles, and suggest that users of the test cases should > >> search for such cycles if they have a GI algorithm available. > > > >i lean more towards the cycles... > >but can live with equivalent > > I also prefer to stick with cycles for now. Even if we allow > rdfEquivalent, we would still need to check for the cycles in any > case (no way to mandate against a valid inference); and I don't think > these graphs are going to get so big that the complexity is really > going to hurt anyone. > > Pat
Received on Friday, 5 October 2001 20:25:36 UTC