Re: SPARQL evaluation semantics

Olaf Hartig wrote:
> Hello,
> 
> In section 12.5 the SPARQL spec. defines an evaluation semantics using an
> operation eval. The result of this operation seems to be a multiset of
> solution mappings and the 2nd operator is said to be a graph pattern. The
> given definitions contain symbols like LeftJoin. The meaning of these symbols
> confuses me. Do they represent graph patterns or algebra operators? Or, do
> you use the same symbol for both - graph patterns in the left part of the
> equation and algebra operators in the right?
> 
> Thanks,
> Olaf

Hi Olaf,

The LeftJoin symbol plays different roles at different stages as the SPARQL 
syntax is turned first in the algebra and then evaluates.

Consider this example:

"(1+2) * (3+4)"

That might be parsed into the abstract syntax tree (AST):

        mult
       /    \
     add    add
    /  \   /  \
    1  2   3  4

or writing in linearly:

mult(add(1,2), add(3,4))

"mult" is just a label in a datastructure at this point.

Evaluation proceeds functionally, bottom-up (strict evaluation) by evaluating 
each sub-express before calling the mult operations.  It's only this latter 
stage that the types of the arguments to mult are 2 integers from the 
evaluation of the sub-expressions add(...).

eval[mult(add(1,2), add(3,4)] =>
   eval[mult(eval[add(1,2)], eval[add(3,4)])] =>
     // Skipping eval(integer) => integer
     eval[mult(3, 7)] ==>
       21

In section 12.5, we're at the evaluation state and LeftJoin is a function - it 
was just a symbol in an expression until this point like "mult" is a symbol in 
the AST.

The arguments to LeftJoin in teh evaluation are multisets from the inner 
evaluation of P1, P2.

eval(D(G), LeftJoin(P1, P2, F)) = LeftJoin(eval(D(G), P1), eval(D(G), P2), F)

The term "pattern" (12.5) is an algebra expression (symbols in a 
datastructure, actually, it's a tree) derived form a syntactic form of a graph 
pattern (symbols in an AST).  eval produces multisets.

	Hope that helps,
	Andy

http://en.wikipedia.org/wiki/Evaluation_strategy

-- 
  Hewlett-Packard Limited
  Registered Office: Cain Road, Bracknell, Berks RG12 1HN
  Registered No: 690597 England

Received on Saturday, 1 December 2007 19:33:46 UTC