Optionals and execution order

Re: ACTION AndyS: to propose test case re optionals and ordering

Before I get to test cases, I'd like to describe the problem.


==== Data:

@prefix :        <http://example.org/ns#> .

:z    :q          "z-q-1" .

:x    :p          "x-p-1" ;
        :q          "x-q-1" ;
        :r          "x-r-1" .

:y    :p          "y-p-1" .

== Query 1:

---------------------------

PREFIX  : <http://example.org/ns#>
SELECT ?a ?v ?w
WHERE
     ( ?a :p ?v )
     OPTIONAL ( ?a :q ?w )

    1 ( ?a = :y) ( ?v = "y-p-1")
    2 ( ?a = :x) ( ?v = "x-p-1") ( ?w = "x-q-1")

The first triple pattern has solutions
   ( ?a = :y) ( ?v = "y-p-1")
   ( ?a = :x) ( ?v = "x-p-1")
and the optional adds  ( ?w = "x-q-1") to the second.


Optional, but also including passing through the input solution of
from the first triple pattern:

    1 ( ?a = :y) ( ?v = "y-p-1")
    2 ( ?a = :x) ( ?v = "x-p-1")
    3 ( ?a = :x) ( ?v = "x-p-1") ( ?w = "x-q-1")

adding the solution at line 2 which is a subset of line 3.

---------------------------

== Query 2:
As Query 1 but with the lines in the WHERE clause reversed.

PREFIX  : <http://example.org/ns#>
SELECT ?a ?v ?w
WHERE
      OPTIONAL ( ?a :q ?w )
      ( ?a :p ?v )

Optional, not passing through input if there is a match:
Different to query 1:

    1 ( ?a = :x) ( ?v = "x-p-1") ( ?w = "x-q-1")

The first pattern, the optional, creates two partial solutions:
     ( ?a = :z) ( ?w = "z-q-1")
     ( ?a = :x) ( ?w = "x-q-1")
the first is masked by the base pattern following.  It's the same as
if there were no optional.


Including passing through the input solutions we get the same as query 1 when it
passed through the input solutions:

    1 ( ?a = :y) ( ?v = "y-p-1")
    2 ( ?a = :x) ( ?v = "x-p-1")
    3 ( ?a = :x) ( ?v = "x-p-1") ( ?w = "x-q-1")

Again, solution 2 is a subset of solution 3.

--------

Call the form of optional including passing through the initial solution
"stable" as it always gets the same answer regardless of order.

But there are always "unhelpful" solutions.  For any optional, there is the
original and extended solutions when the intention was more to be adding in
additional information if available (the "useful" form).


I have not found an algorithm to filter the results of the "stable" optional 
form to get the "useful" form which does not involve sorting the result set in 
some way.  Even then, I am not convinced that it is right to do it by direct 
sorting.

I consider a requirement to sort as undesirable as it breaks streaming and is 
hard to do for large results (larger than available main memory).

A way to resolve this is to generalise the optional variable rule to say that
the execution order must be as if any variables that can be bound by a fixed
pattern are done before an optional they are used in.  Another way of saying 
this: if a variable is in an optional, it must not have been used in later 
pattern if it had not been used in an earlier one.  That makes two optionals, 
sharing a variable illegal.


Much the same goes for constraints:

     AND ?x < 3
     (?a :p ?x)
compared to:
     AND ?x < 3
     (?a :p ?x)


That's an informal description - I'm working on a formal definition.

There is a decision point as to whether the syntactic query is "wrong" if 
variables are out of order or whether the query is "right" and the execution 
engine has to execute in an appropriate order, but exactly the syntactic query 
order.

 Andy

Received on Thursday, 3 February 2005 17:29:17 UTC