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 <mm...@apache.org> 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 > mm...@apache.org >
