On 02/01/2018 06:54, Dinu wrote:
If a different perspective may be helpful to you: If moving overhead to writes is an option (ie you dont have many or time critical writes), then the tree descendants problem can be sped up to stellar speeds by using a path column.
In a more relational spirit, you might add a Leaves(node) table to contain all the leaves (where 'node' is a foreign key to your Nodes table). Query the leaves becomes trivial then. Adding a new node will require two inserts, one into Nodes and one into Leaves. When you add a new edge (u,v), where u and v are existing nodes, you must check whether u is in Leaves and, if so, delete it from there. Edge deletions and updates are a bit more involved, but manageable as well. In a similar vein, if you often need to query descendants/ancestors of a node, you might as well maintain the (reflexive)/transitive closure of your graph explicitly in a separate table TC(ancestor,descendant). There is a SQLite3 extension called 'closure' which might help with that as well (I haven't used it, though). Another idea is to keep the out-degree of each node in the Nodes table, and update it each time you add/remove edges, e.g., with triggers. Hope this helps, Life. _______________________________________________ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
