谱系树算法

2022-01-05 00:00:00 algorithm tree mysql genealogy

我是这个领域的新手，喜欢编写管理家谱数据的应用程序.我主要关心的是如何从 MySQL 存储和检索这些数据.我知道像 Oracle 这样的数据库针对递归查询进行了优化，但也许我可以找到使用 MySQL 的替代解决方案，我认为它不支持 "CONNECT" .附注.我知道现有的开源解决方案有数以千计，但考虑到这些数据将是功能的有限部分，我需要保持对完整代码的控制.

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.

我将看看基于前缀(杜威)的方法，但有人可能知道一种有效且经过验证的共享方法吗?

I'm going to have a look on Prefix-based(Dewey) approach, but one may know an efficient and proven approach to share ?

谢谢

鳃

推荐答案

第一个问题，设计数据架构:我使用父行的外键保留层次结构.很简单.

First problem, design data schema: I keep hierarchis with a foreign key to parent row. It is simply.

第二个问题，检索祖先/后代:正如你所解释的，问题来自于select:选择一些人和所有后代os.要解决这个问题，您应该创建一个新的树表.此表包含对: al 与一个人及其所有祖先(及其本身)的组合:

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

你可以玩距离，只得到祖父母、孙子女等......

You can play with distance to get only grandparents, grandwchildren, etc. ...

最后一个问题，保持树:树必须随时更新数据.您应该自动化:people 的触发器或 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,

已编辑

因为这是一棵家谱树，每个人都必须同时拥有父母和母亲:

Because this is a Genealogy tree, each person must to have both references, parent and mother:

people( id, name, id_parent, id_mother)

那么，需要 2 棵树:

Then, 2 trees are needed:

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

David 要求提供示例数据:

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

问候.

相关文章