Здравствуйте.
Помогите пожалуйста со следующей проблемой:
Необходимо разработать универсальную БД для хранения произвольных иерархических структур (адреса, каталоги и т.д.).
Причем структура имеет произвольное число уровней (глубину). А поиск потомков и предков должен осуществляться в один селект.
Напрашивается подход в виде дерева, но как отвязаться от фиксированности структуры, как добится универсальности???
Помогите, если сможите.
Заранее благодарен Н.Б.Р.
Уважаемые авторы вопросов! Большая просьба сообщить о результатах решения проблемы на этой странице. Иначе, следящие за обсуждением, возможно имеющие аналогичные проблемы, не получают ясного представления об их решении. А авторы ответов не получают обратной связи. Что можно расценивать, как проявление неуважения к отвечающим от автора вопроса.
14-10-2005 03:51 | Вопрос к автору: запрос дополнительной информации
У меня вопрос к Елене. Меня заинтерисовала ваша сртуктура. Не могли бы вы прислать тектс триггеров для работы с вашей структурой. Заранее большое спасибо.
03-03-2005 10:09 | Комментарий к предыдущим ответам
Возражая тебе, Лен, я имел в виду прежде всего ПРОСТОТУ РЕШЕНИЯ, когда основное внимание уделяется не "раскрутке" дерева, а предметным вопросам
...
Именно таких областей применений "деревьев", ИМХО, куда больше, чем те, на которые ты прозрачно намекаешь в своих постах.
Сергей, так я ведь нисколько не спорю с Вами! И простые деревья, о которых Вы говорите, реально чаще требуются в задачах, чем деревья с нестандартными наворотами. С этим я тоже абсолютно согласна.
Но в вопросе была фраза, которая накладывает некоторое ограничение на использование простого дерева, а именно фраза: "А поиск потомков и предков должен осуществляться в один селект."
Только поэтому я вылезла со своим примером. Не убеждать "против" простых деревьев, а просто показать еще один вариант решения такой задачи.
Ну, а потом, просто забрало.. так бывает, когда ввязываешься в разговор на интересную для тебя тему :о)
Насчет того, что я "прозрачно намекаю" — да и так много было написано, не хотелось уводить разговор совсем в сторону, описанием разных примеров.
Только вот вопрос - а зачем это надо и кому,- ведь дерево задумывалось как раз для избежания такого "вертолетного" обзора данных.
Один из реальных примеров: дерево это справочник, к каждой ветке которого привязано много различной информациии из других таблиц. То есть, с помощью дерева информация систематизируется по разным группам. Само дерево (справочник) полностью или любая его ветка (раздел с подразделами) является для клиентской части неким навигатором. То есть, клиентское приложение должно показать это дерево с отображением иерархии, естественно.
По некоторым причинам, поставлены жесткие требования к вычислительным ресурсам — рекурсия на сервере запрещена в принципе. Рекурсия в клиентском приложении крайне нежелательна. Самый идеальный вариант — выполнить запрос на сервере и просто вывести его на клиенте без ресурсоемких вычислений. Поэтому желательно получить иерархию дерева (или ветки) одним запросом.
Именно для показа иерархии справочника. Само дерево модифицируется редко, а вот показывается очень часто. Отсюда и выбор решения — отказ от реализации простого дерева.
Приведенный пример грубо описывает одну из реальных задач работы с деревом, которое более привычно для всех называется "Тематическим каталогом сайта".
Конечно, спорить на тему деревьев и (особенно) графов можно до бесконечности. Как, впрочем, заниматься и нормализацией их моделей. Возражая тебе, Лен, я имел в виду прежде всего ПРОСТОТУ РЕШЕНИЯ, когда основное внимание уделяется не "раскрутке" дерева, а предметным вопросам (для чего, собсно, и используют эти самые деревья) Вот как пример - типовой справочник, построенный на принципах вложенности (Справочник товаров, партнеров, персонала компании и т.д.) Чрезвычайно удобно проектировать такой спр-к "деревом", чтоб можно было вместо банальных поисков по 1000 записей иметь возможность работать с блоками объектов, объедиенных в группы, подгруппы и т.д.
Именно таких областей применений "деревьев", ИМХО, куда больше, чем те, на которые ты прозрачно намекаешь в своих постах.
Так вот, именно при работе с такими "деревянными" таблицами много удобнее опираться на ПРОСТУЮ модель данных, не изобилующей различными промежуточными, пусть и мудро спроектированными, наворотами типа связок, глубин (расстояний) и т.д. Извлекать такие данные на клиент тоже не сложно, даже если надо "вытянуть" весь лес ;) В конце концов можно выудить с сервера все записи простым запросом, а потом в памяти рассовать по тривью и сами записи отобразить либо в стринггриде, либо с помощью CDS. Только вот вопрос - а зачем это надо и кому,- ведь дерево задумывалось как раз для избежания такого "вертолетного" обзора данных.
Что касается областей типа состава изделей, где именно графы, то, естественно, я полностью с тобой согласен, что это сложная проблема и нет единого "всепобеждающего" рецепта ее решения.
28-02-2005 10:27 | Комментарий к предыдущим ответам
> Алексей Румянцев:
:о) Хорошо.
Но если что, я готова дать необходимые пояснения.
> Bulat:
Приходится хранить большой объем служебной информации, при большом кол-ве уровней и разнообразии элементов.
Да, конечно, я об этом и писала. Все дело в том, что в ряде задач хранения дополнительной информации все равно ОПРАВДЫВАЕТ себя.
Да и само понятие "большой объем" это понятие относительное. Если речь идет, например, как в моем случае, о MS SQL Server, то для сервера этот объем не является серьезным ограничением. Особенно, когда критерием оптимальности считается быстродействие выборок при большом количестве одновременных коннекций.
К примеру, вот два "живых" дерева. Пусть:
КВ - количество строк в основной таблице, то есть количество ветвей дерева;
МВ — максимальная вложенность в дереве, количество уровней.
КД — количество записей в дополнительной таблице.
БОльшую часть работы на создание и модификацию дополнительной таблицы при добавлении/удалении/перемещении ветвей можно переложить на триггеры.
Как я уже говорила, бывают задачки еще более неприятные, когда даже эта структура уже не помогает. Тогда таблица дерева принимает еще более непривычную, для любителей нормализации (к коим я отношу и себя), структуру. Но, ведь нормализация не догма, самое главное это решение поставленной задачи.
Если вы встечали где-то статью John Celco о деревьях
Да, конечно встречала. Когда в 2000 году я только начинала заниматься Sql-деревьями, пришлось изучить много литературы.
Вот ссылки на статьи Joe Celko:
оригинал: http://www.dbmsmag.com/9605d06.html
перевод на русский язык: http://sdm.viptop.ru/articles/sqltrees.html
Никоим образом не умаляя авторитета известного SQL-мастера, хочу сказать, что я даже не пробовала пользоваться его множественной моделью дерева. Она не показалась мне "прозрачной" для сложных выборок и у нее есть сложности при изменении структуры дерева (удалить/добавить/переместить ветку).
Вкратце о методе:
В модели "вложенных множеств" предлагается хранить для каждой записи два дополнительных поля LEFT и RIGHT. В этих полях будет хранится число узлов, через которые нужно пройти от корня до текущей записи, если бы мы взялись идти последовательно по всему дереву.
Для такого вида счетчика работает несколько правил:
1) Для всех терминальных узлов разность между LEFT и RIGHT всегда равна 1;
2) Для корневого узла левый счетчик всегда равен 1, а правый -- удвоенному числу всех ветвей в дереве;
3) Величина (RIGHT - LEFT) всегда больше для тех ветвей, которые являются родительскими, то есть находятся выше по иерархии.
При модификации данных в такой структуре портятся значения RIGHT и LEFT, то есть они не отражают более реальных связей. И основную сложность составляет пересчет этих значений, так именно они поддерживают иерархию структуры в рабочем состоянии.
А лучше читайте статьи самого автора. Возможно Вам как раз его способ подойдет лучше.
Уважаемая Елена Филипова: ваш вариант решения проблемы очень изящен, но существуют некоторые минуся:
Приходится хранить большой объем служебной информации, при большом кол-ве уровней и разнообразии элементов.
Если вы встечали где-то статью John Celco о деревьях (представление через множества) то сообщите где или что там за идея реализации.
Заранее благодарен Н.Б.Р.
Елена Филиппова: Когда будет у Вас свободных пара минут, напишите, пожалуйста, в текстовом виде исходные данные таблиц для этой структуры, а то не удается сориентироваться что с чем объединяется.
28-02-2005 04:34 | Комментарий к предыдущим ответам
Сергей, наверное не совсем правильно противопоставлять деревья и графы. Дерево ведь это разновидность графа, или, упрощенно говоря, это связный граф, не имеющий циклов.
Потом, по своему опыту я знаю, что не существует универсальных решений. Почти всегда выбор решения заложен уже в самой задаче.
Да, такая дополнительная таблица может быть удобна при моделировании более сложных графов. Но она очень удобна и для, как Вы выразились, простых деревьев.
А удобна именно тем, что позволяет в одном запросе получить необходимую выборку по предкам или наследникам. Поле расстояние введено в таблице тоже не просто так. Именно оно позволяет оперировать, например, наследниками только определенного уровня. Описанная структура взята не из академических задач, она в свое время была выбрана для решения очень даже практической и не совсем простой задачи. И дело не в простоте дерева, а в том, что с этим деревом придется делать.
Приведенный пример не является универсальным, но в ряде случаев, оказывается очень удобным. Собственно, об этом я и писала.
Если нужно не просто выбирать ветку вверх или вниз от узла, а есть необходимость в частом использовании выборки этой ветки в сложных запросах, то использовать один JOIN проще, чем дополнительные хранимые процедуры.
Опять же, хочу еще раз отметить, что я не претендую на универсальность! Но готова утверждать, что в некоторых случаях такой подход намного удобнее, чем классическая реализация дерева одной таблицей и использование рекурсивной процедуры для обхода дерева.
Более того, бывают задачи, в которых просто неприемлемо использование рекурсий.
А есть задачи, где важно очень быстро и без нагрузок на сервер получить не просто ветку вверх или вниз от какого-то узла, а именно полную иерархию. В таком варианте и описанный способ не годится, приходится использовать иную структуру таблиц для реализации дерева.
В каждом из вариантов либо увеличивается вычислительная нагрузка на сервер, либо увеличивается размер данных, так как приходится хранить дополнительную информацию о дереве. То есть, приходится выбирать, чем предстоит жертвовать.
Это извечная проблема: что важнее, или время или деньги.
Если я не тороплюсь или у меня нет денег, то я поеду на автобусе и спокойно доберусь, куда надо. Если же очень надо добраться до места как можно скорее и у меня есть нужная сумма, то правильнее будет поехать на такси. Нельзя сказать, какой способ лучше вообще, потому что это зависит от конкретной ситуации.
Это лирическое отступление для того, чтобы очередной раз сказать — выбранная в каждом конкретном случае структура данных диктуется в большей части этим самым конкретным случаем, затем наличием или отсутствием необходимых ресурсов и, наконец, умением программиста реализовывать тот или иной вариант.
А вот универсальности выбора иерархической структуры для любых задач нет. У каждой есть плюсы и минусы.
Конечно же, все вышесказанное есть только мое личное мнение, не более того.
Лена, я что-то не совсем понял, зачем нужна еще одна таблица для ДЕРЕВА ?
Доп.таблица (одно из названий - "таблица входимостей") действительно необходима при моделировании ГРАФОВ, где "ребенок" может одновременно "входить" в множество "родителей". И в этой таблице входимости также нужна глубина (у тебя - расстояние) для того, чтобы удобно блокировать входимость объектов самих в себя через другие объекты.
Для простых же деревьев все решается парой достаточно простых хранимок, одна из которых разворачивает "куст" из заданного узла (вызывая сама себя рекурсивно), а вторая определяет список этих самых "кустовых" узлов (в тривью очень хорошо видно, как это должно происходить).
Ну, для особо продвинутых можно написать третью ХП, возвращающую цепочку в обратном направлении (снизу вверх, от внука к деду).
25-02-2005 05:54 | Вопрос к автору: запрос дополнительной информации
А какой объем требуется хранить? Если речь идет о мегабайтах (десятках), то проще строить дерево в памяти и просто выгружать в поток.
Работать будет много быстрее любой БД.
Если же в оперативную память не лезет, то присоединяюсь к Елене Филипповой и прошу ее вынести ее решение в сокровищницу.
Хочу предложить еще один из вариантов иерархической структуры, в которой свободно реализуется произвольное число уровней и, что иногда бывает крайне важно, реализуется простая выборка для обхода дерева, то есть поиска всех предков или всех потомков определенного уровня.
Такая структура реализуется двумя таблицами:
основной и дополнительной (как бы таблицей маршрутов).
Основная таблица:
ID - уникальный идентификатор
ParentID - идентификатор непосредственного родителя.
Name - название объкта
... - все другие атрибуты объекта.
Дополнительная таблица:
ChildID - ID текущей записи
ParentID - ID ее ПРЕДКА
Distance - растояние до этого самого предка.
Для каждой записи в основной таблице будет соответствовать несколько записей в дополнительной таблице. Под "предком" в данном случае следует понимать и "деда" и "прадеда" и так далее, словом это все сущности данной ветки, находящиеся выше по иерархии.
Для всех записей в таблице сущности обязательно будет существовать ХОТЯ БЫ ОДНА запись в таблице маршрута с ChildID = ParentID и Distance = 0.
То есть расстояние до самой себя. Для родительской записи добавится запись с Distance = 1, для "дедушки" - Distance = 2 и так далее.
Если Вы работаете с серверной БД, то формирование дополнительной таблицы можно целиком перенести в триггер на Insert и для каждой новой записи в основной таблице будет автоматически формироваться цепочка записей в дополнительной — как бы маршрут от корня до текущей записи.
Соответственно, надо создать триггер на удаление.
В качестве примера:
Таблицы ITEM_LIST и ITEM_LISTS_TREE - соответственно список тем каталога и таблица маршрутизации. Обе эти таблицы как раз и реализуют SQL-дерево.
1) Все дочерние темы для указанной (ID=7) в порядке их удаления:
Declare @ItemID Int
Set @ItemID = 7
select I.* from ITEM_LISTS I(Nolock)
Inner Join ITEM_LISTS_TREE IT(Nolock) On (IT.ChildID = I.ItemID)
Where IT.ParentID = @ItemID
Order By IT.Distance
ItemID ParentID Name
----------- ----------- ---------------------------------------------
7 259 Работа с MS Office
13 7 Интеграция с Internet Explorer
14 7 Интеграция с OutLook Express
2 7 Работа с Excel
3 7 Работа с MS Word
4 7 Работа с MS Outlook
482 2 Ячейки, области, отдельные листы (cell, range, sheet )
483 2 Формулы, макросы
484 2 Таблицы, оформление областей
503 2 Диаграммы
(10 row(s) affected)
2) Или все родительские компании:
Declare @ItemID Int
Set @ItemID = 7
select I.*
from ITEM_LISTS I(Nolock) Inner Join ITEM_LISTS_TREE IT(Nolock)
On (IT.ParentID = I.ItemID)
Where IT.ChildID = @ItemID Order By IT.Distance
ItemID ParentID Name
----------- ----------- ------------------------------------------
7 259 Работа с MS Office
259 1 Совместная работа с популярными пакетами
1 NULL Взаимодействие приложений ( DDE, OLE, DLL )
В моей задаче получилось так, что вся информация является текстовой, поэтому структура (если не вдаваться в подробности) следующая:
Есть так сказать класс субъекта - есть сами субъекты - у каждого субъекта есть атрибуты
(список атрибутов для нормализации вынесен в таблицу наименований атрибутов)
В таблице атрибутов ID субъекта, ID атрибута, Значение строковое, Ссылка на другой субъект.
В зависимости от типа атрибута берется нужная колонка - при этом если атрибут является ссылкой то в строковое значение наименование субъекта - на который ссылается атрибут.
Если значение просто строковое - то поле ссылки не заполняется.
Если вы заметили орфографическую ошибку на этой странице, просто выделите ошибку мышью и нажмите Ctrl+Enter. Функция может не работать в некоторых версиях броузеров.
