Jan schrieb: > Hi, > > I am planning a database for animal breeding. I need to store the > relations between individuals and therefore I have to build something > like a tree structure. But of course with two parents (There wont be > cloned animals in the database .-) afaik) > > I read a little bit about > > - adjacency list (not very difficult to understand) > - nested sets (hm, more difficult) > - b tree (to difficult) > - ? (something I missed?) > > Could anyone give me an advice what to use or what else to read? Maybe > someone has already done something similar e.g. genealogy. > > Bye > Jan > > _______________________________________________ > sqlite-users mailing list > sqlite-users@sqlite.org > http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users > > The problem you're describing is one of the fundamental relational problems.
A) I'd advice you to use a relational Table like you told before A Table with at least the three fields animal_id_self, animal_id_father, animal_id_mother is necessary to note the different relations. B) Is there something which would be more elegant ? It depends on the amount of data you intend to store in the database. If you have a database for 1000 animals and about 7 generations of animals you could append a blob field to the definition of your table where you store the ancestors from the father and the mother in an array of integer values. This would avoid the interation over the tables. But be warned. With each generation the size of this blob will get sizeof (ancestors_father+1) + sizeof (ancestors_mother+1). This means in the worst case you would get a factor of 2 per generation to avoid the iteration. I would say that 10 generations would be something were i'd take this risk if i have to avoid a iteration and break the rule of avoiding redundant data in tables. In the 10th generation you could have a size of this blob with 1 kByte per animal. C) What is the reason for the lack of a proper algorithm ? Change the point of view and look from the last children back than you'll see, that each animal is the root of an independent binary search tree. Because each animal has two parents, each parent two parents and so on. with each level you get two more entries per ancestor. D) The relational model fits best. This example is perfectly suited for the relational database modell. It asures that you can store the information with the least amount of space and without lose of data. But it also shows that in such situations you have to interate. I would avoid a time saving field like the ancestors column in the database. Insteed it is the best to load this table into the memory and iterate through it. E) A faster approach than with sqlite ? Your animal_id's are integer values so the b-tree approach which is used in sqlite is fast enough to get good iteration results especially when you only store a few thousand values. You would get a bit faster results with hashing. But before you invent your proprietary engine i'd advice to use a relational database with sql. I think you'll store more than only parent information for the animals and then the true strength of the relational model appears. Good luck, Ibrahim _______________________________________________ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
