W3C home > Mailing lists > Public > w3c-rdfcore-wg@w3.org > October 2001

Re: A proposal for entailment tests

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
Message-Id: <OF560F7F4A.EFA3F0DA-ON41256ADD.005BE2D5@bayer-ag.com>


> 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 EDT

This archive was generated by hypermail pre-2.1.9 : Wednesday, 3 September 2003 09:40:57 EDT