3

I am trying to store a family tree. Here is the platform that I am using, Zend framework, Mysql, Ajax I have searched stackoverflow I came across this post which is very helpful in handling data in terms of objects.

"Family Tree" Data Structure

I'll Illustrate my use case in brief. User can create family members or friends based on few relations defined in database. I have Model for relations too. User can create family members like Divorced spouse, frineds. Max the Tree can be deep that we are assuming max to kids of the grandchildren but it can expand in width too. Brother/sister & their family.

I am looking an efficient database design for lesser query time. If I have to use the data structures described in above post where I must keep them as they necessary have to be a Model.

For representation I am planning to use Visualization: Organizational Chart from http://code.google.com/apis/chart/interactive/docs/gallery/orgchart.html#Example

I'll summarize what I need

  1. Database design
  2. Placing of controllers (ajax) & models
  3. The people that the user will create they will not be any other users. just some another data

yeah thats it! I'll post a complete solution on this thread when I'll be completing the project, of course with help of expertise of u guys

Thanks in advance

EDIT I I'll Contribute more to elaborate my situation

I have a user table, a relation table, & last family/family tree table

the Family table must have similar structure to following

ID        userid              relation id             Name

1         34                   3 // for son             ABC
2         34                   4 // for Wife            XYZ
3         34                   3 // for Mom             PQR
4         34                   3 // for DAd             THE
5         34                   3 // for Daughter        GHI
6         34                   3 // for Brother         KLM

The drawback for this approach is generating relations to the other nodes like daughter-in-law, wifes brother & their family.

The ideal way of doing is for a user we can add Parents, siblings, children & for extra relations they must be derived from the family members relation i.e. Brother-in-law must be derived as sister's husband, or wife's brother.

THis is what I can think now. I just need Implementation guidelines.

Hope this helps u guys to provide a better solution.

Community
  • 1
  • 1
SAM
  • 641
  • 2
  • 16
  • 30

1 Answers1

1

I guess that from the database point of view it would be best to implement it like

id | name | parent_male | parent_female

Other option would be string prefixing

id | name | prefix 
1  | Joe  | 0001
2  | Jack | 000100001 //ie. Joes son
3  | Marry| 0001 //ie. Jacks mother
4  | Eve  | 0002 // new family tree
5  | Adam | 00020001 // ie. Eves son
6  | Mark | 000200010001 // ie. Adams son

Other (more effective) algorithms like MPTT assume that the data is a tree, which in this case is not (it has circles).

To show it would work - to select Mark's grandparents:

--Mark
SELECT prefix FROM family_tree WHERE id = 6; 
-- create substring - trim N 4-character groups from the end where N is N-th parent generation => 2 for grandparent ==> 0002
--grandparents
SELECT * FROM family_tree WHERE prefix = '0002' 
-- same for other side of family
-- cousins from one side of family
SELECT * FROM family_tree WHERE prefix LIKE '0002%' AND LENGTH(prefix) = 12
Tomáš Fejfar
  • 11,129
  • 8
  • 54
  • 82
  • i wouldn't go further then one generation, your prefix would get very quickly bloated otherwise – peter Feb 25 '12 at 12:52
  • We use it successfully for 4 levels for e-commerce categories with hundreds of categories. It's really no problem. – Tomáš Fejfar Feb 25 '12 at 23:15
  • Also it depends on how many different trees you plan to save (this prefix has limit of 9999 items in one subtree level (i.e. you can have 9999 different families) that should be enough. And standard varchar(255) can save 64 generations... that's imo good enough – Tomáš Fejfar Jan 30 '14 at 15:02
  • What would be the best way to handle a member deletion here? – kiranvj Nov 28 '18 at 10:15
  • You need to implement it manually, depending on the expected result. What happens when you delete someone's mother? Should the child be also removed? If so, then for mother with prefix 00020001 you do `DELETE FROM family_tree WHERE prefix LIKE '00020001%'`. It will wipe all the children of the removed person. Otherwise you may need to update the prefix to different person manually. – Tomáš Fejfar Nov 29 '18 at 13:35
  • Or you select children (that have length 8 from parent and 4 chars of their own): `WHERE prefix LIKE '00020001%' AND LENGTH(prefix) = 12`. And maybe do something with them. To update a parent you need to update parent's substring of the prefix. So to assign Adam to Marry instead of Eve, you would update him to 0001 + "substring starting with [length of original parents prefix] character" – Tomáš Fejfar Nov 29 '18 at 13:40