Re: Refining Optionals

Andy, I don't see the connection with
http://lists.w3.org/Archives/Public/public-rdf-dawg-comments/2005May/0030.html
but anyhow, when I look to the example

Data:
:book :title "Title" .

Query:
SELECT ?x
WHERE
      {
        OPTIONAL { :book :title ?x }
      }

through N3 glasses, I see

--n3 a.n3
:book :title "Title" .

--filter f.n3
{:book :title ?X} => {(?X) a :Answer} .
{<a.n3>!log:semantics log:notIncludes {:book :title ?X}} => {(?X) a 
:Answer} .


and believe that spurious answers are best avoided
when we assume non-floundering queries (fyi see
http://www.cs.sunysb.edu/~warren/xsbbook/node58.html)
and so rewrite filter as

--filter f.n3
{:book :title ?X} => {(?X) a :Answer} .
{:book :title ?X. <a.n3>!log:semantics log:notIncludes {:book :title ?X}} 
=> {(?X) a :Answer} .

(we actually do this implicitly in our implementation now..)

-- 
Jos De Roo, AGFA http://www.agfa.com/w3c/jdroo/




"Seaborne, Andy" <andy.seaborne@hp.com>
Sent by: public-rdf-dawg-request@w3.org
27/06/2005 14:13
Please respond to andy.seaborne

 
        To:     RDF Data Access Working Group <public-rdf-dawg@w3.org>, Geoff Chappell 
<geoff@sover.net>
        cc:     (bcc: Jos De_Roo/AMDUS/MOR/Agfa-NV/BE/BAYER)
        Subject:        Refining Optionals



The handling of optionals needs to be refined - this isn't changing the 
test
cases and user problem that optionals solves, it a matter of getting a 
definition
that works.

There are no syntax changes, no test case changes.

These issues were pointed out by Geoff Chappell (included in the 
recipients of
this message).

http://lists.w3.org/Archives/Public/public-rdf-dawg-comments/2005May/0030.html
and thread.

== Problem

Data:
:book :title "Title" .

Query:
SELECT ?x
WHERE
      {
        OPTIONAL { :book :title ?x }
      }

in other words, a single optional.

Solutions: (desired)
?x = "Title"

But these are also solutions:
?x = "Junk"   - where a variable used in an optional has a spurious value
?x = unbound  - where a variable used in an optional is also unbound.

because OPTIONAL is defined as "P or not(P)". The alternative form of 
optional
"P or true" also has similar issues.

== Requirement

The requirement is to make some condition on the set of solutions so that
spurious solutions are not included.  It's not a matter of tweaking the 
Optional
definition of what makes a solution.

== Approach

Everything appears in groups in the syntax; the definitions don't force 
this but
a graph pattern P and a group of one pattern {P} have the same solutions.

First, canonicalize groups: rewrite unions as two parts, each of which 
have to be
solved, and remove groups in groups.  Collect all basic patterns in a 
group
together to give a canonical form:

BP, F, Opt1, Opt2, ....

for basic pattern BP, F is a combined filter, from the UNION branchs or 
direct
subgroups, and OPTIONALs Opt1, ... (Filters in optionals stay with their 
patterns).

BP may be the empty set.  { OPTIONAL { :book :title ?x } } for example.

We define {} to have one solution with no variables.

So we have to provide a definition for groups with optionals.  If BP 
involves
?x, then the cases of "?x = junk" and "?x = unbound" don't matter. We do 
not
need to consider the case where ?x occurs in BP any further.

== Outline

This is an informal description of definitions : it will need formalizing.

We also require that in a group:

?x = "junk"
For this, we require that if ?x is not mentioned in BP then ?x solves the
pattern of one of Opt1, Opt2 so writing Opt1 = OPTIONAL(P1) then ?x is a
solution of some Pi.

?x = unbound
If ?x occurs in some Pi and BP.Pi has a solution, then a solution with ?x
unbound is not considered a solution of the group.

This looks as if it can be combined in to a condition for a group solution 
S 
involving ?x, where ?x is mentioned in some optional Opt(Pi), then ?x is a 

solution BP.Pi or no BP.Pj has a solution and ?x is unbound.  This is now 
defining optional as a "solution extension" to solutions of the basic 
pattern in 
the group.


Details still need to be worked out but I'd appreciate comments and 
feedback on 
the approach.

                 Andy

Received on Tuesday, 28 June 2005 09:48:16 UTC