Uma ideia que vem do esquema Geneapro e RootsMagic .
person
------
person_id
name (etc)
life_event_types
----------------
life_event_type_id
life_event_type_description (divorce, marriage, birth, death)
life_events
-----------
life_event_id
life_event_type_id
life_event_description
life_event_date
life_event_roles
----------------
life_event_role_id
life_event_role (mother, father, child)
person_event_role
-----------------
person_id - who
life_event_id - what happened
life_event_role_id - what this person did
Assim, você poderia ter um evento de vida do tipo "nascimento", e o role_id informa quem eram os pais e quem era a criança. Isso pode ser estendido a casamentos, mortes, divórcios, pais adotivos, pais substitutos (onde você pode ter 3 ou 4 pais com um relacionamento muito complicado), etc.
Quanto ao armazenamento de relacionamentos mais distantes, você pode calculá-los. Por exemplo, você pode calcular o Pai de qualquer pessoa obtendo a pessoa que tem a função 'pai' com um event_id correspondente. Você pode então obter o pai dessa pessoa e você tem o avô da pessoa original. Em qualquer lugar que alguém seja desconhecido, crie a pessoa com dados desconhecidos.