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

Re: A proposal for entailment tests

From: Pat Hayes <phayes@ai.uwf.edu>
Date: Mon, 8 Oct 2001 16:27:43 -0500
Message-Id: <p05101010b7e7c63c94bc@[205.160.76.193]>
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 EDT

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