族谱树算法 [英] Genealogy tree Algorithm
问题描述
我在这个新的领域,并喜欢写的应用程序管理家谱数据。我主要关心的是如何存储和从MySQL retreive这些数据。我知道,数据库,如Oracle的递归查询优化,但也许我能找到一个替代的解决方案使用MySQL,我undestand是不支持连接。 PS。我知道,有成千上万的现有的开源解决方案,但考虑到这些数据将是功能有限的一部分,我需要保持充分code控制。
I'm new in this domain and like to write an application managing genealogical data. My main concern is how to store and retreive these data from MySQL. I know that DB like Oracle are optimised for recursive queries, but maybe I can find an alternative solution to use MySQL which I undestand is not supporting "CONNECT" . PS. I know that there are thousands of existing Open source solutions, but consider that these data will be a limited part of the functionality, and I need to keep control of the full code.
我有一个快速浏览一下在网络上,并发现了一些有趣的方法,例如基于间隔的算法中这是完美的查询,但不尽如人意的更新/删除。
I had a quick look on the web and found some interesting approach, for instance Interval-based algo which is perfect for queries but not satisfactory for update / deletion.
我要对preFIX为主(杜威)的方式来看看,但有可能知道一个有效的和行之有效的方法来共享?
I'm going to have a look on Prefix-based(Dewey) approach, but one may know an efficient and proven approach to share ?
感谢
吉尔斯
推荐答案
第一个问题,设计数据模式:我一直hierarchis一个外键父行。这简直是。
First problem, design data schema: I keep hierarchis with a foreign key to parent row. It is simply.
问题二,找回祖先/后裔:如您解释一下,问题自带的选择:选择一些人,所有后代OS长辈。为了解决这个问题,你应该创建一个新的树表。此表包含对:人组合到一个人所有,他们的祖先(和自己):
Second problem, retrieve ascendants/descendants: As you explain, problems comes with select: select some people and all descendants os ascendants. To solve this you should to create a new tree table. This table contains pairs: al combination to a person with all they ancestors (and itself):
people( id, name, id_parent)
people_tree( id, id_ancestor, distance )
Noticie,与该结构很容易地查询层次结构。示例:有人的所有后代:
Noticie that with this structure is easy to query hierarchies. Sample: all descendants of somebody:
select people.*, distance
from
people p
inner join
people_tree t
on ( p.id = t.id)
where
id_ancesor = **sombody.id **
您可以用距离打得到的只有爷爷奶奶,grandwchildren,等等...
You can play with distance to get only grandparents, grandwchildren, etc. ...
最后一个问题,保持树:树必须全部时间可达数据。你应该你完成这项:触发了人
或CRUD操作一个存储过程,
Last problem, keep tree: tree must be all time up to data. You should automatize this: a trigger over people
or a store procedure for CRUD operations,
EDITED
由于这是一个家谱树,每个人都必须有两个参考,父和母:
Because this is a Genealogy tree, each person must to have both references, parent and mother:
people( id, name, id_parent, id_mother)
然后,需要两棵树:
Then, 2 trees are needed:
parent_ancestors_tree( id, id_ancestor, distance )
mother_ancestors_tree( id, id_ancestor, distance )
大卫索要样本数据:
David ask for sample data:
people: id name id_parent id_mother
1 Adam NULL NULL
2 Eva NULL NULL
3 Cain 1 2
.. ...
8 Enoc 3 5
parent_ancestors_tree id id_ancestor distance
(Adam) 1 1 0
(Eva) 2 2 0
(Cain) 3 3 0
3 1 1
(Enoc) 8 8 0
8 3 1
8 1 2
mother_ancestors_tree id id_ancestor distance
(Adam) 1 1 0
(Eva) 2 2 0
(Cain) 3 3 0
3 2 1
(Enoc) 8 8 0
-- here ancestors of Enoc's mother --
问候。
这篇关于族谱树算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!