You are viewing a plain text version of this content. The canonical link for it is here.
Posted to users@jena.apache.org by james anderson <ja...@dydra.com> on 2015/01/14 13:39:17 UTC

where does on find the sse language definition?

good afternoon;

the documentation notes for jena’s sparql s-expression syntax ends with the following passage.

  SSE Grammar
  @@ insert grammar here

whereby, the document itself actually already describes all of the distinguishing features of the grammar.

the missing information is the enumeration of the operator names and their signatures.
it would not even be necessary to have their definitions, as those would likely follow from the sparql grammar and language semantics.

is such a list hidden somewhere in the source tree?

best regards, from berlin,
---
james anderson | james@dydra.com | http://dydra.com






Re: Re: where does on find the sse language definition?

Posted by Andy Seaborne <an...@epimorphics.com>.
james,

As I have mentioned offlist, all your emails are dropping into the 
moderators inbox.

I think I have found the cause -- your emails have this header:

Received-SPF: pass (athena.apache.org: domain of 
0000014ae8a13fa3-4f7d980b-c53b-4688-857c-a0fc7e5ada3e-000000@eu-west-1.amazonses.com 
designates 54.240.6.212 as permitted sender)

I think this means your verfied email address to be that horrible UUID 
like thing @eu-west-1.amazonses.com, not james@dydra.com

Worse, it is different in different emails.

I am trying to coax the mail list filters to recognize james@dydra.com 
but, with a SPF, it is possible that the system will not recognize the 
declared email address, only the verified one.

	Andy

Re: where does on find the sse language definition?

Posted by james anderson <ja...@dydra.com>.
good afternoon rob;

On 2015-01-19, at 13:50, Rob Vesse <rv...@dotnetrdf.org> wrote:

> James
> 
> […]
> 
> Relevant flags are:
> 
> - ARQ.optIndexJoinStrategy
> - ARQ.optTopNSorting
> 
> You set these to false in a ARQ Context object that you pass to the calls
> of Optimize.optimize() should you wish to use the ARQ optimiser.
> 
> Of course if you don't wish to use the optimiser then you can override the
> modifyOp() method on your QueryEngine instance (assuming you start by
> extending QueryEngineBase) and not call the optimiser at all.

as our use case is a library to be used by others, we will need to look at the extent to which we can stipulate these approaches and still be compliant.

as it were, i would have no remorse about rewriting optimized operators back to standard algebra for the cases when we do not already implement under some other name.

> 
> Alternatively if you just want the "standard" algebra (i.e. the fairly
> true to spec, no optimisation version) then the basic Op structure
> generated by the AlgebraGenerator should be sufficient for your uses if
> you need just the algebra
> 
> In our system we then translate the algebra (using a custom visitor) into
> a form that our backend understands and ship that across the network
> rather than serialising the algebra out to strings and re-parsing it
> elsewhere (we've done that in the past but performance and maintenance
> wise it proved much better to transform the algebra into something that
> could be processed directly by our back end).

in our system, we compile a language similar to arq’s sse pretty much directly to machine code.
beyond  direct serialization and reading, all we need to know is the operator signatures.
if you would happen to have a synopsis of those as an alternative to crawling the implementations, that would be the most useful bit of information.

> 
> In terms of the stability of the algebra API I think there has only been 1
> breaking change to the API in the time we've been using it and that was
> actually proposed by us and was necessary to resolve an interesting corner
> case bug involving the optimiser and custom algebra operators.

ok. it sounds good, that it is stable.

> 
> Hope this helps,
> 
> Rob


best regards, from berlin,
---
james anderson | james@dydra.com | http://dydra.com






Re: where does on find the sse language definition?

Posted by Rob Vesse <rv...@dotnetrdf.org>.
James

Perhaps it is useful if I weigh in since what you are proposing to do
sounds very like what we at Cray have been doing for several years now.

We have a system where the front ends are Java based and we use ARQ for
the initial parsing of queries, translation into basic algebra and as part
of our optimiser.  The nice thing about the ARQ optimiser is that you can
set flags which disable each optimisation so in our case we disable all
the optimisations that generate non-standard algebra operators - these are
the topn, sequence, conditional and disjunction which Andy already
mentioned

Relevant flags are:

- ARQ.optIndexJoinStrategy
- ARQ.optTopNSorting

You set these to false in a ARQ Context object that you pass to the calls
of Optimize.optimize() should you wish to use the ARQ optimiser.

Of course if you don't wish to use the optimiser then you can override the
modifyOp() method on your QueryEngine instance (assuming you start by
extending QueryEngineBase) and not call the optimiser at all.

