Re: Issues with evaluating optional: Commutativity of AND

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 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 - the world goes on.

> 
> 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.  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.

> 
> Point 3:
> 	There are related issues with the scope of variables. (I think.)
> 

	Andy

Received on Friday, 13 October 2006 10:40:03 UTC