On Thu, Mar 18, 2010 at 10:05:20AM +0100, Fredrik Karlsson scratched on the wall: > Dear list, > > I have a (small) directed graph which I would be able to fins all > ancestors or descendents of a certain vertex (transitive closure?). > So, using this graph: > > CREATE TABLE levels_levels (parent_id INTEGER ,child_id INTEGER, > UNIQUE(parent_id, child_id)); > INSERT INTO "levels_levels" VALUES(6,7); > INSERT INTO "levels_levels" VALUES(6,8); > INSERT INTO "levels_levels" VALUES(8,9); > INSERT INTO "levels_levels" VALUES(7,10); > INSERT INTO "levels_levels" VALUES(9,10);
> I have found a couple of procedural solutions using procedural calls > in sql server or postgresql, but is there a solution that I could get > into sqlite? No, not with this table design. Oracle, and a few other RDBMS products, have custom SQL extensions for dealing with this kind of "edge tree", but SQLite does not. If you want to use this representation, you will end up writing loops in your code. > The graph will never be very big, updating efficiency is not an > important factor. It will be queried a lot though, so search > efficiency is important. You might want to look into using a nested set. Nested sets can do these types of queries very quickly. The big disadvantage is that they can be extremely expensive to update. If that isn't a problem, it might be a better representation. Nested Sets are usually used for DAGs, so you may still end up looping over multiple node ID (for example, "find all the parents of 10" may require two queries, one for each "10" in the tree), but it is still likely to be faster. With enough JOINs you might be able to do this in one pass. It is too early for me to think too hard about that. Just do a websearch for "nested set SQL" and start reading. -j -- Jay A. Kreibich < J A Y @ K R E I B I.C H > "Our opponent is an alien starship packed with atomic bombs. We have a protractor." "I'll go home and see if I can scrounge up a ruler and a piece of string." --from Anathem by Neal Stephenson _______________________________________________ sqlite-users mailing list [email protected] http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