Alternatively if you just want the "standard" algebra (i.e. the fairly
true to spec, no optimisation version) then the basic Op structure
generated by the AlgebraGenerator should be sufficient for your uses if
you need just the algebra

In our system we then translate the algebra (using a custom visitor) into
a form that our backend understands and ship that across the network
rather than serialising the algebra out to strings and re-parsing it
elsewhere (we've done that in the past but performance and maintenance
wise it proved much better to transform the algebra into something that
could be processed directly by our back end).

In terms of the stability of the algebra API I think there has only been 1
breaking change to the API in the time we've been using it and that was
actually proposed by us and was necessary to resolve an interesting corner
case bug involving the optimiser and custom algebra operators.

Hope this helps,

Rob

On 16/01/2015 15:22, "james anderson" <ja...@dydra.com> wrote:

>
>On 2015-01-16, at 16:05, Andy Seaborne <an...@apache.org> wrote:
>
>> On 16/01/15 14:55, james anderson wrote:
>>> as expected - so long as one does not change their approach to
>>>argument order…
>> 
>> Is there a place where ARQ does?  It's not intended AFAIK.
>
>the are already some, for which our signature differs from arq’s, but
>that is not the issue.
>that is no different than that some of our operator names are not an
>exact match to arq’s.
>it would become an issue for us to track if arq were to change its
>convention between version.
>
>best regards, from berlin
>---
>james anderson | james@dydra.com | http://dydra.com
>
>
>
>
>





Re: where does on find the sse language definition?

Posted by james anderson <ja...@dydra.com>.
On 2015-01-16, at 16:05, Andy Seaborne <an...@apache.org> wrote:

> On 16/01/15 14:55, james anderson wrote:
>> as expected - so long as one does not change their approach to argument order…
> 
> Is there a place where ARQ does?  It's not intended AFAIK.

the are already some, for which our signature differs from arq’s, but that is not the issue.
that is no different than that some of our operator names are not an exact match to arq’s.
it would become an issue for us to track if arq were to change its convention between version.

best regards, from berlin
---
james anderson | james@dydra.com | http://dydra.com






Re: where does on find the sse language definition?

Posted by Andy Seaborne <an...@apache.org>.
On 16/01/15 14:55, james anderson wrote:
> as expected - so long as one does not change their approach to argument order…

Is there a place where ARQ does?  It's not intended AFAIK.

	Andy




Re: where does on find the sse language definition?

Posted by james anderson <ja...@dydra.com>.
good afternoon;

On 2015-01-16, at 15:35, Andy Seaborne <an...@apache.org> wrote:

> james,
> 
> (mostly offline driving yesterday)
> 
> The algebra in ARQ extends the SPARQL algebra so the SSE forms have both aspects.
> 
> The SPARQL algebra part is, necessarily, stable.  It reflects the design in the SPARQL 1.1 doc.

as expected - so long as one does not change their approach to argument order…

> 
> The extensions, which are mainly generated by the optimizer to do things in a "better way".
> 
> Example: (topN).  A Top N query - that is, the SPARQL query has ORDER/LIMIT and the limit is some reasonable value - can be executed with an algorithm that is O(x) fashion, avoiding the full O(x*log(x)) sort, where x is the number of matches of the WHERE clause.  What's more, it only need memory proportional to the limit, not x.
> 
> (topN) is not in the SPARQL 1.1 doc.
> 
> Other operators are introduced to be better joins, where better algorithms are possible but its still a join.  e.g. (conditional) is a left-join without worrying about variable scope.

as the jena sparql implementation is conformant, it would have to be possible for us to either rewrite the special cases back to equivalent standard forms or - to the extent that we can, implement them directly. i would be very curious about any optimization form from which it were not possible to recover the standard equivalent.

> 
> In reality, the algebra is stable even if not formally declared as such.  Other external systems depend on it; other modules in Jena use it; a lot of execution and processing is via the visitor pattern so adding or changing it is non-trivial work [*] .
> 
> That does not give you a contract guarantee although the reality is very close.  If you are using just the SPARQL 1.1 algebra, it is fixed. Change in the the optimization operations would most likely to add a new operator. All the extended operators are the result of a optimization transform and each and every one is switchable on and off.
> 
> SSE also extends into ways to have data structures - graphs, result sets, various other things.
> 
> Would it help if 'Tags' was broken up into modules for the different SSE uses?

it would be useful to know which of the operators enumerated in the tags file would be required to interpret a standard sse which are in jena's “optimized” realm.
any purportedly conformant sparql 1.1 implementation (as ours is) would need to support just the standard forms and could ignore all the others.

