RE: Refining Optionals

> -----Original Message-----
> From: Seaborne, Andy [mailto:andy.seaborne@hp.com]
> Sent: Thursday, July 07, 2005 11:27 AM
> To: Geoff Chappell
> Cc: 'RDF Data Access Working Group'; Pat Hayes
> Subject: Re: Refining Optionals
> 
> 
> 
> Geoff Chappell wrote:
> >
> >>-----Original Message-----
> >>From: Seaborne, Andy [mailto:andy.seaborne@hp.com]
> >>Sent: Tuesday, July 05, 2005 5:00 AM
> >>To: Geoff Chappell
> >>Cc: 'RDF Data Access Working Group'
> >>Subject: Re: Refining Optionals
> >>
> >
[...]
> 
> The more I think about it, the more I'm unsure we can sort this out in
> time.
> 
> We have a way of talking about the "Junk" case - although as ?v may appear
> in a
> different position, creating a set of spurious terms from the model, I am
> a
> little nervous of this still.
> 
> It's the unbound case that I still can't get straight.  We are talking
> about
> whether a negated pattern involving unbound variables does or does not
> match a
> graph.  As match is defined as subgraph, anything involving variables
> never
> matches.  The negation always is true - the !P case always admits a
> solution.
>
> As I read your expansion rules above:
> optional { :x :p ?v }
> { :x :p ?v } UNION NOT { :x :p ?v }
> 
> but ?v = unbound is not a solution to  { :x :p ?v } so NOT { :x :p ?v } is
> true
> and hence that is a solution.  I must be missing something.

An unbound var in a solution can be substituted with any RDF-T and the
solution will still be valid. Do you agree with that? I agree the current
definitions don't support the unbound case (however they do seemingly
support the replace-the-unbound-with-all-RDF-T case which means that a query
with an optional could have an infinite number of solutions) -- that
suggests to me a problem with the definition of matching or the definition
of solution, not a problem with the use of unbounds in solutions.

> 
> This approach is based on filtering the space of all possible solutions to
> find
> the solutions that match the query.  There was the alternative approach
> for
> defining SPARQL which to build the solutions up from basic patterns.
> Unbound
> variables never appear in basic pattern matches.
> 
> Instead of approaching the set of solutions from above (considering all
> possible
> solutions and narrowing it down to the ones that match), it is approaching
> the
> set of solutions from below (starting with nothing and creating more
> complex
> sets of solutions).
> 
> Both approachs should get to the same place.
>
> The biggest difference is in the treatment of optionals.  They are better
> handled as a binary operator "A opt B", capturing the idea that optionals
> extend
> another solution where possible.
> 
> A compositional approach would be:
> 
> --------------
> 
> Basic Patterns (no change)
> Subgraph match.  Only include the variables that matter in a solution.
> 
> Union: (no change)
> Union of the sets of solutions of subpatterns.
> 
> Optionals:
> S is a solution to A opt B if:
>      S is a solution of A.B else S is a solution n of A
> 
> The use of "else" here forces the choice.
> 
> Group:
> The composition of the subpatterns.
> 
> The empty group {} has one solution with no variable bindings.
> This is the seed condition and defines { optional {...} }
> 
> A group of one pattern has solutions of that one pattern.
> 
> Define G(A,B) as the group combination of two patterns.
>     if B is a basic pattern, union, another group:
>        G(A,B) has solution S if S is a solution to A and to B.
>     if B is an optional Opt(P)
>        G(A,B) has solution S
>           if is a solution of G(A,P)
>           else S is a solution of A and not of P.
>     if B is a filter F
>        G(A,F) has solution S if S is a solution to A and F(S) is true.
> 
> Define a solution S of group pattern GP = G1, G2, ... as G(group{G1, G2,
> ..},Gn)
> 
> --------------
> 
> That is order dependent.  That could be relaxed by defining it as
> 
>       G(group{Gi i!=j}, Gj)
> 
> which is every order.  Implementation like that is not advised :-)
> Realistically, doing all the fixed parts, then the optionals, spotting any
> order
> dependences (optionals with shared variables that do not occur in a fixed
> part)
> is doable.
> 
> Filters "out of order" would give nothing (undefined variables) with the
> exception of FILTER bound(?x).

It seems to me you'd have more work to prove this is a valid definition than
to just do the slight extra necessary to round out your current definitions.
 
> It leaves it open to provide an alternative set of definitions that are
> based on
> the framework you outline.  It will take time to get consensus around such
> an
> approach (especially with negation and unbound variables being very
> significant
> in how they work).

Won't it take some time for any real solution? It seems like you either have
to take that time or punt on what are valid solutions when optionals are
involved.

> 	Andy

Rgds,

Geoff

Received on Sunday, 10 July 2005 19:35:50 UTC