- 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