Как передать генеалогическое древо в реляционную базу данных?

Хранение генеалогического древа в реляционной БД

Генеалогическое древо (пример графовой структуры) — это иерархия где человек может иметь нескольких родителей и нескольких детей. Это нетривиальная задача для реляционной БД.

Проблема: иерархии в SQL

Реляционные БД хорошо работают с плоскими данными, но иерархии требуют специальных подходов. Нет встроенного способа выразить: "Найди всех предков Иванова".

Подход 1: Adjacency List (список смежности) — ПРОСТОЙ

Самый простой способ: каждый узел хранит ссылку на своего родителя.

CREATE TABLE person (
    id BIGSERIAL PRIMARY KEY,
    name VARCHAR(255) NOT NULL,
    birth_date DATE,
    father_id BIGINT REFERENCES person(id),
    mother_id BIGINT REFERENCES person(id)
);

-- Пример данных:
-- id | name     | father_id | mother_id
-- 1  | Иван     | NULL      | NULL       (прародитель)
-- 2  | Петр     | NULL      | NULL       (прародитель)
-- 3  | Федор    | 1         | 2          (сын Ивана и Петра)
-- 4  | Анна     | 1         | 2          (дочь Ивана и Петра)
-- 5  | Владимир | 3         | NULL       (сын Федора)

Найти всех детей Федора:

SELECT * FROM person WHERE father_id = 3 OR mother_id = 3;
-- Результат: Владимир

Найти родителей Владимира:

SELECT * FROM person WHERE id IN (
    SELECT father_id FROM person WHERE id = 5
    UNION
    SELECT mother_id FROM person WHERE id = 5
);

Проблема: рекурсивный запрос (Найти всех предков)

-- ✅ PostgreSQL (RECURSIVE CTE)
WITH RECURSIVE ancestors AS (
    -- Базовый случай
    SELECT id, name, father_id, mother_id, 1 as level
    FROM person
    WHERE id = 5  -- Владимир
    
    UNION ALL
    
    -- Рекурсивный случай
    SELECT p.id, p.name, p.father_id, p.mother_id, a.level + 1
    FROM person p
    JOIN ancestors a ON (p.id = a.father_id OR p.id = a.mother_id)
    WHERE a.level < 10  -- Ограничиваем глубину
)
SELECT * FROM ancestors;

Пример на Java с Hibernate:

@Entity
@Table(name = "person")
public class Person {
    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    private Long id;
    
    private String name;
    private LocalDate birthDate;
    
    // Ссылки на родителей
    @ManyToOne
    @JoinColumn(name = "father_id")
    private Person father;
    
    @ManyToOne
    @JoinColumn(name = "mother_id")
    private Person mother;
    
    // Ссылки на детей (опционально, для удобства)
    @OneToMany(mappedBy = "father")
    private Set<Person> childrenFromFather = new HashSet<>();
    
    @OneToMany(mappedBy = "mother")
    private Set<Person> childrenFromMother = new HashSet<>();
    
    // Получить всех детей
    public Set<Person> getAllChildren() {
        Set<Person> all = new HashSet<>();
        all.addAll(childrenFromFather);
        all.addAll(childrenFromMother);
        return all;
    }
    
    // Получить всех предков (рекурсивно)
    public Set<Person> getAllAncestors() {
        Set<Person> ancestors = new HashSet<>();
        if (father != null) {
            ancestors.add(father);
            ancestors.addAll(father.getAllAncestors());
        }
        if (mother != null) {
            ancestors.add(mother);
            ancestors.addAll(mother.getAllAncestors());
        }
        return ancestors;
    }
}

Плюсы:

• Простая структура
• Легко добавлять новых членов
• Понятный запросы

Минусы:

• Рекурсивные запросы дорогие
• Сложный поиск дальних предков
• Может быть медленно на больших древах

Подход 2: Nested Set (вложенные множества) — БЫСТРЫЙ ДЛЯ ЧТЕНИЯ

Каждый узел получает левый и правый номер.

CREATE TABLE person (
    id BIGSERIAL PRIMARY KEY,
    name VARCHAR(255) NOT NULL,
    left_num INT NOT NULL,
    right_num INT NOT NULL,
    depth INT NOT NULL
);

-- Пример структуры:
--         Иван (1, 14, 0)
--       /      \
--    Федор    Анна
--    (2,7,1)  (8,13,1)
--     /
-- Владимир (3,4,2)

Найти всех потомков Федора:

SELECT * FROM person 
WHERE left_num > 2 AND right_num < 7;
-- Быстро! Используется индекс

Найти всех предков Владимира:

SELECT * FROM person 
WHERE left_num < 3 AND right_num > 4;

Проблема: добавление новых узлов

-- Нужно пересчитать все номера справа от нового узла
UPDATE person SET right_num = right_num + 2 
WHERE right_num >= 8;

INSERT INTO person (name, left_num, right_num, depth)
VALUES ('Новый', 8, 9, 2);

Плюсы:

• Очень быстрые запросы на чтение (SELECT)
• Эффективные индексы

Минусы:

• Сложное добавление/удаление
• Пересчёт всех номеров
• Не подходит для часто меняющегося древа

Подход 3: Path (путь как строка) — БАЛАНС

Хранить полный путь от корня.

CREATE TABLE person (
    id BIGSERIAL PRIMARY KEY,
    name VARCHAR(255) NOT NULL,
    path VARCHAR(1000),  -- '1/3/5' означает: Иван -> Федор -> Владимир
    depth INT
);

INDEX idx_person_path ON person USING GIST(path);

Найти всех потомков Федора (id=3):

SELECT * FROM person WHERE path LIKE '1/3/%' OR id = 3;

