Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 358

# How to trace a family tree, backwards and forwards?

I need to make a family tree website.  The database will include several seperate, unrelated family trees.  I need to figure out ALL relatives (past and present) of any given person.  Also note that a person can have an unlimited number parents (don't ask...).

I've found stored procs that trace a record through all of its chilren -- but I need something that also finds all the parents and grandparents and THEIR children, etc. -- every relative backwards and forwards.

Any ideas where to start?
0
pudjam666
3 Solutions

Commented:
have you considered the GEDCOM specification
and perhaps an XML implementation of the tree........

database tables and their relationships to enable a meaningful response....

a sample of the output you are expect would also be needed, as you say its fairly easy to visualise a descendant list , but more difficult to achieve the reverse.

good luck.
0

Author Commented:
Thanks for the comment.  Think of it as SixDegrees.com -- remember that website?

You're a node, you could have been invited by 10 people have you could have invited 20 people.  I want to know everyone else in your tree, up and down.
0

Commented:
0

Commented:
Here is another method for walking through a table with multiple entries like this one.
1.  Determine how many levels can exist within a heirarchy (in your case somewhere between 5 and 10 generations).
2.  Determine how many peers can exist beneath any particular level (99).  Flatter models will require more bytes.
3.  Construct a 10 x 2 = 20 byte string to store the relationship. (Heirarchy)

The first node is 01.  Three child nodes are:  0101, 0102, and 0103.  Use string functions to find the lineage between nodes.  Ex:  WHERE Heirarchy like '010302%' would find all of the descendents of 010302.
0

Author Commented:
tx_sipos: interesting method but it doesn't seem to work if a node has 2 (or 3 or 4) parents.

am i right?  or am i missing something?
0

Commented:
It is not a tree, it is a net.

Basic structure
---------------

create table People([ID] int primary key)
create table SubRelatedPeople(
[ID]     int references People([ID])
, ID_Sub int references People([ID])
, RelationType int
, primary key ([ID],ID_Sub)
, check ([ID]<>ID_Sub))

0

Commented:
THE NET WITH ONE-WAY RELATIONS
---------------------------

DIAGRAM
--------
Quido+Eva
|->Eva2+Milan
||->Jakub
||->Petra
|->Ivo+Jindra
||->Ivo2
||->Lucie

DATABASE DESIGN (SAMPLE)
------------------------
drop table RelationTypes,People,SubRelatedPeople
GO
create table RelationTypes(IdType int primary key,RelationName char(20))
create table People([ID] int primary key,[Name] char(10))
create table SubRelatedPeople(
[ID]     int references People([ID])
, ID_Sub int references People([ID])
, RelationType int references RelationTypes(IdType)
, primary key ([ID],ID_Sub)
, check ([ID]<>ID_Sub))

insert into RelationTypes(IdType,RelationName) values (0,'HeMarriedHer')
insert into RelationTypes(IdType,RelationName) values (1,'Child')

insert into People([ID],[Name]) values (1, 'Quido')
insert into People([ID],[Name]) values (2, 'Eva')
insert into People([ID],[Name]) values (3, 'Eva')
insert into People([ID],[Name]) values (4, 'Ivo')
insert into People([ID],[Name]) values (5, 'Ivo')
insert into People([ID],[Name]) values (6, 'Jakub')
insert into People([ID],[Name]) values (7, 'Petra')
insert into People([ID],[Name]) values (8, 'Lucie')
insert into People([ID],[Name]) values (9, 'Milan')
insert into People([ID],[Name]) values (10,'Jindra')

insert into SubRelatedPeople([ID],ID_Sub,RelationType) values (1,2,0)
insert into SubRelatedPeople([ID],ID_Sub,RelationType) values (1,3,1)
insert into SubRelatedPeople([ID],ID_Sub,RelationType) values (2,3,1)
insert into SubRelatedPeople([ID],ID_Sub,RelationType) values (1,4,1)
insert into SubRelatedPeople([ID],ID_Sub,RelationType) values (2,4,1)
insert into SubRelatedPeople([ID],ID_Sub,RelationType) values (9,3,0)
insert into SubRelatedPeople([ID],ID_Sub,RelationType) values (9,6,1)
insert into SubRelatedPeople([ID],ID_Sub,RelationType) values (9,7,1)
insert into SubRelatedPeople([ID],ID_Sub,RelationType) values (3,6,1)
insert into SubRelatedPeople([ID],ID_Sub,RelationType) values (3,7,1)
insert into SubRelatedPeople([ID],ID_Sub,RelationType) values (4,10,0)
insert into SubRelatedPeople([ID],ID_Sub,RelationType) values (4,5,1)
insert into SubRelatedPeople([ID],ID_Sub,RelationType) values (10,5,1)
insert into SubRelatedPeople([ID],ID_Sub,RelationType) values (4,8,1)
insert into SubRelatedPeople([ID],ID_Sub,RelationType) values (10,8,1)

0

Commented:
This sample is for an ideal family.
Parents do not divorse. Two children per family.
In reality, there are relation types like stepmother,stepfather,AdoptiveMother and so on.
0

Commented:
should be simple from here:

- create Families table like ([ID] int primary key, Family varchar(64))
- add new family record in there
- add fk_family column to the People table
- (opt) add relation column to the People
- mark start node in People with new family ID e.g. X
- proceed with updating fk_family in People if the record have fk_family different than X and has any relation to those with fk_family = X
- (opt) while updating calculate relations based on the relation type of newly found family member and family member found on previous iteration
- proceed with updating till no more records left to update

you can work with People directly or if you want to know relations like grandfather, step-brother etc. - with a new temporary indexing table as each starting node in people will produce different relations values. there might be permanent table for it, but it will keep N^2 records when people has N, which might be an issue.

** this is not the answer - just a draft.
0

Commented:

------------------------------------------------------------------------
We all are relatives.
------------------------------------------------------------------------
N   =   6*10^ 9  -- bigint must be used !
About 5000 years of well mapped history, one new generation every 20 years.
X=5000/20=250
M=250*6*10^9=1.5*10^12
M^2=(1.5*10^12)^2=2.25*10^24
R=20*2.25*10^24 B = 4.5*10^25 B
= 4,500,000,000,000 TB
------------------------------------------------------------------------
For a constant population of 6 billion people over 5000 years.
This is the worst case.
------------------------------------------------------------------------

-----------------------------------------------------------------------------------------------------------------
Now I reduce:  100,000 interested people; average of 6 generations; most relations unknown
-----------------------------------------------------------------------------------------------------------------
N=10^5  -- int is enough
M=6*10^5
M^2=(6*10^5)^2=1.2*10^11
R=12*1.2*10^11 B = 1.44*10^12 B
= 1.44 TB
I assume they know about 10^-6 of all relations.
RR= 1.44 TB * 10^-6 = 1.44 MB
---------------------------------------------------------------------------------------------------------------------

One floppy is sufficient for all the relations ?
0

Commented:
I posted normalized tables. These table, with some improvemets, must not allow duplicite information.

Later you can add denormalized fields and tables,
but always have a sure normalized primary source of information.

Denormalized hierarchies can be indexed, queries are very simple and fast.

When you want to manage very large hierarchies (millions of nodes), leave SQL and look for next generation of massive parallel computers. Something like CM.

Good luck !
0

Commented:
pudjam666: