- From: Pat Hayes <phayes@ai.uwf.edu>
- Date: Mon, 8 Oct 2001 16:27:43 -0500
- To: Sergey Melnik <melnik@db.stanford.edu>
- Cc: 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! But what is the alternative? If we allow changes of bNode names and permutations of ordering, both of which seem reasonable, the same problems arise for Ntriples documents. >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?) I think we have thrashed this out to exhaustion, and decided that yes, we do. As soon as query and rule languages appear there are going to be things that are functionally indistinguishable from bNodes in any case, whatever we do. >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? That might be an attractive option. It could even be simply made as an observation, without having a requirement of bNode-acyclicity built into the spec. I don't think this is going to be a problem in practice, in any case; such a cycle cannot arise from interactions between graphs since it is invalid to identify bNodes across graph boundaries, so unless someone actually writes such a cycle, they should never happen. Pat PS. Now, if we were to allow anonymous arcs as well as nodes, I wonder..... >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 -- --------------------------------------------------------------------- IHMC (850)434 8903 home 40 South Alcaniz St. (850)202 4416 office Pensacola, FL 32501 (850)202 4440 fax phayes@ai.uwf.edu http://www.coginst.uwf.edu/~phayes
Received on Monday, 8 October 2001 17:27:47 UTC