Найти предков Владимира (path='1/3/5'):

SELECT * FROM person 
WHERE id IN (1, 3)  -- Извлечь из пути
ORDER BY depth;

Или проще с ltree в PostgreSQL:

CREATE TABLE person (
    id BIGSERIAL PRIMARY KEY,
    name VARCHAR(255) NOT NULL,
    path ltree
);

-- Найти потомков
SELECT * FROM person WHERE path <@ '1.3';

-- Найти предков
SELECT * FROM person WHERE '1.3.5' <@ path;

Плюсы:

• Баланс между скоростью и простотой
• Хорошая производительность
• PostgreSQL оптимизирует ltree

Минусы:

• Требует пересчёта при удалении
• Ограничение по длине строки

Подход 4: Closure Table (таблица замыканий) — СЛОЖНЫЙ НО МОЩНЫЙ

Отдельная таблица для всех отношений предок-потомок.

CREATE TABLE person (
    id BIGSERIAL PRIMARY KEY,
    name VARCHAR(255) NOT NULL
);

-- Таблица для всех связей (включая самого с собой!)
CREATE TABLE person_closure (
    ancestor_id BIGINT NOT NULL,
    descendant_id BIGINT NOT NULL,
    depth INT NOT NULL,
    PRIMARY KEY (ancestor_id, descendant_id),
    FOREIGN KEY (ancestor_id) REFERENCES person(id),
    FOREIGN KEY (descendant_id) REFERENCES person(id)
);

-- Пример для дерева: Иван -> Федор -> Владимир
-- ancestor_id | descendant_id | depth
-- 1           | 1             | 0     (сам с собой)
-- 1           | 3             | 1     (Иван -> Федор)
-- 1           | 5             | 2     (Иван -> Владимир)
-- 3           | 3             | 0     (сам с собой)
-- 3           | 5             | 1     (Федор -> Владимир)
-- 5           | 5             | 0     (сам с собой)

Найти всех потомков Федора (id=3):

SELECT p.* FROM person p
JOIN person_closure pc ON p.id = pc.descendant_id
WHERE pc.ancestor_id = 3 AND pc.depth > 0;
-- Результат: Владимир

Найти всех предков Владимира (id=5):

SELECT p.* FROM person p
JOIN person_closure pc ON p.id = pc.ancestor_id
WHERE pc.descendant_id = 5 AND pc.depth > 0;
-- Результат: Федор, Иван

Добавить нового потомка:

-- Вставить Владимира со скопированием всех предков
INSERT INTO person_closure (ancestor_id, descendant_id, depth)
SELECT ancestor_id, 6, depth + 1
FROM person_closure
WHERE descendant_id = 5  -- Добавляем потомка Владимира
UNION ALL
SELECT 6, 6, 0;  -- Сам с собой

На Java с Hibernate:

@Entity
public class PersonClosure {
    @Id
    @ManyToOne
    @JoinColumn(name = "ancestor_id")
    private Person ancestor;
    
    @Id
    @ManyToOne
    @JoinColumn(name = "descendant_id")
    private Person descendant;
    
    private int depth;
}

Плюсы:

• Очень быстрые запросы
• Гибкие отношения (не только родитель-потомок)
• Хорошо для графов

Минусы:

• Требует дополнительной таблицы
• Сложное добавление/удаление
• Больше места в БД

Сравнение подходов

Рекомендация для генеалогического древа

Если древо редко меняется:

• Используй Nested Set для быстрого поиска

Если часто добавляются новые люди:

• Используй Adjacency List + кэширование предков

Если нужна максимальная гибкость:

• Используй Closure Table для сложных запросов

Гибридный подход (рекомендуемый):

@Entity
public class Person {
    @Id
    private Long id;
    
    private String name;
    
    // Основная иерархия (Adjacency List)
    @ManyToOne
    private Person father;
    
    @ManyToOne
    private Person mother;
    
    // Кэш путей для быстрого поиска
    @Column
    private String ancestorPath;  // '1|3|5'
    
    // Для специфичных запросов используем Closure Table через native queries
}

Типичные запросы для генеалогии

-- 1. Найти общих предков
SELECT DISTINCT a1.ancestor_id
FROM person_closure a1
JOIN person_closure a2 ON a1.ancestor_id = a2.ancestor_id
WHERE a1.descendant_id = 5 AND a2.descendant_id = 3;

-- 2. Найти близость родства (общего предка)
SELECT MIN(a1.depth + a2.depth) as distance
FROM person_closure a1
JOIN person_closure a2 ON a1.ancestor_id = a2.ancestor_id
WHERE a1.descendant_id = 5 AND a2.descendant_id = 3
AND a1.ancestor_id != 5 AND a1.ancestor_id != 3;

-- 3. Построить генеалогическое дерево (с глубиной)
WITH RECURSIVE tree AS (
    SELECT id, name, NULL::BIGINT as parent_id, 0 as level
    FROM person
    WHERE father_id IS NULL AND mother_id IS NULL  -- прородители
    
    UNION ALL
    
    SELECT p.id, p.name, p.father_id, t.level + 1
    FROM person p
    JOIN tree t ON p.father_id = t.id OR p.mother_id = t.id
)
SELECT * FROM tree ORDER BY level, id;

Заключение

Выбор метода зависит от:

1. Частоты обновлений — насколько часто добавляются новые люди
2. Типов запросов — поиск предков, потомков, или обоих
3. Размера дерева — может ли быть тысячи или миллионы людей
4. Требуемой производительности — критичны ли быстрые запросы

Для большинства генеалогических систем хороший выбор — гибридный подход с Adjacency List для основной структуры и кэшированием путей для частых запросов.