(sub)Graph isomorphism and SPARQL tests

Hi Eric

I spent a day thinking about subgraph isomorphism last week.
The results were largely negative, and apply to the SPARQL testing 
question you asked me a while ago.

In as much as SW concerns are about semantics, the syntactic operations 
involved in (sub)graph isomorphism are inappropriate.

For query language issues this is shown most clearly in a triple not 
getting used up if it matches. e.g. comparing

<a> <b> <c> .
<a> <b> _:d .


with

<a> <b> <c> .
_:e <b> <c> .

these two mutually entail one another but have no sub-graph isomorphism 
relationship between them. This sort of example can easily be mapped 
into QL concerns (e.g. adding a ?x node into one of the graphs), or 
thinking of the graph as a query result in some way.

Sorry, I think this is a blank.

However, Herman ter Horst's work on RDF(S) entailment does show that it 
is plausible to build a SPARQL test suite in terms of simple entailment. 
(See Herman's ISWC paper)

Jeremy

Received on Wednesday, 8 December 2004 15:29:34 UTC