On Tue, Dec 31, 2013 at 10:37 AM, Richard Hipp <d...@sqlite.org> wrote: > New tested and supported extensions added to the source tree: > > 2. The transitive_closure virtual table: > www.sqlite.org/src/artifact/6360243
Funny you should mention this. I've written transitive closure computations using pure SQL (in SQLite3) several times now. For my most recent specific needs this virtual table wouldn't quite have been a natural fit, but it's still interesting to see your implementation. FWIW, I do a simple loop over INSERT OR IGNORE INTO SELECT parent ID, childen's children IDs, repeatedly up to the max path length iterations or until the table inserted to stops growing. Since I need to pre-compute all transitive closures in my data set and I need to persist and efficiently-update the result, this approach works well enough and permits subsequent O(1) computations... with the caveat that the pre-computation is expensive: worst-case *bound* with this approach is roughly O(N^2 log N), but for the actual -trusted- dataset it's much, much less. I've even resorted to doing the loop up to max. depth times via a recursive trigger, so it's all pure SQLite3. Nico -- _______________________________________________ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
