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

Question

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

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

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

благодаря

Жиль

Answer 1

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

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

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

Noticie, что с этой структурой легко запросить иерархии. Пример: все потомки кого-то:

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

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

Последней проблемы, сохранить дерево: дерево должно быть все время до данные. Вы должны автоматизируют это: триггер над 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) 

David запрашивать данные выборки:

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). Скорее всего, более важно создать дерево. Вы можете сделать больше данных, когда приложение будет завершено, и все будет хорошо.