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
  • Last Modified:

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
Asked:
pudjam666
3 Solutions
 
LowfatspreadCommented:
have you considered the GEDCOM specification
and perhaps an XML implementation of the tree........

you need to give more information on your proposed
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
 
pudjam666Author 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
 
ispalenyCommented:
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
tx_siposCommented:
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
 
pudjam666Author 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
 
ispalenyCommented:
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
 
ispalenyCommented:
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
 
ispalenyCommented:
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
 
DromCommented:
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
 
ispalenyCommented:

------------------------------------------------------------------------
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
 
ispalenyCommented:
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
 
CleanupPingCommented:
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

Veeam and MySQL: How to Perform Backup & Recovery

MySQL and the MariaDB variant are among the most used databases in Linux environments, and many critical applications support their data on them. Watch this recorded webinar to find out how Veeam Backup & Replication allows you to get consistent backups of MySQL databases.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now