Re:Datalog in Rust
by ulrikrasmussen on Monday June 16, 2025 @02:41AM
(#44287145)
Yes, #1 basically means that they screwed up the design from the get go, since it is impossible to reap the actual benefits of Datalog when the language you evaluate is not, in fact, Datalog. Recursive queries have the ability to perform arbitrary computation in projections, so for starters any top-down evaluation strategy or hybrid evaluation such as magic sets is ruled out.
Curious: How would you usefully & naturally add recursion to SQL without making it Turing-complete?
At first blush that sounds impossible. Maybe there's a clever solution that would occur to someone if they spent a few months working on it, or maybe not.
Not sure either. We added recursion to SQL in Feldera and it's Turing-complete: https://www.feldera.com/blog/recursive-sql-queries-in-felder...
Recent additions to ANSI SQL have added the capacity for recursion, so it's no longer completely impossible. But they have three big disadvantages:
1. They accidentally made SQL Turing-complete. Datalog queries, by contrast, are guaranteed to terminate.
2. They're still extremely clumsy to use.
3. Because of #1, they're often not implemented fully, so they are hard to rely on.