best regards, from berlin,
---
james anderson | james@dydra.com | http://dydra.com






Re: where does on find the sse language definition?

Posted by Andy Seaborne <an...@apache.org>.
james,

(mostly offline driving yesterday)

The algebra in ARQ extends the SPARQL algebra so the SSE forms have both 
aspects.

The SPARQL algebra part is, necessarily, stable.  It reflects the design 
in the SPARQL 1.1 doc.

The extensions, which are mainly generated by the optimizer to do things 
in a "better way".

Example: (topN).  A Top N query - that is, the SPARQL query has 
ORDER/LIMIT and the limit is some reasonable value - can be executed 
with an algorithm that is O(x) fashion, avoiding the full O(x*log(x)) 
sort, where x is the number of matches of the WHERE clause.  What's 
more, it only need memory proportional to the limit, not x.

(topN) is not in the SPARQL 1.1 doc.

Other operators are introduced to be better joins, where better 
algorithms are possible but its still a join.  e.g. (conditional) is a 
left-join without worrying about variable scope.

In reality, the algebra is stable even if not formally declared as such. 
  Other external systems depend on it; other modules in Jena use it; a 
lot of execution and processing is via the visitor pattern so adding or 
changing it is non-trivial work [*] .

That does not give you a contract guarantee although the reality is very 
close.  If you are using just the SPARQL 1.1 algebra, it is fixed. 
Change in the the optimization operations would most likely to add a new 
operator. All the extended operators are the result of a optimization 
transform and each and every one is switchable on and off.

SSE also extends into ways to have data structures - graphs, result 
sets, various other things.

Would it help if 'Tags' was broken up into modules for the different SSE 
uses?

	Andy

[*] I have never found a way to have visitor pattern and extensibility 
but maybe I'm missing something. The visitor pattern relies on

public void visit() { visitor.visit(this) ; }

where the type system cause a dispatch on the type of 'this'.  It's 
compile time.


On 14/01/15 15:10, james anderson wrote:
> good afternoon;
>
> On 2015-01-14, at 15:47, Andy Seaborne <an...@apache.org> wrote:
>
>> On 14/01/15 14:32, james anderson wrote:
>>> good afternoon;
>>>
>>> On 2015-01-14, at 14:56, Andy Seaborne <an...@apache.org> wrote:
>>>
>>>>>> […]
>>>>>
>>>>> ok. so, in the lisp sense, these two are the reader and the
>>>>> package definitions. there still needs to be something which
>>>>> defines the signatures, that is, the function types.
>>>>
>>>> The functions define their signatures. Some are multi-arity;
>>>> some have keyword processing (e.g. distinct).   And some
>>>> evaluations isn't even functional (e.g. &&).
>>>
>>> that is, no one has compiled the information, the individual
>>> function implementation source is the only source and if i use
>>> the content of the Tags.java file to search the source i should
>>> find everything?
>>
>> Could you give some context as to why our asking?  Is it to extend
>> ARQ? Or develop a similar system elsewhere?
>
> we are implementing a jni layer to makes our native rdf store and
> sparql processor available from java. the intent is to provide
> performance on the order of a memory store with the persistence and
> memory footprint of a disk-based store. we have advanced quite far
> toward this goal and now would like to devote some of our effort to
> ensuring interoperability by integrating it into the jena framework.
>
>>
>> Much of this is internal machinery (well, except that much is
>> defined by the SPARQL spec :-) and gets added to and refined for
>> that purpose.  I never conceived of the implementation as a
>> external contract.
>
> to the extent that a parsed query is provided to an implementation of
> a jena provider, the interface appears to treat the query ast as a
> part of a contractual exchange of sorts, and the sse is the natural
> externalization. we observe that the original sparql query expression
> is present as well, but had understood that its existence in the
> interface was somewhat less certain.
>
> in practical terms, our query processor works with forms analogous to
> the arq sse, but with slightly different signatures with respect to
> argument order. its core involves their direct macro-expansion and
> compilation into run-able queries, which means, to use the sse would
> save the effort of reparsing the query string. if, however, your
> message is that the the ast and/or the respective sse is not stable,
> but the presence of the query string is to be ensured, the safer path
> would be for us to re-parse.
>
> best regards, from berlin, --- james anderson | james@dydra.com |
> http://dydra.com
>
>
>
>
>
>


Re: where does on find the sse language definition?

Posted by james anderson <ja...@dydra.com>.
good afternoon;

