Иерархические структуры

← →
Хаванагил (2007-03-22 14:58) [0]

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

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

так вот...
есть ли способ чтобы без рекурсии обойтись?

← →
Ega23 © (2007-03-22 14:59) [1]

> есть ли способ чтобы без рекурсии обойтись?

нет.

← →
Sergey13 © (2007-03-22 15:28) [2]

> есть ли способ чтобы без рекурсии обойтись?

Уйти на Оракл. От рекурсии не уйдешь, но она не будет такой пративной. 8-)

← →
Jan (2007-03-22 15:41) [3]

> нет.

есть :)

← →
Jan (2007-03-22 15:43) [4]

http://gsbelarus.com/gs/modules.php?name=News&file=article&sid=314#c4

← →
Ega23 © (2007-03-22 15:44) [5]

> есть :)

Нет.

← →
Ega23 © (2007-03-22 15:46) [6]

> http://gsbelarus.com/gs/modules.php?name=News&file=article&sid=314#c4

Вопрос внимательно прочитал? Или надо объяснять разницу между MSSQL и FB?

← →
Johnmen © (2007-03-22 15:49) [7]

Ссылочные ключи таблицы на саму себя в MSSQL не пройдут. Что, в общем-то, понятно...

← →
Jan (2007-03-22 15:49) [8]

> Вопрос внимательно прочитал? Или надо объяснять разницу
> между MSSQL и FB?

не понял, что такого есть в ФБ чего нет в МССКЛ?

← →
Ega23 © (2007-03-22 15:50) [9]

> Ссылочные ключи таблицы на саму себя в MSSQL не пройдут.

Это почему? Пройдут.

← →
Jan (2007-03-22 15:50) [10]

> Ссылочные ключи таблицы на саму себя в MSSQL не пройдут.
> Что, в общем-то, понятно...

каскадные да, но кто мешает триггер сделать?

← →
Ega23 © (2007-03-22 15:53) [11]

> не понял, что такого есть в ФБ чего нет в МССКЛ?
>

В MSSQL нельзя из Select from Stored_Procedure сделать

← →
Johnmen © (2007-03-22 15:54) [12]

Если делать триггер, то и ссылочные ключи с каскадным воздействием ни к чему.

← →
Johnmen © (2007-03-22 15:55) [13]

И всё равно это будет рекурсия. Просто неявная... :)

← →
Jan (2007-03-22 16:01) [14]

> В MSSQL нельзя из Select from Stored_Procedure сделать

1. UDF
2. обмануть:
create table #temp ( ... ) insert into #temp exec sp_ select * from #temp

← →
ANB © (2007-03-22 16:02) [15]

> И всё равно это будет рекурсия. Просто неявная... :)

В оракле в твоем коде не будет. Оракл ее внутри сам прокрутит.

← →
Johnmen © (2007-03-22 16:06) [16]

> ANB © (22.03.07 16:02) [15]

Да, я в курсе.
Но рекурсией она быть не перестанет. Кто бы её не крутил... :)

← →
Val © (2007-03-22 16:09) [17]

лучше это...на рыбалочку...

← →
Ega23 © (2007-03-22 16:13) [18]

> Jan (22.03.07 16:01) [14]
>
>
> > В MSSQL нельзя из Select from Stored_Procedure сделать
>
> 1. UDF
> 2. обмануть:
>
> create table #temp (
> ...
> )
> insert into #temp
> exec sp_
>
> select * from #temp
>

Ну про это мы в курсе. А дальше что? Вот мне надо выбрать все данные от определённого узла. Глубина вложенности - неизвестно.
Как без рекурсии?
(способ-то один хитрый есть)

← →
Jan (2007-03-22 16:23) [19]

> Как без рекурсии?

Мы ссылку читаем?
Извлечение узлов поддерева Запрос, извлекающий все узлы поддерева, вершина которого имеет идентификатор P, будет выглядеть следующим образом: SELECT t.* FROM test4 t JOIN test4 t2 ON t.lb > t2.lb AND t.rb <= t2.rb WHERE t2.id = :P Заменив строгое неравенство по левой границе на не строгое, мы добавим саму вершину поддерева в результирующую выборку.

← →
Хаванагил (2007-03-22 16:24) [20]

так так...
пардон, а что за UDF?

