Алгоритм генеалогического дерева

Question

Я новичок в этой области и хотел бы написать приложение, управляющее генеалогическими данными.Моя главная задача - как хранить и извлекать эти данные из MySQL.Я знаю, что БД, такие как Oracle, оптимизированы для рекурсивных запросов, но, возможно, я смогу найти альтернативное решение для использования MySQL, которое, как я понимаю, не поддерживает «CONNECT».PS.Я знаю, что существуют тысячи существующих решений с открытым исходным кодом, но учтите, что эти данные будут ограниченной частью функциональности, и мне нужно сохранить полный контроль над кодом.

Я быстро взглянул нав Интернете и нашел какой-то интересный подход, например, алгоритм на основе интервала, который идеально подходит для запросов, но не подходит для обновления / удаления.

Я собираюсь взглянуть на подход на основе префиксов (Дьюи), но кто-то может знать эффективный и проверенный подход для обмена?

спасибо

gilles

Answer 1

Первая проблема, схема данных проекта : Я храню иерархию с внешним ключом для родительской строки. Это просто.

Вторая проблема, получение потомков / потомков : Как вы объяснили, проблемы возникают с выбором: выберите несколько человек и всех потомков или потомков. Чтобы решить эту проблему, вы должны создать новую таблицу дерева. Эта таблица содержит пары: все комбинации с человеком со всеми его предками (и с самим собой):

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

Вы можете играть на расстоянии, чтобы получить только бабушку и дедушку, внуков и т. Д. ...

Последняя проблема, сохранить дерево : дерево должно быть все время до данных. Вы должны автоматизировать это: триггер над people или процедура сохранения для операций CRUD,

EDITED

Поскольку это генеалогическое древо, у каждого человека должны быть и ссылки, и родитель, и мать:

people( id, name, id_parent, id_mother)

Затем нужно 2 дерева:

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

привет.

Answer 2

Я бы также рекомендовал модель смежного дерева, а для более сложной логики я предлагаю использовать простые запросы mysql (Joins). Скорее всего, важнее создать дерево. Вы можете сделать больше интеллектуального анализа данных, когда приложение будет завершено, и все будет хорошо.