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

On Thu, 2005-06-09 at 14:54 +0200, Jeen Broekstra wrote:
> SPARQL language editor's draft rev 1.379
> 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."

The difference is observable from an approved*** test

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

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 
Abstained: Kendall (has not read them)

though we later amended the test case per punctuationSyntax
on 15 March

Dan Connolly, W3C
D3C2 887B 0F92 6005 C541  0875 0F91 96DE 6E52 C29E

Received on Thursday, 9 June 2005 17:05:16 UTC