SQL выбирает потомков строки

Предположим, что древовидная структура реализована в SQL следующим образом:

CREATE TABLE nodes (
    id INTEGER PRIMARY KEY,
    parent INTEGER -- references nodes(id)
);

Хотя в этом представлении можно создавать циклы, давайте предположим, что мы никогда не позволим этому случиться. В таблице будет храниться только коллекция корней (записи, где parent имеет значение null) и их потомки.

Цель состоит в том, чтобы по идентификатору узла в таблице найти все узлы, являющиеся его потомками.

A является потомком B, если либо родителем A является B, либо A родитель > является потомком B. Обратите внимание на рекурсивное определение.

Вот некоторые примеры данных:

INSERT INTO nodes VALUES (1, NULL);
INSERT INTO nodes VALUES (2, 1);
INSERT INTO nodes VALUES (3, 2);
INSERT INTO nodes VALUES (4, 3);
INSERT INTO nodes VALUES (5, 3);
INSERT INTO nodes VALUES (6, 2);

который представляет:

1
`-- 2
    |-- 3
    |   |-- 4
    |   `-- 5
    |
    `-- 6

Мы можем выбрать (непосредственных) дочерних элементов 1, выполнив следующие действия:

SELECT a.* FROM nodes AS a WHERE parent=1;

Мы можем выбрать детей и внуков 1, выполнив следующие действия:

SELECT a.* FROM nodes AS a WHERE parent=1
UNION ALL
SELECT b.* FROM nodes AS a, nodes AS b WHERE a.parent=1 AND b.parent=a.id;

Мы можем выбрать детей, внуков и правнуков 1, выполнив следующие действия:

SELECT a.* FROM nodes AS a WHERE parent=1
UNION ALL
SELECT b.* FROM nodes AS a, nodes AS b WHERE a.parent=1 AND b.parent=a.id
UNION ALL
SELECT c.* FROM nodes AS a, nodes AS b, nodes AS c WHERE a.parent=1 AND b.parent=a.id AND c.parent=b.id;

Как можно построить запрос, который получает всех потомков узла 1, а не тех, которые находятся на фиксированной глубине? Кажется, мне нужно создать рекурсивный запрос или что-то в этом роде.

Я хотел бы знать, возможен ли такой запрос с использованием SQLite. Однако, если для этого типа запроса требуются функции, недоступные в SQLite, мне любопытно узнать, можно ли это сделать в других базах данных SQL.


sql sqlite recursion recursive-query
person Joey Adams    schedule 30.04.2010    source источник

Ответы (3)


arrow_upward
9
arrow_downward

Некоторые базы данных позволяют использовать рекурсивные общие табличные выражения, но не SQLite.

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

id (varchar)
--------------
001
001002
001002003
001002003004
001002003005
001002006

Это позволяет вам запрашивать всех потомков 1, например:

SELECT * FROM YourTable WHERE id LIKE '001%'

Это звучит немного странно, но на практике работает очень хорошо.

person Andomar    schedule 30.04.2010
comment
Определенно дурацкий, определенно потрясающий! Кроме того, как насчет разделения идентификаторов косой чертой? (например, 1/2/3/4) - person Joey Adams; 30.04.2010
comment
Мне это нравится, это намного проще, чем мое предложение, хотя, возможно, и не так универсально. Я думаю, это зависит от ваших реальных потребностей, хотя... - person Dean Harding; 30.04.2010
comment
в основном это URL-адрес :) вы можете просто использовать URL-адрес, если хотите, и использовать ту же технику. также может поместить маркер для листовых узлов, если вы захотите запросить эти - person Keith Nicholas; 30.04.2010
comment
Моя программа хранит и дедуплицирует файлы (примерно несколько миллионов) на уровне блоков в архиве. И вставка, и поиск должны быть быстрыми, поэтому я думаю, что решение, подобное этому, было бы лучшим. - person Joey Adams; 30.04.2010

arrow_upward
6
arrow_downward

То, как вы настроили свою схему, на самом деле не очень хорошо подходит для реляционной модели (как вы обнаружили). Но есть и другой способ, который поначалу может быть не таким очевидным, но гораздо более гибким. Это называется «моделью вложенных наборов», и она просто структурирует вещи немного по-другому.

Управление иерархическими данными в MySQL (см. раздел "Вложенные Set Model") показывает, как это сделать в MySQL, но это должно быть довольно легко переведено в SQLite. Я не буду вдаваться в подробности, потому что эта статья на самом деле довольно длинная, но она должна дать вам все, что вам нужно для начала работы.

person Dean Harding    schedule 30.04.2010
comment
Я считаю, что реляционная модель вполне подходит. Я определил descendant строго по логике первого порядка, если не ошибаюсь :-) - person Joey Adams; 30.04.2010
comment
Решение в ссылке имеет фиксированную глубину, а вопрос задает любую глубину. Единственная разница с запросом в вопросе заключается в использовании left join вместо union all - person Andomar; 30.04.2010
comment
@Andomar: я не думаю, что вы прочитали всю связанную статью ... начните с раздела под названием Модель вложенного набора - person Dean Harding; 30.04.2010
comment
Вау... это дало бы дорогостоящие обновления! Но это точно любая глубина, +1 :) - person Andomar; 30.04.2010
comment
Да, обновления/вставки/удаления довольно дорогие. Я думаю, это зависит от вашего типичного использования. Для данных, которые в основном читаются, это на самом деле удивительно быстро и гибко. Это хорошо подходит для больших наборов данных, тогда как я бы выбрал ваш, если бы набор данных был меньше. - person Dean Harding; 30.04.2010

arrow_upward
1
arrow_downward

У Oracle есть синтаксис CONNECT BY, который можно использовать для этого, но, конечно, он специфичен для oracle.

person MeBigFatGuy    schedule 30.04.2010
comment
@Andomar: Как я уже сказал в исходном сообщении: Однако, если для этого типа запроса требуются функции, недоступные в SQLite, мне любопытно узнать, можно ли это сделать в других базах данных SQL. - person Joey Adams; 30.04.2010