- From: <jos.deroo.jd@belgium.agfa.com>
- Date: Sat, 6 Oct 2001 17:54:47 +0100
- To: melnik@db.stanford.edu
- Cc: phayes@ai.uwf.edu, jjc@hplb.hpl.hp.com, w3c-rdfcore-wg@w3.org
> 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?) yes > 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? I think it is that what we are doing in our current implementation. We do tests with 100K bNodes in the order of seconds. -- Jos
Received on Saturday, 6 October 2001 11:57:14 UTC