Re: A proposal for entailment tests

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