Re: tolog for TMQL

On Sat, Apr 02, 2011 at 10:10:19AM +0200, Lars Marius Garshol wrote:

> > My concern was and is, that tolog-class languages have severe
> > limitations in terms of optimization opportunities (need too much
> > global knowledge and therefore cannot be easily parallelized).
> 

> You've said this a number of times, but I must confess that I never
> had any idea what you base this claim on. I don't see the big
> difference.  Why are tolog-like languages less parallelizable?

Well, without a more rigorous definition of tolog I am left with what
I think it did from the tutorial(s). The more formal definition

   http://www.garshol.priv.no/download/text/tolog.pdf

came 2006 when TMQL was already well under way. Though I never was
sure that the Ontopia implementation (or any other) was really based
on that semantics (TMQL@rho was implemented verbatim).

And tolog might have changed too, so my suspicions might ungrounded.
But from what I remember (have my notes somewhere in the "pile"):

  - tolog allows to quantify over literals, i.e allows to have
    variables range unboundedly (TMQL@rho never does allow that)

  - tolog does not have a scheme to completely eliminate variables
    (TMQL@rho does). The relevance here is, that

      - you need first A LOT of variables in tolog to "bind things
        together" (output of that is supposed to be input of that). An
        optimizer has to _guess_ the user's intention (TMQL@rho has
        this very explicit from the user side). Consequently TMQL@rho
        "encourages" the user to be more explicit in what should
        happen. This means more information, which then means smaller
        data sets.

      - you cannot flatten a set of tolog predicate evaluations into a
        stream of expressions, say, path expressions, to, say,
        evaluate those in parallel. Sharding with tolog query
        expressions should work, though.

        Variables always mean _state_ information and I certainly do
        not need to tell you that carrying around //state// impedes
        concurrency.

So variable elimination (or actually making all of them neighboring
local) is a pretty cute feature. You certainly will remember Seoul,

   http://www.garshol.priv.no/blog/42.html

and the breakout session you mention in

   http://www.garshol.priv.no/blog/42.html

In that session

   http://www.garshol.priv.no/tmphoto/photo.jsp?id=t36059

I transformed a

   for $p in // person
   where
      is-author (author: $p, opus: $_)

into a chain of PEs which did not contain a single variable. The
semantics appendix in TMQL@rho has a complete transformation defined.