4 ms·
> You need to be careful about infinite cycles and things like that. Not really, just never forget this: always use `UNION`, and never `UNION ALL`, in recursiv
by cryptonector 4y ago
> You need to be careful about infinite cycles and things like that.
Not really, just never forget this: always use `UNION`, and never `UNION ALL`, in recursive queries!
- twic 4y agoThere are still ways to go wrong. Try writing a query which explores a graph from a starting node, building up a path from the start to each node as a string. Even using UNION you will get an infinite loop, because every visit to a node in the loop has a different path, so it makes a unique row.
- cryptonector 4y agoThe aggregation needs to be done after you've computed the transitive closure, not while you're computing it.
- blowski 4y agoTo me, that all sounds like you need to be careful.
- cryptonector 4y agoI mean, yes? This is easy to learn the hard way, but it's also easy to learn. Once learned you don't forget.
- twic 4y agoI think the only way to build the path up is to do it as you're traversing, though. Here's a small example: create table node ( name varchar primary key ); create table edge ( from_name varchar not null references node (name), to_name varchar not null references node (name) ); insert into node values ('Hawaii'), ('San Francisco'), ('New York'), ('Houston'); insert into edge values ('Hawaii', 'San Francisco'), ('San Francisco', 'New York'), ('San Francisco', 'Houston'), ('Houston', 'New York'); with recursive route (destination_name, path) as ( values ('Hawaii', 'Hawaii') union select to_name, route.path || ' -> ' || to_name from route join edge on route.destination_name = edge.from_name ) select * from route; That works as long as the graph is acyclic. If you add an edge from New York to Houston, say, then the query goes into an infinite loop. How would you do this after computing the transitive closure? And how would that avoid an infinite loop?
- cryptonector 4y agoAh, yes, I flubbed -- this one requires aggregation as you go. It's tricky. Ideally you could have a decent aggregation data structure for the path that lets you select a distinct sequence (path) of middle points. One could write such an aggregation function, I think. Lacking that you have to limit the length of all paths between any pair of points to the longest possible path (which is the number of points minus one), which is annoying, and then you still have to fix up each resulting path to remove any repeating suffix. sqlite> .schema CREATE TABLE edge (src text, dst text); sqlite> with recursive paths (src, dst, len, path) as ( ...> select src, dst, 0, src || '->' || dst from edge ...> union ...> select p.src, e.dst, p.len + 1, p.path || '->' || e.src from paths p join edge e on p.dst = e.src where p.len < (select count(*) from (select src from edge union select dst from edge))) select * from paths; Hawaii|San Francisco|0|Hawaii->San Francisco San Francisco|New York|0|San Francisco->New York San Francisco|Houston|0|San Francisco->Houston Houston|New York|0|Houston->New York Houston|Hawaii|0|Houston->Hawaii Hawaii|Houston|1|Hawaii->San Francisco->San Francisco Hawaii|New York|1|Hawaii->San Francisco->San Francisco San Francisco|Hawaii|1|San Francisco->Houston->Houston San Francisco|New York|1|San Francisco->Houston->Houston Houston|San Francisco|1|Houston->Hawaii->Hawaii Hawaii|Hawaii|2|Hawaii->San Francisco->San Francisco->Houston Hawaii|New York|2|Hawaii->San Francisco->San Francisco->Houston San Francisco|San Francisco|2|San Francisco->Houston->Houston->Hawaii Houston|Houston|2|Houston->Hawaii->Hawaii->San Francisco Houston|New York|2|Houston->Hawaii->Hawaii->San Francisco Hawaii|San Francisco|3|Hawaii->San Francisco->San Francisco->Houston->Hawaii San Francisco|Houston|3|San Francisco->Houston->Houston->Hawaii->San Francisco San Francisco|New York|3|San Francisco->Houston->Houston->Hawaii->San Francisco Houston|Hawaii|3|Houston->Hawaii->Hawaii->San Francisco->Houston Houston|New York|3|Houston->Hawaii->Hawaii->San Francisco->Houston Hawaii|Houston|4|Hawaii->San Francisco->San Francisco->Houston->Hawaii->San Francisco Hawaii|New York|4|Hawaii->San Francisco->San Francisco->Houston->Hawaii->San Francisco San Francisco|Hawaii|4|San Francisco->Houston->Houston->Hawaii->San Francisco->Houston San Francisco|New York|4|San Francisco->Houston->Houston->Hawaii->San Francisco->Houston Houston|San Francisco|4|Houston->Hawaii->Hawaii->San Francisco->Houston->Hawaii sqlite>
- deleted 4y ago[deleted]
- magicalhippo 4y agoSeems to be a Postgres-specific advice? Others, for example SQLite[1], seem to advocate using UNION ALL over UNION. [1]: https://sqlite.org/lang_with.html#recursive_query_examples https://sqlite.org/lang_with.html#recursive_query_examples
- cryptonector 4y agoNo, it's not Postgres-specific advice. Using UNION ALL in recursive queries is a mistake if you have cycles in your data. This follows from first principles and the standard.
- magicalhippo 4y agoRight, bit early so wasn't thinking in terms of cyclic data, we've only used it for acyclic graphs (typically trees).
- hedora 4y agoThere is some theoretical work on datalog you might be interested in. Recursive queries over sets are guaranteed to terminate if they don't contain negations / aggregations, and if they have a finite herbrand universe, which, very roughly speaking, means that no functions can return new constants or tuples of unbounded length. eg: recursively generating the set of x := x + 1 won't terminate beacuse x goes to infinity, and you get infinite tuples. x := abs(x) is fine, since you get up to two tuples per input tuple (-1, and 1, for example). Anyway, if you ask for the query to build up all paths (of unbounded length), it won't terminate. If you asked for shortest paths, (bounded by the number of nodes in the source database) it would.
- magicalhippo 4y agoInteresting. Most of that makes sense I think, though a bit outside my normal sphere. I was struggling why aggregates were excluded so to speak, but I guess it's because they have to be repeatedly evaluated? Ie compute the sum, add it to the output, now you might have to recompute the sum? Perhaps I'm being dense here, left my thinking cap at home.