- From: Graham Klyne <gk@ninebynine.org>
- Date: Fri, 13 Jun 2003 22:10:16 +0100
- To: pat hayes <phayes@ihmc.us>, Jeremy Carroll <jjc@hplb.hpl.hp.com>
- Cc: w3c-rdfcore-wg@w3.org
At 14:20 13/06/03 -0500, pat hayes wrote: >One does not need to get into the subgraph problem. The only question you >have to ask is, is this triple redundant? The way to find that out is to >see if it can be instantiated into another triple in the graph, which can >take at most one check per other triple. If it can, then delete it, >remember the instance mapping, and start again from the top. If it can't, >try the next triple. You can detect irredundancy in n|2 checks of one >triple instantiating another. Hmmm... what am I missing?: ex:s1 ex:p1 _:b1 (1) _:b1 ex:p1 _:b2 (2) _:b2 ex:p1 ex:o3 (3) So the triple (2) can be instantiated as either (1) or (3), so it's redundant, hence can be deleted. But in so doing, we lose the information that there is a graph path: ex:s1 --ex:p1-> ? --ex:p1-> ? --ex:p1-> ex:o3 #g -- BTW, Jeremy, is there an easy and efficient way to use your graph isomorphism algorithm to determine if G1 is isomorphic to a subgraph of G2? ------------------- Graham Klyne <GK@NineByNine.org> PGP: 0FAA 69FF C083 000B A2E9 A131 01B9 1C7A DBCA CB5E
Received on Friday, 13 June 2003 17:21:20 UTC