osdir.com


[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: WITH RECURSIVE implementation


There was a relevant discussion some months ago in the Calcite dev mailing
list. Checkout the "Recursive query, graph query, Datalog" discussion.

I guess representationally, extension should be easy. A plan becomes a
graph instead of a tree. Cycles in the graph mean recursion. The tricky
part is that recursive queries have an execution aspect to them, where
evaluation ends when no new facts (data) can be inferred. That has to come
from the execution engine.

Also, interesting questions arise when you start incorporating recursion
such as semi-naive evaluation, and negation and aggregation, whose
semantics have to be monotonic in order for the evaluation to reach a fixed
point. See [1, 2] for more details.

I have started prototyping a Datalog parser, and RelConverter for Calcite
but it does not support recursion yet. Will be happy to brainstorm or
collaborate if someone is interested.

[1] Walaa Eldin Moustafa, Vicky Papavasileiou, Ken Yocum and Alin
Deutsch. Datalography: Scaling Datalog Graph Analytics on Graph Processing
Systems. ICDE Big Data 2016.
http://www.sysnet.ucsd.edu/sysnet/miscpapers/datalog-icbd16.pdf

[2] Jiwon Seo, Stephen Guo, Monica S. Lam. SociaLite: Datalog Extensions
for Efficient Social Network Analysis.
https://mobisocial.stanford.edu/papers/icde13.pdf

Thanks,
Walaa.


On Sat, Nov 17, 2018 at 4:43 PM Michael Mior <mmior@xxxxxxxxxx> wrote:

> I'm curious if anyone has any thoughts on how to go about implementing
> recursive queries. Postgres seems to only allow recursive queries with the
> form "non-recursive-term UNION [ALL] recursive-term" and uses a separate
> "recursive union" operator.
>
> Costing is also certainly a challenge since there's no obvious way to know
> how many times the recursive query will need to run. Specific suggestions
> would probably be best placed on the corresponding issue. Thanks!
>
> https://issues.apache.org/jira/browse/CALCITE-129
>
> --
> Michael Mior
> mmior@xxxxxxxxxx
>