С этими деревьями и у меня одна сплошная мука, по тем же причинам. Ну не поддерживаются они напрямую реляционной схемой, и всё тут. Иерархическими - поддерживаются напрямую, а реляционной - нет. С Вашего позволения, некоторые общие мысли.
Посмотрим на определения деревьев (не упорядоченных. Модификация для упорядоченных деревьев очевидна).
По определению, дерево - это узел ("корень"), который может иметь "потомков" - другие деревья. Т.е. определение в принципе рекурсивное. Чтобы обойти дерево, исходя из этого определения, можно использовать рекурсию.
Любая рекурсия может быть приведена к итерации. Тогда дерево - это структура, состоящая из корневого узла, который может быть связан с другими узлами - "потомками".Каждый узел - "потомок" может быть связан со своими узлами - "потомками", причём с любым узлом - "потомком" должен быть связан ровно один узел - предок. Чтобы обойти дерево, исходя из этого определения, можно использовать итерацию.
Попробуем по-другому. Дерево из N узлов - это матрица T(NxN), такая что 1) элемент T(i,j) = 1, если узел j является предком узла i; 2) элемент T(i,j) = 0, если узел j НЕ является предком узла i; 3) каждая строка, T(i), кроме одной, должна содержать ровно один единичный элемент 4) должна существовать единственная строка T(k), состоящая из одних нулей, и узел k - это корень дерева. С точки зрения реляционной схемы - ещё хуже, получили таблицу с переменным числом столбцов (или переменное число таблиц), и всё равно, менять нужно много элементов. Да и при выборке итерации нужны.
И т.д. Наверное, сколько существует возможных математических аппаратов - столько и определений дерева (можно, например, определить дерево неким формальным языком - и опять, магазинный автомат -> рекурсия).
Обратим внимание, что в определениях отсутствует понятие "уровень" или "номер уровня".
Реляционная схема не поддерживает рекурсии или итерации иначе, чем через расширения SQL или QBE, или ещё какого-либо реляционного языка (потому что отношение - это НЕупорядоченное множество кортежей атомарных элементов). В случае SQL эти расширения - это язык встроенных процедур/триггеров. Другими словами, SELECT реализует операции над неупорядоченными множествами кортежей, состоящих из некоторых "атомарных" элементов (по определению первой нормальной формы). Это справедливо для любого языка, действующего в рамках реляционной модели.
Что же мы должны хранить, явно или неявно, в структуре, моделирующей наше упорядоченное дерево, чтобы можно было сортировать (т.е. "обходить") дерево: 1) Ссылку на предка (явно, или например, "наоборот" - ссылкой на потомка(ов)); 2)Номер потомка (явно или неявно - например, ссылкой на предыдущего брата); 3) И, наконец, информацию, ассоциированную с узлом, из-за которой мы и строим дерево (впрочем, это к делу не относится). Если хотим "просто" делать выборки по уровням: 4) Номер уровня (явно, неявно уже хранится в 1)). Кстати, не видел ещё задачи, где бы потребовалось выбрать не "всех прямых потомков узла Х", а "все узлы 3-го уровня".
Видно, что при некоторой произвольной перестройке дерева, необходимо менять всю информацию о положении узла, а поскольку при этом меняется порядок и других узлов (т.е. их "номер при обходе дерева") - и информацию в них тоже.
- Если мы хотим делать простые выборки - нужно хранить 1), 2) явно - тогда необходимы сложные обновления. Для справочников, которые редко меняются не так и сложно, как здесь уже упоминалось. IMHO, обсуждаемая здесь идея с "предварительной нумерацией" узлов дерева мне очень понравилась (прочёл в рассылке это сайта №66) - даже завидно, как всё просто. (Ведь почти она же описана у Ахо, Ульмана и Ко в "Структурах данных..." при обсуждении деревьев - а вот не увидел...) А целостность дерева пусть обеспечивает механизм транзакций.
- Если нам нужны быстрые обновления - храним 1), 2) неявно (ссылками) - тогда при выборках без процедур не обойтись - нужна рекурсия или итерация.
Кстати, ведь в точности та же проблема и при попытке хранить списки. Список ведь тоже структура рекурсивная, и опять, простые обновления - за счёт сложной выборки. И наоборот. Правда, обновлять нужно 2 узла - но ведь не один (вставляемый-удаляемый-перемещаемый)!
Ожидать в будущем каких-то расширений SQL (именно SQL! Не языков объектно-ориентированных баз), позволяющих "просто" решить данную задачу, IMHO, не стоит - несоответствие теории даром не проходит. А нам нужен SELECT (или UPDATE), выполняющий операции не над "неупорядоченным множеством кортежей атомарных элементов", а над "множеством упорядоченных кортежей множеств".
А вдруг кто-нибудь знает другие красивые идеи по поводу моделирования деревьев в реляционной схеме (возможно, деревьев какого-либо специального вида)?
Прошу прощения за очевидные рассуждения - но с деревьями этими и правда проблема. Причём, такое впечатление, что проблема больше концептуальная, и наверняка глубже, чем я представляю. Может, из-за этих проблем и иерархические схемы БД забыты? Хотя в любой предметной области иерархию не встретить - чудо.
С уважением - Олег.