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

Re: A proposal for entailment tests

From: Sergey Melnik <melnik@db.stanford.edu>
Date: Fri, 05 Oct 2001 17:37:50 -0700
Message-ID: <3BBE525E.C13BA101@db.stanford.edu>
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 EDT

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