> Ega23 © (22.03.07 16:13) [18]

и что за хитрый способ? =)

зы: я не очень в этом деле разбираюсь, так просто интересно стало)
триггеры мне понравилось.. может ими и сделать..

← →
Jan (2007-03-22 16:26) [21]

> пардон, а что за UDF?

запускаем QA набираем create function и тынц Shift+F1

← →
Ega23 © (2007-03-22 16:39) [22]

> и что за хитрый способ? =)

declare @Current_ID int declare @TreeLevel int declare @Stack table (Object_ID int null, TreeLevel int) declare @Results table (Object_ID int null) select @Current_ID = @Object_ID select @TreeLevel = 1 insert into @Stack values (@Current_ID, @TreeLevel) while @TreeLevel > 0 begin if exists (select * from @Stack where TreeLevel = @TreeLevel) begin select top 1 @Current_ID = Object_ID from @Stack where TreeLevel = @TreeLevel insert into @Results (Object_ID) values (@Current_ID) delete from @Stack where TreeLevel = @TreeLevel and Object_ID = @Current_ID if @Type is not null insert into @Stack select Object_ID, @TreeLevel + 1 from Objects where Parent_ID = @Current_ID else insert into @Stack select Object_ID, @TreeLevel + 1 from Objects where Parent_ID = @Current_ID if @@rowcount > 0 select @TreeLevel = @TreeLevel + 1 end else select @TreeLevel = @TreeLevel - 1 end delete from @Results where Object_ID = @Object_ID
Идею, вроде, sniknik как-то подкинул.

← →
Хаванагил (2007-03-22 16:40) [23]

> Jan (22.03.07 16:26) [21]

ооо....

← →
ANB © (2007-03-22 16:40) [24]

> Но рекурсией она быть не перестанет. Кто бы её не крутил.
> .. :)

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

← →
Хаванагил (2007-03-22 16:41) [25]

> Ega23 © (22.03.07 16:39) [22]

ууу...
спасибо, сохраню пока - дома разберусь))

← →
Ega23 © (2007-03-22 16:44) [26]

Да, вот ещё что. MSSQL НЕ ПОДДЕРЖИВАЕТ стек вызовов более 32.
Хотя я для своих задач так и не смог придумать такого дерева, где уровень вложенность был бы больше 32...

← →
Хаванагил (2007-03-22 17:03) [27]

> Ega23 © (22.03.07 16:44) [26]

да, 32 вполне хватит! у меня где-то 6-8 уровней в дереве етом выходит..

спасибо всем, очень интересно! )

← →
clickmaker © (2007-03-22 17:13) [28]

> Идею, вроде, sniknik как-то подкинул

до боли мой код напоминает... ) ну sniknik, так sniknik

Полюбить рекурсию и жить спокойно до старости.

> до боли мой код напоминает... ) ну sniknik, так sniknik

Да, блин, не помню я. Может и твой. Если твой - сейчас комент добавлю (последнее время уже взял за правило - если не мой код, то комент, чей)

> MSSQL НЕ ПОДДЕРЖИВАЕТ стек вызовов более 32

Использование CTE в 2005 обходит это ограничение.

> Использование CTE в 2005 обходит это ограничение.

Мы только-только щупать ExpressEdition начали...

← →
Jan (2007-03-23 11:40) [34]

← →
Jan (2007-03-23 12:49) [35]

> Ega23 © (22.03.07 16:39) [22]

можно проще и быстрее.
declare @ParentID [uniqueidentifier] set @ParentID = "bla-bla-bla" declare @Stack table ([id] [uniqueidentifier]) declare @Result table ([id] [uniqueidentifier]) insert into @Stack select [ID] from [TreeTable] where [ParentID] = @ParentID while (exists(select * from @Stack)) begin set @ParentID = (select top 1 [id] from @Stack) insert into @Stack select [ID] from [TreeTable] where [ParentID] = @ParentID insert into @Result select @ParentID delete from @Stack where [id] = @ParentID end select * from @Result

можно для хранения данных использовать строковое поле.
Например, пусть есть такое дерево
Организация
Отдел1
Отдел2
Подотдел21
Отдел3

