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

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

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

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

Спасибо

жилль

Источник

2 ответа

Решение

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

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

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,

РЕДАКТИРОВАНИЕ

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

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

С уважением.

Источник

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

Источник
Другие вопросы по тегам