On 2015-01-14, at 15:47, Andy Seaborne <an...@apache.org> wrote:

> On 14/01/15 14:32, james anderson wrote:
>> good afternoon;
>> 
>> On 2015-01-14, at 14:56, Andy Seaborne <an...@apache.org> wrote:
>> 
>>>>> […]
>>>> 
>>>> ok. so, in the lisp sense, these two are the reader and the package definitions.
>>>> there still needs to be something which defines the signatures, that is, the function types.
>>> 
>>> The functions define their signatures. Some are multi-arity; some have keyword processing (e.g. distinct).   And some evaluations isn't even functional (e.g. &&).
>> 
>> that is, no one has compiled the information, the individual function implementation source is the only source and if i use the content of the Tags.java file to search the source i should find everything?
> 
> Could you give some context as to why our asking?  Is it to extend ARQ? Or develop a similar system elsewhere?

we are implementing a jni layer to makes our native rdf store and sparql processor available from java.
the intent is to provide performance on the order of a memory store with the persistence and memory footprint of a disk-based store.
we have advanced quite far toward this goal and now would like to devote some of our effort to ensuring interoperability by integrating it into the jena framework.

> 
> Much of this is internal machinery (well, except that much is defined by the SPARQL spec :-) and gets added to and refined for that purpose.  I never conceived of the implementation as a external contract.

to the extent that a parsed query is provided to an implementation of a jena provider, the interface appears to treat the query ast as a part of a contractual exchange of sorts, and the sse is the natural externalization. we observe that the original sparql query expression is present as well, but had understood that its existence in the interface was somewhat less certain.

in practical terms, our query processor works with forms analogous to the arq sse, but with slightly different signatures with respect to argument order.
its core involves their direct macro-expansion and compilation into run-able queries, which means, to use the sse would save the effort of reparsing the query string.
if, however, your message is that the the ast and/or the respective sse is not stable, but the presence of the query string is to be ensured, the safer path would be for us to re-parse.

best regards, from berlin,
---
james anderson | james@dydra.com | http://dydra.com






Re: where does on find the sse language definition?

Posted by Andy Seaborne <an...@apache.org>.
On 14/01/15 14:32, james anderson wrote:
> good afternoon;
>
> On 2015-01-14, at 14:56, Andy Seaborne <an...@apache.org> wrote:
>
>>>> […]
>>>
>>> ok. so, in the lisp sense, these two are the reader and the package definitions.
>>> there still needs to be something which defines the signatures, that is, the function types.
>>
>> The functions define their signatures. Some are multi-arity; some have keyword processing (e.g. distinct).   And some evaluations isn't even functional (e.g. &&).
>
> that is, no one has compiled the information, the individual function implementation source is the only source and if i use the content of the Tags.java file to search the source i should find everything?

Could you give some context as to why our asking?  Is it to extend ARQ? 
Or develop a similar system elsewhere?

Much of this is internal machinery (well, except that much is defined by 
the SPARQL spec :-) and gets added to and refined for that purpose.  I 
never conceived of the implementation as a external contract.

	Andy


>
>>
>> The idea of a general data structure is that it does not prescribe the functions or usage.
>>
>> The SPARQL algebra defines that for it's usage.
>>
>> All "dynamic" in style.
>>
>> 	Andy
>
>
> best regards, from berlin,
> ---
> james anderson | james@dydra.com | http://dydra.com
>
>
>
>
>
>


Re: where does on find the sse language definition?

Posted by james anderson <ja...@dydra.com>.
good afternoon;

On 2015-01-14, at 14:56, Andy Seaborne <an...@apache.org> wrote:

>>> […]
>> 
>> ok. so, in the lisp sense, these two are the reader and the package definitions.
>> there still needs to be something which defines the signatures, that is, the function types.
> 
> The functions define their signatures. Some are multi-arity; some have keyword processing (e.g. distinct).   And some evaluations isn't even functional (e.g. &&).

that is, no one has compiled the information, the individual function implementation source is the only source and if i use the content of the Tags.java file to search the source i should find everything?

> 
> The idea of a general data structure is that it does not prescribe the functions or usage.
> 
> The SPARQL algebra defines that for it's usage.
> 
> All "dynamic" in style.
> 
> 	Andy


best regards, from berlin,
---
james anderson | james@dydra.com | http://dydra.com






Re: where does on find the sse language definition?

