Как найти все узлы в поддереве рекурсивного SQL-запроса?

Question

У меня есть таблица, которая определяет дочерние и родительские отношения между узлами:

CREATE TABLE node (                           ' pseudo code alert
  id        INTEGER PRIMARY KEY,
  parentID  INTEGER, ' should be a valid id.
)

Если parentID всегда указывает на действительный существующий узел, то это естественным образом определит древовидную структуру.

Если parentID равно NULL, то мы можем предположить, что узел является корневым узлом.

Как бы я:

1. Найти все узлы, которые являются потомками данного узла?
2. Найти все узлы данного узла на определенной глубине?

Я хотел бы сделать каждый из них как один SQL (я ожидаю, что он обязательно будет рекурсивным) или два взаимно рекурсивных запроса.

Я делаю это в контексте ODBC, поэтому я не могу полагаться на какие-либо специфические функции поставщика.

Редактировать

• Таблицы еще не написаны, поэтому добавление дополнительных столбцов / таблиц вполне допустимо.
• Дерево потенциально будет обновляться и добавляться довольно часто; Вспомогательные структуры данных / таблицы / столбцы были бы возможны, хотя должны быть обновлены. Если у вас есть какие-нибудь магические книги для такого рода запросов, я хотел бы знать.

Большое спасибо.

Answer 1

Эта ссылка предоставляет учебное пособие как по модели списка смежности (как описано в вопросе), так и по модели вложенного набора. Он написан как часть документации для MySQL.

То, что не обсуждается в этой статье, это время ввода / вывода и стоимость обслуживания двух подходов. Например:

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

Answer 2

Если у вас есть какие-нибудь магические книги, к которым вы обращаетесь для такого рода запросов, я бы хотел знать.

Celko's Деревья и иерархии в SQL для умников

Answer 3

Сохраните весь «путь» от идентификатора корневого узла в отдельном столбце, обязательно используя разделитель в начале и конце. Например. скажем, 1 является родителем 5, который является родителем 17, а ваш символ-разделитель - тире, вы должны сохранить значение -1-5-17- в столбце пути.

Теперь, чтобы найти всех детей 5 лет, вы можете просто выбрать записи, путь к которым включает -5-

Разделители на концах необходимы, поэтому вам не нужно беспокоиться об идентификаторах, которые находятся в крайнем левом или правом конце поля при использовании LIKE.

Что касается вопроса о глубине, то если вы добавите в таблицу столбец глубины, в котором будет указана текущая глубина вложения, это также станет простым. Вы просматриваете глубину вашего начального узла и затем добавляете к нему x, где x - это количество уровней, по которым вы хотите выполнить поиск, и вы отфильтровываете записи с большей глубиной.

Answer 4

Некоторые методы были рассмотрены ранее в этой статье:

SQL - как хранить и перемещаться по иерархиям