On Wed, Jun 03, 2009 at 12:25:14AM +0200, Jan scratched on the wall: > Hi, > > If you don't want to update, but you do want to query for entire > > subtrees, do give nested sets more consideration. > > But as Jay pointed out: Nested sets only work with one parent. Do they?
You can think of nested sets as basically sets of parenthesis. So the tree: A / \ B C / /|\ D E F G Turns into: (A:(B:(D:))(C:(E:)(F:)(G:))) As you can see, quite literally "nested sets" (or "sets of sets"). Each node can have exactly one parent (the containing set) and zero or more (with "more" being > 2) children. In the case of a family tree, you can get around the "one parent" by extracting the table structure out to a detail table, so that the tree table only has "person_id" values that point back to some master "person" table. You can then just build two nested sets: one that represents all fathers and one that represents all mothers. The "father" table will still have daughters, but daughters will always lack any children (in the "father" table). [I think that will work. My morning coffee has just about worn off.] Of course, this cancels out many of the query optimizations that nested sets are good at, since you'll frequently need to combine data from the two trees to get what you want. But it would be possible. The bigger issue is that nested sets assume a perfect tree structure. It has to lead back to a "point." You could, in theory, do a family tree for a single person by turning the table up-side down, but if you're trying to track breeding over a group of animals you need not so much a tree as a scattered mesh that generally trends in one direction. Unless you started out with exactly one male and one female, a nested set isn't going to cut it. I'm also unsure about cross-generational links (Like a son being a half-brother kind of thing) that might happen in lab animals. adjacency lists can deal with all of these quite easily. You can have multiple NULL parents for the "tops" of different sub-trees, and the tree structure is localized to a node and it's parents, meaning the links can go all over the place. As for AVL trees, I'm just confused by that suggestion. AVL trees, like B-trees, Red/Black trees, or just about any kind of balanced tree are designed to hold sorted lists. The whole idea of balanced trees is that the tree structure can rearrange itself at will, just as long as the leaf nodes keep their order and are fast to find. You can't hold a tree structure in a AVL tree since the tree structure is prone to changing if you add or remove leaf nodes. Or am I missing something? -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 sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users