3 ms·
In SQL you say something like: WITH RECURSIVE transitive_closure AS ( SELECT parent, child FROM things UNION SELECT tc.parent, t.child
by cryptonector 2y ago
In SQL you say something like:
WITH RECURSIVE transitive_closure AS (
SELECT parent, child FROM things
UNION
SELECT tc.parent, t.child
FROM things t
JOIN transitive_closure tc ON tc.child = t.parent
)
SELECT * FROM transitive_closure;
where `transitive_closure` is a table that gets all the results of the computation. The engine will run the second part of the query repeatedly until no new rows are added to the `transitive_closure` table. (If you change `UNION` to `UNION ALL` and there's circular paths then this will not terminate.)
Sounds a lot like whatever "tabling" is in Prolog.
- YeGoblynQueenne 2y agoLikely. It depends on how the transitive_closure results are computed. In tabling it's still by resolution so you can still get stuck in infinite loops, e.g. on infinite right-recursions. I think maybe that's more similar to UNION ALL? I should probably read a bit about this again. I rarely used recursive queries in SQL when I worked with it, not least because a couple of times I did, I got into trouble because they went haywire :)
- cryptonector 2y ago> In tabling it's still by resolution so you can still get stuck in infinite loops, e.g. on infinite right-recursions. I think maybe that's more similar to UNION ALL? Must be. With UNION you can't end up with an infinite loop unless you have infinite data (or you're implementing a table-valued Ackermann function and so you have... not infinite results but for all practical intents, yeah).