Solved

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

Posted on 2003-03-19
Medium Priority
340 Views
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
Question by:pudjam666
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• Learn & ask questions

LVL 50

Expert Comment

ID: 8167157
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 Comment

ID: 8167474
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

LVL 13

Expert Comment

ID: 8167752
0

Expert Comment

ID: 8168103
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 Comment

ID: 8168332
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

LVL 13

Expert Comment

ID: 8168835
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

LVL 13

Accepted Solution

ispaleny earned 165 total points
ID: 8169062
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

LVL 13

Expert Comment

ID: 8169145
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

Assisted Solution

Drom earned 60 total points
ID: 8170573
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

LVL 13

Assisted Solution

ispaleny earned 165 total points
ID: 8170758

------------------------------------------------------------------------
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
About 20 B each row.
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
About 12 B each row.
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

LVL 13

Expert Comment

ID: 8170818
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

Expert Comment

ID: 9275738
pudjam666:
This old question needs to be finalized -- accept an answer, split points, or get a refund.  For information on your options, please click here-> http:/help/closing.jsp#1
EXPERTS:
Post your closing recommendations!  No comment means you don't care.
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Load balancing is the method of dividing the total amount of work performed by one computer between two or more computers. Its aim is to get more work done in the same amount of time, ensuring that all the users get served faster.
Ready to get certified? Check out some courses that help you prepare for third-party exams.
This video shows, step by step, how to configure Oracle Heterogeneous Services via the Generic Gateway Agent in order to make a connection from an Oracle session and access a remote SQL Server database table.
Viewers will learn how to use the UPDATE and DELETE statements to change or remove existing data from their tables. Make a table: Update a specific column given a specific row using the UPDATE statement: Remove a set of values using the DELETE s…
###### Suggested Courses
Course of the Month8 days, 20 hours left to enroll

#### 765 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.