I thought about the adjacency lists. The columns would basically look like this I guess:
animal_id (PK), animal_id (father), aninmal_id (mother) Since I cant do a loop in sql how could I build a trigger securing, that no child is e.g a father of it's own father (or grand-father and so on)? To achieve that I would have to loop through the whole hierarchy of ancestors. Jay A. Kreibich schrieb: > 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 > _______________________________________________ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
