Re: can/should a parser join groups?

Dear Ruben, Andy and all,
I hold the following "conjectures" regarding the semantics of SPARQL
1.1 (I did not formally prove them on the algebra, but they seem true
to me after an informal analysis of the spec and some empirical
tests):

1) any reordering of the elements in a GroupGraphPattern that does not
contain BIND clauses (but could contain OPTIONAL, FILTER, etc), leads
to an equivalent GroupGraphPattern;
2) if a GroupGraphPattern (containing possibly also BIND clauses)
complies with note 13 of the grammar (the to-be-bound variable not
already in use), any other complying reordering leads to an equivalent
GroupGraphPattern.

In particular, I conjecture that two BGPs in the same element group
can always be safely merged unless there is a BIND clause between them
and joining them violates note 13. Therefore, for example, Ruben'
queries should be pairwise equivalent (semantically) even if the
corresponding algebra expression is different.
Does it make sense?

I hope to no to be blatantly out of scope, I think that formally
deriving this kind of general semantic equivalences from the spec
could be useful for query optimization.

Best,
Miguel

On Thu, Aug 21, 2014 at 2:50 PM, Andy Seaborne <andy@apache.org> wrote:
> On 21/08/14 13:05, Ruben Verborgh wrote:
>>>
>>> -Correct - adjacent triple patterns and ones separated by FILTER merge
>>> together.
>>
>>
>> And how does it change semantics then?
>> I.e., what would be the difference between
>>
>> SELECT  ?title ?price
>> {  ?x ns:price ?p .
>>     ?x ns:discount ?discount
>>     BIND (?p*(1-?discount) AS ?price)
>>     FILTER(?price < 20)
>>     ?x dc:title ?title .
>> }
>
>
> The process proceeds from beginnign to end of the {}.group
> BIND ends the BGP being built.
>
> That BIND takes the two triple patterns as one BGP: introduces ?price and
> joins it
>
>     (project (?title ?price)
>       (filter (< ?price 20)
>         (join
>           (extend ((?price (* ?p (- 1 ?discount))))
>             (bgp
>               (triple ?x ns:price ?p)
>               (triple ?x ns:discount ?discount)
>             ))
>           (bgp (triple ?x dc:title ?title)))))
>
>
> SELECT  ?title ?price
> {  ?x ns:price ?p .                ## BGP 1
>     ?x ns:discount ?discount       ## BGP 1
>
>     BIND (?p*(1-?discount) AS ?price)
>     FILTER(?price < 20)
>     ?x dc:title ?title .           ## BGP 2
>
> }
>
>
>>
>> and
>>
>> SELECT  ?title ?price
>> {  ?x ns:price ?p .
>>     ?x ns:discount ?discount
>>     ?x dc:title ?title .
>>     BIND (?p*(1-?discount) AS ?price)
>>     FILTER(?price < 20)
>> }
>
>
> whereas BIND after all the triple patterns:
>
>     (project (?title ?price)
>       (filter (< ?price 20)
>         (extend ((?price (* ?p (- 1 ?discount))))
>           (bgp
>             (triple ?x ns:price ?p)
>             (triple ?x ns:discount ?discount)
>             (triple ?x dc:title ?title)
>           ))))
>
>
> SELECT  ?title ?price
> {   ?x ns:price ?p .                    ## BGP 1
>     ?x ns:discount ?discount .          ## BGP 1
>     ?x dc:title ?title .                ## BGP 1
>
>     BIND (?p*(1-?discount) AS ?price)
>     FILTER(?price < 20)
> }
>
>
>>
>> or
>>
>> SELECT  ?title ?price
>> {  ?x ns:price ?p .
>>     OPTIONAL { ?x ns:discount ?discount }
>>     ?x dc:title ?title .
>> }
>
>
> OPTIONAL is applied to the ns:price, and the result joined to the trailing
> BGP of one triple pattern
>
>     (project (?title ?price)
>       (join
>         (leftjoin
>           (bgp (triple ?x ns:price ?p))
>           (bgp (triple ?x ns:discount ?discount)))
>         (bgp (triple ?x dc:title ?title))))
>
>
>>
>> and
>>
>> SELECT  ?title ?price
>> {  ?x ns:price ?p .
>>     ?x dc:title ?title .
>>     OPTIONAL { ?x ns:discount ?discount }
>> }
>
>
> here the BGP is 2 triple patterns, forming the fixed side of a
> leftJoin/OPTIONAL:
>
>     (project (?title ?price)
>       (leftjoin
>         (bgp
>           (triple ?x ns:price ?p)
>           (triple ?x dc:title ?title)
>         )
>         (bgp (triple ?x ns:discount ?discount))))
>
>
> Examples produced by
> http://www.sparql.org/query-validator.html
> (Apache Jena).
>
> The spec is definitive.
>
> http://www.w3.org/TR/sparql11-query/#sparqlQuery
>
> and the important parts here are:
>
>             18.2.2.2 Collect FILTER Elements
>
>             18.2.2.5 Translate Basic Graph Patterns
>             18.2.2.6 Translate Graph Patterns
>
> There are some examples there as well. (sec 18.2.3)
>
>>
>> ?
>>
>> Best,
>>
>> Ruben
>>
>
>

Received on Thursday, 21 August 2014 20:08:17 UTC