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 Monday, 27 June 2005 12:13:47 UTC