小编典典

族谱树算法

algorithm

我是该领域的新手,并且喜欢编写一个管理家谱数据的应用程序。我主要关心的是如何从MySQL存储和检索这些数据。我知道像Oracle这样的数据库已针对递归查询进行了优化,但是也许我可以找到使用MySQL的替代解决方案,但我不理解它不支持“
CONNECT”。PS。我知道有成千上万个现有的开放源代码解决方案,但是考虑到这些数据将是功能的有限部分,因此我需要保持对完整代码的控制。

我在网上浏览了一下,发现了一些有趣的方法,例如基于间隔的算法,该算法非常适合查询,但对更新/删除不满意。

我将研究基于Prefix的(杜威)方法,但是可能有人知道一种有效且行之有效的共享方法?

谢谢

吉尔斯


阅读 560

收藏
2020-07-28

共1个答案

小编典典

第一个问题是设计数据模式 :我保留带有父行外键的层次结构。很简单。

第二个问题,检索上升/下降
:正如您所解释的,select带来的问题是:选择某些人和所有上升后代。为了解决这个问题,您应该创建一个新的树表。该表包含以下几对:一个人及其所有祖先(及其本身)的组合:

people( id, name, id_parent)
people_tree( id, id_ancestor, distance )

注意,使用这种结构很容易查询层次结构。样本:某人的所有后代:

select people.*, distance
from 
  people p
    inner join 
  people_tree t 
    on ( p.id = t.id)
where
  id_ancesor = **sombody.id **

您可以与远方玩耍,只让祖父母,孙子女等…

最后一个问题,保持树 :树必须 一直保持 数据。您应该自动执行此操作:peopleCRUD操作的触发器或存储过程,

已编辑

因为这是家谱树,所以每个人都必须同时具有父母和母亲两个参考:

people( id, name, id_parent, id_mother)

然后,需要两棵树:

parent_ancestors_tree( id, id_ancestor, distance )
mother_ancestors_tree( id, id_ancestor, distance )

大卫要求提供样本数据:

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 --

问候。

2020-07-28