Genealogy tree mysql

Question

I'm trying to create a structure to store and read dogs pedigree using php and mysql.

I found on stackoverflow this kind of structure, and it seems to be efficient: Inbreeding-immune database structure

TABLE people (id, name, father_id, mother_id );
TABLE relatives ( person_id, ancestor_id );

There is a working example here: http://sqlfiddle.com/#!2/0bd39/10

Is it possible to retrieve simply a ordered tree or a subtree (for example 4 or 5 generations) starting by an id?

EDIT

I'm trying to get the data from using the first table...but with 4-5 generations the resulting query is very very heavy. I fear that with a large amount of information in the DB, getting the genealogy could be to much slow and unusable.

SELECT 
    t1.name AS lev1, t2.name as f, ff1.name as ff1, fm1.name as fm1, t3.name as m, 
    mf1.name as mf1, mm1.name as mm1, .......
FROM people AS t1
LEFT JOIN people AS t2  ON t2.id = t1.father_id
 LEFT JOIN people AS ff1 ON ff1.id = t2.father_id
 LEFT JOIN people AS fm1 ON fm1.id = t2.mother_id
   ...
LEFT JOIN people AS t3  ON t3.id = t1.mother_id
 LEFT JOIN people AS mf1 ON mf1.id = t3.father_id
 LEFT JOIN people AS mm1 ON mm1.id = t3.mother_id
    ...
WHERE t1.id = 6;

Your problem is not easy to solve. You can take a look (under the creative commons license) at my pedigree web application but please notice this is a beta version and german(Sorry!). [link](http://www.zujab.at/stm.zip) — idmean, Feb 18 '13 at 14:07
I know that this is not easy to solve..and I'm trying to find some suggestion to the best structure to use with the mysql limitations. — Danilo, Feb 18 '13 at 17:08
See my answer to http://stackoverflow.com/questions/192220/what-is-the-most-efficient-elegant-way-to-parse-a-flat-table-into-a-tree/192462#192462 — Bill Karwin, Feb 18 '13 at 21:03

score 4 · Accepted Answer · answered Feb 18 '13 at 14:39

4

This sort of this is probably better suited for a graph style of data store. Something akin to how facebook keeps hierarchies of relationships.

If you are bound and determined to use MySQL you could probably get away with your schema by using a recursive search. Since your tree can be of variable depth you could start self-joining at given location and 'walk' down a branch recursing until you didn't find anymore descendants. Return that branch and start down the next one. Similar process for traversing up to find parents.

answered Feb 18 '13 at 14:39

ethrbunny

10,379
9
69
131

I have to use mysql. I'm also though to traversing the tree with a recursive approach..but I suppose that it's necessary to use php. Do you think that is faster a single query like the one that I've written in my edited question, or is faster operate with simple recursive queries managed my a php recursive function? – Danilo Feb 18 '13 at 17:38
1

Using a preset query will limit you to a fixed depth. If that's acceptable then it's certainly easier than nesting multiple queries. – ethrbunny Feb 18 '13 at 23:53

score 1 · Answer 2 · answered Feb 18 '13 at 14:34

1

I had this very issue with fish lineages. I found that dumping an adjacency list (like the one you've posted) to a dedicated tree builder like GraphViz was the best solution.

answered Feb 18 '13 at 14:34

dnagirl

20,196
13
80
123

Actually I don't have the possibility to install other software on the webserver, but it seems very useful that tree builder – Danilo Feb 18 '13 at 17:15

Genealogy tree mysql

2 Answers2

Linked