3 ms·
There 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. E
by twic 4y ago
There 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>
- twic 4y ago
- deleted 4y ago[deleted]