8 ms·
Does this mean it’ll be easy to do graph transitive closure computations in sqlite now?
by carterschonwald 6y ago
Does this mean it’ll be easy to do graph transitive closure computations in sqlite now?
- seg_lol 6y agoDo you mean iterating on an agency matrix dimension times to get the full path length between any two nodes? I have had to run my recursive queries external to the database (MySQL, SQLite), this change looks to bring it into the database. Excellent news!
- castratikron 6y agoTransitive closure will tell you if a path between two nodes exists, not the length of the shortest path between two nodes.
- whoisburbansky 6y agoYou're technically correct, but afaik there isn't really a way to compute transitive closure without also computing shortest paths along the way, modulo constant factors?
- simcop2387 6y agoYou'll compute paths along the way but won't know that they're the shortest path. Odds are good though that you'll havr found something good enough for most purposes though.
- whoisburbansky 6y agoIf all you do is iterate over the adjacency matrix, sure, but wouldn't Floyd-Warshall be the same time complexity? All I'm saying is that you get both pieces of information for essentially the same price, modulo constant factors.
- bawolff 6y agoEven if it is, i imagine its not going to be that efficient if it isnt optimized for that use csse.
- nikeee 6y agoI solved a task involving transitive closures in last year's Advent of Code using SQLite: https://github.com/nikeee/advent-of-code-2019/blob/master/06/main.sql https://github.com/nikeee/advent-of-code-2019/blob/master/06... How could this be improved with the new feature of SQLite?