Translation of SPARQL syntax to SPARQL algebra

(50% thinking out loud, 50% note to Steve - anyone feel free to comment)


The generation of algebra in SPARQL 1.0 works in two steps:

1/ Translate graph patterns to algebra, working on multisets of solution 
mappings and resulting in a multiset of solution mappings

2/ Translate the solution modifiers, which work on sequences, to the 
algebra, taking the result of step 2 as input, converting to a sequence 
with ToList.

pattern/multiset ->
    [toList] ->solution modifiers

The solution modifiers are:
# Order by
# Projection
# Distinct, reduced
# limit, offset

In SPARQL 1.1 we have grouping and aggregation. The current draft labels 
this as a solution modifier as it takes the output pattern matching on 
the dataset and performs an operation on solution mappings only, without 
accessing the dataset.  But it does not operate on sequences not does it 
produce a sequence.

SPARQL 1.1 also adds subqueries so there is a ToMultiSet operation to 
turn a sequence from a subquery into a multiset that the pattern 
matching can use.

We need a good name for the thing that is one level in the query: 
pattern match, group/aggregate and solution modifier.  Any suggests? 
"level" is the best I have come up with.

It would seem better to make grouping/aggregation a separate step 
because it works on a multiset and produces a multiset that is further 
processed by the solution modifiers.

pattern matching ->
    group/aggregation/SelectExpressions ->
       [toList] ->solution modifiers.

By putting SelectExpressions in with the post-pattern-matching stage, 
HAVING is a filter of a multiset results in a multiset.

The solution modifiers for SPARQL 1.1 are the same SPARQL 1.0:

 Andy

Received on Thursday, 4 November 2010 14:31:45 UTC