- From: pat hayes <phayes@ihmc.us>
- Date: Mon, 16 Jun 2003 16:53:41 -0500
- To: Jeremy Carroll <jjc@hpl.hp.com>
- Cc: w3c-rdfcore-wg@w3.org
>Jeremy:
>>Let the nodes of R = V(G) U V(H) U { g, h, x } (all distinct blank nodes)
>>
>>Let the triples of R all have predicate rdf:value (which we will omit)
>>
>>Let the triples of R be E(G) U E(H) U { <g, g'> | g' in V(G) }
>> U { <h, h'> | h' in V(H) } U { <x, g>, <x, h> }
>
>
>Pat:
>> But not necessarily the reverse.
>(that is true ...)
>
>> For example let G be
>> <a b> <b c> <c a>
>> and H be
>> <d e> <e f> <d f>
>> then the instance a=d and b=e gives a redundancy (instance which is a
>> proper sub-RDFgraph)
>
>????
OK, I see my error. Never Mind.
>
>irredunancy is not a local phenomenon
Quite. Because although instantiation is transitive and so is
subgraph, it can still be the case that an instance of a non-subgraph
instance is a subgraph. So there is no cheap way to avoid doing a
check of all subgraphs; which is NP. I was under the delusion that
one could search by backtracking down the instances, but that will
miss some cases. Still might be room for a cleverer algorithm, but
maybe I wont try to solve P+NP this week.
>- I need to work on my NP completeness
>proof but you've more work to do on your P proof!
>
>(Note to rest of group these pairs are in fact triples with a missing
>rdf:value in the middle; and all the nodes are blank - this might have
>something to do with RDF)
It means that being a lean graph is potentially a very costly
property to check, whereas I thought it was fairly trivial. Which
means that in general, checking non-entailment between two graphs is
potentially expensive.
Pat
--
---------------------------------------------------------------------
IHMC (850)434 8903 or (650)494 3973 home
40 South Alcaniz St. (850)202 4416 office
Pensacola (850)202 4440 fax
FL 32501 (850)291 0667 cell
phayes@ihmc.us http://www.ihmc.us/users/phayes
Received on Monday, 16 June 2003 17:53:49 UTC