Posted by Andy Seaborne <an...@apache.org>.
On 14/01/15 13:28, james anderson wrote:
> good afternoon;
>
> On 2015-01-14, at 14:12, Andy Seaborne <an...@apache.org> wrote:
>
>> On 14/01/15 12:39, james anderson wrote:
>>> good afternoon;
>>>
>>> the documentation notes for jena’s sparql s-expression syntax ends with the following passage.
>>>
>>>    SSE Grammar
>>>    @@ insert grammar here
>>>
>>> whereby, the document itself actually already describes all of the distinguishing features of the grammar.
>>>
>>> the missing information is the enumeration of the operator names and their signatures.
>>> it would not even be necessary to have their definitions, as those would likely follow from the sparql grammar and language semantics.
>>>
>>> is such a list hidden somewhere in the source tree?
>>
>> https://github.com/apache/jena/blob/master/jena-arq/Grammar/sse/sse.jj
>>
>> Tokens are very literal.
>
> as they well should be.
>
>>
>> This is styled like lisp - the way the data structure gets used defines the operators (I presume you mean SPARQL algebra?
>
> yes,
>
>> SSE used elsewhere as well) not the syntactic language.
>
> but i guess i do not understand the difference, since the point of s-expressions is to muddy the distinction between surface and abstract syntax.
>
>>
>> https://github.com/apache/jena/blob/master/jena-arq/src/main/java/com/hp/hpl/jena/sparql/sse/Tags.java
>
> ok. so, in the lisp sense, these two are the reader and the package definitions.
> there still needs to be something which defines the signatures, that is, the function types.

The functions define their signatures. Some are multi-arity; some have 
keyword processing (e.g. distinct).   And some evaluations isn't even 
functional (e.g. &&).

The idea of a general data structure is that it does not prescribe the 
functions or usage.

The SPARQL algebra defines that for it's usage.

All "dynamic" in style.

	Andy

>
> best regards, from berlin,
> ---
> james anderson | james@dydra.com | http://dydra.com
>
>
>
>
>
>


Re: where does on find the sse language definition?

Posted by james anderson <ja...@dydra.com>.
good afternoon;

On 2015-01-14, at 14:12, Andy Seaborne <an...@apache.org> wrote:

> On 14/01/15 12:39, james anderson wrote:
>> good afternoon;
>> 
>> the documentation notes for jena’s sparql s-expression syntax ends with the following passage.
>> 
>>   SSE Grammar
>>   @@ insert grammar here
>> 
>> whereby, the document itself actually already describes all of the distinguishing features of the grammar.
>> 
>> the missing information is the enumeration of the operator names and their signatures.
>> it would not even be necessary to have their definitions, as those would likely follow from the sparql grammar and language semantics.
>> 
>> is such a list hidden somewhere in the source tree?
> 
> https://github.com/apache/jena/blob/master/jena-arq/Grammar/sse/sse.jj
> 
> Tokens are very literal.

as they well should be.

> 
> This is styled like lisp - the way the data structure gets used defines the operators (I presume you mean SPARQL algebra?

yes,

> SSE used elsewhere as well) not the syntactic language.

but i guess i do not understand the difference, since the point of s-expressions is to muddy the distinction between surface and abstract syntax.

> 
> https://github.com/apache/jena/blob/master/jena-arq/src/main/java/com/hp/hpl/jena/sparql/sse/Tags.java

ok. so, in the lisp sense, these two are the reader and the package definitions. 
there still needs to be something which defines the signatures, that is, the function types.

best regards, from berlin,
---
james anderson | james@dydra.com | http://dydra.com






Re: where does on find the sse language definition?

Posted by Andy Seaborne <an...@apache.org>.
On 14/01/15 12:39, james anderson wrote:
> good afternoon;
>
> the documentation notes for jena’s sparql s-expression syntax ends with the following passage.
>
>    SSE Grammar
>    @@ insert grammar here
>
> whereby, the document itself actually already describes all of the distinguishing features of the grammar.
>
> the missing information is the enumeration of the operator names and their signatures.
> it would not even be necessary to have their definitions, as those would likely follow from the sparql grammar and language semantics.
>
> is such a list hidden somewhere in the source tree?

https://github.com/apache/jena/blob/master/jena-arq/Grammar/sse/sse.jj

Tokens are very literal.

This is styled like lisp - the way the data structure gets used defines 
the operators (I presume you mean SPARQL algebra? SSE used elsewhere as 
well) not the syntactic language.

https://github.com/apache/jena/blob/master/jena-arq/src/main/java/com/hp/hpl/jena/sparql/sse/Tags.java

	Andy

>
> best regards, from berlin,
> ---
> james anderson | james@dydra.com | http://dydra.com
>
>
>
>
>