php - Inbreeding-immune database structure -

i have application requires "simple" family tree. able perform queries give me data entire family given 1 id member in family. simple because not need take account adoption or other obscurities. requirements application follows:

• any 2 people not able breed if they're same genetic line
• needs allow addition of new family lines (new people no previous family)
• need able pull siblings, parents separately through queries

i'm having trouble coming proper structure database. far i've come 2 solutions they're not reliable , out of hand quite quickly.

solution 1 involves placing family_ids field on people table , storing list of unique family ids. each time 2 people breed lists checked against each other make sure no ids match , if checks out merge 2 lists , set child's family_ids field.

example:

father (family_ids: (null)) breeds mother (family_ids: (213, 519)) -> child (family_ids: (213, 519)) breeds random person (family_ids: (813, 712, 122, 767)) -> grandchild (family_ids: (213, 519, 813, 712, 122, 767)) 

and on , forth... problem see lists becoming unreasonably large time goes on.

solution 2 uses cakephp's associations declare:

public $belongsto = array( 'father' => array( 'classname' => 'user', 'foreignkey' => 'father_id' ), 'mother' => array( 'classname' => 'user', 'foreignkey' => 'mother_id' ) ); 

now setting recursive 2 fetch results of mother , father, along mother , father, , on , forth way down line. problem route data in nested arrays , i'm unsure of how efficiently work through code.

if able steer me in direction of efficient way handle want achieve tremendously helpful. , appreciated , i'll gladly answer questions has. lot.

in sql (more correctly, rdbs) i'd use following solution:

1) create table people following fields - id, name, father_id, mother_id. first 1 typical primary key column, father_id , mother_id refer column nullable (to allow addition of new family lines).

2) create table relatives following fields - person_id, ancestor_id. both not null, both form composite primary key, both fk person.id.

and that's it. no, really! ) consider tasks:

• add people without family lines

that's pretty doable: insert people (name) values ('some_name'). trick make insert related fresh person relatives: insert relatives values (%new_person_id%, %new_person_id%)

what's for? consider common task: add person has both father , mother listed in tables already. structure it's done simple (after inserting corresponding record people, , getting person_id result)...

insert relatives select %new_person_id%, ancestor_id relatives person_id in (%father_id%, %mother_id%); insert relatives values (%new_person_id%, %new_person_id%); 

• any 2 people not able breed if they're same genetic line.

with structure described above it's rather simple: have 2 records in relatives has same value in ancestor_id field. example:

 select count(*) relatives ra inner join relatives rb on ra.ancestor_id = rb.ancestor_id ra.person_id = %person_a_id% , rb.person_id = %person_b_id% 

it's quite easy ancestors , children in structure; i'd still prefer de-normalized approach (i.e., storing father_id , mother_id in first table) speed look-up direct parents/children - can done first table alone.

here's working (albeit bit short) sql fiddle example show in more practical color. )