Re: "entails" clearer than "subgraph" in defn Graph Pattern Match

Seaborne, Andy wrote:
> 
> 
> Dan Connolly wrote:
> 
>>I'm going over the definitions, and in the case of...
>>
>>"Graph Pattern GP matches RDF graph G with substitution S if S(GP) is a
>>subgraph of G."
>>
>>I think entails is clearer:
>>
>>"Graph Pattern GP matches RDF graph G with substitution S if G
>>simply entails S(GP)."
> 
> 
> OK - done v1.139
> 
>  Andy
> 
> 
>>with simply entails linked to
>> http://www.w3.org/TR/rdf-mt/#defentail
>>
>>
>>p.s. a public comment asked
>>"which definition of subgraph does SPARQL use - the standard one from
>>graph
>>theory or the expansive one used in RDF semantics in the presence of bnode
>>relabelling?"
>>http://lists.w3.org/Archives/Public/public-rdf-dawg-comments/2004Oct/0003.html
>>
>>it's the one with relabelling. So subgraph is perhaps misleading.
>>

I'm not so sure now - let me run through an example.

Data graph G:
     <a> <b> <c> .
Pattern P:
     (?x <b> <c>)

Test case: is below a pattern solution?  It's logically equivalent (but we would 
have define logical equivalence of result sets as this isn't RDF here):

   ?x = _:z

Defined as entailment then the answer would be "yes" because G simply-entails

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

We have a choice: define matching based on entailment (choice of levels of 
entailment) or we can define match based on subgraph, a subset of the triples 
(traditional graph theory definition given RDF graphs don't have an explicit set 
of graphs nodes).

Using subgraph would preclude the case ?x = _:z and avoid needing to write our 
own definitions of logical equivalence.  Even simple entailment introduces new 
solutions.

A result set is defined as the set of all solutions so
   ?x = _:z
   ?x = <a>
(which is fine technically - it's a logically equivalent graph)

We can use subgraph here - the matching is being defined purely as a graph 
matching, depending on the graph being queried.  There is one solution in the 
result set.

If the graph being queried is a closure under some set of rules, the query will 
see these.  This is pushing entailment to the graph, out of the query language, 
which we already do for controlling whether RDFS-closure rules are applied.  I 
think subgraph is clearer because a result set of a single substitution is 
correct and natural:

   ?x = <a>

So I see the question as "what is the advantage of defining as simple entailment 
  over defining as subgraph"?  What's the test case?

- - - - - -

This also links with the proposal to change the definition of triple pattern to 
be uniform because it heads in the direction of having entailments where the 
predicate is replaced by a bNode.  Entailment over the space defined by triples 
of RDF terms isn't RDF.  It's easy to see how that would be defined but would 
should define "entailment" for DAWG defined spaces.  Subgraph removes the need.

- - - - - -

Testing defines a pass with the text:

"""
A test passes if the graph from the action is logically equivalent to the graph 
named in the result. "Logical equivalence " can be tested by eliminating 
redundant bNodes in both graphs and testing if the graphs are isomorphic: same 
shape, same labels.
"""

What's the formal definition of redundant?  I can't find it in RDF concepts or 
RDF semantics.

 Andy

Received on Wednesday, 24 November 2004 16:11:59 UTC