W3C home > Mailing lists > Public > public-rdf-dawg@w3.org > April to June 2005

Re: Restructure definition of Basic Graph Pattern and pattern match (sec 2.4)

From: Dan Connolly <connolly@w3.org>
Date: Thu, 09 Jun 2005 12:05:13 -0500
To: Jeen Broekstra <jeen@aduna.biz>
Cc: RDF Data Access Working Group <public-rdf-dawg@w3.org>
Message-Id: <1118336713.12287.387.camel@localhost>

On Thu, 2005-06-09 at 14:54 +0200, Jeen Broekstra wrote:
> SPARQL language editor's draft rev 1.379
> http://www.w3.org/2001/sw/DataAccess/rq23/
> 
> In section 2.4 the terms 'Pattern Solution', 'Query Solution' and
> 'Basic Graph Pattern' are defined,
> 
> The definition of Basic Graph Pattern includes what it means to match
> against a graph. It would be better to create a separate definition
> for this, called 'Graph Pattern Match'. The definition of 'Basic Graph
> Pattern' can then be moved to the start of the section, and in any
> case I think an explicit definition of pattern match, that links graph
> patterns to solutions, is a lot clearer.
> 
> Also, the current definition of a match is imprecise. It uses the
> notion 'entails' without specifying what that means. Is that simple
> entailment, RDF(S) entailment, or an entirely different, more loose
> form of entailment? I request instead using the notion of 'subgraph'
> for defining a match.

I was under the impression that simple entailment and subgraph
meant the same thing, but I just double-checked, and not so...

"A subgraph of an RDF graph is a subset of the triples in the graph."

the lemma that relates them also includes the notion of instance...

"The main result for simple RDF inference is:

Interpolation Lemma. S entails a graph E if and only if a subgraph of S
is an instance of E."
 -- http://www.w3.org/TR/2004/REC-rdf-mt-20040210/#entail

The difference is observable from an approved*** test
  http://www.w3.org/2001/sw/DataAccess/tests/#dawg-triple-pattern-001

input:
 :x :p :v1 .
 :x :p :v2 .

query:
  SELECT *
WHERE { :x ?p ?q . }

By the simple-entailment definition, there are solutions that bind
?p to _:foo, but there are no such results in the test results.
I suppose it's possible that the spec could prune the results
down to the ones in the test suite some other way, but I can't
think of any other straightforward way just now.

> Suggested definitions:
> 
>    Definition: *Basic Graph Pattern*
> 
>    A /basic graph pattern/ is a set of Triple Patterns.
> 
>    Definition: *Graph Pattern Match*
> 
>    A graph pattern /matches/ on a graph G with pattern solution S iff
>    S(GP) is a non-empty subgraph of G.

Yes, but... why non-empty? Consider:

 SELECT * where {}.

In the case of the empty solution (i.e. empty set of bindings),
S(GP) is just GP, which is empty. We want that to be a match,
right? i.e. ASK where {} always gives yes, right?

Hmm... I think all solutions work at this point, but they all
get projected down to the one solution with no bindings. Yes...

 The syntax SELECT * is shorthand for "select all the named variables".

Hmm... that's defined syntactically... is the syntactic case of
no variables allowed by the grammar? No...
  'SELECT' ( 'DISTINCT' )? ( ( Var )+ | '*' ) 

So the semantics of SELECT * in the case of no vars should be
explicitly specified:

 The syntax SELECT * is shorthand for "select all the named variables".
 In the case no variables are named in the query, the set of variables
 is empty.



*** I had to do quite a bit of spelunking to find the record of our
decision to approve this test; I thought the manifests had links
to meeting records, or at least approval dates. It would be nice
if they did, going forward. It would be even nicer if I could
follow links from the HTML test cover page to the meeting records.

We made the relevant decision on 2004-11-30:

ACCEPTED simple test cases (1-4) with the correction of 
foaf:knowns=>foaf:knows
Abstained: Kendall (has not read them)
http://lists.w3.org/Archives/Public/public-rdf-dawg/2004OctDec/0394.html

though we later amended the test case per punctuationSyntax
on 15 March
http://lists.w3.org/Archives/Public/public-rdf-dawg/2005JanMar/0358.html

-- 
Dan Connolly, W3C http://www.w3.org/People/Connolly/
D3C2 887B 0F92 6005 C541  0875 0F91 96DE 6E52 C29E
Received on Thursday, 9 June 2005 17:05:16 GMT

This archive was generated by hypermail 2.3.1 : Tuesday, 26 March 2013 16:15:23 GMT