Re: Issues with evaluating optional: Commutativity of AND

On Oct 13, 2006, at 11:39 AM, Seaborne, Andy wrote:

> Bijan Parsia wrote:
> ...
>> Some high level points:
>> Point 1:
>> 	SCS (and the two email above) assert that it is strongly  
>> desirable  that the semantics of the SPARQL algebra have normal  
>> features one  expects, e.g., compositional semantics,  
>> commutativity of conjunction,  etc. I agree with these. They are  
>> very important for optimization,  for example, and for end users.
>
> What I think is bad is designing for commutativity

Well we aren't talking about communtativity of arbitrary operators,  
but of conjunction.

> in such a way that the user either can't achieve the query they  
> want to naturally or is forced to issue two or more queries to get  
> the effect required.  The cases when optionals have order  
> dependency can be spotted by static analysis just from variable  
> scopes.  I don't consider commutativity to be an overriding  
> factor.  SQL Left outer join can be order dependent

But it's a different operator. No one said that all operators had to  
be commutative!

> - the world goes on.

I would be interested in your reaction to the details of the worked  
examples, especially the translation of the two evaluation mechanisms  
into (augmented) relational operators.

>> Point 2:
>> 	There are possible *ways of evaluating a SPARQL parse tree (or   
>> abstract syntax tree)* that do not support these features (as  
>> shown  in SCS). The way to evaluate a SPARQL parse tree (oh, let's  
>> call it a  "query plan" ok?) is not clear, from what I can tell,  
>> in the current  spec. 0000.html suggests this. We should  
>> definitely *nail down* a  semantics for the evaluation of query  
>> plans that is *unambiguous*. I  would prefer that it met the  
>> criteria in point 1 as well.
>
> Certainly, one way to approach defining SPARQL algebra is to define  
> a canonical evaluation.

I didn't mean that we had to nail it in terms of an evaluation. SCS  
does it all in terms of set theoretically defined operators (at least  
for E1). That the current spec *allows* for two, incompatible  
evaluation mechanisms is clearly a problem in the semantics of the  
language. The technique to resolve it is separate.

> If we do, we might as well do something obvious like "lexical  
> order" for groups of patterns (not filters) which gives a unique  
> and explainable outcome.  Optimizers are of course permitted to  
> make any changes they like if the semantics are maintained.

Sure. SCS presents the navigational approach and gives an algorithm  
for it.

Cheers,
Bijan.

Received on Friday, 13 October 2006 10:58:32 UTC