Тогда таблица будет иметь поля
create table departments(
name varchar(100), название отдела
hcode varchar(50), иерархический код этой записи
cnt int количество непосредственных подузлов(т.е. дети детей не считаются)

Содержимое таблицы:
Организация "00", 3
Отдел1 "0000", 0
Отдел2 "0001", 1
Подотдел21 "000100", 0
Отдел3 "0002", 0

Поля hcode и cnt обслуживают иерархические связи.
hcode - иерархический код записи
Поле cnt - это количество уже существующих у узла потомков.
Нужно для расчета hcode у новых потомков.

На каждый уровень иерархии выделяем два символа (можно больше, дело хозяйское).
И символы в моем примере ограничены цифрами (что не обязательно),
т.е. максимальное количество детей (именно детей, т.е. НЕПОСРЕДСТВЕННЫХ потомков)
у каждого родителя не будет превышать 100 штук.
hcode нового узла формируется как: код родителя + "свой код".
"Свой код" формируется на основании поля cnt. Например, если у родительской записи
hcode = "1234", cnt = 15, то у нового потомка hcode="123416".
Думаю, идея понятна.

Имеет недостатки.
В частности, вставка-удаление записи затрагивает еще одну запись (родительскую, ведь надо cnt у родителя уменьшить/увеличить). Соответственно, чтобы обеспечить корректность этих операций, нужно приложить усилия по написанию дополнительного кода.
Вероятно, не годится для многотысячных иерархий.
Зато наверное все "деревянные" задачи решаются без рекурсий.

Выбрать ВСЕХ потомков записи с hcode=@hcode:

SET @len=LEN(@hcode) SELECT * FROM departments WHERE hcode LIKE @hcode+"%" AND LEN(hcode)>@len

Удаление всех потомков

BEGIN TRAN DELETE FROM departments WHERE hcode LIKE "@hcode+"%" AND LEN(hcode)>@len SELECT @err = @@ERROR, @rc=@@ROWCOUNT IF @err<>0 GOTO FAIL_EXIT UPDATE departments SET cnt=cnt-@rc WHERE hcode=@hcode SET @err = @@ERROR IF @err<>0 GOTO FAIL_EXIT COMMIT TRAN RETURN 0 FAIL_EXIT: ROLLBACK TRAN RETURN @err

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

Да тут критиковать-то нечего..
Для "классической" древесины с макс.вложенностью 5-6 можно использовать, правда будут хитромудрые запросы, которые к тому же будут тормозить.

Для неограниченных деревьев и, тем более, графов, неприемлима

> Bless © (23.03.07 18:11) [36]

Похоже были организованы деревья в первых версиях 1С (до 6-ки точно).
Ничего - работоспособный вариант, но проблемы с количеством уровней.
И ограничение на количество цифр в ID ветки дерева.
Тока Cnt там нафиг не нужно.
Я в клиппере отказался от этой идеи - обычные парентовые деревья намного гибче.

Люди добрые! Здравствуйте! Я к Вам за помощью. Тут было сказано, что надо полюбить рекурсию. Вот я хочу начать это дело.

В общем имеется традиционная база - структура отделов организации.

ID Name ParentID
1 Экономики 0
2 Финансов 0
3 подЭконом 1
4 подФин 2
.........

Хочу написать рекурсию, которая бы удаляла Node и всех его детей и внуков и правнуков ....

Мои мысли такие: собрать все необходимые для удаления ID и одним запросом их удалить.

Вот попытка сбора ID
// ----------------------------- procedure TFormTree.Make_Del_List(ID:integer); begin if HasChild(ID) then begin while not Q.Eof do begin Make_Del_List(Q.FieldByName("ID").AsInteger); end; end; List.Add(IntToStr(ID)); end; // -------- есть ли дети ---------------------- function TFormTree.HasChild(ID:integer):boolean; begin Q.Close; Q.SQL.Clear; Q.SQL.Add("SELECT * FROM Dep WHERE ParentID = " + IntToStr(ID)); Q.Open; Result := Q.RecordCount > 0; end;

но она не так работает.. порой пропускает детей... если у одного детя есть внук..... вот (((

> но тогда ссылка должна мочь быть null (для самого верхнего
> уровня, над которым уже ничего нет)

Кто сказал, что "должна" ?
Что мешает сделать эту ссылку, например, равной первичному ключу этой же записи ?

Иерархические структуры Найти похожие ветки