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

Dan,

After thinking a bit more about this I think that "entails" doesn't add anything 
and does appear to cause some confusion.

Queries can operate over a graph and its entailments (as virtual triples) so 
"subgraph" match for pattern match is then the same as entailment.  This is more 
conistent with the treatment for inference and datatype processing.


RDF concepts mentions subgraphs.
http://www.w3.org/TR/2004/REC-rdf-mt-20040210/#graphdefs
[[
A subgraph of an RDF graph is a subset of the triples
in the graph. A triple is identified with the singleton
set containing it, so that each triple in a graph is
considered to be a subgraph. A proper subgraph is a
proper subset of the triples in the graph.
]]
and
[[
Subgraph Lemma. A graph entails all its subgraphs.
]]

Is there an example to show how "entails" leads to something different?  If not, 
then sticking with "subgraph" makes for clarity.

 Andy


Seaborne, Andy wrote:
> 
> 
> 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 Friday, 3 December 2004 14:55:23 UTC