Деревья без рекурсии

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

ALTER TABLE Tree

ADD RIGHT_BOUND INTEGER

ALTER TABLE Tree

ADD LEFT_BOUND INTEGER

Заполним эти новые столбцы следующими числами:

UPDATE Tree SET LEFT_BOUND = 1, RIGHT_BOUND = 26 WHERE ID = 1

UPDATE Tree SET LEFT_BOUND = 2, RIGHT_BOUND = 7 WHERE ID = 2

UPDATE Tree SET LEFT_BOUND = 8, RIGHT_BOUND = 19 WHERE ID = 3

UPDATE Tree SET LEFT_BOUND = 20, RIGHT_BOUND = 25 WHERE ID = 4

UPDATE Tree SET LEFT_BOUND = 3, RIGHT_BOUND = 4 WHERE ID = 5

UPDATE Tree SET LEFT_BOUND = 5, RIGHT_BOUND = 6 WHERE ID = 6

UPDATE Tree SET LEFT_BOUND = 9, RIGHT_BOUND = 10 WHERE ID = 7

UPDATE Tree SET LEFT_BOUND = 11, RIGHT_BOUND = 16 WHERE ID = 8

UPDATE Tree SET LEFT_BOUND = 17, RIGHT_BOUND = 18 WHERE ID = 9

UPDATE Tree SET LEFT_BOUND = 21, RIGHT_BOUND = 22

WHERE ID = 10

UPDATE Tree SET LEFT_BOUND = 23, RIGHT_BOUND = 24

WHERE ID = 11

UPDATE Tree SET LEFT_BOUND = 12, RIGHT_BOUND = 13

WHERE ID = 12

UPDATE Tree SET LEFT_BOUND = 14, RIGHT_BOUND = 15

WHERE ID = 13

Фактически мы реализовали стек, нумеруя строки данных. Вот поясняющая картинка:

Теперь, чтобы получить всех предков МОТОЦИКЛА, мы только берем границы МОТОЦИКЛА (MOTORCYCLE) - слева 12, а справа 13 - и помещаем их в предложение WHERE, выбирая данные, правая граница которых превышает 12, а левая меньше 13.

И вот запрос, дающий тот же самый результат, что и сложный иерархический рекурсивный запрос:

SELECT *
FROM Tree
WHERE RIGHT_BOUND > 12

AND LEFT_BOUND < 13;

Такое представление деревьев хорошо известно в литературе по БД, особенно в трудах Джо Селко ("Деревья и иерархии" и т. д.).