On Wed, Jun 03, 2009 at 10:51:52AM -0700, Harold Wood scratched on the wall: > just curious. why not a table for stricty for the linkages > ? > structure similar to > ? > create table Linkages > ( > ??? Parent_Id int, > ??? Child_Id? int > ??? PRIMARY KEY (Parent_Id, Child_Id)) > ? > This would allow a lot of flexability in the parenting, you could > have (A:B), (A:C), (B:D), (B:E), (B:F), (E:G) and if you > wanted to get a little insane, (A:D), etc.
This is essentially a bridge-table that creates a Many-to-Many relationship between nodes, allowing for each node to have an arbitrary number of parents and children. At this point you're representing not so much a tree as any generic directed graph. If, in the context of the OP's situation, we assume each individual animal has exactly one father and one mother we can simplify this design, since we know there should be exactly two Linkages rows with a given Child_Id. Knowing that, we can just roll the two Parent_Id values from those two Linkages rows into the Animal row as Mother_Id and Father_Id. If you needed to represent something more complex, like "We know the Mother is animal #435, but the Father may be either #596 or #854" you could use a bridge table like this to associate multiple Father (or Mother) relationships, possibly with other meta-data about the Linkage, like a probability. This design is very much the next abstraction from a traditional adjacency list. It is more flexible, but it is also more complex. -j > --- On Wed, 6/3/09, Jay A. Kreibich <j...@kreibi.ch> wrote: > > > From: Jay A. Kreibich <j...@kreibi.ch> > Subject: Re: [sqlite] Db design question (so. like a tree) > To: "General Discussion of SQLite Database" <sqlite-users@sqlite.org> > Date: Wednesday, June 3, 2009, 12:36 PM > > > 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 -- 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
